|
CSL356: Lecture Notes
|
|
July 26: Introduction
|
|
July 28: Introduction to Graphs and BFS
|
|
July 29: DFS, connectivity, and topological ordering.
|
|
August 2: Greedy algorithms (Interval Scheduling, Fractional Knapsack)
|
|
August 4: Greedy algorithms (Fractional Knapsack contd., Job Scheduling)
|
|
August 5: Greedy algorithms (Minimum Spanning Tree)
|
|
August 9: Greedy algorithms (Kruskal's Algorithm using union-find, Shortest Path)
|
|
August 11: Greedy algorithms (Shortest Path, Huffman Coding)
|
|
August 12: Greedy algorithms (Huffman Coding, Set Cover, Minimum Makespan)
|
|
August 18: Divide and Conquer (Closest pair of points on a plane)
|
|
August 19: Divide and Conquer (Closest pair of points on a plane, Median Finding)
|
|
August 23: Divide and Conquer (Median Finding, Fast Fourier Transform)
|
|
August 25: Divide and Conquer (Fast Fourier Transform, Randomized Median Finding, Recurrence Relations)
|
|
August 26: Amortized analysis of Data Structures (Stack using Array, Queue using two Stacks)
|
|
August 30: Strongly Connected Components in a Directed Graph.
|
|
September 6: Dynamic Programming (Longest Increasing Subsequence, Longest Common Subsequence)
|
|
September 8: Dynamic Programming (Longest Common Subsequence, Memoization, Matrix Chain Multiplication)
|
|
September 9: Dynamic Programming (Memoization (animation),
All pairs shortest path, Subset Sum)
|
|
September 13: Dynamic Programming (Travelling Salesperson, Viterbi's algorithm, CYK algorithm for Context Free Parsing)
|
|
September 15: Network Flow (Ford-Fulkerson algorithm)
|
|
September 16: Network Flow (Ford-Fulkerson algorithm, Max-flow-min-cut theorem, Faster max-flow)
|
|
September 20: Network Flow (Ford-Fulkerson algorithm on networks with irrational capacities, Edmonds-Karp algorithm, Bipartite matching)
|
|
September 22: Network Flow (Hall's Theorem, Feasible Circulation, Survey Design)
|
|
September 23: Network Flow (Survey Design, Edge-disjoint Paths, Team elimination)
|
|
September 27: Network Flow (Team elimination, Project selection)
|
|
September 29: Network Flow (Project selection, Image Segmentation, Summary of Network Flow)
|
|
September 30: Computational Intractability (Introduction, Polynomial-time reduction, Vertex-cover vs Independent-set)
|
|
October 4: Computational Intractability (Polynomial-time reductions: Vertex-cover, Independent-set, Set-cover, SAT)
|
|
October 5: Network Flow Applications (Min-flow with lower bound, Maximum cohesiveness)
|
|
October 11: Computational Intractability (NP, NP-complete)
|
|
October 13: Computational Intractability (NP-complete, Cook-Levin Theorem)
|
|
October 14: Computational Intractability (NP-complete problems: Hamiltonian Cycle, Travelling Salesperson)
|
|
October 18: Computational Intractability (NP-complete problems: 3-coloring, Subset-sum, Scheduling)
|
|
October 20: Computational Intractability (Many-one reduction, NP-complete problems: 3D-matching, Subset-sum)
|
|
October 21: Computational Intractability (An overview of complexity classes: P, NP, co-NP, PSPACE)
|
|
November 1: Linear Programming (Introduction, Integer Linear Program)
|
|
November 3: Linear Programming (Applications, Standard form, Slack form)
|
|
November 4: Linear Programming (Simplex Algorithm)
|
|
November 11: Linear Programming (Simplex Algorithm)
|
|
November 15: Linear Programming (Approximation algorithms using LP)
|
|
November 17: Review of selected topics
|
|
November 18: Review of selected topics
|