Final: Auction Bots

Out: 28 April 2003 Due: Monday, 5 May 2003, 4:55pm (turn in at Olsson 236A)

Note: The exam handed out in class misnumbered the questions and had two question 5s. You need to answer both of them. The numbering has been corrected in the on-line version, but nothing else has changed.

Work alone. You may not discuss these problems or anything related to them with anyone except for the course staff between receiving this exam and May 6. You may send email to evans@cs.virginia.edu to ask for clarifications on what the questions mean.

Open book. You may use any books you want, lecture notes and slides, your notes, problem sets, and anything you find on the web. If you use anything other than the course books and notes, cite what you used. If you want, you may use DrScheme, but you are not expected to test real code for any of these questions.

Time Limited. For your own protection, you are not allowed to spend more than 3 hours actually working at a computer on this exam. You may spend as much time as you want not in front of a computer, but you should keep track of all the time you spend working at a computer. If you are close to reaching the 3 hour time limit and think more time would be helpful, send email to evans@cs.virginia.edu explaining why you think more time would be helpful. You may be granted permission to spend more time on it, but stop working on it after you reach the 3 hour limit until you are. You can spend as much time as you want working away from a computer.

Answer well. Answer all 8 questions. 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.

Download: Download final.zip to your machine and unzip it into your home directory J:\cs200\final. This file contains: final.ss — A template for your answers. You should do the problem set by editing this file. auction.ss — Provided auction code from the PS5 solutions. database.ss — Provided database code from PS5 solutions. listprocs.ss — Some useful procedures for manipulating lists (you have seen most of them already in class).

Auction Bots

For the final, you will answer some questions about complexity and computability and extend the auction program from PS5 to support bid bots. Bid bots are programs that place bids automatically on behalf of a bidder. For example, on ebay, bidders can submit a bid that is actually a bid bot that will keep bidding one more than the highest other bidder up to a limit amount specified by the bidder. Questions 5 and 6 require you to write some code; the other questions are about complexity and computability. You should answer Question 7 even if you cannot answer Question 6.

Complexity of Original Implementation

In listprocs.ss we defined find-element-number, a procedure that takes a list and a value, and evaluates to the number of the first element in the list that matches the value, or an error if no element matches the value:

(define (find-element-number lst el)
  (if (null? lst)
      (error "Element not found: " el)
      (if (eq? (car lst) el)
	  1
	  (+ 1 (find-element-number (cdr lst) el)))))

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.

Consider the find element problem:

Input: an unordered list lst of n elements, and a value v
Output: if there is an element of lst that is equal to v, then output index where index is the number of the element in the list (counted starting from 1 as the first element in the list). If there is no element of lst that is equal to v, output error.

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

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

In the provided code, we defined get-highest-bid (some of these procedures are defined in listprocs.ss, others in database.ss):

(define (make-table fieldlist entries) (cons fieldlist entries))
(define (table-fields table) (car table))
(define (table-entries table) (cdr table))

(define (make-string-selector match)
  (lambda (fval) (string=? fval match)))

(define (find-field-number table field)
  (find-element-number (table-fields table) field))

(define (table-select table field proc)
  (make-table
   (table-fields table)
   (let ((fieldno (find-field-number table field)))
     (filter
      (lambda (x) (proc (get-nth x fieldno)))
      (table-entries table)))))

