CMSC 451: Design and Analysis of Computer Algorithms
Spring
2006
Announcements
In addition to the regular office hours, Dov and Aravind will have the following additional office hours, on the week of May 8: Dov: 1-3 on Tuesday, and 1-2 on Thursday; Aravind: 2-3 on Wednesday, and 10-12 on Friday.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.
General Information
Class Time and Venue: Tue, Thu 9:30-10:45, CSI 2117Class Homepage (this page): http://www.cs.umd.edu/class/spring2006/cmsc451/index.html
Instructor: Aravind Srinivasan
Aravind's Office Hours: Tue, Thu 2-3PM, in his office (A.V. Williams 3227)
TA: Dov Gordon, gordon AT cs.umd.edu
Dov's Office Hours: Mon, Wed 1-2PM, in AVW 1112
Course Description
Course Overview:
This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include graph algorithms, and basic algorithm design paradigms (such as divide-and-conquer, dynamic programming and greedy algorithms), lower bounds and NP-completeness. CMSC 351 is the prerequisite. Each student is expected to know the basic concepts of programming (e.g. loops, pointers, recursion), discrete mathematics (proof by induction, sets), simple data structures (lists, stacks, queues, trees, heaps), and calculus (logarithms, differentiation, integration). We will assume knowledge of the basic algorithm-analysis techniques covered in CMSC 351. The required textbook is Algorithm Design (ISBN: 0-321-29535-8) by Jon Kleinberg and Éva Tardos, published by Addison-Wesley. The coursework will consist of 5-7 homework assignments, a small project and two exams (one midterm and a comprehensive final). Homework problems will be mathematically oriented.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, no late homeworks will be accepted. All homeworks are to be done independently, with no help from the web, or other sources. If you have questions, please talk to the TA or the Instructor. Assignments are to be written up neatly. Please staple your homework. It is your responsibility to make sure that you pick up all homeworks and handouts. All course information and handouts will be available on the class web page.
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.
Grading and Exams:
Final grades will be based on homework assignments, the project, the midterm exam, and the comprehensive final exam. The relative weights of these will be 25% for the homework total, 10% for the project, 25% for the midterm, and 40% for the final exam. The final examination, according to the official university schedule, will be on Monday, May 15, 8-10 AM. The midterm will be on Thursday, March 16, during class hours (9:30--10:45 AM). Both exams will be held in the classroom, and will both be closed-book, closed-notes. Graduate students in this class will be given extra work on homeworks and exams.Homework, Exams, Project, Handouts
| 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.
Additional Information
Students claiming a excused absence must apply in writing and furnish documentary support (such as from a health care professional who treated the student) for any assertion that the absence qualifies as an excused absence. The support should explicitly indicate the dates or times the student was incapacitated due to illness. Self-documentation of illness is not itself sufficient support to excuse the absence. The instructor is not under obligation to offer a substitute assignment or to give a student a make-up assessment unless the failure to perform was due to an excused absence. An excused absence for an individual typically does not translate into an extension for team deliverables on a project.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.