## CMSC 451: Design and Analysis of Algorithms Spring 2012

Instructor: Clyde Kruskal.

Office: AVW 3215.

Office phone: 301-405-2683.

Email: kruskal@cs.umd.edu.

Office hours: Wednesday 3:00-5:00pm

By appointment.

Teaching Assistant: Catalin-Stefan Tiseanu.

Email: ctiseanu@cs.umd.edu

Office: AVW 1112.

Office hours: Monday and Wednesday 1:30pm-3:00pm

**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.
Home work 4.
Home work 5.
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.

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

Back to the Department of Computer Science Class Pages