Lectures

Lectures 1-20 Class 1: Introduction (Notes) What is Computer Science?    Euclid, Ada and Bill Why Computer Science is Not Engineering    The Apollo Guidance Computer Recursive Definitions and antifloccipoccinihilipilification Class 2: Formal Systems and Languages (Notes) Course Expectations, Drinking from the Firehose Formal Systems 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 (Notes) Language Elements Why don't we program computers using English? Rules of Evaluation Class 4: Evaluation (Notes) Evaluation Compose Problem Set 1 Class 5: Recursing Recursively (GEB Chapter V) (Notes) Recursive Procedures Fibonacci RTNs and BNFs Music and Recursion Class 6: Cons car cdr sdr wdr (Notes) Recursion Practice (fast-fibo) Introducing Lists Class 7: List Recursion (Notes) Class 8: Recursion Practice (Notes) Class 9: Strange Loops (Do be do be) (Notes) Class 10: Cracker Barrel Puzzle (Notes, no slides) Class 11: Pegboard Puzzle (Notes) Class 12: On Grounds Sorting (Notes Only) Class 13: Of On and Off Grounds Sorting (Notes) Measuring Work Sorting Class 16: Quicker Sorting (Notes) Understanding Θ InsertSort Class 17: Mutation (Notes) Mutation Primitives Programming with Mutation PS5 Class 18: Think Globally, Mutate Locally (Notes) Environments New Evaluation Rules Class 19: Golden Ages and Astrophysics Orders of Growth Knowledge of the Universe Cracker Barrel Complexity Tractable and Intractable Problems Class 20: Quick Sorting (Notes) Divide and Conquer (Evenly) Trees

Lectures 21-40 Class 21: The Story So Far (Notes) Class 22: Objects (Notes) Class 23: Inheritance (Notes) Class 24: Gödel's Theorem (Notes, Quiz) Class 25: Computability (Notes) Quiz Answers Computability Halting Problem Class 26: Halting Problem 1 (Notes) Class 27: Halting Problem 2 (Notes) Halting Problem Proving Non-Computability Modeling Computation (Intro) Class 28: Networks, The Internet, and the World Wide Web (Notes) Class 29: Building Dynamic Web Sites (Notes) Class 30: Modeling Computation (Notes) Class 31: Universal Turing Machines and Lambda Calculus (Notes) Class 32: Meaning of Truth (Notes) Class 33: Learning to Count (Notes continued from Class 32) Class 34: Exam Review (no slides or notes) Class 35: Cookie Monsters and Semi-Secure Websites (Notes) Class 36: Public-Key Cryptography (Notes) Class 37: P = NP? (Notes) Permute Sort Problems and Procedures Nondeterministic Computing Complexity Classes P and NP Class 38: Intractable Problems (Smiley Puzzles and Curing Cancer) (Notes) Class 39: Meaning of Life (Notes) Class 40: Project Presentations (Notes)