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 Essential Computer Mathematics, while NTO stands for The New Turing Omnibus. The abbreviation of the book is followed by a colon and a chapter number. For example, ``NTO:22'' refers to chapter 22 of The New Turing Omnibus. Occasionally the chapter number is followed by a period and a section number. For example, ``ECM:14.1'' refers to section 1 of chapter 14 of Essential Computer Mathematics. An asterisk preceding a reading, such as [NTO:*13], means that the chapter contains some difficult material and you are not expected to read it completely and in detail.

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