Computer Science 172

[Email HKN about this data] [Info about this page]

Title	Computability and Complexity
Instructors in Charge	Manuel Blum, Alistair Sinclair, Umesh Vazirani
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.
Exam Files	Available
Newsgroup	ucb.class.cs172

Sections Instructor Teaching Effectiveness How worthwhile was this course?

Spring 2008 Seshia 6.2 / 7 ± 0.5
6.1 / 7 ± 0.3

Spring 2007 Trevisan 6.5 / 7 ± 0.5
6.7 / 7 ± 0.3

Fall 2006 Seshia 5.6 / 7 ± 0.6
5.6 / 7 ± 0.6

Fall 2005 Trevisan 5.3 / 7 ± 0.6
5.2 / 7 ± 0.9

Spring 2005 Lucena 6.0 / 7 ± 0.6
5.6 / 7 ± 0.8

Fall 2004 Sinclair 6.2 / 7 ± 0.3
5.6 / 7 ± 0.6

Spring 2004 Trevisan 5.2 / 7 ± 0.9
5.4 / 7 ± 1.1

Fall 2003 Henzinger 5.9 / 7 ± 0.4
5.9 / 7 ± 0.4

Spring 2003 Sinclair 6.5 / 7 ± 0.2
5.8 / 7 ± 0.4

Fall 2002 Morris 5.3 / 7 ± 0.7
5.1 / 7 ± 0.8

Spring 2002 Sinclair 6.3 / 7 ± 0.3
5.8 / 7 ± 0.4

Fall 2001 Van Dam 5.5 / 7 ± 0.5
5.5 / 7 ± 0.4

Spring 2001 Vazirani 6.0 / 7 ± 0.4
5.9 / 7 ± 0.7

Fall 2000 Henzinger 5.2 / 7 ± 0.6
5.1 / 7 ± 0.6

Spring 2000 Henzinger 4.7 / 7 ± 0.5
4.8 / 7 ± 0.5

Fall 1999 Jordan 5.9 / 7 ± 0.2
5.9 / 7 ± 0.4

Spring 1999 Manuel Blum 5.6 / 7 ± 0.3
4.7 / 7 ± 0.5

Spring 1998 Amin Shokrollahi 4.8 / 7 ± 0.6
5.4 / 7 ± 0.3

Fall 1997 Henzinger 6.0 / 7 ± 0.6
5.2 / 7 ± 1.0

Spring 1997 Henzinger 5.1 / 7 ± 0.4
4.9 / 7 ± 0.5

Fall 1996 Raz 3.6 / 7 ± 1.1
3.4 / 7 ± 1.2

Spring 1996 Papadimitriou 5.5 / 7 ± 0.4
5.1 / 7 ± 0.5

Fall 1995 Sinclair 6.0 / 7 ± 0.4
5.5 / 7 ± 0.3

Spring 1995 Sinclair 5.9 / 7 ± 0.4
5.0 / 7 ± 0.4

Fall 1994 Wolfe 6.1 / 7 ± 0.3
5.3 / 7 ± 0.4

Spring 1994 Sinclair 6.0 / 7 ± 0.4
5.2 / 7 ± 0.7

Fall 1993 Wolfe 6.2 / 7 ± 0.3
5.3 / 7 ± 0.5

Spring 1993 Wolfe 5.5 / 7 ± 0.4
4.5 / 7 ± 0.6

Fall 1992 Section 2 Wolfe 4.4 / 7 ± 0.7
4.3 / 7 ± 0.6

Spring 1992 Section 1 Manuel Blum 6.5 / 7 ± 0.4
4.9 / 7 ± 0.7

Spring 1992 Section 2 Manuel Blum 6.2 / 7 ± 0.5
5.3 / 7 ± 0.5

Fall 1991 Lawler 4.4 / 7 ± 0.5
4.3 / 7 ± 0.5

Spring 1991 Section 1 Anvari 3.0 / 7 ± 0.6
3.0 / 7 ± 0.6

Spring 1991 Section 2 Lenore Blum 6.6 / 7 ± 0.3
6.1 / 7 ± 0.4

Fall 1990 Harrison 4.7 / 7 ± 0.6
4.5 / 7 ± 1.1

Spring 1990 Saran 3.6 / 7 ± 0.6
3.8 / 7 ± 0.6

Fall 1989 Vazirani 4.9 / 7 ± 0.4
4.2 / 7 ± 0.5

Spring 1989 Vazirani 4.8 / 7 ± 0.6
4.2 / 7 ± 0.6

Fall 1988 Seidel 5.5 / 7 ± 0.5
4.7 / 7 ± 0.7

Overall Rating Teaching Effectiveness How worthwhile was this course?

Computer Science 172 5.6 / 7 ± 0.0
5.4 / 7 ± 0.0

Hint: You can click on the colored rating bars to see detailed statistics on a particular rating.