Foundations of Computer Science

PDF version of this text.

This document was built on Mar 30, 2024. \(~\)

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
  • 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
  • Subset Sum
  • Concluding Remarks
• Search and Approximation
  • Approximation for Minimum Vertex Cover
  • Maximum Cut
  • Knapsack
  • Other Approaches to NP-Hard Problems

Randomness

• Randomized Algorithms
  • Review of Probability
  • Randomized Approximations
  • 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

About

This text was originally written for EECS 376, the Foundations of Computer Science course at the University of Michigan, by Amir Kamil in Fall 2020. This is version 0.4 of the text.

• Contributions: Chris Peikert, Thatchaphol Saranurak

This text is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license.

Please report bugs and other issues here.

Index

• Index