printer friendly pageCS 154: Introduction to Automata and Complexity Theory
This course provides a mathematical introduction to the following questions: What is computation? Given a computational model, what problems can we hope to solve in principle with this model? Besides those solvable in principle, what problems can we hope to efficiently solve? In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in computer science and mathematics. By the end of this course, students will be able to classify computational problems in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NP-complete? PSPACE-complete?, etc.). Students will gain a deeper appreciation for some of the fundamental issues in computing that are independent of trends of technology, such as the Church-Turing Thesis and the P versus NP problem. Prerequisites:
CS 103 or 103B.
Terms: Win
| Units: 3-4
| UG Reqs: GER:DB-EngrAppSci
CS 367: Algebraic Graph Algorithms
Due to the surprisingly fast algorithms for the problem, matrix multiplication is routinely used as a basic building block for algorithms beating the brute-force approach. This course explores matrix multiplication algorithms and a variety of problems, mostly within graph algorithms, that can be solved faster using a fast matrix multiplication algorithm. Topics include: Fast Matrix Multiplication, algebraic algorithms for Graph Transitive Closure, All Pairs Shortest Paths and variants of the problem, Perfect Matching and Minimum Cycle, and a variety of equivalences between problems involving matrix multiplication. Prerequisites:
CS154,
CS161, or the equivalent mathematical maturity.
Terms: Aut
| Units: 3
Instructors:
Williams, V. (PI)
;
Kim, A. (TA)
Filter Results: