15-451/651 - COURSE PROFILE
Course Level: Undergraduate/Graduate | Units: 12 | Special 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.edu | https://www.cs.cmu.edu/ | Back to Course Profile List |