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

Spring 2002

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 |

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 |

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: