6.001 Spring 98: Recitation presentation topics

6.001 Spring 98: Recitation oral presentation topics

Each student must make a 5-minute oral presentation in recitation once during the semester. Here are the topics for each class. Specific assignments will be made by your recitation instructor.

Topic #1 -- Present at the recitation of Friday, February 6, 1998

Write a procedure named add-digits in Scheme, and present it to the class. This procedure takes a positive integer, adds up its digits (in decimal representation), and returns the total as its result. Before starting, check out the Scheme primitives remainder and quotient to see if they help simplify the problem.

Topic #2 -- Present at the recitation of Wednesday, February 11, 1998

Write a procedure that computes a*b by using only simple tests like = and the addition operator +. Explain what kind of process your procedure causes (e.g. recursive versus iterative) and why.

Topic #3 -- Present at the recitation of Friday, February 13, 1998

Here are some procedures that double or triple their argument:

(define double
  (lambda (x) (* 2 x)))

(define triple
  (lambda (x) (* 3 x)))

Write a procedure that takes a number as argument, and returns a procedure that multiplies its argument by the number, for example:

(define doubler (make-mul 2))

(doubler 5)
;Value: 10

(doubler 7)
;Value: 14

Topic #4 -- Present at the recitation of Wednesday, February 18, 1998

Sometimes we have procedures that are supposed to be exact inverses of each other. For example, there might be a program that squares its arguments and another that takes the square root. One test of these programs is to see if the square root of the square of a number is the original number.

Write, and explain to the class, a program named make-inverse-test. This program should take in two functions, some procedure and its inverse, and it should return a function that, when used, applies the procedure, applies the inverse, and returns the result.

Topic #5 -- Present at the recitation of Friday, February 20, 1998

Explain to the class how Scheme prints compound data structures. Use as examples the way the following three things print:

(define s1 (cons 7 14))

(define s2 (list 7 14))

(define s3 (cons 7 nil))

s1 -> ???

s2 -> ???

s3 -> ???

Topic #6 -- Present at the recitation of Wednesday, February 25, 1998

Using box and pointer notation, explain how map works. In particular, use a simple example of applying map to a list, e.g.

(map (lambda (x) (* x 2))
     (list 1 2 3))

and show at each stage what box and pointer structures are present and which ones are arguments to a call to map .

Topic #7 -- Present at the recitation of Friday, February 27, 1998

The two programs below were found in a trash can, perhaps because they didn't work quite right. From their names, they appear to be attempts to create a list whose elements are the same but in reverse order from some starting list. With the help of box-and-pointer diagrams, explain what each actually does.

(define (reverse L1)
  (cond ((null? L1) nil)
        (else (reverse (cdr L1))
              (cons (car L1) (cdr L1)))))

(define (reverse L1)
  (if (null? L1)
      nil
      (cons (reverse (cdr L1)) (car L1))))

Topic #8 -- Present at the recitation of Wednesday, March 4, 1998

Write a procedure that finds the last pair in a list and returns it. Use box-and-pointer diagrams to demonstrate that your procedure works for all legal inputs.

Topic #9 -- Present at the recitation of Friday, March 6, 1998

A list named miscellany consists of a large number of pairs. Each pair contains in its car a symbol, and in its cdr an associated value. You have explored the list a bit and found that the symbol 'salary appears in several different pairs, and the associated values seem to be salaries, in dollars, of various employees of your company.

Write a program that prints the total of the salaries, and explain to the class how it works. Be sure to point out any use you make of manifest data types. Show an example of how your program works, using box-and-pointer diagrams.

Topic #10 -- Present at the recitation of Wednesday, March 11, 1998

Describe the main differences between a patent, a copyright and a trade secret, as it applies to protecting software.

Topic #11 -- Present at the recitation of Friday, March 13, 1998

Explain the example on pages 257-58 of the textbook, and do exercise 3.15

Topic #12 -- Present at the recitation of Wednesday, March 18, 1998

Use the environment model to explain the stages of evaluation in the following example:

(define (make-incrementer n)
  (lambda (x) (+ x n)))

(define plus-four (make-incrementer 4))

(plus-four 2)

Topic #13 -- Present at the recitation of Friday, March 20, 1998

Explain, using the environment model, how a procedure named make-counter (which you are going to write) works. A counter is a procedure that one calls with no arguments. On each successive call, it returns a value that is one larger than the previous value it returned. The procedure make-counter takes one argument, the initial value of the counter it will create. The first time someone uses counter, it should return the initial value plus one.