(define (get-bids item)
  (table-entries (table-select bids 'item-name (make-string-selector item))))

(define (bid-amount bid)
  (get-nth bid  (find-field-number bids 'amount)))

(define (get-highest-bid item)
  (let ((sortbids 
	 (quicksort
	  (lambda (entry1 entry2)
	    (> (bid-amount entry1) (bid-amount entry2)))
	  (get-bids item))))
    (if (> (length sortbids) 0)
	(car sortbids)
	null)))

Assume the quicksort procedure is Θ(n log₂ n) where n is the length of the list passed in as its second parameter.

Assume the filter procedure (used in table-select) is Θ(n) where n is the length of the list passed in as its second parameter.

Assume the get-nth procedure is Θ(n) where n is the value of its second parameter. For example, the time it takes to evaluate (get-nth x fieldno) in table-select depends only on the value of fieldno.

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.

Effy Shiente suggests using this code instead:

(define (get-highest-bid item)
  (define (get-highest-helper itembids)
    (if (null? itembids)
	null
	(let ((rest (get-highest-helper (cdr itembids)))
	      (current (bid-amount (car itembids))))
	  (if (or (null? rest) (> current rest))
	      current
	      rest))))
  (get-highest-helper (get-bids item)))

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.

Implementing Bid Bots

A bid bot is a procedure that takes a number as input representing the current high bid. The bid bot evaluates to either a number higher than the input number, representing the bid bot's owner's new bid, or evaluates to #f if the bid bot is not making a higher bid.

For example, a bid bit that keeps increasing the bid up to $100 is defined by:

(define (up-to-100 bid) (if (< bid 100) (+ bid 1) #f))

Instead of just bidding fixed amounts, a bidder may submit a bid bot. When a bid bot is installed, it is evaluated with the current high bid on the item passed in as its parameter. Every time a new high bid is submitted for an item, all the bid bots for that item are re-evaluated with the new high bid. The bid bots are evaluated in the order in which they were submitted. Note that if one of the bid bots evaluates to a new higher bid, then all the other bid bots are re-evaluated with that new higher bid. This process continues until no bid bot is willing to make a higher bid. Note that a bid bot should never be evaluated on its own bid — that would be like a bidder outbidding herself.

To extend our auction service to support bid bots, we will allow the amount field of the bids table to hold either a fixed value (as it does now) or a cons pair of a value and a procedure. The value of the cons pair represents the last value the bid-bot procedure evaluated to. This is either the high bid, or #f if it is not the high bid.

We have modified the place-bid procedure to place either a plain value bid or a bidbot bid. After a new high bid is placed, it evaluates (reevaluate-bidbots item amount) to give the installed bidbots a chance to outbid the new bid.

(define (place-bid bidder item bid)
 (let ((bidder-entry (table-entries 
                      (table-select bidders 'name (make-string-selector bidder))))
    (item-entry (table-entries 
                 (table-select items 'item-name (make-string-selector item)))))

       ... code for checking bidder elided

       (let ((highest-bid (get-highest-bid item)))
         (if (procedure? bid) ;;; its a bid bot
             (install-bidbot! 
              bidder item
              (if (null? highest-bid) 0 (bid-amount highest-bid))
              bid) ;;; The bidbot procedure
             (begin ;;; not a bid bot
               (if (> bid (bid-amount highest-bid))
                   (begin
                     (printf "~a is now the high bidder for ~a: ~a~n" 
                             bidder item bid)
                     (insert-bid bidder item bid)
                     (reset-bidbots! item)
                     (reevaluate-bidbots item bid)
                     (void))
                   (printf "Bid amount does not exceed previous highest bid: ~a~n"
                           (bid-amount highest-bid)))))))))))))

If the bid is a procedure, we call install-bidbot! to install a bidbot. If a new bid is placed, we evaluate (reset-bidbots! item) to reset the value associated with every bidbot for this item to #f, and then (reevaluate-bidbots item bid) to give all the bidbots a chance to place new bids.

The install-bidbot! procedure (defined in auction.ss take four parameters: a bidder, item, current high bid, and a bidbot procedure. It installs a cons pair in the bids table of the bid value (false if the bidbot will not outbid the high bid). Note that the bidbot is installed with #f as its value if it does not outbid the high bid.

(define (install-bidbot! bidder item highest-bid proc)
  (let ((newbid (proc highest-bid)))
    (if newbid
	(begin
	  (reset-bidbots! item)
	  (table-insert! bids (list bidder item (cons newbid proc)))
	  (printf "~a is now the high bidder for ~a: ~a~n" bidder item newbid)
	  (reevaluate-bidbots item newbid))
	(table-insert! bids (list bidder item (cons #f proc))))
    newbid))

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. You may want to use these procedures defined in auction.ss: (get-bid-values item) — evaluates to a list of bid values for item. A bid value is either a number for a normal bid, or a cons pair for a bidbot. (bidbot? bid) — evaluates to #t if bid is a bidbot, otherwise evalates to #f.

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.

Here are some sample executions:

> (load "final.ss")

> (place-bid "Katie Couric" "CLAS" (lambda (bid) (if (< bid 10000000) (+ bid 1) #f)))

Katie Couric is now the high bidder for CLAS: 2000001

2000001

> (place-bid "Dave Matthews" "CLAS" 3000000)

Dave Matthews is now the high bidder for CLAS: 3000000
New automated high bid for CLAS from Katie Couric: 3000001

>(place-bid "Dave Matthews" "CLAS" (lambda (bid) (+ bid 10000)))

Dave Matthews is now the high bidder for CLAS: 3010001
New automated high bid for CLAS from Katie Couric: 3010002
New automated high bid for CLAS from Dave Matthews: 3020002
New automated high bid for CLAS from Katie Couric: 3020003
New automated high bid for CLAS from Dave Matthews: 3030003
New automated high bid for CLAS from Katie Couric: 3030004
... (many lines elided)
New automated high bid for CLAS from Dave Matthews: 9990699
New automated high bid for CLAS from Katie Couric: 9990700
New automated high bid for CLAS from Dave Matthews: 10000700

3010001

It is fine if your program does not print out such descriptive bid messages are in these examples. It is sufficient to just print out the amount of each new bid.

Decidability

Consider the settle auction problem:

Input: a set of bidbots. A bidbot is a procedure that takes a number parameter and evaluates to either #f or a number higher than the input number.

Output: the winning bid value. The highest bid is initially 0. The winning bid it determined by evaluating each bidbot on the current highest bid, until no bidbot produces a new bid value.

Note that for simplicity, we have changed the bidding process from your implementation to not worry about bidbots outbidding their own bid. A bidbot will keep bidding even if the current highest bid is its own bid.

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

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.

End of Exam Enjoy your Summer!

	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