Algorithms (CS2443)
Lectures
Monday (11:00am--11:55am), Wednesday (10:00am--10:55am) and Thursday (9:00am--9:55am)
Venue
C-LH2 (2 Jan to 16 Feb)
A-LH2 (17 Feb to 2 May)
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
Lecture 1:
General Information. Asymptotics.
Lectures 2 -- 9:
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).
Lectures 10 -- 12:
Dynamic Programming, Longest Common Subsequence.
Edit Distance, Knapsack, pseudopolynomial time.
Lectures 13 -- 17:
Greedy Algorithms, Interval Scheduling.
Codes, prefix-free codes, Huffman codes.
Stable Matching.
Lectures 18 -- 19:
Graphs, graph exploration, BFS.
BFS, DFS, connected components.
Lecture 20:
Discussion : Assignment 1.
Lectures 21-23:
BFS, DFS, Directed graphs, DAGs, Topological Ordering.
Minimum Spanning Trees, Prim's and Kruskal's algorithm, Union-Find data structure.
Lectures 24-27:
Shortest Paths in weighted graphs, Dijkstra's Algorithm.
Dijkstra's Algorithm (contd.), Discussion (Quiz 1 and Assignment 2).
Shortest paths with negative weights -- Bellman Ford algorithm.
Lectures 28-31:
Network Flows, Ford-Fulkerson algorithm, Max-Flow Min-Cut Theorem, Applications of network flows.