0368.1105 Extended Introduction to Computer Science

Course outline

This list may be updated as the course progresses.
Section numbers mentioned are from SICP2, and when included without comment they were covered in full, except for exercises. Material not covered in the book is marked with a (*).
  1. Sun Oct 29 :
    Introduction to the course and its requirements.
    Expressions (1.1.1).
    Naming and environment (1.1.2).
    Evaluating combinations (1.1.3).
    Compound procedures (1.1.4).
    Constructing procedures using lambda (without let) (1.3.2) - briefly.

  2. Thu Nov 2 :
    Substitution model for procedure evaluation (1.1.5) - Conditional expressions and predicates (1.1.6) - only if Example: Square roots by Newton's method (1.1.7).
    Procedures as black-box abstractions (1.1.8).

  3. Sun Nov 5 :
    Internal definitions and block structure (1.1.8).
    Substitution model revisited : Applicative and normal order (1.1.5) Linear recursion and iteration (1.2.1).
    Exponentiation (the simple case) (1.2.4).
    Orders of growth (both big Oh and theta) (1.2.3).

  4. Thu Nov 9 :
    cond special form.
    Tree recursion (1.2.2). cond (1.1.6).
    Fast Exponentiation.
    Computing run time of recursive programs using recurrence equations (*).
    [ Greatest Common Divisors (1.2.5) - should do in Tirgul ]
    Primality testing (1.2.6). The RSA algorithm (*).

  5. Sun Nov 12 :
    Procedures as parameters (1.3.1).
    Let (1.3.2).
    Procedures as general methods (1.3.3) - fixed point.
    [ half-interval method in Tirgul ]
    Procedures as returned values (1.3.4) - just start.

  6. Thu Nov 16 :
    Procedures as returned values (1.3.4).
    Introduction to data abstraction (2.1).
    Example: Aritmetic operators for rational numbers (2.1.1).
    Abstraction barriers (2.1.2).

  7. Sun Nov 19 :
    Pairs (2.1.1).
    What is meant by data? (2.1.3).
    Hierarchical data (2.2).
    Representing sequences (2.2.1) - list operations.
    [ In Tirgul - Printing lists (*).]

  8. Thu Nov 23 :
    Representing sequences (2.2.1) - (cont.) - mapping over lists.
    Sequences as conventional interfaces (2.2.3) [ no nested mapping ].
    Hierarchical Structures (2.2.2).

  9. Sun Nov 26 :
    Symbols and quote (2.3.1).
    Data representations in the read-eval-print loop (*).
    Symbolic Differentiation (2.3.2).

  10. Thu Nov 30 :
    Sets (2.3.3).
    Example: Huffman Encoding Trees (2.3.4) - only started.

  11. Sun Dec 3 :
    Example: Huffman Encoding Trees (2.3.4).
    Example: A picture language (2.2.4).

  12. Thu Dec 7 :
    Multiple representations of abstract data (2.4) (introduction).
    Representations for complex numbers (2.4.1).
    Tagged data (Manifest types) (2.4.2).
    Data-directed programming (2.4.3).

  13. Sun Dec 10 :
    Message Passing (2.4.3).
    Review.

  14. Thu Dec 14 :
    Midterm Exam.

  15. Sun Dec 17 :
    The environment model of evaluation (3.2).
    The rules for evaluation (3.2.1).
    Applying simple procedures (3.2.2).
    Frames as the repository of local state (3.2.3).
    Internal definitions (3.2.4).

  16. Thu Dec 21 :
    Assignment and local state (3.1).
    Local state variables (3.1.1).
    The costs of introducing assignment (3.1.3).
    The benefits of introducing assignemnt (3.1.2).


  18. Sun Dec 24 :
    Hannuka Thu Dec 28 :
    Mutable list structure (3.3.1).
    Representing queues (3.3.2).

  19. Sun Dec 31 :
    OO version of queues, Stacks (briefly) (*).
    Representing tables [just 1 dimension] (3.3.3)
    Streams :
    Streams Are Delayed Lists (3.5.1).

  20. Thu Jan 4 :
    Infinitley long streams (3.5.2)
    Exploiting the stream paradigm (3.5.3) [Memoization for stream - mentioned briefly - to be done in Tirgul? ex. 3.27 in homework].

  21. Sun Jan 7 :
    Exploiting the stream paradigm (cont): infinite streams of pairs (3.5.3) ("Streams as signals" not covered ).
    A functional programming view of time (3.5.5) - briefly
    Concurrency (different from SICP).

  22. Thu Jan 11 :
    Vectors (*). Binary search (*).
    Sorting: bubble sort (*). Quicksort (*). Mergesort (*).

  23. Sun Jan 14 :
    The metacircular evaluator (mc-eval) (4.1).
    The core of the evaluator (4.1.1).
    Representing expressions (4.1.2).

  24. Thu Jan 18 :
    Representing expressions (4.1.2) - finish.
    Evaluator data structures (4.1.3).

  25. Sun Jan 21 :
    Running the evaluator as a program. (4.1.4).
    Data as programs (4.1.5).

  26. Thu Jan 25 :
    Separating syntactic analysis from execution (a-eval) (4.1.7).
    Variations on a Scheme -lazy evaluation (4.2, 4.2.1 4.2.2).

  27. Sun Jan 28 :
    Dynamic binding (*). [ Not covered]
    Adding a macro facility (*).
    Typed-mini-scheme - a static typed variant of scheme (*).

  28. Thu Feb 8 :
    Summary and review of the course.