COMSW 4231 Analysis of Algorithms I, Fall 1999

The course is over

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


Staff:

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:

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


Handouts


Problem Sets


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


Misc


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. 16Hurricane -- 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. 30Randomized 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


Last modified 12/7/99, 4:00pm
luca@cs.berkeley.edu