CMSC 451: Design and Analysis of Algorithms Fall 2011


Instructor: Clyde Kruskal.
Office: AVW 3215.
Office phone: 301-405-2683.
Email: kruskal@cs.umd.edu.
Office hours: Tuesday 2:00-4:30pm
Also by appointment.

Teaching Assistant: Reza Khani.
Email: khani@cs.umd.edu
Office hours: AVW 1112.
Office hours: Monday 4:00pm-7:00pm
Also by appointment.

Course Overview: This course presents fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include graph algorithms, sorting, searching, and basic algorithm design paradigms (such as divide-and-conquer, dynamic programming, and greedy algorithms), lower bounds, and NP-completeness.

Text: Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, 2005. Supplemental Text: Thomas Cormen, Charles Leiserson, Ron Rivest, and Clifford Stein, Introduction to Algorithms, McGraw Hill and MIT Press, Second Edition, 2001.

Prerequisite: CMSC 351. 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), and calculus (logarithms, differentiation, integration). Also, each student is expected to have taken an introductory algorithms course (cmsc351, or its equivalent).

Course Work: Course work will consist of written homework assignments and two exams (one midterm and a final). Homework problems will be mathematically oriented. Homeworks are to be turned in at the start of class on the due date. All homeworks are to be written up independently. They should be clear and NEAT.
Home work 1.
Home work 2.
Home work 3.
Practice Midterm.
Home work 4.
Home work 5.
Home work 6.
Practice Final.

Grading: Final grades will be based on homework assignments, the midterm exam, and the comprehensive final exam. The relative weights of these will be approximately 10% for the homework total, 40% for of the midterm, and 50% for the final exam.

Syllabus: The following is a tentative list of topics and readings. Other topics may be covered.

  1. Introduction (Ch. 1)
  2. Graphs (Ch. 3)
  3. Greedy algorithms (Ch. 4)
  4. Divide and Conquer (Ch. 5)
  5. Dynamic programming (Ch. 6)
  6. NP-completeness (Ch. 8)
  7. Approximation Algorithms (and Linear Programming) (Ch. 11)

[Back] Back to the Department of Computer Science Class Pages