Foundations of Computer Science

PDF version of this text.

This document was built on Jan 23, 2021.

Algorithms

• Introduction
  • Course Objectives
  • Tools for Abstraction
  • The First Algorithm
• The Potential Method
  • A Potential Function for Euclid’s Algorithm
• Divide and Conquer
  • The Master Theorem
    • 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
  • Turing Machines
  • The Language of a Turing Machine
• 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
  • 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
  • Skip Lists
  • Quick Sort
• Probabilistic Complexity Classes
• Monte Carlo Methods and Chernoff Bounds
  • Chernoff Bounds
  • Polling
  • Amplification for Two-Sided-Error Algorithms
  • Load Balancing

Cryptography

• Introduction to Cryptography
• Diffie-Hellman Key Exchange
• RSA
  • RSA Signatures
  • Quantum Computers and Cryptography

Appendix

• Appendix
  • Proof of the Upper-Tail Chernoff Bound
  • 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.1-alpha of the text.

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

Index

• Index