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
Class Time / Venue
- M-F 9:30am - 10:55am @ CSI 3117
Piazza
Textbook (on reserve at McKeldin Library)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). MIT Press (Any edition is fine)
Supplementary Book
- Parberry and Gasarch. Problems on Algorithms (free with small suggested donation)
Exams
- Midterm: Wednesday, June 27, 8:45am
- Final: Friday, July 6, 8:45am
Syllabus
Office Hours
- Clyde Kruskal: Every day: 11:00am-12:00pm
- TA's: Monday, Tuesday, Wednesday, Thursday: 2:00pm-5:00pm
- Peter Sutor (psutor@umd.edu), Shuhao Tan (shuhao@cs.umd.edu)
Class Resources
- Note on mathematical induction
- Introductory Slides
- Maximum contiguous subsequence
- Sorting algorithms
- Integer addition
- Integer multiplication
- Heap sort animation
- Knuth's article: Estimating the Efficiency of Backtrack Programs
- Analysis of quick sort slides
- Counting Sort
- Radix Sort
- Selection
- Selection Worst Case
- Prim's minimum spanning tree algorithm
- Dijkstra's shortest paths algorithm
Online Resources
- David Mount's Lecture Notes
- CMSC351 Spring Spring 2011 Reference Pages