Algorithms (CS2443)

Syllabus

• Introduction and Asymptotics.
• Divide and Conquer.
• Dynamic Programming.
• Greedy Algorithms.
• Graph Algorithms.
• Minimum Spanning Trees.
• Shortest Paths and its variants.
• Network Flows and its applications.

Evaluations

Textbook and References

• Jeff Erickson (2019), Algorithms.
  https://jeffe.cs.illinois.edu/teaching/algorithms/
• Jon Kleinberg and Eva Tardos (2005), Algorithm Design.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms.

Lectures

1. Lecture 1: General Information. Asymptotics.


2. Lectures 2 -- 10:
   • Insertion sort, Merge sort.
   • Recurrences (Recurrence tree, Substitution method, Domain and Range transformation).
   • Quicksort, Randomized Quicksort, Lower bounds for sorting.
   • Integer multiplication, Fast Fourier transformation, Linear-time median finding algorithm (Blum-Floyd-Pratt-Rivest-Tarjan'73).


3. Lectures 11 -- 13: Tutorials and preparation for Quiz 1.


4. Lectures 14 -- 16:
   • Dynamic Programming, Longest Common Subsequence.
   • Parenthesization, Edit Distance.
   • Knapsack, pseudopolynomial time, Discussion on Quiz 1.


5. Lectures 17 -- 28:
   • Greedy Algorithms, Interval Scheduling.
   • Interval Scheduling - Minimizing the maximum lateness.
   • Codes, prefix-free codes, Huffman codes.
   • Stable Matching.
   • Graphs, BFS, DFS, connected components.
   • Directed graphs, DAGs, Topological Ordering.
   • Minimum Spanning Trees, Prim's and Kruskal's algorithm, Union-Find data structure.


6. Lectures 29 -- 32:
   • Shortest Paths in weighted graphs, Dijkstra's Algorithm.
   • Dijkstra's Algorithm (contd.), Shortest paths with negative weights -- Bellman-Ford algorithm.
   • Tutorial for Quiz 3.
   • Shortest paths with negative weights (contd.)
7. Lectures 33 -- 37:
   • Network Flows, Ford-Fulkerson algorithm, Max-Flow Min-Cut Theorem, Applications of network flows.