# 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.)

### Previous Course Websites

### Grades

grade server