CS 3510-A, Design and Analysis of Algorithms, Spring 2013

[Course Information] [ Approximate Schedule]


General info



Lectures

  1. 01/09: Intro & Admin. Computing Fibonacci numbers.
  2. 01/11: Insertion Sort.
    Reading: [CLRS] Chapters 2.1 and 2.2.
  3. 01/14: Asymptotic Analysis.
    Reading: [CLRS] Chapter 3.
  4. 01/16: Divide and conquer. Mergesort. Reccurences
    Reading: [CLRS] Chapters 2.3 and 4.
  5. 01/18: Reccurences. The master theorem.
    Reading: [CLRS] Chapter 4.
  6. 01/23: Karatsuba multiplication. Strassen algorithm.
  7. 01/25: QuickSort. QuickSelect.
    Optional readings: probabilistic analysis and formal analysis of Randomized QuickSort.
  8. 01/28: Linear-time Selection, a determinstic linear algorithm.
    Reading: [CLRS] Chapters 9.3.
  9. 01/30: Review of Hwk 2. Quiz Review.
  10. 02/01: First Quiz Review.
  11. 02/04: Comparison-based lower bounds for sorting.
    Reading: [CLRS] Chapter 8.1.
  12. 02/06: Graph Algorithms. Breadth First Search.
    Reading: [CLRS] Chapters 22.1, 22.2.
  13. 02/08: Depth First Search.
    Reading: [CLRS] Chapter 22.3.
  14. 02/11: Topological Sort.
    Reading: [CLRS] Chapter 22.4.
  15. 02/13: Strongly Connected Components.
    Reading: [CLRS] Chapter 22.5.
  16. 02/15: Review of Hwk 3.
  17. 02/18: Minimum Spanning Trees. The Cut Property.
    Reading: [CLRS] Chapter 23.1.
  18. 02/20: Kruskal's Algorithm. Union Find.
    Reading: [CLRS] Chapters 23.2. 21.1, and 21.2.
  19. 02/22: Prim's Algorithm. Min-Priority Queues.
    Reading: [CLRS] Chapters 23.2.
  20. 02/25:Shortest Path Problems. Disjkstra's Algorithm.
    Reading: [CLRS] Chapters 24.0, 24.3.
  21. 02/27: Disjkstra's Algorithm. Min-Priority Queues. Binary Heaps.
  22. 03/01: Review of Hwk 4. Quiz Review.
  23. 03/04: Second Quiz.
  24. 03/06: Dynamic Programming. Longest Common Subsequence.
    Reading: [CLRS] Chapters 15.4.
  25. 03/08: Dynamic Programming. The Knapsack problem.
  26. 03/11: Dynamic Programming. Matrix Chain Multiplication.
    Reading: [CLRS] Chapters 15.2, 15.3.
  27. 03/13: Dynamic Programming. Longest Increasing Subsequences.
  28. 03/15: Dynamic Programming. The Bellman Ford Algorithm.
  29. 03/25: Dynamic Programming. All-pairs Shortest Paths.
    Reading: [CLRS] Chapter 25.1.
  30. 03/27: Dynamic Programming. The Floyd Warshall Algorithm.
    Reading: Reading: [CLRS] Chapter 25.2.
  31. 03/29: Dynamic Programming. Maximum Independent Sets in Trees.
  32. 04/01: Review of HWK 6. Quiz Review.
  33. 04/03: Third Quiz.
  34. 04/05: Tractable and Intractable Problems. NP-Completness.
    Reading: [CLRS] Chapters 34.1, 34.2, 34.3.
  35. 04/08: Tractable and Intractable Problems. NP-Completness.
    Reading: [CLRS] Chapters 34.1, 34.2, 34.3.
  36. 04/10: Tractable and Intractable Problems. NP-Completness.
    Reading: [CLRS] Chapters 34.1, 34.2, 34.3.
  37. 04/12: Tractable and Intractable Problems. NP-Completness.
    Reading: [CLRS] Chapters 34.1, 34.2, 34.3.
  38. 04/15: Tractable and Intractable Problems. NP-Completness.
    Reading: [CLRS] Chapters 34.4, 34.5.
  39. 04/17: Tractable and Intractable Problems. NP-Completness.
    Reading: [CLRS] Chapters 34.4, 34.5.
  40. 04/19: Introduction to Machine Learning Theory.