There are many ways of explaining this program. One possible approach is:

demonstrate the operation of the statement that defines make-counter
demonstrate a couple of uses of make-counter, to create two different counters
demonstrate a couple of uses of each of the two counters.

Plan your time and presentation carefully, because this will seem like a lot of stuff to explain in just five minutes. You can assume that by the time of your presentation that the class has seen environment diagrams.

Topic #14 -- Present at the recitation of Wednesday, April 1, 1998

Write a predicate equal-streams? which takes two streams as input and says whether they look the same, i.e. have the same number of elements and each corresponding pair is the same.

Topic #15 -- Present at the recitation of Friday, April 3, 1998

Now that we are using the environment model, it is a little easier to understand what define does. But define and set! both seem to change the environment. Explain to the class, using examples, the difference between what define and set! do.

Topic #16 -- Present at the recitation of Wednesday, April 8, 1998

Explain to the class, using box and pointer diagrams, what the following procedure does:

(define (make-ring x)
  (set-cdr! (last x) x)
  "The dirty deed is done!")

when applied to the list letters

(define letters (list 'a 'b 'c))

Last is a procedure that returns the last element of a list:

(define (last y)
  (if (null? (cdr y))
      y
      (last (cdr y))))

An interesting way to approach this explanation is to write the two procedures and the list on the board, and then ask the class what happens when you type

(make-ring letters)

Topic #17 -- Present at the recitation of Friday, April 10, 1998

Now that we can look at the implementation of the metacircular evaluator we might expect that finally we can figure out in what order it evaluates the sub-expressions in a combination. The procedure that evaluates those expressions is named list-of-values and is found on page 367 of Section 4.1 in the textbook. Unfortunately, it turns out that our metacircular evaluator inherits the order of evaluation that the underlying Scheme interpreter happens to use. Explain this observation to the class, and then show how to modify list-of-values so that it always evaluates expressions left to right.

Topic #18 -- Present at the recitation of Wednesday, April 15, 1998

Review the discussion of internal definitions in section 4.1.6 of the text. Discuss Exercise 4.19 (You need not give an implementation).

Topic #19 -- Present at the recitation of Friday, April 17, 1998

Give a short summary of the lecture on Java given by Dr. Steele.

Topic #20 -- Present at the recitation of Wednesday, April 22, 1998

Discuss section 4.2.1, on normal order evaluation vs applicative order evaluation. Do exercise 4.25.

Topic #21 -- Present at the recitation of Friday, April 24, 1998

Yesterday, we saw a language that incorporates choice and search into its control structure. Do Exercise 4.44 (Write a program to solve the eight queens problem). Show your solution and explain it to the class.

Topic #22 -- Present at the recitation of Wednesday, April 29, 1998

Design and explain the operation of a register machine that reads a stream of numbers. (Each time you hit the *next* button, the next number from the stream comes into a register named *nextnum*. You can tell you have come to the end of the stream when you start seeing zeros in the *nextnum* register. No matter how many times you hit the *next* button, from then on you get a zero.) The goal of the machine is to place the N'th item from the stream in a register named *answer*. This would be easy if N were specified in advance. The problem is that the number N is the last number in the stream, just before you come to the first zero.

Topic #23 -- Present at the recitation of Friday, May 1, 1998

Please briefly summarize the contracts for Eval and Apply in the Explicit Control Evaluator. If possible, explain why the contents of the Continue register are left on the stack when setting up the dispatch to Apply.

Topic #24 -- Present at the recitation of Wednesday, May 6, 1998

Please briefly summarize the key points from yesterdays lecture. Do not worry about details of the compiler, but rather focus on the relationship between the explicit control evaluator and the compiler.

Topic #25 -- Present at the recitation of Friday, May 8, 1998

Specify a register machine that implements the countleaves procedure below. Assume that the machine registers can hold list data, and that the operations cons, car, pair?, not, eq?, null? and + are available as primitives to be used in the machine. Write a machine definition, and draw a diagram showing the data paths.

(define (countleaves tree)
  (cond ((null? tree) 0)
    ((not (pair? tree)) 1)
    (else (+ (countleaves (car tree))
             (countleaves (cdr tree))))))

Topic #26 -- Present at the recitation of Wednesday, May 13, 1998 Summarize the main points of the lecture of May 7. Take a position on what you think the future role of computer assisted surgery will be in medicine, and whether you think computers should be used to aid surgeons in delicate surgery such as neurosurgery.

Return to 6.001 Home Page