COMP 200 Elements of Computer Science Fall 2004 Lecture Notes & Handouts

This page contains the lecture notes that I use as a guide to each day's class. It also includes pdf copies of any handouts given in class (except, of course, exams). If you discover that some are either missing or not accessible, please contact me directly.

The primary purpose of the lecture notes is to provide a record of the material covered in class. They are not a definitive record of class. Instead, they are the actual notes that I use to guide the lecture.

1. Introductory lecture
   General Information Handout
2. Algorithms versus Problems
   Recipe Slides from Lecture 2
3. Expressing Algorithms
   
   
4. Formalizing Pizza Arithmetic into Scheme
5. Methodology of Programming, part I
   Installing Dr. Scheme on the Mac
6. Finish Conditionals, On to the Matter of Names,
   Digression on Spreadsheets
   Scheme code for FirstClassMail
   Scheme code for Abvalue
   
   
7. Introduction to Structures in Scheme,
   includes an additional example, not given in class
8. More Work with Structures and a brief attempt to relate Scheme programming to Chapter 2
   Scheme code for LineLength
   
   
9. Programming with Lists
   Solution to Homework 2
10. More Work with Lists
    Material above this line may appear on the first exam

    ---

    
    
11. Reconnecting with the Book, material from Chapter 2
12. Abstraction and Data Structures
    with a quick review of built-in list constructs (See also Homework 3)
13. More abstractions: trees & graphs
    
    
14. Recursion over the counting numbers
    Solution to Homework 3
15. Introduction to Search: Traversing Binary Trees
16. Divide & Conquer as an Algorithmic Strategy
    
    
17. Finishing Divide & Conquer, Starting Greedy Algorithms
    Driving Problem, Scheme for MergeSort (v1), and Scheme for MergeSort (v2)
18. More Greedy Algorithms
    Homework 4 is available.
19. Dynamic Planning
    
    
20. Introduction to Algorithmic Complexity
21. More on Algorithmic Complexity
22. Worst, Best, and Average Case Complexity
    
    
23. Upper & Lower Bounds, NP-Complete Problems
24. Biological Analogies in Computing
    Material above this line may appear on the second exam

    ---

25. Intelligence & the Turing Test
26. Review for Second Exam & Intro to Models of Computation
27. Friday, we spent most of the period talking about final projects.
    
    
28. Universal Turing Machines
29. Programs->Executions
30. From a Turing machine to a PC and the PowerPoint introduction
    
    
31. Introduction to Cryptography
32. Public-key cryptography
33. Deterministic Finite Automata
    
    
34. Regular Expressions and Context-Free Grammars
35. Wrap up and Review