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

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)

cs200-staff@cs.virginia.edu
Using these Materials