Course Level: Undergraduate | Units: 3 | Special Permission Required: No (if yes, please see Notes below) |
Frequency Offered: Generally offered every fall semester - confirm course offerings for upcoming semesters by accessing the university Schedule of Classes Course Relevance (who should take this course?): Students who are looking for intensive exposure to theoretical computer science |
Key Topics: | Background Knowledge: | Assessment Structure: |
Selected topics in theory of computation Most Recent Syllabus Available: http://www.cs.cmu.edu/~15251/252.html | Would help to have experience in LaTeX Sample Assignment: not provided Sample class notes: not provided | Homework problems and attendance 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 real-world applications of computational concepts.
- State and explain the important and well-known 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: https://www.cs.cmu.edu/~15251/252.html |
Learning Resources: | Pre-reqs, Cross list, Related: | Notes: |
- Slides or Notes
- Piazza
- Optional Textbooks
| - Prerequisites Required: (15-122 or 15-150) and (15-151 or 21-127 or 21-128)
- Minimum Grades in Prereqs: C in 15-122, C in 15-150, B in 15-151, B in 21-127, B in 21-128
- Corequisites: 15-251
- Prerequisite for: 15-300, 15-312, 15-354, 15-355, 15-359, 15-414, 15-451,15-453, 15-455
- Anti-requisites:
- Cross-Listed:
- Substitutes: 15-123 for 15-122, 15-212 for 15-150, 21-127 for 15-151, 21-128 for 21-127, 15-151 for 21-127
- Related Courses: None
- Reservations:
| Graduate students MUST enroll in the graduate level version of the course. Graduate students will NOT be enrolled into the undergraduate level course and will be removed from the waitlist without notification. |
Department Website: | College Website: | Updated October 2017 |
https://www.csd.cs.cmu.edu/ | https://www.cs.cmu.edu/ | Back to Course Profile List |