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

[Course Information] [ Approximate Schedule]

General info

• Lectures: MWF 11:05-11:55, Klauss 2447.
• Instructor: Maria Florina Balcan
• Teaching Assistants: Chris Berlind and Sam Kim
• Course Information
• Approximate Schedule

Homeworks

• Homework 1 [pdf].
• Homework 2 [pdf].
• Homework 3 [pdf].
• Homework 4 [pdf].
• Homework 5 [pdf].
• Homework 6 [pdf].

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.