Foundations of Computer Science
0.5

Algorithms

  • Introduction
    • Text Objectives
    • Tools for Abstraction
    • The First Algorithm: Euclid’s GCD
  • The Potential Method
    • A Potential Function for Euclid’s Algorithm
  • Divide and Conquer
    • The Master Theorem
      • Master Theorem with Log Factors
    • Integer Multiplication
      • The Karatsuba Algorithm
    • The Closest-Pair Problem
  • Dynamic Programming
    • Implementation Strategies
    • Weighted Task Selection
    • Longest Increasing Subsequence
    • Longest Common Subsequence
    • All-Pairs Shortest Paths
  • Greedy Algorithms

Computability

  • Introduction to Computability
    • Formal Languages
    • Overview of Automata
  • Finite Automata
    • Formal Definition
  • Turing Machines
    • The Language of a Turing Machine
    • Decidable Languages
    • Equivalent Models
  • Diagonalization
    • Countable Sets
    • Uncountable Sets
    • The Existence of an Undecidable Language
  • “Natural” Undecidable Problems
    • Code as Input
    • The Barber Language
    • The Acceptance Language and Simulation
    • The Halting Problem
  • Turing Reductions
    • The Halts-on-Empty Problem
    • More Undecidable Languages and Turing Reductions
    • Wang Tiling
  • Recognizability
    • Unrecognizable Languages
    • Dovetailing
  • Rice’s Theorem
    • Rice’s Theorem and Program Analysis

Complexity

  • Introduction to Complexity
    • Polynomial Time and the Class \(\P\)
    • Examples of Efficient Verification
    • Efficient Verifiers and the Class \(\NP\)
      • Discussion of Completeness and Soundness
      • Discussion of Efficiency
      • The Class \(\NP\)
    • P Versus NP
  • Satisfiability and the Cook-Levin Theorem
  • Proof of the Cook-Levin Theorem
    • Configurations and Tableaus
    • Constructing the Formula
      • Cell Consistency
      • Accepting Tableau
      • Starting Configuration
      • Transitions
    • Conclusion
  • \(\NP\)-Completeness
    • Polynomial-Time Mapping Reductions
    • \(\NP\)-Hardness and \(\NP\)-Completeness
    • Resolving \(\P\) versus \(\NP\)
  • More \(\NP\)-Complete Problems
    • 3SAT
    • Clique
    • Vertex Cover
    • Set Cover
    • Hamiltonian Cycle
    • Concluding Remarks
  • Search Problems and Search-to-Decision Reductions
  • Approximation Algorithms
    • Minimum Vertex Cover
    • Maximum Cut
    • Knapsack
    • Other Approaches to NP-Hard Problems

Randomness

  • Randomized Algorithms
    • Review of Probability
      • Probability Spaces and Events
      • Random Variables
      • Expectation
      • Analyzing Rock-Paper-Scissors
    • Randomized Approximation Algorithms
    • Quick Sort
    • Skip Lists
  • Monte Carlo Methods and Concentration Bounds
    • Variance and Chebyshev’s Inequality
    • Hoeffding’s Inequality
    • Polling
      • Analysis with Hoeffding’s Inequality
    • Load Balancing

Cryptography

  • Introduction to Cryptography
    • Review of Modular Arithmetic
      • Fast Modular Exponentiation
      • Division and Modular Inverses
    • One-time Pad
  • Diffie-Hellman Key Exchange
  • RSA
    • RSA Signatures
    • Quantum Computers and Cryptography

Supplemental Material

  • Supplemental: Algorithms
    • Non-master-theorem Recurrences
  • Supplemental: Computability
    • Applying Rice’s Theorem
    • Computable Functions and Kolmogorov Complexity
  • Supplemental: Randomness
    • Primality Testing
      • The Miller-Rabin Test
    • Multiplicative Chernoff Bounds
      • Polling Analysis with Chernoff Bounds
    • Probabilistic Complexity Classes
    • Amplification for Two-Sided-Error Algorithms

Appendix

  • Appendix
    • Proof of the Master Theorem
    • Alternative Analysis of Quick Sort
    • Proof of the Simplified Multiplicative Chernoff Bounds
    • Proof of the Upper-Tail Hoeffding’s Inequality
    • General Case of Hoeffding’s Inequality

Index

  • Index
Foundations of Computer Science
  • Search

© Copyright 2020-2024, Amir Kamil and Chris Peikert, licensed under the Creative Commons Attribution-ShareAlike 4.0 International license.

Built with Sphinx using a theme provided by Read the Docs.