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

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

Location | RY 251 |

Meeting Times | Wednesday 5:30pm - 8:30pm |

Website: | http://people.cs.uchicago.edu/~brady/MPCS55001/ |

Fulfills | Core Theory |

**Course Description**

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.

**Course Content**

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.

**Coursework***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.

**Course grade**

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%

**Textbook**

Introduction to Algorithms (Third or Fourth Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (MIT Press).

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 review the UChicago CS Student Resource Guide here: https://uchicago-cs.github.io/student-resource-guide/.

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

- MPCS 53020-1 -- Foundations of Database Systems
- MPCS 56511-1 -- Introduction to Computer Security
- MPCS 52553-1 -- Web Development
- MPCS 53112-1 -- Advanced Data Analytics

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)
Masters Program in Computer Science (new students)