If you have a sticker on your returned exam, it can be interpreted as a lower bound (Ω) on your grade in the course (as long as you do a satisfactory job completing PS8) as described below. There is no upper bound (O) on anyone's grade for the course yet, except as constrained by the registrar (O(A+)).

• Enormous Shiny Gold Smiley Face — Congratulations! You've done enough to convince me you have learned to think like a computer scientist and you deserve an "A" in the course. You are free to do the final if you want, but you are not required to. Taking the final cannot hurt your grade. As long as you do a satisfactory job on PS8 you will get no worse than an "A" in the course.
• Big Shiny Multi-Colored Star — You've done well in the course, but haven't quite completely convinced me yet that you can think like a computer scientist. You have earned at least a "B+" in the course, but should take advantage of PS8 and the Final to convince me you deserve an "A".

Objects and Environments

1. For Problem Set 6, Question 4, two common answers were given:

Answer A:

(define (make-professor name)
  (let ((super (make-lecturer name)))
    (lambda (message)
      (if (eq? message 'profess)
	    (lambda (self message)
	          (ask self 'say (list "It is intuitively obvious that"))
		  (ask self 'lecture message))
	      (get-method super message)))))

Answer B:

(define (make-professor name)
  (let ((super (make-lecturer name)))
    (lambda (message)
      (if (eq? message 'profess)
	    (lambda (self message)
	          (ask self 'say (list "It is intuitively obvious that"))
		  (ask self 'say stuff)
		  (ask self 'say (list "you should be taking notes")))
	    (get-method super message)))))

Average: 9.6 out of 10

Answer A is better for these reasons:

• Since is uses the lecture method of its super class, if the lecture behavior changes, the profess behavior changes also.
• It is shorter and avoids code duplication by using inheritance.
• It is correct — answer B uses stuff which is not defined. (This was an unintended mistake on my part, but is a valid answer.)

Answer B is better for these reasons:

• Since is uses the lecture method of its super class, if the lecture behavior changes, the profess behavior changes also. (Whether or not this is good or bad depends on if we want profess to mean, say "It is intuitively obvious that" and then lecture, or something else that happens to be the same as the current method for lecturing.)
• It may be slightly more efficient. (Doesn't need to overhead of the extra method call to lecture.

Overall Answer A is better for most uses, but you could make an argument for Answer B (except for the unintended mistake using stuff).

(definitions removed, see original exam for details)

Average: 6.7 / 10

(define mystery ((make-person "Tom") 'location)

Many students had a hard time with this one and answers just (make-person "Tom"). The first thing you should notice from the diagram is that mystery is pointing to a procedure with parameters self and body location. So, mystery is a procedure (lambda (self) location). The result of an application of make-person is a procedure (lambda (message) (case message (...))) so mystery must be something else. The second thing to notice is the enclosing environment is a frame that defines message as 'location. Hence, we must have applied a procedure that has a parameter message to the input 'location. That would be the result of a make-person application. Looking up to the next frame, we see the let variables for make-person, and abot that, the frame that has name value Tom. This corresponds to applying the make-person procedure to "Tom", since its parameter is name.

Note that is it not quite correct to have

(define mystery (ask (make-person "Tom") 'location)

since the application of ask would have created an additional frame which is not shown in the diagram.

Average: 8.1 / 10

A frame is created whenever an application is done:

• Evaluating (make-mobile-object "bike") creates a frame with name bound to "bike". (Frame 1)
• Evaluating the body of make-mobile-object:
  • The let is syntactic sugar for an application, so a new frame is created with place super. (Frame 2)
  • Evaluating (make-physical-object name) (to get the value for super):
    • Creates a new frame containing name for the application. (Frame 3)
    • Creates a new fram containing super and location for the let application. (Frame 4)
    • Evaluating (make-object name) creates a new frame containing name for the make-object application. (Frame 5)

Computability

Input: A description of a Turing Machine and input tape.

Output: If executing the Turing Machine on the given input would ever repeat a machine configuration (the state of the finite state machine and the contents of the tape), output true. Otherwise, output false. That is, the output should be true if and only if executing the Turing Machine on the given input would encounter the same exact machine configuration more than once.

Average: 7.7 / 10

The repeats-configuration problem is undecidable.

Before explaining why, we'll discuss the common attempts to show this and why they are unconvincing:

• Since the tape is infinite, you cannot check if two machine configurations are identical in a finite time, so there is no algorithm to solve repeats-configuration. — Although this sounds reasonable, there are two flaws in this argument: (1) the tape is infinite, but only a finite number of squares contain symbols, as demarked by the end-of-tape symbols. Hence, checking two machine configurations are equivalent only involes examining a finite number of symbols on the tape. (2) Even if the tape could contain infinitely many symbols, that does not prove repeats-configuration is undecibale. One cannot assume it is neceesary to simulate execution of the input TM and examine the entire machine configuration, to know that a configuration never repeats. Although simulating the input TM, keeping track of all machine configurations, and checking if one ever repeats seems like the most straightforward way to implement repeats-configuration, that does not mean there could not be a different way (that doesn't involve simulating the input TM).
• If we simulate the input TM and a machine configuration repeats, that means the input TM never halts. Thus, an algorithm that solves repeats-configuration could be used to solve halts? like this:
     (define (halts? P I) (not (repeats-configuration? P I))). — This is a good attempt, but there is one major whole in the argument! The definition of halts? is not correct. It is true that if a machine state repeats in evaluating P on I, we know it will never halt: Turing machines are deterministic, so if a configuration is repeated, it must do the same thing as it did last time, and will repeat all the steps to return to the repeated configuration. But, it is not true that if (repeats-configuration? P I) is false that must mean (P I) halts. For example, consider a simple program that in state 1 alwyas moves Right, writes a "*" on the tape, and returns to state 1. This program never halts, but never repeats a machine configuration since it keeps writing more "*"s on the tape forever.

A correct argument needs to show how an algorithm that solves repeats-configuration would allow us to define an algorithm that solves halts. Here's how:

1. For simplicity of description, assume we have two infinite tapes, T1 and T2. Note that this does not increase the power of the TM, since we could represent two tapes with one tape that is folded over on itself.
2. Modify the input program P to replace every transition rule with an extra transition that writes a "*" on T2 and moves the T2 tape head to the right. This way, the configuration of T2 will never repeat during the execution of P.
3. Replace all transitions to the Halt state with transitions to a new state will: rewrite T1 (the original input tape) to contain the original input I, and erase all the "*"s on T2, and then transition to the original Start state. Note that after this is done, the machine configuration will have returned to the original input configuration.

So, the modified program P' will repeat a machine configuration if the original program P halts. But, it will never repeat a machine configuration if P does not halt (even if P would repeat a configuration, since the "*"s on T2 prevent P' from repeating). Hence, we can not correctly define halts: (define (halts? P I) (repeats-configuration (modify-program P I) I) where modify-program performs the transofmrations described above.

Input: A description of a Turing Machine and input tape.

Output: If executing the Turing Machine on the given input would ever repeat a finite state machine state, output true. Otherwise, output false. That is, the output should be true if and only if executing the Turing Machine on the given input would enter the same finite state machine state more than once.

Average: 8.9 / 10

The repeats-fsm-state problem is decidable.

The important difference here is that we only care about whether the FSM state repeats, even if the contents of the tape are different. There are a fininte number of FSM states, so this is decidable. Here is an algorithm that decides it:

• Simulate the input TM, P for up to s + 1 steps, where s is the number of states in P. Each time P would enter a new state, record the state it enters.
• If P halts before repeating a state, output false. Otherwise, output true. We know we can output true after s + 1 steps, since if P has not halted after s + 1 steps, it must have repeated a state — there are only s states to use.

This is an application of the pigeon hole principle. See this Car Talk Puzzler (http://www.cartalk.com/content/puzzler/transcripts/200404/index.html) and answer for a similar problem.

Building Web Communities

    $result = executeQuery ("SELECT id FROM users");
    for ($i = 0; $i < mysql_num_rows ($result); $i++) {
        for ($j = 0; $j < mysql_num_rows ($result); $j++) {
           if ($i != $j) {
               $exists = executeQuery ("SELECT fromid FROM acquaints 
                                        WHERE fromid='$i' AND toid='$j'");
               if (mysql_num_rows ($exists) == 0) {
                 executeQuery ("INSERT INTO acquaints (fromid, toid)
                                VALUES ('$i', '$j')");
	       } } } }

Average: 8.9 / 10

Θ(n²) where n is the number of community members (entries in the users table).

The first query produces a table of size n (and takes Θ(n) time to execute). Then, the outer loop executes once for each entry in the result table: n iterations. Within the outer loop, the inner loop ($j) executed n times. So, the body inside the two loops executes n² times. The amount of work for each iteration is constant: it involves at worst two queries, each of which involves Θ(1) work. Note that the first select returns at most one entry, so it is Θ(1).

Note: Bob Metcow is not related to Bob Metcalfe, who invented Ethernet (which is the networking protocol nearly all machines use for local networks today, including those in the ITC labs) for his 1970 Harvard PhD thesis (which was originally rejected for not being "theoretical enough") and went on two found 3Com. Metcalfe's Law states that the value of a communication system is Θ(n²) where n is the number of users on the system. (Note that this is more conservative than Reed's law, which claims that the value of a community scales as Θ(2ⁿ) which may explain why http://www.thefacebook.com/ is more useful than your PS7 site.

She conducts experiments with communities containing 200 and 400 members and obtains these measurements:

Estimate how big a community Alyssa's new implementation can support. (As in PS7, assume that the only constraint on community size is that the mamximum query response time cannot exceed 60 seconds. State clearly any additional assumptions you need to make.)

Average: 8.6 / 10

About 5000 members. The easiest way to answer this is just some trial and error expression evaluations:

> (define (nlogn n) (* n (log n)))
> (define w (/ 3.5 (nlogn 400)))
> (* w (nlogn 200))
1.547544063485211
> (* w (nlogn 1000))
10.08816095227816
> (* w (nlogn 10000))
134.50881269704217
> (* w (nlogn 5000))
62.19300793565135

Average: 8.1 / 10

About 6 years. Here is my interactions buffer (some of the code is taken from Lecture 19):

> (define (communitysize init years)
    (if (= years 0) init
        (communitysize (* 10 init) (- years 1))))
> (define (time-to-solve n years)
    (/ (nlogn n) (computing-power years)))
> (define (computing-power years)
    (if (= years 0) 1 (* 1.586 (computing-power (- years 1)))))
> (define (time-to-solve n years)
    (* w (/ (nlogn n) (computing-power years))))
> (define (communitysize init years)
    (if (= years 0) init
        (communitysize (* 2 init) (- years 1))))
> (define nmembers 1000)
> (time-to-solve (communitysize nmembers 4) 4)
35.74975753242224
> (time-to-solve (communitysize nmembers 5) 5)
48.30966931405207
> (time-to-solve (communitysize nmembers 6) 6)
64.9907656681721

Lambda Calculus