CS200: Computer Science, Spring 2004

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:Explain which answer is better and why.(define (makeprofessor name) (let ((super (makelecturer name))) (lambda (message) (if (eq? message 'profess) (lambda (self message) (ask self 'say (list "It is intuitively obvious that")) (ask self 'lecture message)) (getmethod super message)))))Answer B:(define (makeprofessor name) (let ((super (makelecturer 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"))) (getmethod super message)))))Note: The original question had stuff instead of message in (ask self 'say message). This was an unintended mistake.
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 (makeobject name) (lambda (message) (case message ((class) (lambda (self) 'object)) ((name) (lambda (self) name)) (else nomethod)))) (define (makephysicalobject name) (let ((super (makeobject name)) (location nullplace)) ; location set when we install (lambda (message) ; Normal actions (case message ((class) (lambda (self) 'physicalobject)) ((location) (lambda (self) location)) (else (getmethod super message)))))) (define (makemobileobject name) (let ((super (makephysicalobject name))) (lambda (message) (case message ((class) (lambda (self) 'mobileobject)) (else (getmethod super message)))))) (define (makeperson name) (let ((super (makemobileobject name)) (possessions '()) (restlessness 0.0)) (lambda (message) (case message ((class) (lambda (self) 'person)) (else (getmethod 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 mystery3. How many frames would be created when (makemobileobject "bike") is evaluated? (Explain why each frame is generated. Recall that let is syntactic sugar for ((lambda (...) )).)
Computability
4. Is the repeatsconfiguration 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 repeatsfsmstate 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 throwmixer.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 throwmixer.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 findlinksprocess to use a priority queue implementation. The reduces the work require for findmin to Θ(log n) and the overall work of findlinksprocess 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:
Note: The original exam used a table that was inconsistent with the text (200 and 400 members instead of 100 and 200.
Community Size Maximum Query Response Time 100 1.5 seconds 200 3.5 seconds 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:Suppose we change the definition of succ to be:
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
succ ≡ λ x . cons T x9. 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: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.)
 Their formal and mathematiclal properties
 Their hardware realizations
 Their linguistic realizations
 Their applications
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?
cs200staff@cs.virginia.edu Using these Materials 