This course is an introduction to basic techniques in the design and analysis of efficient algorithms, through the study of various classical algorithmic problems. Algorithmic problems include sorting and searching, discrete optimization, and a series of graph problems. Design techniques include divide-and-conquer, dynamic programming, randomization, and greedy methods, as well as the design of efficient data structures. Algorithm analysis includes asymptotic notation, evaluation of recurrences, and correctness. Weekly homework assignments develop strong problem-solving skills. In addition to solving interesting homework problems teaching algorithmic techniques, students learn to implement their algorithmic ideas using python on a weekly programming problem. The course will give students some experience in algorithm design and emphasizes both mathematical and applied aspects of algorithm efficiency.
Topics include sorting and searching; divide-and-conquer; randomization; dynamic programming; hash tables, heaps, and binary search trees; graph search; graph shortest paths; minimum spanning trees; and network flow. The course concludes by introducing the notion of NP-completeness and presenting some NP-complete problems.
Lectures: Students are responsible for all material presented in lectures and homework.
Class sessions: Course material for the current week will be presented in lecture format at the class meetings.
Homework: All students are required to submit weekly homework to pass the course. Weekly homework assignments will be posted after class and are due the day before class on the following week. Homework must be submitted electronically. Homework will include a weekly programming assignment in Python.
Examinations: There will be two quizzes, a midterm exam, and a final exam. There will be no makeup midterm or final exams.
The course grade is based on homework, quizzes, and exams:
- Homework Assignments: 10%
- Quizzes: 10% (5% for each quiz)
- Midterm Exam: 30%
- Final Exam: 50%
Introduction to Algorithms (Third or Fourth Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (MIT Press).