CSE 202 Home Page

CSE 202 Section B - Algorithm Design & Analysis

Latest News

I'm not here on Tuesday. If you have questions about the final, I'll be here 2:00-3:00 on Wednesday. (And probably other times too.) Or use email.
Here is version 3.1 of the final. There are now 5 problems listed. (Looks like the sixth problem isn't going to appear - you wouldn't have liked it anyway.) It includes a slight rewording to problem 3(a). It's due Thursday, 12/12 at 12 midnight. Have fun!

Assignments & tests

Please read this important information about homeworks.

November 26 Homework #4 due. (Most recent revision: Version 2.1.)
October 31 Homework #3 due. (Most recent revision: Version 1.2.1, which differs from Version 1.2 by only adding the word "Max" to "Build-Heap")
October 15 Homework #2 due. (Most recent revision: Version 1.0)
October 3 Homework #1 due.

Reading Assignments

Week 10 (by Dec 3): Read Chapter 34.
Week 8 (by Nov 21): Read Chapter 26.
Week 6-7 (by Nov 14): Skim Chapters 21, 23, and read 24 and 25.
Week 5 (by Oct 29): Read Chapters 15 and 16.
Week 3-4 (by Oct 22): Read Chapters 9 to 14.
Week 2 (by Oct 10): Read Chapter 4 (except 4.4), 6, 7, 8.
Week 1 (by Oct 2): 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.

Lecture Notes

Topic	Dates	Notes format
Introduction	Sept 26-Oct 1	PowerPoint or PDF
Euclidean Alg., Divide&Conquer	Oct 1-3	PowerPoint or PDF
Recurrences	Oct 3	PowerPoint or PDF
Quicksort and Heapsort	Oct 8	PowerPoint or PDF
Memory Hierarchy Analysis	Oct 10	PowerPoint or PDF
More on Sorting	Oct 15 (revised 10/24)	PowerPoint or PDF
Hashing	Oct 17-22 (revised 10/22)	PowerPoint or PDF
Dynamic Search Trees	Oct 24 (revised)	PowerPoint or PDF
Dynamic Programming	Oct 29-31 (revised)	PowerPoint or PDF
Greedy Algorithms	Oct 31	PowerPoint or PDF
Minimum Spanning Trees	Nov 5 - 12	PowerPoint or PDF
Shortest Paths Problems	Nov 15-19 (expanded)	PowerPoint or PDF
Max Flow Min Cut	Nov 21	PowerPoint or PDF
FFT's and other goodies	Nov 26	PowerPoint or PDF
Incomplete notes on NP completeness	Dec 3	PowerPoint or PDF

Textbook

Cormen, Leiserson, Rivest and Stein, "Introduction to Algorithms (2nd edition)". Available at the UCSD bookstore, amazon.com, and perhaps at Barnes&Noble.
Several students have recommended a book by Daniel Solow, "How to Read and Do Proofs".

Classroom

413 University Center, Room 1. (Hint: It's exactly due east of AP&M.)

Instructor

Larry Carter (carter@cs.ucsd.edu).
Office hours: Tuesdays and Thursdays 3:30 - 5:00. AP&M 4101. Or by appointment.

TA

John-Paul Fryckman (jfryckm@cs.ucsd.edu)
Office hours: Wednesdays 1:00 to 2:00, AP&M 2331. Or by appointment.

Old News

"So what's the midterm going to be like?" you ask. I don't totally promise, but I think there will basically be two parts:
1. Short answers. The goal here is to see that you are understanding what's in the book and lectures. There will be a couple of recurrence equations (like T(n) = 2 T(floor(n/2)) + n^2) for which you should give the big-Theta complexity (no proof or derivation required. It's either right or wrong.) There will definitely be a few questions that ask, "Is [blah] a number, a function, a set, or a statement?" For instance, if [blah] were "the sample space for a probability function", the answer would be "a set". My expectation is that most people will get most answers right, that this part will only take a half hour, and I'll be assured that you all deserve at least a "B".
2. Problems requiring some creative thinking. I might ask you for a short-and-easy proof, or for a derivation of the solution to a recurrence that you probably haven't seen before. I'll probably ask for an algorithm that might require divide and conquer or dynamic programming or whatever. Looking at old comps question might be good training. The purpose of this part of the test is to see who deserves "A"'s. I recommend doing the other part of the test first, since it will be easy to get stuck on these questions.
I hope this helps.
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 of the message "subscribe cse202-b me@wherever" (using your email address in place of me@whatever.)
Here's a cool demo, written by Geoff Leach at RMIT University in Melbourne, Australia. It's at the bottom of his webpage.
"More on Sorting" has added pages (and extra credit opportunity.)
Information about the midterm:
Part A low score = 29, quartiles = 33, 38.5, 42.5, high score = 49
Part B low score = 0, quartiles = 4, 10, 15, high score = 30.
Here's an answer sheet.