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
➔ The Maximum Subarray Problem
➔ Interpreting Bellman-Ford in the DP framework.
Week 09.b -- More Dynamic Programming
➔ Interpreting Floyd-Warshall in the DP framework
➔ Longest Increasing Subsequence (LIS)
➔ Interpreting LIS as finding longest paths in DAGs
➔ Edit Distance and interpreting optimal alignment as Shortest Path in a DAG
Week 10.a -- Even More Dynamic Programming
➔ Edit Distance with Human Genome (or solving the edit distance problem when given a bound on the optimal distance)
➔ {0,1}-Knapsack Problem
➔ Distributing Midterm Exam Copies
Week 11.a -- Wrapping up Dynamic Programming and Intro to Linear Programming
➔ {0,1}-Knapsack Problem (recap)
➔ Knapsack with Repetition
➔ Chain Matrix Multiplication
➔ Intro to Linear Programming: Defining Feasible Region and the Solution Space Geometry.