# MPCS 55001 Algorithms (Winter 2023)

Section 1 Brady, Geraldine (gb52) Ryerson 251 Thursday 5:30pm - 8:30pm Core Theory

## Syllabus

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 and class discussion:
Students are responsible for all material presented in lectures and in 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.
Exams: Midterm exam (week 5) and final exam (week 10).  There will be no make-up exams.

Course grade
The course grade is based on homework and exams:

• Homework Assignments: 10%
• Midterm Exam: 30%
• Final Exam: 60%

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)

### Course Prerequisites

MPCS 50103 Discrete Math (Immersion Math) OR a passing score on the Mathematics Placement exam.
Core Programming (completed or concurrently taking).

### Other Prerequisites

This course requires competency in Unix and Linux. If you attended the MPCS Unix Bootcamp you covered the required material. If you did not, please review the UChicago CS Student Resource Guide here: https://uchicago-cs.github.io/student-resource-guide/.

### Overlapping Classes

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

• MPCS 50103-1 -- Mathematics for Computer Science: Discrete Mathematics
• MPCS 52011-2 -- Introduction to Computer Systems
• MPCS 51083-1 -- Cloud Computing
• MPCS 51240-1 -- Product Management
• MPCS 51044-1 -- C++ for Advanced Programmers

### Eligible Programs

Masters Program in Computer Science MS in Computational Analysis in Public Policy (Year 1) MS in Computational Analysis in Public Policy (Year 2) 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)