Theory Resources

CSE Home

About Us

Search

Contact Info

This page is devoted to providing computation and complexity resources to students in CSE theory courses. Links are provided when they are available. Some of the web sites have restricted access (to U.W. IP addresses).

• Library Resources
  • University of Washington Library
  • INSPEC - Extensive database for computer science, EE, and other science and engineering fields. Restricted access. Can be accessed from a U.W. account.
  • ACM Digital Library
  • MathSciNet - Mathematical Reviews on the Web sponsored by the American Mathematical Society. Restricted access. Can be accessed from a U.W. account.
  • MATH - MATH Database 1931-1999 a service of the European Mathematical Society.
  • U.W. library internet resources for CS (various resources that U.W. pays for us to use)
  • ResearchIndex (web crawler that indexes academic papers)
• Journals
  • Information and Computation (Requires cookies!)
  • Journal of Computer and System Sciences (Requires cookies!)
  • Information Processing Letters
  • SIAM Journal on Computing
  • Journal of the ACM
• Books
  • Garey & Johnson, Computers and Intractability, W.H. Freeman, 1979.
    A discussion on NP-completeness with tips on how to find proofs and what to do about the problems. Also contains a list of about 300 NP-complete (and some PSPACE-complete) problems.
  • Papadimitriou, Christos H, Computational complexity, Addison-Wesley, 1994.
  • Hopcroft, Motwani, and Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, 2000.
• Conference Series on Algorithms
  • ACM Symposium on Theory of Computing (STOC)
  • IEEE Computational Complexity conference (formerly Structure in Complexity Theory)
  • Foundations of Computer Science (FOCS)
  • Symposium on Theoretical Aspects of Computer Science (STACS)
• Other Interesting Sites
  • U.W. page on the Steam-Powered Turing Machine or check the east stairwell in Sieg between the 2nd and 3rd floors.
  • Turing Machine Simulator - program a Turing machine. (Java applet)
  • An online list of NP-optimization problems (the focus here is on approximation algorithms and complexity classes relating to approximability)
  • A list of the putative greats in CS theory: The Theory of Computing Hall of Fame.
  • Sequitur home page. Sequitur is a data compression technique based on finding a small context-free grammar that generates the string to be compressed.
  • Stephen Wolfram's new book A New Kind of Science is based on cellular automata.

	Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to ladner]