|
University of Virginia Computer Science CS150: Computer Science, Fall 2005 |
| Final |
Out: 5 December 2005 Due: Friday, 9 December, 4:59PM (to Brenda Perkins in CS office) |
Name: _________________________________________________________
1. The Schemer's Guide to Python includes this BNF description of the ApplicationStatement:Directions
Note the Open DrScheme direction is different from Exam 1 and Exam 2, but otherwise, all the directions are the same.Work alone. You may not discuss these problems or anything related to the material covered by this exam with anyone except for the course staff between receiving this exam and 5:00pm Friday.
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 DrScheme. You may run DrScheme or any other interpreter of your choice. Keep in mind, though, that your answers to the programming questions will be evaluated based on whether or not you have the basic idea of how to solve them correctly and elegantly, not based on whether your code is exactly correct. It is not necessary to spend time using the Scheme interpreter to get your syntax exactly correct.
Answer well. Answer all questions and optionally answer the optional questions. Write your answers on this exam or on separate sheets of paper. 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 a well-prepared student more than an hour or two 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.
ApplicationStatement ::= Name ( Arguments )Draw a Recursive Transition Network that describes the same language as that generated by the ApplicationStatement above.
Arguments ::=
Arguments ::= MoreArguments
MoreArguments ::= Argument ,MoreArguments
MoreArguments ::= Argument
Argument ::= Expression
Santa Claus is coming to town!
You better watch out
You better not cry
You better not pout
I'm telling you why
Santa Claus is coming to town
He's making a list,
Checking it twice;
Gonna find out who's naughty or nice.
(define (find-deserving children)
(filter is-nice? (filter is-nice? children)))
where the filter procedure was defined in listprocs.ss
(Problem Set 5):
(define (insertl f lst start)
(if (null? lst)
start
(f (car lst) (insertl f (cdr lst) start))))
(define (filter f lst)
(insertl
(lambda (el rest) (if (f el) (cons el rest) rest))
lst
null))
What is the complexity of Santa's find-deserving procedure?
Describe carefully the meaning of all variables you use in your answer
and any assumptions you make (for example, about the is-nice?
procedure used in find-deserving).
3. Santa's elves make toys to distribute to the children. The global environment contains a variable toys that keeps track of all the available toys. It is a list of <toy, count> pairs, where the car of each pair is a string that uniquely identifies the toy and the cdr is the number of those toys available. For example, the list
(("smiley-puzzle" . 3253) ("aquadoodle" . 47382))
would mean that the elves have made 3253 smiley-puzzles and 47382 aquadoodles.
Define the procedure add-toy! that an elve calls after making a
toy.
It should take the name of a toy as its parameter and modify the global
toys list. If the toys list already contains an entry
whose
toy name matches the parameter name, then the count associated with that
toy should increase by 1. If there is no entry with the passed in toy
name, then a new pair should be added to the toys list that
contains the new toy name and count 1. Your add-toy! procedure
should
produce the following interactions:
Hint: you probably want to define an add-toy-helper! procedure that takes a list of toys as a parameter also, but be careful that your code mutates the global toys object.> toys
(("smiley-puzzle" . 3253) ("aquadoodle" . 47382))
> (add-toy! "smiley-puzzle")
> toys
(("smiley-puzzle" . 3254) ("aquadoodle" . 47382))
> (add-toy! "super-soaker"
> toys
(("smiley-puzzle" . 3254) ("aquadoodle" . 47382) ("super-soaker" . 1))
(define (add-toy! toy)
)
Bonus. There are many elves working in parallel, each with their
own Scheme interpreter, but there is one global toys list.
Explain clearly what might go wrong it two elves apply your
add-toy! procedure concurrently.
4. After making the toys and identifying the nice children, Santa needs to match up
the available toys with the nice children.
He will go through the list of nice children and their wish lists, and
then find the first requested toy
that is available in the toys list. That it, the child's wist list is
in order of most wanted to least wanted, and
the child should receive the most wanted gift currently available on the
toys list. (This approach is known as a greedy algorithm,
see Class 35.)
Define the procedure match-toys! that matches a gift with each nice child. As input it takes a list of <child, wishlist> pairs where the wishlist is a list of toys wanted by the child ordered by preference. It should use the global toys object that initially reflects all the toys made by elves. Once a toy is matched with a child, it should be removed from the toys list. As output, it should produce a list of <child, toy> pairs where the toy is the avaliable toy that best matches the child's wishlist or null if there is no matching toy available.
For example, your match-toys! procedure should work like this:
5. What is the complexity of your match-toys! procedure? (Be sure to define any variables you use clearly and state all your assumptions.)> toys
(("smiley-puzzle" . 3254) ("aquadoodle" . 47382) ("super-soaker" . 1))
> (match-toys! (list (cons "Huey" (list "super-soaker" "smiley-puzzle")) (cons "Dewey" (list "super-soaker" "smiley-puzzle")) (cons "Louie" (list "super-soaker"))))
(("Huey" "super-soaker") ("Dewey" "smiley-puzzle") ("Louie" null))
> toys
(("smiley-puzzle" . 3253) ("aquadoodle" . 47382) ("super-soaker" . 0))
Santa Claus is coming to town.
Little toy dolls
that cuddle and coo,
Elephants, boats
and Kiddie cars too.
Input: A list of <toy, count> pairs, and a list of <child, wishlist> pairs where the wishlist is list of toys requested by the associated child in preference order.Explain as clearly as possible how you would prove the MatchToys problem is NP-Complete.Output: A list of <child, toy> pairs where (1) each toy appears no more than its count number of times in the list, and (2) the list maximizes the toy utility function which is 3*number of children who got their first choice toy + 2 * number of children who got their second choice toy + 1 * number of children who got their third choice toy. (Note that children who list more than three toys on their wishlists are considered greedy and do not satisfy the "being nice" requirement, so they do not get a toy.)
7. Explain what the NP-Completeness of the MatchToys problem means for Santa. 8. In addition to matching toys with children, Santa must also deliver all the toys on time. Consider the CanDeliverOnTime problem:
Input: A list of <child, location, toy> triples where the location values are the longitude and latitude location of the child who should receive the toy; v, the maximum velocity of Santa's sleigh; and t, the amount of time available to deliver all the toys.Is the CanDeliverOnTime problem decidable or undecidable? Support your answer with a clear and convincing argument. 9. In Class 30 we argued that HTML was not a universal language because there was no way to describe an infinite loop in HTML. Suppose the following construct was added to HTML to make HTMLR:Output: If there is an ordering of the list so that Santa can deliver all the toys to all the childern at the given locations, starting from the North Pole, and travelling at velocity v within time t, output true. Otherwise, output false. (Note that the laws of physics do not apply to Santa. His reindeer can travel at constant velocity v, and there is no problem with exceeding the speed of light, and it takes no time to drop off a toy once the correct location is reached.)
Element ::= <repeat> Elements </repeat>The meaning of <repeat> Elements </repeat> is to keep repeating Elements.
Is HTMLR a universal language? Support your answer with a clear and convincing argument.
10. Appendix B of the Google paper argued (somewhat unconvincingly) that because the amount of human-generated content is finite, text indexing algorithms can be made near-linear, and processors are improving exponentially, that the fraction of content covered by web search engines will continue to improve. Assume in 2005 that Santa is able to finsh evaluating(match-toys! (join-with-lists (find-deserving children) wish-lists)by December 24th to be able to deliver presents on time if the book on naughty or niceness is closed on December 1. (That is, it takes Santa 24 days to complete the evaluation.)
The join-with-lists procedure matches each deserving child with that child's wishlist. It is Θ(n log w) where n is the number of children (the length of the list passed as its first parameter) and w is the number of wishlists. (This assumes the wishlists are sorted and the children are not.)
Predict what Santa's naughty/nice cut-off date will be in 2011. Explain your answer at least as convincingly as Google's Appendix B.
11. (No expected point value) The goal of this course is to teach students to think like computer scientists, and the goal of this exam is to measure how well you have done that so I can fairly determine your final grade. If you feel your answers on this exam will not adequately demonstrate what you have learned, or that I should take other things into account in determining your final grade, use this space to explain why.
|
End of Exam Happy Holidays! |
|
CS 150: Computer Science University of Virginia |
evans@virginia.edu Using these Materials |