Computer Science 172

Title Computability and Complexity
Units 4
Prerequisites 170.
Description Finite automata, Turing machines and RAMs. Undecidable, exponential, and polynomial-time problems. Polynomial-time equivalence of all reasonable models of computation. Nondeterministic Turing machines. Theory of NP-completeness: Cook's theorem, NP-completeness of basic problems. Selected topics in language theory, complexity and randomness.
Course Guide Course Guide
Sections Instructor Teaching Effectiveness How worthwhile was this course?
Fall 2022 Avishay Tal 6.2 / 7 6.2 / 7
Spring 2022 Avishay Tal 6.8 / 7 6.3 / 7
Spring 2021 Alistair Sinclair 6.4 / 7 5.9 / 7
Spring 2015 Luca Trevisan 5.6 / 7 5.8 / 7
Spring 2012 Koushik Sen 5.9 / 7 5.8 / 7
Spring 2011 Koushik Sen 5.8 / 7 5.5 / 7
Spring 2010 Sanjit Seshia 6.6 / 7 6.3 / 7
Fall 2009 Luca Trevisan 5.4 / 7 5.3 / 7
Spring 2008 Sanjit Seshia 6.2 / 7 6.1 / 7
Spring 2007 Luca Trevisan 6.5 / 7 6.7 / 7
Fall 2005 Luca Trevisan 5.3 / 7 5.2 / 7
Spring 2005 Brian Lucena 6.0 / 7 5.6 / 7
Fall 2004 Alistair Sinclair 6.2 / 7 5.6 / 7
Spring 2004 Luca Trevisan 5.2 / 7 5.4 / 7
Fall 2003 Thomas A. Henzinger 5.9 / 7 5.9 / 7
Spring 2003 Alistair Sinclair 6.5 / 7 5.8 / 7
Fall 2002 B. Morris 5.3 / 7 5.1 / 7
Spring 2002 Alistair Sinclair 6.3 / 7 5.8 / 7
Fall 2001 Wim Van Dam 5.5 / 7 5.5 / 7
Spring 2001 Umesh Vazirani 6.0 / 7 5.9 / 7
Fall 2000 Thomas A. Henzinger 5.2 / 7 5.1 / 7
Spring 2000 Thomas A. Henzinger 4.7 / 7 4.8 / 7
Fall 1999 Michael Jordan 5.9 / 7 5.9 / 7
Spring 1999 Manuel Blum 5.6 / 7 4.7 / 7
Spring 1998 Amin Shokrollahi 4.8 / 7 5.4 / 7
Fall 1997 Thomas A. Henzinger 6.0 / 7 5.2 / 7
Spring 1997 Thomas A. Henzinger 5.1 / 7 4.9 / 7
Fall 1996 Dan Raz 3.6 / 7 3.4 / 7
Fall 1995 Alistair Sinclair 6.0 / 7 5.5 / 7
Spring 1995 Alistair Sinclair 5.9 / 7 5.0 / 7
Fall 1994 David Wolfe 6.1 / 7 5.3 / 7
Spring 1994 Alistair Sinclair 6.0 / 7 5.2 / 7
Fall 1993 David Wolfe 6.2 / 7 5.3 / 7
Spring 1993 David Wolfe 5.5 / 7 4.5 / 7
Fall 1992 David Wolfe 4.4 / 7 4.3 / 7
Spring 1992 Manuel Blum 6.2 / 7 5.3 / 7
Spring 1992 Manuel Blum 6.5 / 7 4.9 / 7
Fall 1991 Eugene Lawler 4.4 / 7 4.3 / 7
Spring 1991 Lenore Blum 6.6 / 7 6.1 / 7
Spring 1991 Morteza Anvari 3.0 / 7 3.0 / 7
Fall 1990 Michael A. Harrison 4.7 / 7 4.5 / 7
Spring 1990 H. Saran 3.6 / 7 3.8 / 7
Fall 1989 Umesh Vazirani 4.9 / 7 4.2 / 7
Spring 1989 Umesh Vazirani 4.8 / 7 4.2 / 7
Fall 1988 Raimund Seidel 5.5 / 7 4.7 / 7
Overall Rating Teaching Effectiveness How worthwhile was this course?
[Email HKN about this data] [Info about this page]