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 120 What is Computer Science?Class 2: Formal Systems and Languages (Notes)
Euclid, Ada and Bill
Why Computer Science is Not Engineering
The Apollo Guidance Computer
Recursive Definitions and antifloccipoccinihilipilification
Course Expectations, Drinking from the FirehoseClass 3: Rules of Evaluation (Notes)
Formal Systems
What are languages made of?
History of Computer Programming
Admiral Grace Hopper, John Backus
Describing Languages
BackusNaur Form
SchemeLanguage ElementsClass 4: Evaluation (Notes)
Why don't we program computers using English?
Rules of Evaluation
EvaluationClass 5: Recursing Recursively (GEB Chapter V) (Notes)
Compose
Problem Set 1
Recursive ProceduresClass 6: Cons car cdr sdr wdr (Notes)
Fibonacci
RTNs and BNFs
Music and RecursionRecursion Practice (fastfibo)Class 7: List Recursion (Notes)
Introducing Lists
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 WorkClass 16: Quicker Sorting (Notes)
SortingUnderstanding ΘClass 17: Mutation (Notes)
InsertSortMutation PrimitivesClass 18: Think Globally, Mutate Locally (Notes)
Programming with Mutation
PS5EnvironmentsClass 19: Golden Ages and Astrophysics
New Evaluation RulesOrders of GrowthClass 20: Quick Sorting (Notes)
Knowledge of the Universe
Cracker Barrel Complexity
Tractable and Intractable ProblemsDivide and Conquer (Evenly)
Trees
Lectures 2140 Class 21: The Story So Far (Notes)
Class 22: Objects (Notes)Class 24: Gödel's Theorem (Notes, Quiz)
Class 25: Computability (Notes)
Quiz AnswersClass 26: Halting Problem 1 (Notes)
Computability
Halting ProblemClass 27: Halting Problem 2 (Notes)
Halting Problem
Proving NonComputability
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 SemiSecure Websites (Notes)
Class 36: PublicKey Cryptography (Notes)
Permute SortClass 38: Intractable Problems (Smiley Puzzles and Curing Cancer) (Notes)
Problems and Procedures
Nondeterministic Computing
Complexity Classes P and NP
cs200staff@cs.virginia.edu Using these Materials 