CMSC 451: Design and Analysis of Computer Algorithms
Fall 2001
(This page must be viewed with a table-capable browser, such as
Netscape.)
General Information
Homeworks
Lectures
Viewing and Printing
General Information
| Class Time: | Tue, Thur 9:30-10:45. |
| Room: | CSS 1113 |
| Course Syllabus: | Postscript Format |
| Instructor: | Samir Khuller |
| Office: | A.V. Williams 3217. |
| Office Hours: | Mon 3:00 - 4:00, Thu 11:00- 12:00 Fri 3:30 to 4:15 |
| Send me email: | samir@cs.umd.edu |
| Teaching Assistant: | Eiman Elnahrawy |
| Office: | A.V. Williams 1151. |
| Office Hours: | Tue 2-3 and Wed 3-4 (starting 11/20) or send her email to arrange a time |
| Send her email: | eiman@cs.umd.edu |
Homeworks and Handouts
Homeworks will be due at the start of class on the due date. Late homeworks will not be accepted. Due dates etc will be corrected soon.
| Assignment | Due Date | Solutions | Avg. | |
|---|---|---|---|---|
| Homework 1 (pdf) | September 13 | Solution (pdf) | 62/100 (undergrad) and 93/120 (grad) | |
| Homework 2 (pdf) | September 27-->Oct 2 due to Tornado | Solution (pdf) | 79/100 (grad and undergrad!) | |
| Homework 3 (pdf) | October 11 | Solution (pdf) | 76/100 (undergrad) 97/100 (grad) | |
| Homework 4 (pdf) | October 23 | Solution (pdf) | 77/100 (grad) and 51/100 (undergrad) | |
| Homework 5 (pdf) | Nov 13 | Solution (pdf) | 84/100 (grad) and 74/100 (undergrad) | |
| Project Part I (pdf) | Nov 27 | Solution (pdf) | 18.5/20 | |
| Project Part II (pdf) | Dec 11 | Frequently Asked Questions | Test Files | |
| Homework 6 (pdf) | Dec 6 | Solution (pdf) |
| Handout | Date |
|---|---|
| Notes on Biconnectivity | September 4 |
| The Toothpick Game | October 18 |
| Network Flows | Nov 7 |
| NP-Completeness | November |
| NP-Completeness (Reductions) | Dec 6 |
Grades and Announcements
The midterm exam will be in class on Oct 25 (Thu) . The midterm is closed notes, closed book etc. The midterm average is around 33 for undergrads and 39 for graduate students. Students with scores below 25 should seriously consider dropping the class.
There is a newsgroup for the class, "csd.cmsc451". Check it periodically.
The final exam will be on Mon, Dec 17 10:30 - 12:30 . The exam will be comprehensive, and you will be allowed two HANDWRITTEN, 8.5 x 11 "cheat sheets". Any papers deviating from these rules will be confiscated. If you cannot read your own handwriting, why do you expect us to be able to read it?
There is a talk by David Johnson on Monday Dec 10 at 4pm in CLB of interest to people in this class. Title: Pet Peeves and Pitfalls in the Experimental Analysis of Heuristics. Checkout the CS Dept Colloquium Schedule for the Abstract
Viewing and Printing
All handouts and lectures are in postscript format. On campus UNIX/X11 workstations (WAM and Glue) they can be displayed and printed using the "ghostview" program. If you are using a PC with MS-Windows, you can download the program GSview from the University of Wisconsin for viewing and printing handouts.