Great Ideas in Theoretical Computer Science Course ID 15251 Description This course is about how to use theoretical ideas to formulate and solve problems in computer science. It integrates mathematical material with general problem solving techniques and computer science applications. Examples are drawn from algorithms, complexity theory, game theory, probability theory, graph theory, automata theory, algebra, cryptography, and combinatorics. Assignments involve both mathematical proofs and programming. NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. Key Topics Algorithms, Computability, Computational complexity, Finite automata, Turing machines, Graph theory,,Boolean circuit complexity, P, NP, NP-completeness, Probability theory, Randomized computation, Cryptography Required Background Knowledge Reasoning abstractly and knowing how to write proofs. Knowledge of basic discrete probability theory. Course Relevance Any student who needs to take the course to fulfill their degree requirements should take it. That could be a CS major, or some other major (e.g. Computational Biology, AI). Math majors can take it instead of 21-228. CS minors can take it to fulfill the minor requirements. Typically 1st, 2nd or 3rd year undergraduates students will take the course. Course Goals 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. Learning Resources refer to course website Assessment Structure Changes from semester to semester. Current semester: 35% homework, 5% attendance, 60% exams (2 midterms, 1 final) Course Link http://www.cs.cmu.edu/~15251/
