CS 3510-B, Design and Analysis of Algorithms, Spring 2014

[Course Information] [ Approximate Schedule]


General info


Homeworks


Lectures

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