Algorithm Design and Analysis

Analyzing algorithm complexity and designing algorithms for sorting, searching, graphs, and optimization, including greedy and dynamic programming approaches.

Course: CSE 301/302 (lecture and lab)

Institution: Dhaka International University

Taught: Fall 2017

Enrollment: 54 students in lecture and lab

Course Overview

This course gives students a working knowledge of how to design and analyze algorithms: searching and sorting in linear and non-linear data structures, graph algorithms, and dynamic programming, with practical applications to everyday problems. Lectures used whiteboard derivations and slides, and lab sessions gave students practice implementing the algorithms.

Learning Objectives

After completing this course, students will be able to:

  • Define and develop searching algorithms for linear and non-linear data structures
  • Develop and apply different sorting algorithms
  • Solve practical problems using these algorithms
  • Analyze, design, and propose new algorithms for sorting and searching
  • Distinguish among sorting algorithms and recommend one for a given situation

Textbooks

  • Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms
  • Kleinberg and Tardos, Algorithm Design
  • Skiena, The Algorithm Design Manual
  • Sedgewick and Wayne, Algorithms
  • Dasgupta, Papadimitriou, and Vazirani, Algorithms

Schedule

Week Topic
1 Growth Functions and Recurrences

Review of growth functions, summations, and recurrence relations.
2 Sorting

Heap sort, quicksort, merge sort, and radix sort.
3 Sorting Bounds and Search Trees

Bucket sort, the lower bound for comparison sorting, binary search trees, and red-black trees.
4 Advanced Data Structures

Binomial heaps, Fibonacci heaps, and disjoint sets.
5 Dynamic Programming

Longest common subsequence and optimal polygon triangulation.
6 Greedy Algorithms and Amortized Analysis

Huffman coding, task scheduling, Strassen’s algorithm, and the potential method.
7 Graph Traversal I

Graph basics and breadth-first search with applications.
8 Graph Traversal II

Depth-first search and strongly connected components.
9 Directed Acyclic Graphs

Edge classification, DAGs, and topological sort.
10 Minimum Spanning Trees

Spanning trees and Prim’s algorithm.
11 Spanning Trees and Shortest Paths

Kruskal’s algorithm, and Dijkstra’s and Floyd–Warshall shortest-path algorithms.
12 Negative Edges and Knapsack

The Bellman–Ford algorithm and the 0-1 knapsack problem.
13 Applied Problem Solving

Chessboard and rock-climbing problems, network flow, and min-cut and max-cut problems.