CS 161 Theory of Computer Science

The course will progress through finite automata, circuits and decision trees, Turing machines and computability, efficient algorithms, reducibility, the P versus NP problem, NP-completeness, the power of randomness, and computational learning theory. It examines the classes of problems that can and cannot be solved by various kinds of machines. It tries to explain the key differences between computational models that affect their power. No degree credits for CS majors.