COMSW 4231 Analysis of Algorithms I, Fall 1999

Note: problem sets and problem set solutions are off-line

Staff:

• Lecturer: Luca Trevisan (luca@cs.columbia.edu), Office 462 CSB, Tel. (212) 939 7019.
• TA: Dario Catalano (dario@cs.columbia.edu), Office 509 CSB, Tel. (212) 939 7026, Office hours Mondays 12-1pm, Wednesdays 12-1pm.

Prerequisites: W3139 (Algorithms and Data Structures) and W3203 (Discrete Mathematics).

Very short description: Introduction to the design and analysis of efficient algorithms. Topics covered include: models of computation, efficient sorting and searching, algorithms for algebraic problems, graph algorithms, dynamic programming, probabilistic methods, and NP-completeness.

Textbook:

• T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms, MIT Press, 1990.

Grades will be determined by: 55% Homeworks (6 assignments, the worst grade will be dropped), 20% midterm, 25% final.

Handouts

• Handout 0 (9/7), Course information. [postscript] [PDF]
• Handout 1 (9/7), Notes on models of computation and lower bounds. [postscript] [PDF]
• Handout 2 (9/9), Problem Set 1. [postscript] [PDF]
• Handout 3 (9/21), Notes on discrete probability. [postscript] [PDF]
• Handout 4 (9/28), Problem Set 2. [postscript] [PDF]
• Handout 5 (10/7), Problem Set 1, solutions. [postscript] [PDF]
• Handout 6 (10/11), Problem Set 3. [postscript] [PDF]
• Handout 7 (10/11), Practice Midterm. [postscript] [PDF]
• Handout 8 (10/18), Practice Midterm Solutions. [postscript] [PDF]
• Handout 9 (10/26), Problem Set 2 Solutions. [postscript] [PDF]
• Handout 10 (10/26), Problem Set 4. [postscript] [PDF]
• Handout 11 (11/9, Revised 11/10), Problem set 5. [postscript] [PDF]
• Handout 12 (11/9), Notes on Dynamic Programming. [postscript] [PDF]
• Handout 13 (11/23), Problem set 6. [postscript] [PDF]
• Handout 14 (12/2), Notes on numerical algorithms. [postscript] [PDF]
• Handout 15 (12/14), Problem Set 3 Solutions. [postscript] [PDF]
• Handout 16 (12/14), Problem Set 4 Solutions. [postscript] [PDF]
• Handout 17 (12/14), Problem Set 5 Solutions. [postscript] [PDF]
• Handout 18 (12/14), Problem Set 6 Solutions. [postscript] [PDF]

• Handout M (10/19), Midterm. [postscript] [PDF]
• Handout M2 (10/20), Midterm 2. [postscript] [PDF]
• Handout PF (12/7), Practice Final. [Postscript] [PDF]
• Handout PFS (12/13), Practice Final Solutions. [Postscript] [PDF]

Problem Sets

• Problem Set 1 (9/9). [postscript] [PDF]
  Solutions: [postscript] [PDF]
• Problem Set 2 (9/28). [postscript] [PDF]
  Solutions: [postscript] [PDF]
• Problem Set 3 (10/11). [postscript] [PDF]
  Solutions: [postscript] [PDF]
• Problem Set 4 (10/26). [postscript] [PDF]
  Solutions: [postscript] [PDF]
• Problem Set 5 (11/9, Revised 11/10). [postscript] [PDF]
  Solutions: [postscript] [PDF]
• Problem Set 6 (11/23). [postscript] [PDF]
  Solutions: [postscript] [PDF]

Slides

1. Lecture 1 (9/7, revised 9/8). [postscript] [PDF]
2. Lecture 2 (9/9). [postscript] [PDF]
3. Lecture 3 (9/14). [postscript] [PDF]
4. Lecture 4 (9/21, revised 9/23). [postscript] [PDF]
5. Lecture 5 (9/23, revised 9/29). [postscript] [PDF]
6. Lecture 6 (9/28). [postscript] [PDF]
7. Lecture 7 (9/30, revised 10/4). [postscript] [PDF]
8. Lecture 8 (10/5, revised 10/6). [postscript] [PDF]
9. Lecture 9 (10/7). [postscript] [PDF]
10. Lecture 10 (10/11). [postscript] [PDF]
11. Lecture 11 (10/21, revised 10/25). [postscript] [PDF]
12. Lecture 12 (10/26). [postscript] [PDF]
13. Lecture 13 (10/28, revised 11/8). [postscript] [PDF]
14. Lecture 14 (11/4). [postscript] [PDF]
15. Lecture 15 (11/9). [postscript] [PDF]
16. Lecture 16 (11/11, preliminary version). [postscript] [PDF]
17. Lecture 17 (11/16, revised 11/18). [postscript] [PDF]
18. Lecture 18 (11/18). [postscript] [PDF]
19. Lecture 19 (11/23, preliminary version). [postscript] [PDF]
20. Lecture 20 (11/30, preliminary version). [postscript] [PDF]
21. Lecture 21 (12/2). No slides
22. Lecture 22 (12/3). [postscript] [PDF]
23. Lecture 23 (12/7). [postscript] [PDF]

Lecture Notes

• Handout 1 (9/7), Notes on models of computation and lower bounds. [postscript] [PDF]
• Handout 3 (9/21), Notes on discrete probability. [postscript] [PDF]
• Handout 12 (11/9), Notes on dynamic programming. [postscript] [PDF]
• Handout 14 (12/2), Notes on numerical algorithms. [postscript] [PDF]

Misc

• C.H. Papadimitriou. NP-completeness: A restrospective, 1997.

Schedule of Lectures

Past

Day	Topic	Reading	Homework
Sept. 7	Introduction, models of computation, lower bounds	1, 9.1, notes
Sept. 9	Divide and conquer, Master theorem	4.3, 4.4, 10.1	Pset 1 out
Sept. 14	Linear time median	10.3
Sept. 16	Hurricane -- no lecture
Sept. 21	Probability	6, notes, 10.2
Sept. 23	Sorting in linear time	9.2, 9.3, 9.4
Sept. 28	Data structures, introduction. Hashing	12	Pset 1 in, Pset 2 out
Sept. 30	Randomized hashing	12.3.3, notes
Oct. 5	More Hashing, Binomial heaps	13, 20
Oct. 7	Amortization	18
Oct. 11	Fibonacci heaps	21	Pset 2 in, Pset 3 out, Practice midterm out
Oct. 12	No lecture (moved to Oct. 11)
Oct. 14	No lecture (moved to Oct. 11)
Oct. 19	Midterm
Oct. 21	Graphs, introduction.	23.1, 23.2, 23.3
Oct. 26	Topological Sort. Shortest paths.	23.4, 25.1, 25.2, 25.4	Pset 3 in, Pset 4 out
Oct. 28	Max flow	27.1, 27.2
Nov. 2	Election day -- no lectures
Nov. 4	Max Flow/Min Cut theorem, randomized min cut	27.3
Nov. 9	Matching, Dynamic programming	16.2, 26.2	Pset 4 in, Pset 5 out
Nov. 11	Dynamic programming	notes
Nov. 16	Dynamic programming, NP-completeness	36.1, 36.2
Nov. 18	NP-complete problems	36.3
Nov. 23	NP-complete problems	36.4	Pset 5 in, Pset 6 out
Nov. 25	Thanksgiving -- no lectures
Nov. 30	NP-complete problems	36.5
Dec. 2	Number-theoretic algorithms	33.1, 33.2, 33.3, 33.4, 33.6
Dec. 3	RSA encryption	33.7
Dec. 7	Primality testing	33.8	Pset 6 in