**ICS 1F -- What Can We Compute?
Winter Quarter, 1998
Course Outline and Relevant Reading**

Instructor: David Eppstein, CS 358D, 824-6384, eppstein@ics.uci.edu. Course work will consist of weekly homeworks, a midterm, and a comprehensive final exam. Group work on homeworks is not permitted.

Readings in the texts are indicated in brackets after the lecture topic
to which they correspond. ECM stands for

This outline is not absolutely firm. Some changes may be made as the quarter progresses.

- Week I: Introduction
- Symbolic vs. numeric computation
- What is an algorithm? [NTO:1]
- Examples of problems to be considered

- Weeks II-III: Some useful mathematics
- Binary vs. decimal representation of numbers [ECM:1.1-1.4]
- Sets [ECM:6]
- Boolean algebra [ECM:4, NTO:3, NTO:*13]
- Homework 1 due Friday January 16 --
Solutions
- Strings, languages, and the existence of undecidable languages
- Quantifiers and boolean logic
- Boolean circuits
- Homework 2 due Wednesday January 28 -- Solutions

- Weeks IV-V: A simple model of computation (finite state machines)
- Directed graphs [ECM:14.9 and *14.10]
- States and transitions [ECM:*14.11, *14.12, 14.13, NTO:2]
- Final states and acceptance
- Homework 3 due Wednesday February 4 --
Solutions
- Regular languages [NTO:14]
- Intersection, union, and complementation of regular languages
- Nondeterministic finite state machines [NTO:26]
- Languages that are not regular
- Midterm, Monday February 9 -- Solutions

- Weeks VI-VIII: More powerful models of computation
- Church's thesis [NTO:*66]
- Turing machines [NTO:*31]
- Homework 4 due Wednesday February 25 --
Solutions
- Universal turing machines [NTO:*51]
- Cellular automata [NTO:*44]
- Random access machines [NTO:*17]
- Some undecidable problems [NTO:*39, *59]
- Homework 5 due Friday March 6 -- Solutions

- Week IX: Time complexity and efficient algorithms
- Growth rates and their implications
- Polynomial and nondeterministic polynomial time
- Polynomial transformability
- Cook's theorem
- Implications of NP-completeness
- Homework 6 due Friday March 13 -- Solutions

- Week X: Recent developments
- Quantum computation
- DNA-based computation

David Eppstein, Dept. Information & Computer Science, UC Irvine, .