Lectures

Classes 1-13 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 Drinking from the Firehose Class 2: Formal Systems and Languages (Notes) Survey Results 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: Recursive Definitions (Notes) Defining Recursive Procedures Fibonacci Problem Set 1 Answers Problem Set 2 Class 5: Recursing Recursively (GEB Chapter V) (Notes) Fibonacci Continued RTNs and BNFs Music and Recursion Class 6 and 7: Cracking the Cracker Barrel (Notes only) Class 8: Cons car cdr sdr wdr (Notes) History of Scheme (Lots of Insipid Silly Parentheses) From Pairs to Lists Recursive Procedures on Lists Class 9: The Great Lambda Tree of Knowledge and Power (Notes) Programming with Lists Lindenmayer Systems and PS 3 Class 10: Barista Assista (Notes only) Programing with Lists Practice Class 11: Sorting Grounds and Bubbles (Notes) Find Most Sorting Class 12: Decrypting Work, Working on Decrypting (Notes) How do computer scientists measure work? Θ(n2) Insertion Sort PS4: Cryptology Class 13: Quickersorting (Notes) Insertsort in halves Trees Quicksort

Classes 14-25 Class 14: Tim Koogle's visit (no slides or notes) Class 15: Goalden Ages and Astrophysics (Notes) Simulating the Universe Problems that are more work than simulating the Universe Goalden Ages and Grade Inflation Liberal Arts Returns Class 16: Mutation (Notes) Mutation Primitives Differences between Functional and Imperative Programming Advantages and Disadvantages of Mutation Problem Set 5 Class 17: Environments (Notes) Environments Evaluation Rules Exam 1 Class 18: Gödel's Theorem (Notes) Mechanizing Reasoning Gödel's Theorem Class 19: Computability (Notes) Proofs in Axiomatic Systems Undecidable Problems The Halting Problem Class 20: Objects (Notes) Packaging State and Procedures Object-Oriented Programming Class 21: Inheritance (Notes) Programming with Objects Inheritance Problem Set 5 Problem Set 6 Class 22: P = NP? (Notes) Permute Sort O, Θ, and Ω Problems and Procedures Complexity Classes P and NP Class 23: NP Completeness (Notes) Smileys Puzzle 3SAT NP-complete Problems Class 24: Metalinguistics (Notes) Problem Classification Summary Computability in Theory and Practice (Ali G) Quantum Mechanics for Dummies Metalinguistic Abstraction Class 25: The Metacircular Evaluator (Notes) Slides available, but not used.

Classes 26-37 Class 26: In Praise of Idleness (Notes) Implementing Environments Lazy Evaluation Class 27: Types of Types (Notes) Types Type Checking Mini-Scheme Class 28: Networks, The Internet and the World Wide Web (Notes) Brief History of Networking Latency and Bandwidth Class 29: How to Build a Dynamic Web Site (Notes) Dynamic Web Sites HTML, PHP and SQL Class 30: Modeling Computation (Notes) Modeling Computation Finite State Machines Turing Machines Class 31: Universal Turing Machines and Lambda Calculus (Notes) Universal Turing Machine Lambda Calculus Substitution and Reduction Church-Turing Thesis Class 32: The Meaning of Truth (Notes) Lambda Calculus Review Proving Lambda Calculus is equivalent to a Turing Machine Making Primitives out of Nothing but Glue The Meaning of Truth Making Numbers and Lists Class 33: Making Recursion (Notes) Lambda Calculus Review Fixed Points Y Operator Class 34: Exam Review (no slides or notes) Class 35: Cookie Monsters and Semi-Secure Websites (Notes) Authentication Passwords Cookies Class 36: Public-Key Cryptography (Notes) Asymmetric Cryptosystems RSA Certificates SSL Class 37: Secret of Life (Notes) 50th Anniversary DNA and Computing Computing with DNA

	CS 200: Computer Science Department of Computer Science University of Virginia	cs200-staff@cs.virginia.edu Using these Materials