Final: Auction Bots - Comments

Question 1: How much work is find-element-number? Express your answer using Θ notation. Be sure to clear explain what any variables (e.g., n) you use in your answer mean.

Answer: Θ (n) where n is the number of elements in the input list.

find-element-number will cdr down the whole list, looking at each element one at a time. On average, the element to be found will be in the middle of the list (or not in the list at all). So, if the length of the list doubles, the amount of work would double.

Question 2: Is the find element problem decidable or undecidable? Argue convincingly to support your answer.

Decidable.

Since the find-element-number procedure provided for question 1 solves the find element problem, to show it is decidable all we need to do is argue that we have procedure that solves it that always terminates. We know find-element-number will always terminate, since every time it is called it either stops because the list is null (or because it has found the element), or it calls find-element-number recursively with the cdr of the list. Since (cdr lst) is always one shorter than lst, we know the size of the input list will decrease by one for each recursive call. It must eventually reach zero. When it does, the list is null and the evaluation will terminate.

Question 3: How complex is the find element problem? Provide and justify both an upper (O) and lower (Ω) bound.

We use n to represent the length of the input list. We know the problem is O(n) from question 1 — since we have a procedure that solves the find element problem that is Θ(n) we know we can to at least that well, and the upper bound is O (n).

We need to look at every element in the input list, though, since if we stop before looking at every input we may miss the matching element. Hence, it is also Ω (n). Note that the lower bound is different from the best case execution time. In the best case, the first element matches the one we are looking for and we do not need to look beyond it (hence, we can solve the problem in the best case with Θ(1) work). But, for a lower bound we need to know how much work the best possible procedure will require for a typical input.

Since we know the problem is O (n) and Ω (n), we also have a tight bound Θ (n).

Question 4: How much work is the get-highest-bid procedure? Express your answer using Θ notation. Be sure to clear explain what any variables (e.g., n) you use in your answer mean.

Answer: Θ (b log ₂ b) where b is the number of bids.

The procedure uses quicksort to sort the bids:

	 (quicksort
	  (lambda (entry1 entry2)
	    (> (bid-amount entry1) (bid-amount entry2)))
	  (get-bids item))))

The (get-bids item) evaluation uses table-select to find the number of bids for the item. This involves going through each bid in the bids table. The amount of work for each bid is constant — it depends only on the number of fields in the table (a constant). So, it involves &Theta(b) work, and evaluates to a list that contains at most b elements.

Evaluating the quicksort application will evaluate the passed procedure n log ₂ n times where n is the length of the input list to quicksort. The length of the list is at most b, the total number of bids. The amount of work to evaluate the procedure is constant. Even though bid-amount uses find-element-number which is Θ(n), the important thing to recognize is that the n here is a constant (the number of fields in the table); it does not increase with the input size, so the amount of work is constant. Hence, the total work is Θ(b) for the (get-bids item) evaluation plus Θ(b log₂ b) for the quicksort application evaluation. Since b log₂ b grows faster than b, we can simplify this to Θ(b log₂ b).

Question 5: How much work is Effy's get-highest-bid procedure? Express your answer using Θ notation. Be sure to clear explain what any variables (e.g., n) you use in your answer mean.

Answer: Θ (b) where b is the number of bids.

This procedure is faster since it does not sort the bids, but just looks down the list at each bid in turn to find the highest bid.

Question 6: Define the reset-bidbots! procedure. It takes an item as its parameter and sets the bid value of every bidbot for that item to #f.

(define (reset-bidbots! item)
  (map
   (lambda (bid)
     (if (bidbot? bid) 
	 (set-car! bid #f)))
   (get-bid-values item)))

Question 7: Define the reevaluate-bidbots procedure. It takes an item and the new highest bid for that item as parameters. It reevaluates all the bidbots for that item with the new highest bid. If a bidbot produces a new higher bid, it should print out the new bid, reset all the other bidbots and then reevaluate all the bidbots with the new higher bid. Your reevaluate-bidbots procedure should keep giving bidbots a chance to bid until every bidbot has had a chance to bid with the new highest value.

(define (reevaluate-bidbots item highbidvalue)
  (define (reevaluate-helper bids item highbidvalue)
    (if (null? bids)
        (void)
        (let ((bid (bid-bid (car bids))))
          (if (bidbot? bid)
              (if (not (bidbot-amount bid))
                  (let ((newbid ((bidbot-proc bid) highbidvalue)))
                    (if newbid
                        (begin
                          (reset-bidbots! item)
                          (set-car! bid newbid)
                          (printf "New automated high bid for ~a from ~a: ~a~n" item
                                  (bid-bidder (car bids))
                                  newbid)
                          (reevaluate-bidbots item newbid))
                        (reevaluate-helper (cdr bids) item highbidvalue)))
                  (reevaluate-helper (cdr bids) item highbidvalue))
              (reevaluate-helper (cdr bids) item highbidvalue)))))
  (reevaluate-helper (get-bids item) item highbidvalue))

This question was designed to be tough enough that anyone who got close to a correct procedure deserved (and received) an A in the course.

Question 8: Is the settle auction problem decidable? Provide a very convincing argument to support your answer.

No, the settle auction problem is undecidable.

If the bidbots can be any procedure (as stated in the question), it is easy to reduce the halting problem to the settle auction problem:

(define (halts? P I)
   (> 0 (settle-auction 
           (list (lambda (x) (if (< x 1) (begin (P I) 1) #f))))))

If (P I) halts the bidbot will bid 1 the first time it gets a change to bid (starting from 0), and the auction will end with high bid 1.

Its harder to see (and not necessary for this question) that even if bidbots must be simple procedures that do not use anything that could not terminate, that the settle auction problem is still undecidable. We can convert any input program into a set of bidbots that calculate the same thing by dividing the code among bidbots that are themselves simple (terminating) procedures, and relying on the auction procedure to provide the looping behavior.

Question 9: (Optional, no credit) Do you feel your performance on this exam will fairly reflect your understanding of the course material? If not, explain why.

Several students said they thought the exam was unfair because it only covered a small subset of the material, focusing on measuring work and defining procedures. It is certainly true that this exam didn't attempt to cover the whole course. It wasn't meant to be comprehensive, since you had recently taken Exam 2 (which was fairly comprehensive), but rather to give students an opportunity to convince me they understand the most important things that caused the most trouble on Exam 2. To make the exam short, this meant the questions were designed to be hard enough so that if you could answer them well it was convincing evidence that you deserved a good grade in the course. I think some students found this overly traumatizing because I didn't make it clear that that was the point of the final, but I believe a short, hard final is a better use of your time than a long, comprehensive one.

	CS 200: Computer Science Department of Computer Science University of Virginia Circle Fractal by Ramsey Arnaoot and Qi Wang	cs200-staff@cs.virginia.edu Using these Materials