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

• Midterm Review Session@CMSC Room 1115: 3:30 pm, Monday, March 29
• Talk Announcement:Greedy Algorithms and Linear Programming - a two pronged attack on NP-Completeness"by Dr. Samir Kuller@CSIC Room 1115, 4:00pm, Feb 8, 2010. (all students are strongly recommended to attend the talk.)

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

• Homework 1 pdf (Mean = 88.70)
• Homework 2 pdf (Mean = 79.57)
• Clarification: Our favorite method means to assume that algorithm doesn't return an optimal solution and show by cotradiction that it can improve the optimal solution.

• Homework 3 pdf (Mean = 76.50)
• Hints:For problem 2, form two vectors Q = (q1, ..., qn, 0, 0, ... 0) with n-1 zeros P = (-1/(n-1)^2, ..., -1/2^2, -1/1^2, 0, 1/1^2, 1/2^2, ..., 1/(n-1^2))

compute the convolution R = Q * P here * means convolution using FFT which takes O(nlogn). After getting the convolution, try to use that to get the result we want.

• Homework 4 pdf (Due next Monday, 5/10)
• Homework 5 pdf (Mean = 80.15)

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

• Course notes on "Integer Multiplication"pdf (Thanks Martin Petrov for the note.)