CS 3510, Design and Analysis of Algorithms, Spring 2011

[Course Information] [ Approximate Schedule]

General info

• Lectures: MWF 11:05-11:55, Klauss 1447.
• Instructor: Maria Florina Balcan
• Teaching Assistant/Grader: Jacob Robertson and Nishad Kothari
• Course Information
• Approximate Schedule

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.