Spring 2006

Srinivasan Parthasarathy will be covering the lecture for Aravind on 3/28.

The due-date for HW6 has been extended to April 27.

Dov Gordon will be covering the lecture on 4/25.

Homeworks are to be turned in at the start of class on the due date. Since homework solutions will be handed out on the day the homework is due,

The topics, times and order listed in the syllabus next are tentative and are subject to change:

Graph exploration: 4-5 lectures; Greedy algorithms: 4 lectures; Divide and Conquer algorithms: 4 lectures; Dynamic programming: 5 lectures; String-type algorithms: 1 lecture; Lower Bounds: 1 lecture; NP-completeness and Intractability: 5 lectures; Approximation Algorithms: 2 lectures; and Randomized Algorithms: 2 lectures.

Assignment | Due Date | Solution | Avg ugrads | Max ugrads |
---|---|---|---|---|

Homework 1 [ps] [pdf] | Feb 14 | [pdf] | 20.7 | 35 |

Homework 2 [ps] [pdf] | Feb 23 | [pdf] | 17.0 | 25 |

Homework 3 [ps] [pdf] | March 7 | [pdf] | 35.0 | 40 |

Homework 4 [ps] [pdf] | March 14 | [pdf] | 17.2 | 20 |

Midterm | March 16 | [pdf] | 26.3 | 30 |

Homework 5 [ps] [pdf] | April 6 | [pdf] | 26.7 | 30 |

Project [ps] [pdf] | Part I due April 18 | [pdf] | 9.3 | 10 |

Part II due May 9 | ||||

Homework 6 [ps] [pdf] | April 27 | [pdf] | 34.8 | 40 |

Homework 7 [ps] [pdf] | May 11 | [pdf] | 16.6 | 20 |

The following sections from the textbook are included for
the mid-term:

Chapter 3,

Sections 4.1, 4.2, 4.4, 4.5, 4.7,

Sections 5.1, 5.3, 5.4, 5.6.

The following sections from the textbook are included for
the final:

Chapter 3,

Sections 4.1, 4.2, 4.4, 4.5, 4.7,

Sections 5.1, 5.3, 5.4, 5.6,

Sections 6.1, 6.2, 6.4, 6.5, 6.8,

Material on lower bounds from outside the textbook,
covered in class on April 6th,

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.

Sections 11.1, 11.2, 11.6, and

Sections 13.1, 13.3, 13.4.

Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.

The University of Maryland, College Park has a nationally recognized Code of Academic Integrity, administered by the Student Honor Council. This Code sets standards for academic integrity at Maryland for all undergraduate and graduate students. As a student you are responsible for upholding these standards for this course. It is very important for you to be aware of the consequences of cheating, fabrication, facilitation, and plagiarism. For more information on the Code of Academic Integrity or the Student Honor Council, please visit http://www.studenthonorcouncil.umd.edu/whatis.html.