CSE 202 - Algorithm Design & Analysis - Spring 2003

Latest News

• Version 1.1 of HW5 is posted below. This assignment is a bit unusual ... I "encourage" you to start thinking about it before the last minute. (The description of what I'm looking for has been expanded since version 1.0)
• Here's the list of assigned times for taking the final. If you want to switch to some time that is still available, send email to carter@cs.ucsd.edu.

Assignments & tests

• April 10: Homework #1 due.
• April 22: Homework #2 due. This is a group homework.
• May 1: Homework #3 due. This is a group homework.
• The in-class midterm will be May 6.
• May 27: Homework #4 due. This is a group homework.
• June 9: Homework #5 (version 1.1) due. This is a group homework.

Reading Assignments

• Week 1 (by April 8): Skim chapters 1 to 3 and appendices A and B. Try some problems. If they seem like gobbleygook, go back and read the chapter thoroughly.
• Week 2 (by April 15): Read Chapter 4 (except 4.4), 6, 7, 8.
• Week 3-4 (by April 29): Read Chapters 9 to 14.
• Week 6 (by May 13): Read Chapters 15 and 16.
• --------- Midterm ---------
• Week 7 (by May 20): Skim Chapters 21 and 23; read 24 and 25.
• Week 8 (by May 27): Read Chapter 26.
• Week 10 (by June 10): Read Chapter 34.

Lecture Notes

Textbook

• Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms (2nd edition)". Available at the UCSD bookstore, amazon.com, and perhaps at Barnes&Noble. (Note: using the first edition is sort-of OK, but many things - including the chapter numbering - have changed.)
• Several students have recommended a book by Daniel Solow, "How to Read and Do Proofs".

Class

Instructor

Old News

• Sign up for the class mailing list. I will only use this list for important announcements (like, "Problem 3 the homework is wrong!"). To do so, send email to majordomo@cs.ucsd.edu with the body (not header) of the message "subscribe cse202 me@wherever" (using your email address in place of me@wherever.)
• The class notes for class 4 (Quicksort & Heapsort) have been substantially revised.
• Version 1.0 of Homework #3, a group homework, is posted. This homework (in particular the project) cannot be done entirely at the last minute, since you are almost certain to encounter questions about what I'm talking about or what I want. Please plan accordingly! And please ask questions whenever anything isn't clear.
• There's an opportunity for one bonus point by improving your experiments and write-up (see 5/8 lecture notes). Must be handed in by classtime next Tuesday (5/13).

  The goal is to show me that you can perform sound experiments, analyze the data, form hypotheses, test the hypotheses (via new experiments if necessary), and end up with interesting conclusions that are well supported by the experiments. The conclusions can be virtually anything (e.g. "the timer on my machine gets reset to zero whenever there is a disk access") as long as it's true and you present a convincing argument. Every data set I looked at had interesting features, but mostly people didn't even notice the features, let alone explain them.

• An interesting paper that shows how Universal Hashing can prevent a certain type of denial-of-service attack.