Course Description

This course presents an introduction to the techniques for designing efficient computer algorithms and analyzing their running times. General topics include asymptotics, solving summations and recurrences, algorithm design techniques, analysis of data structures, and introduction to NP-completeness.

This course presents an introduction to the techniques for designing efficient computer algorithms and analyzing their running times. General topics include asymptotics, solving summations and recurrences, algorithm design techniques, analysis of data structures, and introduction to NP-completeness.

Course Information

### Instructor

- Clyde Kruskal (kruskal@cs.umd.edu), Office 3215 AV Williams

### Piazza

- We will be using piazza for announcements and discussions. Please register yourself on Piazza. You can ask private questions (only instructor and TAs can see) or ask/reply anonymously. However DO NOT post your answer and ask if it is correct. If in doubt, ask private question or come during office hours.

### Books

- Cormen, Thomas H.; Leiserson, Charles E.; Rivest,
Ronald L.; Stein, Clifford (2009).
*Introduction to Algorithms*(3rd ed.). MIT Press (Any edition is fine) - Parberry and Gasarch.
*Problems on Algorithms*(free with small suggested donation)

### Teaching Assistants

- Hanuma Teja Maddali (hmaddali@umd.edu)
- Hong Hao Fu (h7fu@umd.edu)
- Jerry Tan (jerrybtw@terpmail.umd.edu)
- Melika Abolhassani (melika.abolhasani@gmail.com)
- Phong Dinh (pdinh@umd.edu)
- Sheng Yang (yangsheng6810@gmail.com)

### Midterm Exam

### Final Exam

### Syllabus

Office Hours

- Clyde Kruskal: Monday, Wednesday 2:30-4:00pm
- Hanuma Teja Maddali: Tuesday, Thursday 3:30pm-5:30pm
- Hong Hao Fu: Tuesday, Thursday 10:30am-12:30pm
- Phong Dinh: Monday, Wednesday 6:00pm-8:00pm
- Jerry Tan: Tuesday, Thursday 5:30pm-7:30pm
- Sheng Yang: Tuesday, Thursday 3:30pm-5:30pm
- Melika Abolhassani: Friday 10:00am-12:00pm
- Jeffrey Falgout: Thursday, Friday 2:00pm-3:00pm
- Ruizhe Li: Monday, Wednesday 4:00pm-5:00pm
- Jamie Matthews: Monday 1:45pm-2:45pm, Thursday 5:30pm-7:30pm
- Monday: 1:45pm-2:45pm, 2:30pm-4:00pm, 4:00-5:00pm, 6:00pm-8:00pm
- Tuesday: 10:30am-12:30pm, 3:30pm-5:30pm, 5:30-7:30pm
- Wednesday: 2:30pm-4:00pm, 4:00-5:00pm, 6:00pm-8:00pm
- Thursday: 10:30am-12:30pm, 2:00pm-3:00pm, 3:30pm-5:30pm, 5:30-7:30pm
- Friday: 10:00am-12:00pm, 2:00pm-3:00pm

### By person

### By day

Class Resources

- Quadratic sorting algorithms
- Integer multiplication
- Heap sort animation
- Pseudo code for heap sort
- Note on mathematical induction
- Analysis of quick sort slides
- Knuth's article: Estimating the Efficiency of Backtrack Programs
- Counting Sort
- Radix Sort
- Selection
- Dijkstra's shortest paths algorithm
- Prim's minimum spanning tree algorithm
- Homework 7 solution: does not allow knight's path to close
- Homework 7 solution: allows knight's path to close

Online Resources

- David Mount's Lecture Notes
- CMSC351 Spring Spring 2011 Reference Pages