| Section | 1 |
|---|---|
| Instructor(s) | Brady, Geraldine (gb52) |
| Location | Eckhart 203 |
| Meeting Times | Tuesday 5:30pm - 8:30pm |
| Fulfills | Core Theory |
Course Description
The focus of this course is on the design and analysis of efficient algorithms, through the study of various algorithmic problems in different topics. Weekly homework assignments in theory and programming develop strong problem-solving skills. In addition to solving interesting homework problems employing various algorithmic techniques, students learn to implement their algorithmic ideas in python in solving a programming problem each week. At the end of the course, the theory of NP-completeness is introduced, and some of the many interesting and important problems for which there are no known efficient algorithms are presented. The course goal is to teach students the skills to design new algorithms and to understand both mathematical and applied aspects of algorithm efficiency and correctness. Hands-on work in algorithm design and original homework problems written specially for this course are student favorites.
Course Content
Topics include design techniques: divide-and-conquer; randomization; dynamic programming; some common data structures used to speed up the the performance of many algorithms: hash tables, heaps, and binary search trees; a series of interesting graph problems on graph search, shortest paths; minimum spanning trees, and network flow; and finally an introduction to linear programming, an algorithmic technique which is widely used in optimization and in industry applications of algorithms. The course concludes by introducing the theory of NP-completeness and presenting some NP-complete problems and interesting reduction techniques used in their study.
Coursework
Lectures and class discussion: Students are responsible for all material presented in lectures/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. Theory homework must be submitted electronically in LaTeX. Homework will include a weekly programming assignment in Python.
Exams: Midterm exam (week 5) and final exam (week 10). There will be no make-up exams.
Quizzes: Weekly quizzes will be given at the beginning of class, starting with week 2.
Course grade
The course grade is based on homework and exams:
Textbooks
Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 978-0-262-03384-8); Algorithms by S. Dasgupta, C.H. Papadimitriou, and U. V. Vaziran (ISN 978-0073523408); Algorithm Design by J. Kleinberg and E. Tardos (ISBN 0-321-29535-8).
Must have completed MPCS 50103 Discrete Math or received a PASS on the MPCS Discrete Math Exam AND have completed or concurrently taking MPCS 51036, 51040, 51042, 51046, 51100, CAPP 30122 or MACS 30122 or have received a Core Waiver for Programming.
This course requires competency in Unix and Linux. If you attended the MPCS Unix Bootcamp you covered the required material. If you did not, please review the UChicago CS Student Resource Guide here: https://uchicago-cs.github.io/student-resource-guide/.
Course request information for non-MPCS students: https://masters.cs.uchicago.edu/student-resources/non-mpcs-student-course-requests/
This class is scheduled at a time that conflicts with these other classes: