Tom Altman
University of Colorado at Denver
Department:
Computer Science and Engineering
Phone:
(303) 315-1401
E-mail:
Tom.Altman@ucdenver.edu
Home
CSCI-4172/5172: Computational Complexity and Problem Solving.
Syllabus
Reading Materials:
1.
Accidental Algorithms
2.
Black Hole Computers
3.
NP-Completeness A Retrospective
4.
The Status of the P Versus NP Problem
5.
Algebrization: A New Barrier in Complexity Theory
6.
An Algebraic View of Ambiguity in Context-free Grammars and Language Expressions
7.
Non-deterministic Exponential Time Has Two-prover Interactive Protocols
8.
Indexings of Subrecursive Classes
9.
On Determinism Versus Non-Determinism And Related Problems
10.
Oracles Are Subtle But Not Malicious
11.
Relativization Barriers and The Universality of Poly-time Turing Equivalence
12.
The Role of Relativization in Complexity Theory
13.
Essentials of Theoretical Computer Science
Sample Project Report:
1.
Report
2.
Presentation