Section | 1 |
---|---|

Instructor(s) | Ng, Timothy (timng) |

Location | Ryerson 251 |

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

Fulfills | Core Theory |

**Course Description**

The course is an introduction to the design and analysis of efficient algorithms, with emphasis on developing techniques for the design and rigorous analysis of algorithms rather than on implementation. Algorithmic problems include sorting and searching, discrete optimization, and algorithmic graph theory. Design techniques include divide-and-conquer methods, dynamic programming, greedy methods, graph search, 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-completeness is discussed at the end the course. Students who complete the course will have demonstrated the ability to use divide-and-conquer methods, dynamic programming methods, and greedy methods, when an algorithmic design problem calls for such a method. 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 or modify such algorithms to solve algorithm problems when appropriate. They will have derived and solved recurrences describing the performance of divide-and-conquer algorithms, have analyzed the time and space complexity of dynamic programming algorithms, and have analyzed the efficiency of the major graph algorithms, using asymptotic analysis.

**Course Contents**

Topics covered include: sorting and searching; divide-and-conquer; dynamic programming; graph search; shortest paths; minimum spanning trees; network flow; hashing and binary search trees, as time permits. NP-complete problems are discussed at the end of the course.

MPCS 50103 Discrete Math (Immersion Math) OR successfully passing the Mathematics Placement exam.

Core Programming (completed or 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 51410-1 -- Object Oriented Programming
- MPCS 56430-1 -- Introduction to Scientific Computing
- MPCS 51039-1 -- Mobile Software Development
- MPCS 52040-1 -- Distributed Systems

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