15-451/651 Algorithm Design and Analysis

15-451/651 - COURSE PROFILE


Course Level: Undergraduate/GraduateUnits: 12Special Permission Required: No 
(if yes, please see Notes)

Frequency Offered: Generally offered every fall and spring semester - confirm course offerings for upcoming semesters by accessing the university Schedule of Classes.

Course Relevance (who should take this course?): This course is for undergraduate students interested in modern, theoretical algorithm design techniques as well as provable guarantees of algorithm correctness and running time.

Key Topics:Background Knowledge:Assessment Structure:
  • Efficient data structures
  • Lower bounds and NP-completeness
  • Approximation algorithms
  • Randomized algorithms
  • Geometric algorithms
  • Low level techniques for efficient programming
  • Linear programming
  • On-line algorithms
  • Graph algorithms (including maximum flow and matchings)
  • Streaming
  • String algorithms
Most Recent Syllabus: https://www.cs.cmu.edu/~15451/

The course relies on mathematical thinking and proofs, and requires the ability to program in a compiled language. (15-251, 15-210, 21-241)

Sample class notes: not provided

Sample Assignment: not provided

  • 4 Written Homeworks: 20%
  • 3 Oral Homeworks: 15%
  • Online Quizzes: 10%
  • 2 Midterms: 30%
  • Final: 25%
Sample Exam: not provided

Sample Lecture Recording: https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.aspx#folderSets=15&folderID=%222d165709-dee6-4ebc-9cae-30cac5ce12c0%22

Course Goals/Objectives:
  • Understanding of the design and analysis on algorithms for a variety of problems
  • Develop skills to reason about and prove properties of algorithms such as their correctness and running time.
  • Understand how data structures can provide space-efficient ways to quickly answer queries about data, and understand how these data structures can be used to build efficient algorithms.
  • Understand analysis techniques such as amortized analysis, probabilistic analysis, and minimax optimality.
  • Understand how and why randomness can be used to provide efficient solutions to some problems.
  • Learn to implement advanced algorithms efficiently.
  • Use the concept of approximation to find efficient algorithms for hard problems.
  • Use the theory of NP-completeness and other lower bounding techniques to argue for the difficulty of some problems.

Course Website: https://www.cs.cmu.edu/~15451/

Learning Resources:Pre-reqs, Cross list, Related:Notes:
  • Piazza
  • Gradescope
  • Autolab
  • On-line quizzes
  • Optional textbooks (many free) are linked on the course website.
  • Prerequisites Required: 15-210 and 21-241 and 15-251
  • Minimum Grades in Prereqs:
    C in 15-210, D in 21-241, C in 15-251
  • Corequisites: None
  • Prerequisite for: 
  • Anti-requisites: None
  • Cross-Listed: 15-651
  • Substitutes: 18-202 for 21-241, 21-235 for 21-241, 21-242 for 21-241, 21-341 for 21-241
  • Related Courses: None
  • Reservations: Some reservations are for Undergraduates in Computer Science; Some reservations are for Undergraduates
MS students should take 15-651. CSD Ph.D. students should likely take a more advanced algorithms class.
Department Website:College Website:Updated November 2017
https://www.csd.cs.cmu.eduhttps://www.cs.cmu.edu/ Back to Course Profile List