This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. After a brief review of prerequisite material (asymptotics, recurrences, sorting), we will discuss efficient algorithms for basic graph problems (minimum spanning trees, shortest paths, connectivity problem, network flows), solving optimization problems through greedy algorithms and dynamic programming, proofs of intractability and NP-completeness, and approximation algorithms.
For further information, please see the Course Syllabus.
Check here frequently for important class announcements. A complete list of announcements can be found on the Announcements Page.
- Wed, May 21:
- The course is finished for the semester. Have a great summer!
- Mon, May 19:
- Final Grades are now available on the Grades Page. If you would like to see your final exam, you can come by my office. Seven students whose grade fell close to a cutoff had their grade increased (e.g., B+ to A-) because of Extra Credit points. I have notified these students by email, so if you haven't heard from me, the grade listed is your final grade.
- Grades were computed as follows. "HWAvg" is the average of
the four highest homework grades with the lowest homework grade
dropped. It is then rounded to the nearest integer. All
homeworks were graded out of 100 points. "Total" is the weighted
sum of HWAvg (25%), Ex1 (30%), and ExF (45%). Grades were
assigned based on the following cutoffs:
- A: 85-100
- B: 73-85
- C: 64-73
- D: 50-64
- F: less than 50