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

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

Location | Online Only |

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

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

Fulfills | Core Theory |

***This course will be conducted remotely and will be online only for Winter 2021***

Course Description

The course is an introduction to the design and analysis of efficient algorithms, with emphasis on developing design techniques. Algorithmic problems include sorting and searching, discrete optimization, and algorithmic graph theory. Design techniques include divide-and-conquer methods, dynamic programming, 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. NP-complete problems and reductions are discussed at the end the course.

**Course Contents**

Topics covered include: sorting and searching; divide-and-conquer; randomization; dynamic programming; graph search; shortest paths; minimum spanning trees; network flow; NP-complete problems and reductions.

**Coursework****Lectures and class discussion**: Students are responsible for all material presented in lectures and discussed in class. **Homework**: Weekly homework assignments are posted after class and are due the following week at the beginning of class. Homework is submitted electronically using LaTeX.**Exams**: Midterm exam (week 5) and final exam (week 11). There will be no make-up exams.

**Course grade**

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

- Homework: 30%
- Midterm: 30%
- Final: 35%
- Class participation: 5%

**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 passing score on the Mathematics Placement exam.

Core Programming (completed or concurrently taking).

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

- MPCS 56511-1 -- Introduction to Computer Security
- MPCS 51030-1 -- iOS Application Development
- MPCS 51200-1 -- Introduction to Software Engineering