Course Level: Undergraduate 
Units: 12 
Special Permission Required: No (if yes, please see Notes below) 
Frequency Offered: Generally offered every spring and fall  confirm course offerings for upcoming semesters by accessing the university Schedule of Classes 
Course Relevance (who should take this course?): 
Key Topics: 
Background Knowledge: 
Assessment Structure: 
 Algorithms
 Computability
 Computational complexity
 Finite automata
 Turing machines
 Graph theory
 Boolean circuit complexity
 P, NP, NPcompleteness
 Probability theory
 Randomized computation
 Cryptography
Most Recent Syllabus Available: http://www.cs.cmu.edu/~15251/policy.html

In particular, we expect the students to have taken an introductory computer science course that goes beyond basic computer programming and covers algorithmic thinking. On the mathematics side, we expect the students to have experience reasoning abstractly and be comfortable with writing formal proofs.
Sample Assignment: not provided
Sample class notes: not provided

Standard Grading:
 Homework 30%
 Midterm 1 20%
 Midterm 2 20%
 Final 25%
 Participation 5%
Alternative Grading for a maximum letter grade of C:
 Homework 30% (lowest 4 homeworks halfweighted)
 Higher Midterm 30%
 Final 35 %
 Participation 5 %
To pass the course with a letter grade of C or higher, one of your exam scores must be at least 70%.
Sample Exam: not provided
Sample Lecture Recording: not applicable

Course Objectives: 
 Define mathematically the notions of computation, computational problem, and algorithm.
 Express, analyze and compare the computability and computational complexity of problems.
 Use mathematical tools from set theory, combinatorics, graph theory, probability theory, and number theory in the study of computability, computational complexity, and some of the realworld applications of computational concepts.
 State and explain the important and wellknown open problems in the theory of computation.
 Write clearly presented proofs that meet rigorous standards of correctness and conventional guidelines on style.
 Identify and critique proofs that are logically flawed and/or do no meet the expected standards of clarity.
 Cooperate with other people in order to solve challenging and rigorous problems related to the study of computer science.
Course Website: http://www.cs.cmu.edu/~15251/

Learning Resources: 
Prereqs, Cross list, Related: 
Notes: 
 Recorded Lectures
 Slides
 Course Notes
 Piazza
 Optional Textbooks

 Prerequisites Required: (15122 or 15150) and (21127 or 21128 or 15151)
 Minimum Grades in Prereqs: C
 Corequisites: None
 Prerequisite for: 15300, 15312, 15354, 15355, 15359, 15414, 15451,15453, 15455
 Antirequisites:
 CrossListed:
 Substitutes: 15123 for 15122, 15212 for 15150, 21127 for 15151, 21128 for 21127, 15151 for 21127
 Related Courses: None
 Reservations:


Department Website: 
College Website: 
Updated October 2017 
https://www.csd.cs.cmu.edu/ 
https://www.cs.cmu.edu/ 
Back to Course Profile List 