CSL356: Lecture Notes

  • July 22: Introduction

  • July 23: Introduction to graphs, BFS
    		•

  • July 24: DFS, DAG, Topological Ordering
    		•

  • Aug 01: Greedy Algorithms (Interval Scheduling, Fractional Knapsack)
    		•

  • Aug 05: Greedy Algorithms (Interval Scheduling, Fractional Knapsack, Job Scheduling)
    		•

  • Aug 06: Greedy Algorithms (Job Scheduling, Minimum Spanning Tree)
    		•

  • Aug 08: Greedy Algorithms (Minimum Spanning Tree, Union-Find)
    		•

  • Aug 12: Greedy Algorithms (Dijkstra's Algorithm, Huffman Coding)
    		•

  • Aug 13: Greedy Algorithms (Huffman Coding)
    		•

  • Aug 19: Greedy Algorithms (Approximation algorithms for Set Cover and Minimum Makespan)
    		•

  • Aug 20: Divide and Conquer (Closest pair of points)
    		•

  • Aug 22: Divide and Conquer (Median finding, FFT)
    		•

  • Aug 26: Divide and Conquer (FFT)
    		•

  • Aug 27: Problem Session
    		•
    Minor-I exam (28 Aug.)

  • Sep 02: Dynamic Programming (Longest Increasing Subsequence)

  • Sep 03: Dynamic Programming (Longest Common Subsequence)

  • Sep 05: Dynamic Programming (Matrix Chain Multiplication, All pairs shortest paths)

  • Sep 09: Dynamic Programming (All pairs shortest paths, Subset Sum, Travelling Salesperson)

  • Sep 10: Dynamic Programming (Travelling Salesperson, Viterbi's Algorithm)

  • Sep 12: Network Flow (Ford Fulkerson Algorithm)

  • Sep 16: Network Flow (Ford Fulkerson Algorithm, Max-flow-min-cut theorem, faster max-flow)

  • Sep 17: Network Flow (Scaling max-flow, Edmonds-Karp algorithm)

  • Sep 23: Network Flow (Edmonds-Karp algorithm, Bipartite Matching, Hall's Theorem)

  • Sep 24: Network Flow (Hall's Theorem, Team Elimination)

  • Sep 26: Network Flow (Team Elimination, Feasible Circulation)

  • Sep 30: Network Flow (Feasible Circulation, Survey Design, Edge-disjoint Paths)

  • Oct 01: Network Flow (Edge-disjoint Paths, Image Segmentation, Project Selection)

  • Oct 07: Network Flow Summary, Practice problems
    		•
    Minor-II exam (09 Oct.)

  • Oct 14: Computational Intractability (Introduction, Polynomial-time reduction)

  • Oct 15: Computational Intractability (Polynomial time reductions)

  • Oct 17: Computational Intractability (NP and NP-completeness)

  • Oct 28,29: Computational Intractability (3-SAT, Hamiltonian Cycle, TSP)

  • Nov 11: Computational Intractability (Hamiltonian Cycle, TSP, Coloring)

  • Nov 12: Computational Intractability (TSP, Coloring, Subset-sum, Scheduling, 3-D matching)

  • Nov 14: Computational Intractability (3-D matching, Subset Sum, Complexity Classes)

  • Nov 15: Linear Programming (Introduction)

  • Nov 16: Linear Programming (Simplex Algorithm)

  • Nov 18: Linear Programming (Rounding)
    		•

  • Nov 19: Problem Session
    		•

  • Nov 21: Problem Session
    		•
    Major exam (26 November, 8-10am)