CMSC 451: Design and Analysis of Computer Algorithms
Spring 2005
General Information
| Class Time: | Tue, Thu 12:30-1:45. |
| Room: | CSI 2107 |
| Course Description: |
| Instructor: | Aravind Srinivasan |
| Office: | A.V. Williams 3227. |
| Office Hours: | Tue, Thu 10 - 11 AM |
| Teaching Assistant: | Nan Wang |
| Office Hrs Venue: | A.V. Williams 1112. |
| Office Hour Times: | Mon, Wed 4PM - 5PM |
Homeworks, Exams, Project, Handouts
Homeworks will be due at the start of class on the due date. Late homeworks will not be accepted.
| Assignment | Due Date | Solution | Avg ugrads | Max ugrads | Avg grads | Max grads |
|---|---|---|---|---|---|---|
| Homework 1 [ps] [pdf] | Feb 15 | Solution [ps] [pdf] | 16/20 | 20/20 | 23.5/30 | 25/30 |
| Homework 2 [ps] [pdf] | Mar 1 | Solution [ps] [pdf] | 10.5/20 | 20/20 | N.A./30 | N.A./30 |
| Homework 3 [ps] [pdf] | Mar 15 | Solution [ps] [pdf] | 10.7/20 | 20/20 | N.A./30 | N.A./30 |
| Mid-term | Solution [ps] [pdf] | 12.8/15 | 15/15 | |||
| Makeup mid-term | Solution [ps] [pdf] | |||||
| Project [ps] [pdf] | May 12 | Solution [ps] [pdf] | 18.2/20 | 20/20 | ||
| Homework 4 [ps] [pdf] | April 12 | Solution [ps] [pdf] | 12/20 | 19/20 | ||
| Homework 5 [ps] [pdf] | April 26 | Solution [ps] [pdf] | 12.75/20 | 20/20 | ||
| Homework 6 [ps] [pdf] | May 12 | Solution [ps] [pdf] | 15/20 | 20/20 |
Announcements
The required textbook is Algorithm Design by Jon Kleinberg and Éva Tardos, to be published by Addison-Wesley in 2005. Students are asked to buy a preliminary version of the book in the Armory Building, Room 0127, phone number 301-314-2679.The final exam will be on Friday, May 20, 1:30 - 3:30PM. The midterm will be held on March 17th, during class hours. Both exams will be held in the classroom, and will both be closed-book, closed-notes.
The following material from the book is included for the mid-term:
1. All of Chapter 3
2. Chapter 4: Sections 4.1, 4.2, 4.4, 4.5, 4.7
3. Chapter 5: Sections 5.1, 5.3, 5.4, 5.5, and material from Section 5.6 covered up to the end of the class on March 10th (i.e., all material in Section 5.6 except for step (iii) of FFT).
We also covered lower bounds for sorting in class on April 7th from outside the textbook, and a handout on this was given in class. Please make sure to get this handout from Aravind in case you did not attend class on April 7th.
The following material is included for the final exam. All items except for item 5 below, denote sections/chapters in the textbook.
1. All of Chapter 3
2. Chapter 4: Sections 4.1, 4.2, 4.4, 4.5, 4.7.
3. Chapter 5: Sections 5.1, 5.3, 5.4, 5.5, and 5.6.
4. Chapter 6: Sections 6.1, 6.2, 6.4, 6.5, 6.8 and 6.9.
5. Material on lower bounds from outside the textbook, covered in class on April 7th.
6. Chapter 8:
* Sections 8.1, 8.2, 8.3, 8.4 and 8.9;
* You are also required to understand the statements of Theorems 8.17, 8.18, 8.19, 8.20, 8.21, 8.22, 8.23 and 8.24 in the textbook. You are not required to know their proofs, but you need to understand what the problems referred to in these theorems mean.
7. Chapter 11: Sections 11.1, 11.2, and 11.6.
8. Chapter 13: Sections 13.1, 13.3, and 13.4.
On the week of May 16, Aravind will have extra office hours in his office (AVW 3227) as follows: Tue (5/17): 9-11 AM, and Thu (5/19): 10 AM - 12 noon.