University of Virginia Computer Science
CS150: Computer Science, Fall 2005


Lecture slides are available as either the original PowerPoint slides (download the PPT link) or PDF for printing (6 slides per page).

Class 1: Introduction [PPT, PDF] (Notes)
What is Computer Science?
   Euclid, Ada and Bill
Why Computer Science is Not Engineering
   The Apollo Guidance Computer
Course Expectations, Drinking from the Firehose
Class 2: Formal Systems and Languages [PPT, PDF] (Notes)
Formal Systems
Recursive Definitions and antifloccipoccinihilipilification
What are languages made of?
History of Computer Programming
   Admiral Grace Hopper, John Backus
Describing Languages
   Backus-Naur Form
Class 3: Rules of Evaluation [PPT, PDF] (Notes)
Language Elements
Why don't we program computers using English?
Rules of Evaluation
Class 4: Programming with Data [PPT, PDF] (slides not used in class) (Notes)
Making data
cons, car, cdr
Making lists
Class 5: Recursing on Lists [PPT, PDF] (Notes)
Making cons, car, and cdr
Problem Set 1
   Procedural Abstraction
List Procedures
Class 6: List Recursion (Notes only)
length, sumlist, map

Class 7: Recursion Practice (Notes only)

How to define recursive procedures
remove insertl

Class 8: Recursing Recursivey [PPT, PDF] (Notes)

Recursive Procedures
RTNs and BNFs
Music and Recursion

Class 9: On On and Off Grounds Sorting [PPT, PDF] (Notes)

PS2: Data Abstraction
Measuring Work Intro
Simple Sorting
Class 10: Quicker Sorting [PPT, PDF] (Notes)
Measuring Work: Theta Notation
Insertion Sort
Class 11: Golden Ages, Orders of Growth, and Astrophysics [PPT, PDF] (Notes)
Simulating the Universe
Insert Sort with Halves
Endless Golden Ages
Class 12: Quickest Sorting [PPT, PDF] (Notes)
Binary Trees
Inserting in Trees
Sorting using Trees
Class 13: Problems [PPT, PDF] (Notes)
Problems and Procedures
Permute Sort
Proving lower and upper bounds on a problem
Sorting problem is Θ(n log n)
Class 14: Intractable Problems [PPT, PDF] (Notes)
Smileys Puzzle
Class P and NP
Reduction Proofs
Class 15: P vs. NP (Smiley Puzzles and Curing Cancer) [PPT, PDF]
Smileys Problem
Complexity Classes
Class 16: NP-Completeness [PPT, PDF]
Complexity Classes
Problem Reductions
Story so Far (Where we've been, where we're going)
NP Complete Problems
Class 17: Sex, Religion, and Politics [PPT, PDF]
PS4, Question 1f
Malthus and Orders of Growth
Breaking Fish
Class 18: Mutation (slides lost)

Class 19: Environments [PPT, PDF] (Notes)

Class 20: Objects [PPT, PDF] (Notes) (These slides were not actually used in class)

Class 21: Purpose of College (No slides or notes)

Class 22: Inheritance [PPT, PDF] (Notes)

Class 23: Gödel's Theorem [PPT, PDF] (Notes)

PS5, PS6
Introduction to Computability
Axiomatic Systems and Incompleteness
Class 24: Computability [PPT, PDF] (Notes)
Proofs and Proof Checking
Halting Problem
Class 25: Undecidable Problems [PPT, PDF] (Notes)
Proving Undecidability
Virus Detection
Class 26: Modeling Computing [PPT, PDF] (Notes)
Modeling Computing
Finite State Machine
Turing Machine
Class 27: Universal Turing Machines [PPT, PDF] (Notes)
Describing Turing Machines
Universal Turing Machines
Church-Turing Thesis
Lambda Calculus
Class 28: The Meaning of Truth [PPT, PDF] (Notes)
Lambda Calculus
Beta Reduction
Making True, False, and if
Class 29: Trick-or-Treat Protocols [PPT, PDF] (Notes)
Bandwidth and Latency
Class 30: Vocational Skills [PPT, PDF] (Notes)
Who Invented the Internet? vs.
Building Dynamic Web Applications
Class 31: Cookie Monsters and Semi-Secure Websites [PPT, PDF] (Notes) (These slides were not used because we had class outside.)

Class 32: Computability in Theory and Practice [PPT, PDF] (Notes)

Making Numbers
Ali G Problem
Class 33: Computing with Photons [PPT, PDF] (Notes)
Church-Turing Thesis
Quantum Computing
Class 34: Computing with Life, Life Computing [PPT, PDF]
DNA Computers
Viruses and Immune Systems
Class 35: Decoding DNA [PPT, PDF] (Notes)
Human Genome Project
Genome Assembly Problem
Class 36: Public-Key Cryptography [PPT, PDF] (Notes)
Key Distribution Problem
Asymmetric Cryptosystems
PKI, Certificates
Class 37: How to Find Aliens [PPT, PDF] (Notes)
Distributed Computing
Race Conditions and Deadlocks
Class 38: Googling Google [PPT, PDF] (Notes)
Crawling the Web
Hash Searching

"); print ( $res[$first] ) ; print (""); ?>
CS 150: Computer Science
University of Virginia
Using these Materials