Section | 2 |
---|---|

Instructor(s) | Brady, Geraldine (gb52) |

Location | Ryerson 251 (In-Person Only) |

Meeting Times | Tuesday 5:30pm - 7:30pm |

Fulfills | Core Theory |

****Cannot take this course in your last quarter in the program****

Course Description

The course is an introduction to the design and analysis of efficient algorithms, with emphasis on design techniques. Algorithmic problems include sorting and searching, discrete optimization, and algorithmic graph theory. Design techniques include divide-and-conquer methods, dynamic programming, randomization, greedy methods, as well as the design of efficient data structures. Methods of algorithm analysis include asymptotic notation, evaluation of recurrences, and the concepts of polynomial-time algorithms. Students who complete the course will have demonstrated the ability to use divide-and-conquer methods, dynamic programming methods, and greedy methods in algorithmic design. They will have learned the design strategies employed by the major sorting algorithms and the major graph algorithms, and will have demonstrated the ability to use these design strategies to solve algorithm problems. They will have derived and solved recurrences describing the performance of divide-and-conquer algorithms, analyzed the time and space complexity of dynamic programming algorithms, and analyzed the efficiency of the basic graph algorithms, using asymptotic analysis.

**Course Content**

Topics covered include: sorting and searching; divide-and-conquer; randomization; dynamic programming; hash tables and binary search trees; graph search; shortest paths; minimum spanning trees; and network flow.

**Coursework**

Lectures: Students are responsible for all material presented in lectures.

Class sessions: Course material for the current week will be presented in lecture format at the class meetings.

Homework: Weekly homework assignments are 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.

Exams: There will be two quizzes, a midterm exam, and a final exam. There will be no make-up exams.

**Course grade**

The course grade will be based on homework, quizzes, and exams:

- Homework: 10%
- Quizzes: 10% (5% for each quiz)
- Midterm: 30%
- Final: 50%

**Textbook**

Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 978-0-262-03384-8).

MPCS 50103 Discrete Math (Immersion Math) OR a passing score on the MPCS Mathematics Placement exam.

Immerse Programming (completed) or Core programming (concurrently taking).

This course requires competency in Unix and Linux. Please plan to attend the MPCS Unix Bootcamp (https://masters.cs.uchicago.edu/page/mpcs-unix-bootcamp) or take the online MPCS Unix Bootcamp Course on Canvas.

This class is scheduled at a time that conflicts with these other classes:

- MPCS 51046-1 -- Intermediate Python Programming
- MPCS 51042-2 -- Python Programming
- MPCS 52560-1 -- Applied Financial Technology
- MPCS 51230-1 -- User Interface and User Experience Design
- MPCS 52011-1 -- Introduction to Computer Systems
- MPCS 50101-1 -- Concepts of Programming

Masters Program in Computer Science
MS in Computational Analysis in Public Policy (Year 2)
MA in Computational Social Science (Year 2)
Bx/MS in Computer Science (Option 3: Profesionally-oriented - Non-CS Majors)