Computer Science 170

Title Efficient Algorithms and Intractable Problems
Units 4
Prerequisites 61B, Mathematics 55.
Description Concept and basic techniques in the design and analysis of algorithms; models of computation; lower bounds; algorithms for optimum search trees, balanced trees and UNION-FIND algorithms; numerical and algebraic algorithms; combinatorial algorithms. Turing machines, how to count steps, deterministic and nondeterministic Turing machines, NP-completeness. Unsolvable and intractable problems.
Course Guide Course Guide
Sections Instructor Teaching Effectiveness How worthwhile was this course?
Fall 2023 Nika Haghtalab 6.2 / 7 5.9 / 7
John Wright 6.3 / 7 5.9 / 7
Spring 2023 Prasad Raghavendra 5.6 / 7 5.8 / 7
John Wright 6.0 / 7 5.8 / 7
Fall 2022 James W Demmel 6.1 / 7 5.9 / 7
Jelani Nelson 6.3 / 7 5.9 / 7
Spring 2022 Prasad Raghavendra 5.3 / 7 5.4 / 7
John Wright 5.7 / 7 5.4 / 7
Fall 2021 Jelani Nelson 5.9 / 7 5.5 / 7
Spring 2021 Alessandro Chiesa 6.1 / 7 5.7 / 7
James W Demmel 5.2 / 7 5.7 / 7
Fall 2020 Avishay Tal 5.9 / 7 5.8 / 7
Umesh Vazirani 5.8 / 7 5.8 / 7
Spring 2020 Alessandro Chiesa 5.7 / 7 5.6 / 7
Jelani Nelson 6.0 / 7 5.6 / 7
Fall 2019 Prasad Raghavendra 5.5 / 7 5.6 / 7
Satish Rao 4.9 / 7 5.6 / 7
Fall 2018 Alessandro Chiesa 6.1 / 7 5.8 / 7
Satish Rao 5.0 / 7 5.8 / 7
Spring 2018 Alessandro Chiesa 6.0 / 7 6.0 / 7
Umesh Vazirani 5.8 / 7 6.0 / 7
Fall 2017 Prasad Raghavendra 5.4 / 7 6.0 / 7
Spring 2017 Sanjam Garg 5.2 / 7 6.0 / 7
Prasad Raghavendra 5.7 / 7 6.0 / 7
Fall 2016 Christos Papadimitriou 6.1 / 7 6.1 / 7
Luca Trevisan 5.2 / 7 6.1 / 7
Spring 2016 Alessandro Chiesa 5.3 / 7 6.2 / 7
Umesh Vazirani 6.0 / 7 6.3 / 7
Fall 2015 Sanjam Garg 5.2 / 7 6.2 / 7
Prasad Raghavendra 5.8 / 7 6.2 / 7
Spring 2015 Christos Papadimitriou 5.8 / 7 5.8 / 7
Prasad Raghavendra 5.6 / 7 6.1 / 7
Fall 2014 David Wagner 6.8 / 7 6.8 / 7
Spring 2014 Elchanan Mossel 4.9 / 7 6.0 / 7
Spring 2013 Christos Papadimitriou 6.2 / 7 6.5 / 7
Prasad Raghavendra 5.4 / 7 6.4 / 7
Fall 2012 Satish Rao 5.3 / 7 6.0 / 7
Spring 2012 Christos Papadimitriou 5.6 / 7 6.0 / 7
Satish Rao 5.2 / 7 6.0 / 7
Fall 2011 James W Demmel 5.3 / 7 6.2 / 7
Spring 2011 Satish Rao 5.0 / 7 5.4 / 7
Umesh Vazirani 5.2 / 7 5.5 / 7
Fall 2010 Christos Papadimitriou 6.0 / 7 6.4 / 7
Spring 2010 James W Demmel 4.9 / 7 5.9 / 7
Fall 2009 Christos Papadimitriou 6.1 / 7 6.2 / 7
Spring 2009 David Wagner 6.7 / 7 6.6 / 7
Fall 2008 Satish Rao 4.6 / 7 5.3 / 7
Spring 2008 Satish Rao 4.0 / 7 5.5 / 7
Fall 2007 Christos Papadimitriou 6.3 / 7 6.3 / 7
Spring 2007 James W Demmel 4.8 / 7 5.7 / 7
Fall 2006 Christos Papadimitriou 5.8 / 7 5.9 / 7
Umesh Vazirani 5.8 / 7 6.1 / 7
Spring 2006 Alistair Sinclair 6.3 / 7 6.1 / 7
Fall 2005 Michael Jordan 6.1 / 7 6.0 / 7
Spring 2005 Christos Papadimitriou 6.1 / 7 5.6 / 7
Luca Trevisan 4.6 / 7 5.4 / 7
Fall 2004 Gene Myers 4.6 / 7 5.3 / 7
Spring 2004 Christos Papadimitriou 5.9 / 7 5.7 / 7
Umesh Vazirani 5.6 / 7 5.7 / 7
Fall 2003 Satish Rao 5.5 / 7 5.9 / 7
Spring 2003 David Wagner 6.5 / 7 6.2 / 7
Fall 2002 Thomas A. Henzinger 5.5 / 7 6.0 / 7
Spring 2002 Satish Rao 5.2 / 7 5.6 / 7
Fall 2001 Luca Trevisan 4.5 / 7 5.7 / 7
Spring 2001 James W Demmel 5.4 / 7 5.4 / 7
Jonathan Shewchuk 5.0 / 7 5.2 / 7
Fall 2000 Michael J. Clancy 5.0 / 7 5.4 / 7
Spring 2000 Michael J. Clancy 4.9 / 7 5.3 / 7
Fall 1999 James W Demmel 5.2 / 7 5.1 / 7
Spring 1999 Christos Papadimitriou 5.3 / 7 5.1 / 7
Umesh Vazirani 5.3 / 7 5.1 / 7
Fall 1998 Christos Papadimitriou 5.5 / 7 5.4 / 7
Umesh Vazirani 5.3 / 7 5.2 / 7
Spring 1998 James W Demmel 5.2 / 7 4.8 / 7
Spring 1997 Umesh Vazirani 5.8 / 7 5.7 / 7
Fall 1996 Umesh Vazirani 4.7 / 7 4.4 / 7
Spring 1996 David Wolfe 5.6 / 7 5.3 / 7
Fall 1995 Umesh Vazirani 5.3 / 7 5.2 / 7
Fall 1995 Umesh Vazirani 4.8 / 7 4.8 / 7
Spring 1995 David Wolfe 6.0 / 7 5.6 / 7
Spring 1995 David Wolfe 5.6 / 7 5.0 / 7
Fall 1994 C. Kenyon 4.1 / 7 3.9 / 7
Fall 1994 C. Kenyon 4.8 / 7 4.5 / 7
Spring 1994 Manuel Blum 6.0 / 7 5.3 / 7
Spring 1994 Manuel Blum 6.0 / 7 5.3 / 7
Fall 1993 Abhiram Ranade 5.4 / 7 5.2 / 7
Fall 1993 Abhiram Ranade 5.2 / 7 5.6 / 7
Spring 1993 Manuel Blum 6.1 / 7 5.6 / 7
Spring 1993 Manuel Blum 5.6 / 7 5.0 / 7
Fall 1992 Abhiram Ranade 4.7 / 7 4.4 / 7
Fall 1992 Abhiram Ranade 5.0 / 7 5.0 / 7
Spring 1992 Raimund Seidel 5.0 / 7 4.6 / 7
Spring 1992 Raimund Seidel 5.5 / 7 4.8 / 7
Fall 1991 John Canny 4.5 / 7 4.3 / 7
Fall 1991 John Canny 3.9 / 7 3.9 / 7
Spring 1991 John Canny 4.2 / 7 4.0 / 7
Spring 1991 John Canny 4.0 / 7 3.6 / 7
Fall 1990 A. Gill 4.5 / 7 4.3 / 7
Spring 1990 Raimund Seidel 3.7 / 7 3.7 / 7
Spring 1990 Raimund Seidel 3.4 / 7 4.2 / 7
Fall 1989 Manuel Blum 6.2 / 7 5.5 / 7
Spring 1989 Richard M. Karp 5.9 / 7 5.3 / 7
Fall 1988 A. Gill 5.1 / 7 4.7 / 7
Fall 1988 A. Gill 4.7 / 7 4.9 / 7
Overall Rating Teaching Effectiveness How worthwhile was this course?
[Email HKN about this data] [Info about this page]