How To Design Programs: summary (PR)

• [square brackets enclose selected applications]
• I. Processing Simple Forms of Data
  • 1. Introduction
  • 2. Numbers, arithmetic, (+ 5 5) syntax, variables, 'programs' (i.e. functions), define syntax, defining constants, design recipe (problem analysis and data definition, contract, examples, function template, function header, tests)
  • 3. Composing (i.e. designing) functions
  • 4. Conditional expressions, comparisons, true, false, and, or, cond
  • 5. Symbols and quotation (quote not used)
  • 6. Structures: define-struct, constructors, selectors, "box representation", data definitions [moving rectangles and circles, hangman]
  • 7. Type predicates (e.g. boolean?), functions for mixed data [moving shape], checked functions, errors (can do assert here?)
• Intermezzo 1: Syntax and Semantics
  • 8. Scheme vocabulary and grammar (beginning student language)
• II. Processing Arbitrary Large Data
  • 9. Lists, cons, first, rest (i.e. car, cdr), recursive definition of list, processing lists of arbitrary length, designing functions for recursive definitions
  • 10. Functions that produce lists, lists that contain structures
  • 11. Recursive definition of natural numbers, functions on natural numbers (e.g. factorial)
  • 12. Composing recursive functions, auxiliary recursive functions
• Intermezzo 2: List Abbreviations
  • 13. list syntax, quoted lists
• III. More On Processing Arbitrarily Large Data
  • 14. Multi-clausal recursive data definitions [ancestral family trees, binary search trees, "Web pages", simple Scheme evaluator]
  • 15. Mutually referential data definitions [descendant family trees]
  • 16. Iterative refinement [file systems]
  • 17. Processing two complex pieces of data [merging, evaluating polynomials, prefix-checking, equality of lists]
• Intermezzo 3: Local Definitions and Lexical Scope
  • 18. local, encapsulation, block structure, binding
• IV: Abstracting Design
  • 19. Functional abstraction, filters, polymorphism, generic functions, parametric data definitions
  • 20. Functions as data
  • 21. Designing abstractions from examples, "single point of control" [moving pictures revisited]
  • 22. Functions that produce functions [graphical user interface]
  • 23. Mathematical examples [sequences and series (arithmetic, geometric, Taylor), numerical integration and differentiation]
• Intermezzo 4: Defining Functions On The Fly
  • 24. local + define = lambda
• V. Generative Recursion
  • 25. Generative versus structural recursion [moving ball on table, quicksort]
  • 26. Designing algorithms: termination, infinite loops [GCD two ways]
  • 27. Examples [fractals: Sierpinski triangle and Bezier curve, breaking files into lines, binary search for roots, Newton's method, Gaussian elimination]
  • 28. Backtracking algorithms [reachability in directed graphs, eight queens]
• Intermezzo 5: The Cost of Computing, and Vectors
  • 29. "on the order of", O-notation (as set), vectors (access to middle of list in constant time)
• VI. Accumulating Knowledge
  • 30. Naive structural renormalizing list is n^2 algorithm, naive generative connectivity does not terminate
  • 31. Designing accumulator-style functions, invariants [height of binary trees]
  • 32. Examples [all ancestors, missionaries and cannibals, peg solitaire]
• Intermezzo 6: The Nature of Inexact Numbers
  • 33. Floating point
• VII: Changing The State of Variables
  • 34. Need for memory
  • 35. Assignment to variables, set!, begin expressions [swap, address book]
  • 36. Designing functions with memory, initializers
  • 37. Examples [guessing colours, hangman], state changes from recursion [maze games]
• Intermezzo 7: The Final Syntax and Semantics
  • 38. Grammar and vocabulary, semantics of set! with respect to lambda
• VIII: Changing Compound Values
  • 39. Encapsulation [multiple traffic lights], service managers
  • 40. Mutable structures, mutable functional structures, mutators, mutable vectors
  • 41. Designing functions that change structures, structural design recipes and mutation [hands of cards]
  • 42. Equality: intensional versus extensional
  • 43. Small projects [insertion sort, quicksort, constructing graph representations, reachability, backtracking]