CS 170. Introduction to CS Theory

Current Schedule (Fall 2016)


Catalog Description: (4 units) 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.

Prerequisites: CS 61B, Mathematics 55, CS 70

Course objectives: Provide familiarity with algorithms for recurring basic problems. Learn to design algorithms to solve novel problems. Learn about the concept of the intrinsic difficulty of certain computational problems.

Topics covered:

General Catalog