# (This page must be viewed with a table-capable browser, such as Netscape.)

General InformationHomeworks, 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). Instead
of 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.

• 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.

## 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.

Web Accessibility