Foundations of Computer Science

PDF version of this text.

This document was built on May 21, 2023.

Algorithms

• Introduction
  • Text Objectives
  • Tools for Abstraction
  • The First Algorithm
• 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
  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • All-Pairs Shortest Path
• Greedy Algorithms

Computability

• Introduction to Computability
  • Formal Languages
  • Overview of Automata
• Finite Automata
  • Formal Definition
• Turing Machines
  • Equivalent Models
  • The Language of a Turing Machine
  • Proving a Language is Decidable
• Diagonalization
  • Countable Sets
  • Uncountable Sets
  • The Existence of an Undecidable Language
• The Halting Problem
• Reducibility
  • Wang Tiling
• Recognizability
  • Dovetailing
• Rice’s Theorem
  • Rice’s Theorem and Program Analysis

Complexity

• Introduction to Complexity
  • Efficiently Verifiable Languages
  • P Versus NP
• The Cook-Levin Theorem
  • Starting Configuration
  • Cell Consistency
  • Accepting Configuration
  • Transitions
  • Conclusion
• NP-Completeness
  • 3SAT
  • Clique
  • Vertex Cover
  • Set Cover
  • Hamiltonian Cycle
  • Subset Sum
  • Concluding Remarks
• Search and Approximation
  • Approximation for Minimal Vertex Cover
  • Maximal 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.3 of the text.

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

Please report bugs and other issues here.

Index

• Index