Collaboration Policy - Read Very Carefully

If you wish to work on this assignment alone or with any one student of your choice, you need to send me an email by 11:59 pm, Sunday, 9 October containing who you want to work with (or that you want to work along), and your answer to Question 4 (both parts). (As long as you send evidence of a reasonable effort, you will be permitted to work with your selected partner or alone. It doesn't matter if your answer is correct.)

If you don't send me such an email, you will be assigned a partner for PS5.

Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways. You may consult any outside resources you wish including books, papers, web sites and people. If you use resources other than the class materials, indicate what you used along with your answer.

• Learn to program using state and mutation.
• Learn how mutation changes the Scheme evaluation rules.
• Learn about databases and SQL commands.
• Save the University from further cuts to "non-essential" services.

Download: Download ps5.zip to your machine and unzip it into your home directory J:\cs150\ps5. This file contains: ps5.ss — A template for your answers. You should do the problem set by editing this file. auction.ss — Partial code for setting up an auction. database.ss — Partial implementation of a database. listprocs.ss — Some useful procedures for manipulating lists (you have seen most of them already in class).

Background

Fortunately, the University was able to get "Character" status from the Commonwealth, which gives it more power to control its own destiny by raising tuition and selling off assets. The Board of Transients has decided the time for drastic measures has arrived, and they will conduct an auction to raise money. To avoid paying fees to a commercial auction service, they have asked you do develop an auction service for them.

The auction service will be built using a database. A database is just a way of storing and manipulating a large amount of structured data. For this problem set, you will implement a database and use it to implement an auction service. Our database is controlled using Scheme procedures that are similar to the SQL commands used to control nearly all commercial databases. In Problem Set 8, you will build a dynamic web site that uses SQL commands to interact with a database.

Data in a database is stored in tables. The fields of a table describe the data and are not mutable. The entries of a table are the data, and can be changed. We will represent a table using a cons pair where the car is a list of the table fields and the cdr is a list of the table entries. These definitions are found in database.ss:

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

     (define bidders (make-new-table (list 'name 'email)))
     (define items (make-new-table (list 'item-name 'description)))
     (define bids (make-new-table (list 'bidder-name 'item-name 'amount)))

Question 2: a. Draw the global environment after the following expressions are evaluated (starting in a clean global environment where make-new-table, table-fields and table-entries are defined as above): (define t1 (make-new-table (list 'name 'email))) (set-car! (table-fields t1) 'nom) (set-cdr! t1 t1) b. Suppose we then evaluate: (define (length lst) (if (null? lst) 0 (+ 1 (length (cdr lst))))) (length t1) Explain why the evaluation of (length t1) never terminates.

Try evaluating the expressions in Question 2 in DrScheme. Also evaluate t1 and see if you can figure out what the printed value means.

Inserting Entries

The table-insert! procedure inserts an entry into a table. We follow the Scheme (and Yahoo!?) convention of using an ! at the end of the names of procedures that mutate state. You should follow this convention also.

You shouldn't need to change the definition of table-insert!, but you should be able to understand it (defined in database.ss):

(define (table-insert! table entry)
  (assert (= (length entry) (length (table-fields table))))
  (if (null? (table-entries table))
      (set-cdr! table (list entry))
      (append! (table-entries table) (list entry)))
  (void)) ;;; don't evaluate to a value

(define (assert pred)
  (if (not pred) (error "Assertion failed!")))

Question 3: a. Why does the definition of table-insert! use append! instead of append? (Your answer should clearly explain what would go wrong if we used append.) b. Why does the definition of table-insert! need to do something different in the case where (table-entries table) is null? Hint: try evaluating (define lst null) (append! lst 3) lst Note that DrScheme's append! behaves differently then the append! defined in SICP Exercise 3.12.

Our auction service will need procedures for adding bidders, posting items for sale and bidding on items. For now, define simple procedures that insert entries in the appropriate tables:

• add-bidder! should take two parameters (name and email) and add an entry in the bidders table.
• post-item! should take two parameters (name, description) and add an entry in the items table
• insert-bid! should take three parameters (bidder, item and amount) and add an entry in the bids table

We have provided a table-display procedure in database.ss for printing out a table. (You don't need to understand the details of how table-display works.)

If you define add-bidder!, post-item! and insert-bid! correctly, you should obtain the following interactions:

> (table-display bidders)

name                       email                      
-------------------------  -------------------------  

> (add-bidder! "Tim Koogle" "tk@yahoo.com")

> (add-bidder! "Mick Jagger" "mick@stones.com")

> (add-bidder! "Tina Fey" "tina@snl.com")

> (add-bidder! "Dave Matthews" "dave@dmb.com")

> (table-display bidders)

name                       email                     
-------------------------  ------------------------- 
Tim Koogle                 tk@yahoo.com              
Mick Jagger                mick@stones.com
Tina Fey                   tina@snl.com
Dave Matthews              dave@dmb.com              

Selecting Entries

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

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

Question 5: Define the table-select procedure. You may find the find-element-number, get-nth and filter procedures defined in listprocs.ss useful (but are not required to use them).

If your table-select is working correctly, you should see the following interactions: (Remember our University is completely fictional. The bid amounts should not be construed to have anything to do with the actual value of any aspects of any real Universities with which you might be familiar (or with the generosity of actual University alumni who might have similar names.)

> (insert-bid! "Tim Koogle" "SEAS" 10000000)

> (insert-bid! "Dave Matthews" "CLAS" 2000000)

> (insert-bid! "Mick Jagger" "SEAS" 15000000)

> (table-select bids 'item-name (lambda (pitem) (string=? pitem "CLAS")))

((bidder-name item-name amount) ("Dave Matthews" "CLAS" 2000000))

> (table-display (table-select bids 'item-name (lambda (pitem) (string=? pitem "CLAS"))))

bidder-name                item-name                  amount
-------------------------  -------------------------  -------------------------
Dave Matthews              CLAS                       2000000

> (table-entries (table-select bids 'item-name (lambda (pitem) (string=? pitem "SEAS"))))

(("Tim Koogle" "SEAS" 10000000) ("Mick Jagger" "SEAS" 15000000))

> (table-entries (table-select bids 'item-name (lambda (pitem) (string=? pitem "Rotunda"))))

()

> (table-entries (table-select bids 'amount (lambda (pamount) (> pamount 10000000))))

(("Mick Jagger" "SEAS" 15000000))

> (table-entries
    (table-select
      (table-select bids 'amount (lambda (pamount) (<= pamount 10000000)))
      'bidder-name
      (lambda (pbidder) (string=? pbidder "Tim Koogle"))))

(("Tim Koogle" "SEAS" 10000000))

Selects can be nested. Here we use (table-select bids 'amount (lambda (pamount) (<= pamount 10000000))) to produce the table of all bids over 10000000, and then use another table-select to select the bids from that table where the bidder name is "Tim Koogle". To make sure you understand table-select, produce a different expression that will evaluate to the same table by selecting the name first and then the amount.

Placing Bids

• Only allow bids on items that are up for sale. If a bid is made for an item that does not match the name of an item in the items table, the place-bid procedure should report an error and not modify the bids table.
• Only allow a new bid on an item if the amount of the bid exceeds the amount of the highest earlier bid for the item. If a bid is made that is equal to or less than that amount, place-bid should report an error and not modify the bids table.

Your get-highest-bid procedure should work like this:

> (setup-tables)

> (get-highest-bid "SEAS")

("Mick Jagger" "SEAS" 15000000)

> (get-highest-bid "Rotunda")

()

You may want to use the printf procedure builtin to DrScheme to generate the output. For example,

      (printf "~a is now the high bidder for ~a: $~a~n" bidder item amount)

You should get interactions similar to these:

> (setup-tables)

> (place-bid "Tim Koogle" "SEAS" 20000000)

Tim Koogle is now the high bidder for SEAS: $20000000

> (place-bid "Mick Jagger" "SEAS" 18000000)

Bid amount does not exceed previous highest bid: (Tim Koogle SEAS 20000000)

> (table-display bids)

bidder-name                item-name                  amount                     
-------------------------  -------------------------  -------------------------  
Tim Koogle                 SEAS                       10000000                   
Dave Matthews              CLAS                       2000000                    
Mick Jagger                SEAS                       15000000                   
Tim Koogle                 SEAS                       12000000                   
Tim Koogle                 SEAS                       20000000                   

> (place-bid "Mick Jagger" "SEAS" 22000000)

Mick Jagger is now the high bidder for SEAS: $22000000

> (place-bid "Dave Matthews" "AFC" 1000000)

Dave Matthews is now the high bidder for AFC: 1000000

> (place-bid "Dave Matthews" "Rotunda" 1000000)

The Rotunda is not for sale!

> (place-bid "Dave Evans" "SEAS" 10000000000)

Dave Evans is not an authorized bidder!

Ending the Auction

Question 9: Define a procedure end-auction! that completes the auction. It should go through every item in the items table. If there are any bids, the item is sold to the highest bidder and a message displays the winning bid. If there are no bids on the item, the item remains unsold.

Here's an example:

> (setup-tables)

> (place-bid "Tim Koogle" "SEAS" 18000000)

Tim Koogle is now the high bidder for SEAS: 18000000

> (place-bid "Mick Jagger" "CLAS" 1000)

Mick Jagger is now the high bidder for CLAS: 1000

> (end-auction!)

Congratulations Tim Koogle!  You have won the SEAS for $18000000.
   Please drop off the cash under Mr. Jefferson's statue.
Congratulations Mick Jagger!  You have won the CLAS for $1000.
   Please drop off the cash under Mr. Jefferson's statue.
No bids on AFC.

Try some sample auctions to demonstrate your program. See if you can make enough money to save the University, but be careful not to sell off too many important assets — we will revisit the University in Charlottansville in Problem Set 6.

Question 10: Describe the time complexity of your end-auction! procedure. (You answer should use Θ notation, should clearly define the meaning of all variables you use in your answer, and should include a convincing explanation of why it is correct.)

Credits: This problem set was created for CS200 Spring 2003 by Katie Winstanley, Rachel Dada, Spencer Stockdale and David Evans, revised for CS200 Spring 2004 by Sarah Bergkuist and David Evans, and revised for CS150 Fall 2005 by David Evans. Any similarity between the events depicted in this problem set and the goings on at a real University are purely coincidental, especially the parts about needing to pay millions of dollars to replace a basketball coach and the Board of Visitors deciding to spend thousands of dollars to hide empty seats in the new basketball arena at the same meeting where they discussed increasing student housing rates because the first year dorms are deteriorating.