|
CSL356: Lecture Notes
|
|
July 24: Introduction
|
|
July 26: Indroduction to Graphs, BFS
|
|
July 27: DFS, Connectivity, Topological ordering
|
|
July 31: Greedy Algorithms (Interval Scheduling, Fractional Knapsack)
|
|
August 3: Greedy Algorithms (Fractional Knapsack, Job Scheduling)
|
|
August 7: Greedy Algorithms (Job Scheduling, Minimum Spanning Tree)
|
|
August 9: Greedy Algorithms (Minimum Spanning Tree, Prim's/Kruskal's Algorithm)
|
|
August 14: Greedy Algorithms (Dijkstra's Algorithm, Huffman Coding)
|
|
August 16: Greedy Algorithms (Huffman Coding, Approximation algorithm for Set Cover)
|
|
August 17: Greedy Algorithms (Approximation algorithms for Set Cover and Minimum Makespan)
|
|
August 23: Divide and Conquer (Closest pair of points on a plane)
|
|
August 24: Divide and Conquer (Finding k^th smallest number in unsorted array)
|
|
August 28: Divide and Conquer (Fast Fourier Transform)
|
|
August 30: Divide and Conquer (Fast Fourier Transform, Randomized Median Finding)
|
|
August 31: Problem Session
|
|
September 6: Dynamic Programming (Longest increasing sequence, Longest Common Subsequence)
|
|
September 7: Dynamic Programming (Longest Common Subsequence, Memoization, Matrix chain Multiplication)
|
|
September 11: Dynamic Programming (All pairs shortest path, Subset sum)
|
|
September 13: Dynamic Programming (Travelling Salesman Problem, Viterbi's Algorithm)
|
|
September 14: Dynamic Programming (Travelling Salesman Problem, Viterbi's Algorithm), Network Flows introduction.
|
|
September 18: Network Flow (Ford Fulkerson Algorithm).
|
|
September 20: Network Flow (Ford Fulkerson Algorithm, Max-flow-min-cut Theorem, Faster max-flow).
|
|
September 25: Network Flow (Ford-Fulkerson on network with irrational capacities, Edmonds-Karp Algorithm).
|
|
September 27: Network Flow (Edmonds-Karp algorithm, Bipartite Matching, Hall's Theorem).
|
|
September 28: Network Flow (Hall's Theorem, Team elimination).
|
|
October 03: Network Flow (Team elimination, Feasible circulation, Survey design).
|
|
October 04: Network Flow (Survey design, Edge-disjoint paths, Image segmentation)
|
|
October 05: Network Flow (Image Segmentation, Project Selection, Summary)
|
|
October 11: Computational Intractability (Introduction, Polynomial-time reduction, Vertex-cover Vs Independent Set)
|
|
October 12: Computational Intractability (Polynomial time reductions: Set cover, Vertex cover, SAT, 3-SAT)
|
|
October 16: Computational Intractability (NP)
|
|
October 18: Computational Intractability (NP, NP-complete, Cook-Levin Theorem, NP-hard)
|
|
October 19: Computational Intractability (NP-complete problems: TSP, Hamiltonian-cycle, Hamiltonian Path)
|
|
October 30: Computational Intractability (NP-complete problems: k-Coloring, Scheduling, Many-one reduction)
|
|
November 1: Computational Intractability (NP-complete problems: 3-D Matching, Subset-sum)
|
|
November 2: Computational Intractability (Introduction to Computational Complexity Classes)
|
|
November 3: Linear Programming (Introduction)
|
|
November 6: Linear Programming (Applications, Standard form, Slack form)
|
|
November 8: Linear Programming (Simplex algorithm)
|
|
November 9: Linear Programming (Simplex algorithm)
|
|
November 15: Linear Programming (Approximation algorithms using LP)
|
|
November 16: Review of selected topics
|