Led by: Haseeb Qureshi, instructor at App Academy
######Topics:
- The Halting Problem
- What is computation?
- Turing Machines (picture)
- Asymptotic analysis, scalability, and Moore's Law (Big Oh)
- P, NP, and the Millenium Prize (picture)
- NP-hard and NP-complete
- Satisfiability (Cook's Theorem), Reductions
- Heuristics, parameterizations, and approximations
######List of NP-complete problems:
- Knapsack Problem
- 3-SAT (Boolean satisfiability)
- Vertex Cover
- Traveling Salesman
- Clique Problem
- Longest Common Subsequence (of arbitrarily many input sequences)
- Super Mario Bros
- Tetris