Textbook: Algorithms by Dasgupta, Papadimitriou and Vazirani
When: Mon and Thu, 2:00 PM to 3:25 PM
Where: LH 101
Topics:
Week 01 -- Karatsuba Multiplication
Week 02.a -- Algorithms for Computing Fibonacci Numbers faster than the iterative textbook algorithm
Week 02.b -- Divide and Conquer and Faster Algorithms for Matrix Multiplication
Week 03.a -- Linear time deterministic algorithm for finding median of an array and introduction to graphs
Week 03.b -- Depth First Search, Counting number of connected components of a graph, Pre/Post Numberings
Week 04.a -- DFS on directed graphs, Topological Ordering of DAGs, Algorithm for finding SCCs, BFS
Week 04.b -- Dijkstra's algorithm and detecting negative cycles in graphs
Week 05.a -- Correctness of negative cycle detection algorithm and Greedy Algorithm for Fractional Knapsack
Week 05.b -- Greedy Algorithms for Interval Scheduling and The Set Cover Problem
Week 06.a -- Kruskal's algorithm for finding Minimum Spanning Tree of a Graph and the Cut Property
Week 06.b -- Prim's algorithm for MSTs and The Reverse Delete Algorithm
Week 07.a -- What makes MST problem such a magnet for all kinds of Greedy Algorithms?
➔ Greedy Algorithms for finding largest independent sets in Matroids
(I did not cover this to my satisfaction)
Week 07.b -- Revision of Problems for Midterm
Week 08.a/b -- The Midterm
Week 09.a -- Intro to Dynamic Programming
➔ Computing Fibonacci Numbers
➔ Shortest Paths in DAGs
➔ The Monk/Cannibal Puzzle
➔ Interpreting Bellman-Ford in the DP framework.