Theory of Computation (V-U)

A definition of Information, Incompressible Strings (V-U)

An Approximation Algorithm for TSP Problem (V-U)

Big Oh and Little Oh Notations, Time Complexity (V-U)

Computable Functions (Cont.), Reducibility (V-U)

Reducibility (Cont.), Recursion Theorem (V-U)

Decidable Languages, The Acceptance Problem for DFAs (V-U)

Relationship between Space and Time Complexity, PSPACE-Completeness (V-U)

Designing Turing Machines (V-U)

Russell's Paradox, Emptiness Problem (V-U)

Enumerators, Dovetailing, The Church-Turing Thesis, Hilbert's Tenth Problem (V-U)

Satisfiability (Cont.) (V-U)

Generalized Geography (Cont.) (V-U)

Satisfiability (Cont.), 3-Color (V-U)

Hamiltonian Path Problem (V-U)

Set Thoery, Sequences, Tuples, Functions, Relations and Graphs (V-U)

Incompressible Strings (Cont.), Complexity Theory (V-U)

Space Complexity (Cont.) (V-U)

Independent Sets (Cont.), NP-Completeness (Cont.), Clique, Vertex Cover (V-U)

Space Complexity (V-U)

Introduction (V-U)

Subset Sum Problem, Satisfiability (V-U)

Linear Bounded Automata, Computation Histories, Context Free Grammars (V-U)

The Class NP (Cont.) (V-U)

The Class NP (Cont.), Polynomial Time Verifiers (V-U)

Logical Theories (Cont.) (V-U)