The semester is over - these are the former office hours.
Solutions are available for previous quizzes, and exams. Solutions for some of the homeworks will be posted as we go.
(define (runtime) ; Get cpu time in milliseconds less garbage collection time. ; This is to deal with fact that (runtime) does not exist ; within mzscheme of drscheme. (- (current-process-milliseconds) (current-gc-milliseconds)))
We will cover the essentials of the first four chapters of the text. The readings, homeworks, and topics discussed are listed for each date.
Introduction, TA office hours, prerequisites, drscheme, textbook and coverage, course organization and requirements, overview of programming paradigms, scheme and lisp, list as basic data type, scheme is weakly typed, list syntax, heterogeneous element types within list, function call as evaluation of a list, ran drscheme. Reading: sections 1-1.1.4. Homework #1: run drscheme, experiment with function calls, visit menus.
Drscheme, edlab accounts, recursion, base case, recursive case, examples of recursion, tree traverals, combinations, (define ...), special form, environment, #t, #f, (if ...), (cond ...). Reading: sections 1.1.5, 1.1.6, 1.1.8, 1.2, 1.2.1. Homework #2: due 9:30AM Feb 9, exercises 1.1, 1.3, 1.4, 1.5, 1.6, 1.9.
Applicative order, normal order, substitution model, other than #f logically equivalent (for true/false purposes) to #t, (and ...), (or ...), (not ...), local procedure, lexical scope, bound variable, free variable, process versus procedure, delayed computation, linear recursive process, linear iterative process, tree recursion. Reading: sections 1.2.2-1.2.6.
Homework #2 was returned and discussed. A worksheet was completed covering Linear Recursive Process vs. Iterative Process, bound vs. free variables, and the interpreter's response to various simple procedures.
O(log n) calculation of integer exponentiation, sheme implementation, how to test complexity empirically, applicative order evaluation, O(root n) calculation of primeness, implementation, O(log n) Fermat calculation of likely primeness, carmichael number, (lambda ...). Reading: sections 1.3, 1.3.1, 1.3.2. Homework #3: due 9:30AM Feb 16, exercises 1.12, 1.15, 1.16, 1.17, 1.22, 1.30, 1.31, 1.32a, 1.34.
Whether `if' or `cond', clarity of code, generality versus readability and ease of use, generalization of the summation function, passing a procedure as an argument, more on lambda expressions, identity function, product function, (accumulate ...), (let ...), pair, (car ...), (cdr ...), (cons ...). Reading: sections 2, 2.1, 2.1.1.
Questions about Homework #3 were answered, Homework #2 was returned and discussed, and a Worksheet on iterative vs. recursive, Orders of Growth, and Lambda was completed.
Chapter #1 review, compound data (multiple components), list structures for data structures, data type for rational numbers, top-down design, use of `let' to improve readability, lack of type checking, canonical form, gcd (used), list as a recursive structure, recursive `list-length' function. Reading: sections 2.1.2, 2.1.3, skip 2.1.4. Homework #4: due 9:30AM Feb 23, exercises 2.1, 2.2, 2.4.
Homework #3 was returned, Homework #4 was discussed, and a worksheet with some examples of cons, car, and cdr was completed and discussed. Homeworks that were not picked up during discussion are available during office hours (W 1-4pm in LGRT 220).
Abstraction levels and barriers, lambda representation of pair, object, message passing, (list-ref ...), variable number of arguments, (append ...). Reading: sections 2.2, 2.2.1. Homework #5: due 9:30AM Mar 2, exercises 2.17, 2.18, 2.20, 2.21.
(map ...), (apply ...), (count-leaves ...), (quote ...), (nil) versus nil, composition of functions of lists, (filter ...), (flatten ...). Reading: sections 2.2.2, 2.2.3, skip 2.2.4, 2.3, 2.3.1.
Homework #4 was returned and discussed. A worksheet demonstrating helper functions, intermediate quanties, "let", "map", box and pointer notation, and recursive procedures was completed and discussed.
(reverse ...), macros, (accumulate ...) with list operations, (apply append (map ...)), (memq? ...), (eq? ...), (equal? ...). Reading: sections 2.3.2, 2.3.3, skip 2.3.4. Homework #6: due 9:30AM Mar 9, exercises 2.25, 2.27, 2.32, 2.33, 2.53, 2.54, 2.55.
This will cover assigned reading in text up through and including Section 2.2.2. No macros. The questions concentrate on Chapter 2 material. Among other things, be sure to understand how to write functions with a variable number of arguments. Be comfortable with (append ...), (apply ...), and (map ...). You will need to write code.
Homework #5 was returned and discussed. A worksheet covering trees, the use of "append", "cons", and "list" was discussed, and a procedure for accumulating the number of leaves was completed and discussed.
Symbolic differentiation, constructor, selector, predicate, simplification, sets, set operators, set intersection as filter, set union, avl tree representation, data type for complex numbers and arithmetic. Reading: sections 2.4 through 2.4.3. Homework #7: due 9:30AM Mar 16, exercises 2.56, 2.59, 2.73, 2.75.
Data type for complex arithmetic, rectangular and polar representations, tagged data type, data-directed programmin, (put ...), (get ...), table of functions indexed by operation and type, data as procedure with message passing. Reading: sections 2.5 through 2.5.2, skip 2.5.3.
Homework #6 was returned and discussed. A worksheet covering operations on trees using "map" was completed and discussed.
Larger arithmetic data type, nested types produce multiple type tags, type coercion, (put-coercion ...), (get-coercion ...), modified (apply-generic ...), implementation of bignums. Reading: sections 3, 3.1.2. Homework #8: due 9:30AM Mar 30, exercises 2.77, 2.83, 3.1, 3.2, 3.6, implement (my-and ...) special form as a macro.
Imperative programming, assignment, state, state variables, (set! ...), (begin ...), implicit begin in (cond ...), lexically bound local variable persists if lambda created and kept, (make-account ...) example. Reading: sections 3.1.3, 3.2, 3.2.1, 3.2.2.
Midterm #1 was discussed and a worksheet covering operations on sets and a O(n) implementation of union-set was completed and discussed.
Multiple variable names for same data item, environmental model of evaluation, frame, environment, global environment, possible representations for frames and environments, function storage, variable changed by set!, local variable binding, (make-withdraw ...) environment, statically bound local variable referenced by named lambda. Reading: sections 3.2.3, 3.2.4, 3.3, 3.3.1, 3.3.2. Homework #9: due 9:30AM Apr 6, exercises 3.8, 3.9 (factorial 3), implement (my-begin ...) special form, 3.10, 3.12, 3.13, 3.17, 3.21.
Locally defined functions, mutators, (set-car! ...), (set-cdr! ...), destructive operations, (append! ...), cyclic structures, (display ...) of cyclic structures, (count-pairs ...) of cyclic structures, lambda version of cons that includes set-car! and set-cdr!, queues, tables, assoc list, alist, table as headed alist, (assoc ...), (lookup ...), (insert ...) into table. Reading: sections 3.3.3, skip 3.3.4, skip 3.3.5, skip 3.4-3.4.2, read 3.5, 3.5.1.
Hwk #7 was returned and discussed. Hwk #8 was also discussed and "my-and" was covered in preparation for the midterm.
Two-dimensional (two-key) tables, stream, delayed list, (stream-car ...), (stream-cdr ...), (cons-stream ...), (stream-null? ...), the-empty-stream, (delay ...), (force ...), lazy evaluation. Homework #10: due 9:30AM Apr 13, exercises 3.25, 3.27, 3.50, 3.51, implement and test the `second prime from 10000..1000000' example. Recall that examples from book are available on-line. Implement (cons-stream ...) and (delay ...) special forms as macros.
This will emphasize material since Midterm #1 through and including queues in Section 3.3.2. It is likely that you will need to write a macro.
Hwk #8 was returned and discussed. The solutions for Midterm #2 were presented and talked about.
More illustrations of streams, live implementations/demos, infinite streams, integers stream, odd integers stream, fibs stream, ones stream, (add-streams ...), (memoize ...), (memo-proc ...). Reading: sections 3.5.2, 3.5.3 (up to and including `sequence accelerator, skip rest). Homework #11: due 9:30AM Apr 20, exercises 3.53, 3.56.
Newton's method, (sqrt x), sequence of successively improved approximation, stream of approximations, (sqrt-stream ...), stream as method for representing state in a functional paradigm, metalinguistic abstraction, metacircular evaluator, program as interpreter, (eval ...), started on (eval-poker-hand ...). Reading: skip 3.5.4, read 3.5.5, 4, 4.1, 4.1.1.
Implementation language versus implemented language, top down design of interpreter, (self-evaluating? ...), (variable? ...), (quoted? ...), (tagged-list? ...), (text-of-quotation ...), (eval-if ..), (begin? ...), (eval-sequence ...), (apply ...), (extend-environment ...), (make-procedure ...), (extend-environment ...), (make-frame ...), box and pointer diagram of environment, (lookup-variable-value ...), (set-variable-value! ...), (add-binding-to-frame! ...). Reading: read 4.1.2, 4.1.3, 4.1.4. Homework #12: due 9:30AM Apr 27, exercise 4.1, implement (cond->if ...), 4.4, 4.12, 4.14.
Top level of interpreter, creating global environment, primitive procedure objects, global constants, (driver-loop ...), input expressions are program to creator, data to interpreter, binding internal definitions, separation of syntactic analysis from execution procedures. Reading: read 4.1.5-4.1.7, 4.2, 4.2.1.
Returned homeworks #9 and #11. Discussed the environmental model of evaluation (frames and procedure objects), specifically Exercises 3.9 and 3.10 from the book. Also discussed macros and presented several solutions to writing (my-begin ...).
Applicative order, normal order, strict, non-strict, lazy evaluator, thunk, (delay-it ...), (force-it ..), (actual-value ...), evaluated-thunk, memoizing force-it, streams as lazy lists, non-strict cons, list-ref behaves like stream-ref. Reading: read 4.2.2, 4.2.3, 4.3, 4.3.1. Homework #13: due 9:30AM May 4, exercises 4.19, 4.22, 4.25, 4.27, 4.31, 4.33.
The amb evaluator, search embedded in interpreter, (amb ...), (amb-require ...), depth-first search, generate-and-test, success continuation, failure continuation, exercise 4.42 (see below), eight-queens problem. Reading: read 4.3.2 (omit segment on "parsing natural language"), skip 4.3.3 (implementation of amb interpreter), read 4.4, 4.4.1.(define (rank-students) (let ((b (amb 1 2 3 4 5)) (e (amb 1 2 3 4 5)) (j (amb 1 2 3 4 5)) (k (amb 1 2 3 4 5)) (m (amb 1 2 3 4 5))) (amb-require (distinct? (list b e j k m))) (amb-require (xor (= b 3) (= k 2))) (amb-require (xor (= e 1) (= j 2))) (amb-require (xor (= j 3) (= e 5))) (amb-require (xor (= m 4) (= k 2))) (amb-require (xor (= b 1) (= m 4))) (list (cons 'b b) (cons 'e e) (cons 'j j) (cons 'k k) (cons 'm m))))
Homeworks #10 and #12 were returned. The environment diagram for memo-fib was discussed. The macros for delay and cond-if were also covered.
Solution to exercise 4.44, query interpreter for logic programming, database of assertions, relational data, variable as atom starting with questions mark, pattern matching, bindings, modus ponens, rules, dot notation, compound query, (lisp-value ...), (outranked-by ...), efficiency of query, computation as query for result, (append-to-form ...). Reading: read 4.4.2, 4.4.3, skip 4.4.4, and 5.3. Homework #14: due 9:30AM May 16, do exercise 4.44, 4.55(b), 4.60, 4.68.
Patrick will present lecture today. The topic will cover computational architectures in Robotics with emphasis on research that is conducted in the CS department.
Chapter 4 was discussed. Several problems from the book were completed.
Pattern matching, bindings, matching compound query, unification, most general unifier, matching for rule application, garbage collection.
Course main themes.
Patrick will not be able to conduct discussion on this date, discussion is canceled.
At 8:00AM in ECSC-0119.
Current grades are updated throughout the semester.
If you do not have your own machine, then you will need to become familiar with the EdLab machines. You have an EdLab account. We will use the drscheme implementation of the Scheme dialect of Lisp. You may want to download drscheme onto your own machine. Documentation is available too.
Homework is due at the beginning of class on the date stated. Do not be late or absent in order to complete a homework. Hand in your best effort by the deadline. Late homework will be not be accepted. You need to keep up with the homeworks as a means of learning the material and understanding the lectures and discussions. You need to spend time in your laboratory (Dr. Scheme) posing and answering questions, implementing and testing code, conducting experiments, being your own best critic, and generally practicing. Cognitive skill is acquired through exertion, practice, and drill. To do well, be sure to persevere with your homework.
If you have not completed CMPSCI 187 successfully, do not take this course. I need to count on your being at least this familiar with programming and data structures.
You need to come to class. You need to do the assigned homework. We will have two in-class midterms, no quizzes, and a final exam. The homeworks count 35%, the two midterms count 15% each, and the final counts 35%.
We will use Structure and Interpretation of Computer Programs, second edition, 1996, by Abelson, Sussman, and Sussman. It is available in the Textbook Annex, and online. A handy online tutorial is Teach Yourself Scheme in Fixnum Days by Dorai Sitaram.
Your work for the course needs to be the result of your individual effort. Talking with fellow classmates is of course an important and exciting part of the learning process, so you will need to use good judgement. If you are in doubt, feel free to ask. Be sure to attribute correctly those ideas that you borrow from others.
Many of the materials created for this course are the intellectual property of the instructor. This includes, but is not limited to, the syllabus, lectures and course notes. Except to the extent not protected by copyright law, any use, distribution or sale of such materials requires the permission of the instructor. Please be aware that it is a violation of university policy to reproduce, for distribution or sale, class lectures or class notes, unless copyright has been explicity waived by the faculty member.