MPCS 55001 Algorithms (Autumn 2020)

Section 2
Instructor(s) Chaudhary, Amitabh (amitabh)
Location Online Only
Meeting Times Tuesday 2:40pm - 4pm
Thursday 2:40pm - 4pm
Fulfills Core Theory


*This course will be conducted remotely and will be online only for Autumn 2020*

Course Description

**Cannot take this course in your last quarter in the program**
The course is an introduction to the design and analysis of algorithms, with emphasis on developing design techniques for efficient algorithms. 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.

Lectures: Students are responsible for all material presented in class and on homework assignments.
Problem sessions: Weekly problem sessions are held on Saturdays. Students are responsible for material covered at the problem sessions.  Class participation is encouraged.
Homework: Weekly homework assignments are posted after class and are due the day before the next class.  Homework must be submitted electronically.
Exams: There are four quizzes (weeks 3, 4, 9, and 10), a midterm exam (week 5), and a final exam (week 11).  There will be no make-up exams.

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

  • Homework: 5%.
  • Quizzes: 20% (5% for each of 4 quizzes).
  • Midterm: 25%.
  • Final: 50%.

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 successfully passing the Mathematics Placement exam.
Core Programming (completed or concurrently taking).

Other Prerequisites

Overlapping Classes

This class is scheduled at a time that does not conflict with any other classes this quarter.