Exam 2

Out: 14 April 2004 Due: Monday, 19 April 2004, 2:01PM

Name: _________________________________________________________

Directions

Work alone. You may not discuss these problems or anything else related to this course with anyone except for the course staff between receiving this exam and class Monday.

Open book. You may use any books you want, lecture notes and slides, your notes, and problem sets. If you use anything other than the course books and notes, cite what you used.

Open computer. You may use a computer and any programming languages and environments you want for this exam. You are not required to use a computer (other than your own brain if you think it is one) to do well on this exam.

Answer well. Answer all 10 questions. Write your answers on this exam. You should not need more space than is provided to write good answers, but if you want more space you may attach extra sheets. If you do, make sure the answers are clearly marked.

The questions are not necessarily in order of increasing difficulty, so if you get stuck on one question you should continue on to the next question. There is no time limit on this exam, but it should not take more than a few hours to complete.

Full credit depends on the clarity and elegance of your answer, not just correctness. Your answers should be as short and simple as possible, but not simpler.

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 message)
		  (ask self 'say (list "you should be taking notes")))
	    (get-method super message)))))

Note: The original question had stuff instead of message in (ask self 'say message). This was an unintended mistake.

Explain which answer is better and why.

2. Consider the following definitions taken from the PS6 code (without modification except for removing some methods that are not needed for this question):

(define (make-object name)
  (lambda (message)
    (case message
      ((class) (lambda (self) 'object))
      ((name) (lambda (self) name))
      (else no-method))))

(define (make-physical-object name)
  (let ((super (make-object name))
	(location null-place)) ; location set when we install
    (lambda (message) ; Normal actions
      (case message
	((class) (lambda (self) 'physical-object))
	((location) (lambda (self) location))
	(else (get-method super message))))))

(define (make-mobile-object name)
  (let ((super (make-physical-object name)))
    (lambda (message)
      (case message
	((class) (lambda (self) 'mobile-object))
	(else (get-method super message))))))

(define (make-person name)
  (let ((super (make-mobile-object name))
        (possessions '())  
	(restlessness 0.0))
    (lambda (message)
      (case message
	((class) (lambda (self) 'person))
	(else (get-method super message))))))

Provide the simplest possible expression that could have been used in the definition of mystery to produce the given environment diagram shown on the next page:

(define mystery

3. How many frames would be created when (make-mobile-object "bike") is evaluated? (Explain why each frame is generated. Recall that let is syntactic sugar for ((lambda (...) )).)

Computability

4. Is the repeats-configuration problem defined below decidable or undecidable? For credit, your answer must include a convincing argument to support your answer.

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.

5. Is the repeats-fsm-state problem defined below decidable or undecidable? For credit, your answer must include a convincing argument to support your answer.

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.

Building Web Communities

6. Bob Metcow is upset that members of his community are not interacting as usefully as he wants since there are not enough acquaintance links in his community. He decides to implement a program that will add acquaintance links between all pairs of members in his community. He adds a throw-mixer.php program to his website that adds acquaintance links between all members of his community:

    $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')");
	       } } } }

How much work is throw-mixer.php? (Assume executeQuery is defined as in PS7; you may assume it is Θ(r) where r is the number of rows in the table resulting from the query. You should clearly document all other assumptions you make and define the meaning of all variables you use in your result.)

7. Alyssa P. Hacker is upset to discover the PS7 community code cannot support communities with more than 1000 members (see PS7, question #5 comments) since because of her tremendous computer science understanding she has many thousands of friends. So, she reimplements Dijkstra's algorithm used in find-links-process to use a priority queue implementation. The reduces the work require for findmin to Θ(log n) and the overall work of find-links-process to Θ(n log n + m) where n is the number of community members and m is the total number of links.

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

Community Size	Maximum Query Response Time
100	1.5 seconds
200	3.5 seconds

Note: The original exam used a table that was inconsistent with the text (200 and 400 members instead of 100 and 200.

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.)

8. Because of their expertise in building dynamic web sites, Alyssa and her friends rapidly acquire new friends. Assume each member of Alyssa's community invites one new member into the community every year. Since those members also learn to build dynamic web sites, after one year each new community member also invites a new member into the community, and continues to do so every year. Thus, the size of Alyssa's community doubles every year. If Alyssa's community starts with 1000 members in 2004, for how many years can her community grow before the maximum query response time exceeds 60 seconds. Alyssa's web site runs on ITC's web server which improves consistently with Moore's Law (that is, assume its processing power and memory double every 18 months). (Note: you may find it helpful to write a short program to solve this problem. You may use any language you want. Include all the code you wrote with your answer on an attached sheet.)

Lambda Calculus

In Lecture 33, we saw the following definitions:

T ≡ λ x (λ y . x) F ≡ λ xy . y if ≡ λ pca . pca cons ≡ λ xy . (λ z . zxy) car ≡ λ p . p T cdr ≡ λ p . p F

null ≡ λ p . T null? ≡ λ x . (x λ y . λ z . F) zero? ≡ null? pred ≡ cdr succ ≡ λ x . cons F x 0 ≡ null

Suppose we change the definition of succ to be:

succ ≡ λ x . cons T x

9. Show pred (succ 0) reduces to 0 with the new definition. Make sure the reduction steps you perform are clear in your answer.

10. A popular Computer Science textbook defines Computer Science as:

Computer Science is the study of algorithms including:

1. Their formal and mathematiclal properties
2. Their hardware realizations
3. Their linguistic realizations
4. Their applications

Is this a good definition? Explain why or why not. (Hint: you may safely assume that the person grading your answer to this question believes every question on this exam is about Computer Science.)

These two questions are optional and worth no credit, but I appreciate your answers. Feel free to continue your answers on the back if you want more space.

11. Do you feel your performance on this exam will fairly reflect your understanding of the course material so far? If not, explain why.

12. What did you hope to get out of this course that you have not yet gotten?