- Section 8.1,
- Section 9.1 (excluding the material on "Simultaneous minimum and maximum") and Section 9.3,
- Sections 15.2, 15.3, and 15.5,
- Section 16.1,
- Chapter 22, Chapter 23, Chapter 24 (except Sections 24.2 and 24.4),
- Chapter 25 (up to the end of Section 25.2),
- Section 28.2,
- Chapter 32 (except Sections 32.2 and 32.4),
- Section 33.4,
- Chapter 34 (up to the end of Section 34.5.2; also, you don't need to know the proof that 3-CNF-SAT is NP-complete), and
- Section 35.1.
CMSC 451: Design and Analysis of Computer Algorithms
Spring 2002
(This page must be viewed with a table-capable browser, such as Netscape.)
General Information
Homeworks,
Exams, Project, HandoutsAnnouncementsViewing
and Printing
General Information
| Class Time: | Tue, Thur 11:00-12:15. |
| Room: | ARM0119 |
| Course Syllabus: | Postscript Format |
| Instructor: | Aravind Srinivasan |
| Office: | A.V. Williams 3227. |
| Office Hours: | TuTh 2-3PM |
| Send me email: | srin@cs.umd.edu |
| Teaching Assistant: | Chiu Yuen Koo |
| Office: | A.V. Williams 1151. |
| Office Hours: | MF 9:30-10:30AM or send him an email to arrange the time |
| Send him email: | cykoo@cs.umd.edu |
Homeworks, Exams, Project, Handouts
Note: There is a bug in the solution to ungraded hw5 (32.3-3). Insteadof having the edges from state i to state i+1 in the state transition
diagram, there are edges from state i to state 1(with label P[1]) as well.
Consider P = 'axk', P1a = 'aa', then the largest k s.t. Pk ] 'aa' is 1.
Thanks to Dimitrios Tsoumakos for pointing out the mistake.
Homeworks will be due at the start of class on the due date. Late homeworks will not be accepted.
| Assignment | Due Date |
|---|---|
| Homework 1(pdf) | Feb 14 |
| Homework 2 (pdf) | Feb 28 |
| Homework 3 (pdf) | Mar 12 |
| Homework 4 (pdf) | Apr 18 |
| Homework 5 (pdf) | None |
The mid-term exam is available in postscript and pdf formats.
Here is the Project Description in postscript
and in pdf. (Note: In question (i) of Part I,
the question has been modified from showing:
if i is the largest integer such that a_i
> 0, then any optimal solution will broadcast at time i + 0.5, and will
have no broadcasts after time i + 0.5.
to Suppose i is the largest
integer such that a_i > 0. Show that any optimal solution will broadcast
at time i + 0.5. The change has been reflected in the updated
version.) Thanks to Rajiv Gandhi, Ph.D. student in the Department of Computer
Science, for suggesting this project.
Here is the Project Part II Description in postscript
and in pdf.
| Handouts | Date Released |
|---|---|
| Dynamic Programming Examples (pdf) | Apr 8 |
| D.P. Supplementary Handout (pdf) | Apr 17 |
Announcements
The mid-term exam will be from 11AM to 12:15PM in Room 3258, A.V. Williams Building. The exam will be closed-book, closed-notes.The make-up class will be 6--7:15PM on May 3rd, Friday; it will be held in Room 1112, A.V. Williams Building.
The final exam will be from 10:30AM to 12:30PM on May 18, Saturday, in Room 3258, A.V. Williams Building. (Two or three students will take the exam in the nearby Room 3227, A.V. Williams Building.) The exam will be closed-book, closed-notes. Since some of you may not have access to A. V. Williams on a Saturday, please try to arrive by 10:15 AM--we will have someone waiting just inside the front entrance of A. V. Williams from 10:15 until 11:45 (or until all students have arrived). Please arrive by 10:15, so that this person is not kept waiting. Thanks for your co-operation.
Please read the following topics from the book for the exam: