CMSC 451 - Design and Analysis of Computer Algorithms

Course Description

Fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include sorting, selection, graph algorithms, and basic algorithm design paradigms (such as divide-and-conquer, dynamic programming and greedy algorithms), lower bounds and NP-completeness.

General Information

Class Time/Location
The class meets Monday and Wednesday, 2:00pm-3:15pm in CSI 1122
Instructor
Clyde Kruskal
Office Hours
Monday, Tuesday 12:30pm-2:00pm
Teaching Assistant
Jun-Cheng Chen, Email: pullpull_at_cs_dot_umd_dot_edu
TA Office Hours
Monday 9:00-11:00am, Wednesday 9:00-11:00am AVW 1112
Textbook
Algorithm Design, by Jon Kleinberg, Éva Tardos

News

Syllabus

syllabus (Midterm: in class Wednesday, March 31, Makeup Miterm: in class Wednesday, April 14, Final exam: Monday, May 17, 1:30-3:30pm.)

Homeworks

Homeworks are due at the start of class.

An example of suggested format when you present your algorithm pdf

The following tips are borrowed from CMSC754, instructed by Dr. Dave Mount.

Some tips about writing algorithms: Henceforth, whenever you are asked to present an "algorithm," you should present three things: (1)the algorithm(60%),(2)an informal proof of its correctness(20%), and (3)a derivation of its running time(20%). Remember that your description is intended to be read by a human, not a compiler, so conciseness and clarity are preferred over technical details. Unless otherwise stated, you may use any results from class, or results from any standard algorithm text. Nonetheless, be sufficiently complete that all critical issues are addressed, except for those that are obvious. (See the lecture notes for examples.)

Resources

Previous Course Websites

Grades

grade server