Classes

Class 1: Introduction [PPT, PDF] (Notes) What is Computer Science?    Euclid, Ada and Bill Why Computer Science is Not Engineering    The Apollo Guidance Computer Course Expectations, Drinking from the Firehose Class 2: Formal Systems and Languages [PPT, PDF] (Notes) Formal Systems Recursive Definitions and antifloccipoccinihilipilification What are languages made of? History of Computer Programming    Admiral Grace Hopper, John Backus Describing Languages    Backus-Naur Form Scheme Class 3: Rules of Evaluation [PPT, PDF] (Notes) Language Elements Why don't we program computers using English? Rules of Evaluation Class 4: Programming with Data [PPT, PDF] (slides not used in class) (Notes) Making data cons, car, cdr Making lists Class 5: Recursing on Lists [PPT, PDF] (Notes) Making cons, car, and cdr Problem Set 1    Procedural Abstraction List Procedures Class 6: List Recursion (Notes only) length, sumlist, map Class 7: Recursion Practice (Notes only) How to define recursive procedures remove insertl Class 8: Recursing Recursivey [PPT, PDF] (Notes) Recursive Procedures Fibonacci RTNs and BNFs Music and Recursion Class 9: On On and Off Grounds Sorting [PPT, PDF] (Notes) PS2: Data Abstraction Measuring Work Intro Simple Sorting Class 10: Quicker Sorting [PPT, PDF] (Notes) Measuring Work: Theta Notation Insertion Sort Class 11: Golden Ages, Orders of Growth, and Astrophysics [PPT, PDF] (Notes) Simulating the Universe Insert Sort with Halves Endless Golden Ages Class 12: Quickest Sorting [PPT, PDF] (Notes) Binary Trees Inserting in Trees Sorting using Trees Class 13: Problems [PPT, PDF] (Notes) Problems and Procedures Permute Sort Proving lower and upper bounds on a problem Sorting problem is Θ(n log n) Class 14: Intractable Problems [PPT, PDF] (Notes) Smileys Puzzle Class P and NP Reduction Proofs Class 15: P vs. NP (Smiley Puzzles and Curing Cancer) [PPT, PDF] Smileys Problem Complexity Classes 3SAT Class 16: NP-Completeness [PPT, PDF] Complexity Classes Problem Reductions Story so Far (Where we've been, where we're going) NP Complete Problems

Class 17: Sex, Religion, and Politics [PPT, PDF] PS4, Question 1f Malthus and Orders of Growth Breaking Fish Class 18: Mutation (slides lost) Class 19: Environments [PPT, PDF] (Notes) Class 20: Objects [PPT, PDF] (Notes) (These slides were not actually used in class) Class 21: Purpose of College (No slides or notes) Class 22: Inheritance [PPT, PDF] (Notes) Class 23: Gödel's Theorem [PPT, PDF] (Notes) PS5, PS6 Introduction to Computability Axiomatic Systems and Incompleteness Class 24: Computability [PPT, PDF] (Notes) Proofs and Proof Checking Computability Halting Problem Class 25: Undecidable Problems [PPT, PDF] (Notes) Proving Undecidability Virus Detection Class 26: Modeling Computing [PPT, PDF] (Notes) Modeling Computing Finite State Machine Turing Machine Class 27: Universal Turing Machines [PPT, PDF] (Notes) Describing Turing Machines Universal Turing Machines Church-Turing Thesis Lambda Calculus Class 28: The Meaning of Truth [PPT, PDF] (Notes) Lambda Calculus Beta Reduction Making True, False, and if Class 29: Trick-or-Treat Protocols [PPT, PDF] (Notes) Networking Bandwidth and Latency Trick-or-Treat Class 30: Vocational Skills [PPT, PDF] (Notes) Who Invented the Internet? twinkiesproject.com vs. ebay.com Building Dynamic Web Applications Class 31: Cookie Monsters and Semi-Secure Websites [PPT, PDF] (Notes) (These slides were not used because we had class outside.) Class 32: Computability in Theory and Practice [PPT, PDF] (Notes) Making Numbers Ali G Problem Class 33: Computing with Photons [PPT, PDF] (Notes) Church-Turing Thesis Quantum Computing Class 34: Computing with Life, Life Computing [PPT, PDF] DNA Computers Viruses and Immune Systems Class 35: Decoding DNA [PPT, PDF] (Notes) Human Genome Project Genome Assembly Problem Class 36: Public-Key Cryptography [PPT, PDF] (Notes) Key Distribution Problem Asymmetric Cryptosystems PKI, Certificates Class 37: How to Find Aliens [PPT, PDF] (Notes) Distributed Computing Race Conditions and Deadlocks Class 38: Googling Google [PPT, PDF] (Notes) Crawling the Web Hash Searching PageRank