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