CS 200 Computer Science from Ada and Euclid to Quantum Computing and the World Wide Web Spring 2004 Schedule - Problem Sets - Exams - Lectures - Syllabus - Links

## Lectures

 Lectures 1-20 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 10: Cracker Barrel Puzzle (Notes, no slides) Class 12: On Grounds Sorting (Notes Only) 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 22: Objects (Notes) Quiz Answers Computability Halting Problem Class 26: Halting Problem 1 (Notes) Halting Problem Proving Non-Computability Modeling Computation (Intro) Class 33: Learning to Count (Notes continued from Class 32) Class 34: Exam Review (no slides or notes) Permute Sort Problems and Procedures Nondeterministic Computing Complexity Classes P and NP Class 38: Intractable Problems (Smiley Puzzles and Curing Cancer) (Notes)