| Section | 2 |
|---|---|
| Instructor(s) | Brady, Geraldine (gb52) |
| Location | Ryerson 251 |
| 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).
MPCS 50103 Discrete Math (Immersion Math) OR a passing score on the MPCS Math Placement exam. Core Programming (completed or concurrently taking) or a Core Waiver for programming.
This course requires competency in Unix and Linux. New students must attend the MPCS Unix Bootcamp during orientation. Continuing students who previously attended the MPCS Unix Bootcamp have covered the required material. Continuing students who did not attend the MPCS Unix Bootcamp may review the UChicago CS Student Resource Guide here: https://uchicago-cs.github.io/student-resource-guide/.
Non-MPCS, MSCAPP or MACSS students should review our MPCS Course Request Policy: https://masters.cs.uchicago.edu/page/course-requests
This class is scheduled at a time that conflicts with these other classes: