Foundations of Computer Science

PDF version of this text.

This document was built on Sep 12, 2022.

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
    • Non-master-theorem Recurrences
  • 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
• Computable Functions and Kolmogorov Complexity
• Rice’s Theorem
  • Applying 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
  • 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
  • Primality Testing
    • The Miller-Rabin Test
  • Skip Lists
  • Quick Sort
• Probabilistic Complexity Classes
• Monte Carlo Methods and Concentration Bounds
  • Chernoff Bounds
  • Hoeffding’s Inequality
  • Polling
    • Analysis with Chernoff Bounds
    • Analysis with Hoeffding’s Inequality
  • Amplification for Two-Sided-Error Algorithms
  • Load Balancing

Cryptography

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

Appendix

• Appendix
  • Proof of the Simplified 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