CS 3510-A, Design and Analysis of Algorithms, Fall 2012

[Course Information] [ Approximate Schedule]

General info

Homeworks

Lectures

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