Instructor: Neil Rhodes
Email: nrhodes@cs.ucsd.edu
Office: APM 3151
Office hours: Tuesday 3:30-4:30 Thursday 2:30-3:30 or by appointment; drop-ins are welcome
Thursday, Week 10, extra office hours: 5-7:30.
Monday, Finals week, extra office hours: 6:00-8:00.
TA: Sashka Davis (sdavis [at] cs [dot] ucsd [dot] edu) Office hours: Th 9-10:30 APM 4414 Week 2 only: Friday instead of Thursday
Lectures: Tuesday/Thursday 12:30-1:50 WLH 2209
Website: http://www.cse.ucsd.edu/classes/sp05/cse202
Textbook: Introduction to Algorithms, 2nd edition by Cormen, Leiserson, Rivest, & Stien [CLRS]. ISBN: 0-07-013151-1. http://froogle.com shows used copies available starting at $65. The first edition can be used, but isn't recommended. In addition, a supplementary PDF textbook (http://www.cse.ucsd.edu/classes/sp05/cse101/JeffEdmondsBook.pdf) by Jeff Edmonds will be used for a few topics.
Tentative Schedule
| Topic | Dates | Reading |
| Proofs/Loop invariants | Day 1 Loop Invariants Proof | Skim chapters 1-3 and Appendices A-C. Try some problems. If you can't do them, go back and read the chapters thorougly |
| Big-O, etc., Proofs | Day 2 Day 2 Slides | |
| Recurrence relations/Master method | Day 3 Recurrence Slides (updated) | Chapter 4 (not 4.4) |
| Divide and Conquer (Sorting) | Day 4-6 Day 4 Slides Day 5 Slides Day 6 Slides | Chapters 6-9 |
| Sorting Networks | Day 7 Day 7 Slides Homework 1 due Homework 1 solution | Chapter 27 |
| Hashing | Day 8-9 Day 8 Slides Day 9 Slides | Chapter 10-11 |
| Dynamic Search Trees | Day 10 Day 10 Slides | Chapters 12-14 |
| Midterm | Day 11 Homework 2 due (Homework 2 solution) (Midterm Solution) | |
| Midterm review | Day 12 | |
| Dynamic Programming | Day 13-14 Day 13 Slides | Chapter 15 |
| Greedy Algorithms | Day 15 Day 15 Slides | Chapter 16 |
| Minimum Spanning Tree/Shortest Path | Day 16 Homework 3 due Homework 3 solution Day 16 Slides | Chapter 22-24 |
| All-pairs Shortest Path | Day 17 Day 17-19 Slides | Chapters 25 |
| Max Flow/Min Cut | Day 18-20 Day 20 Slides Homework 4 due (Homework 4 Solution) | Chapter 26 |
Prerequisites: CSE 12, CSE 21, CSE 100, CSE 101 (or equivalents).
You are expected to know:
A Demonstrate mastery of the material
B Understand most of the material. Can solve all routine problems and some hard ones.
C Don't get it
D, F Gave up
We'll have one midterm, one final, and a number of homeworks. A linear combination of the scores (with coefficients to be determined later) will be used to come up with a final grade.
Please turn in your homework on 3-hole punched paper with each problem on a separate page (for ease of grading). Student name(s) should appear at the top of each page.
Mailing list is cse202@cs.ucsd.edu. Add yourself to the list by sending email to cse202-join@cs.ucsd.edu.
I'll use this list only for important messages like corrections to homework, or cancellations of class.
There are two types of homework, individual and group.
Individual homeworks will be analysis and easier algorithm questions. For individual homework, you should solve and write the problems up yourself. Discussing basic techniques with classmates is OK, but there is a fine line between "discussing" (which is OK) and "getting the answer" (which is cheating). To ensure you don't cross the line, never make written notes while discussing individual homeworks. If you need to draw a picture or write something down, throw the paper away immediately.
Group homework will tend to involve finding efficient algorithms, and some may be hard. For group homework, you are encouraged to work in a group of up to three people, and write up a single solution. Each member of a group is responsible for understanding the solution (I may ask any one of you explain it to me.) You should not look for answers to homework problems in other books or papers. However, since you may be using other texts as a study tool, you may accidentally find a solution to a homework problems. In this case, write up your solution without consulting the text, and also give an acknowledgement of the text.
Remember the following guidelines: