CS 3510, Design and Analysis of Algorithms, Spring 2011

[Course Information] [ Approximate Schedule]


General info


Lectures

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