Problem Set 5: Hints

sources = ["first source", "second source"]

If you can read these words, you are doing it correctly.

Question 1

The global environment contains all the Scheme primitives, but we need only show the new definitions. The only important ones for this question are make-new-table which is a procedure, amd bidders which is defined as (make-new-table (list 'name 'email)). To evaluate (make-new-table (list 'name 'email)) we evaluate the body of the procedure that make-new-table evaluates to in an environment pointing to a frame where its parameter (fieldlist) is bound to the value of (list 'name 'email).

Hint 2:

The body of make-new-table is (cons fieldlist null). Evaluating fieldlist in the application environment produces the value of (list 'name 'email), hence the value of bidders is a cons cell where the car is (list 'name 'email) and the cdr is null.

Question 2

The state after (define t1 (make-new-table (list 'name 'email))) is the same as in question 1, except t1 instead of bidders. The (set-car! (table-fields t1) 'nom) expression replaces the value of the car part of (table-fields t1) with 'nom. The value of (table-fields t1) is just (car t1).

Hint 1 for Part A:

So, (set-car! (table-fields t1) 'nom) replaces the 'name in (car (car t1)) with 'nom. Then, (set-cdr! t1 t1) replaces the value in the cdr part of t1 with the value of t1. The value of t1 is the cons cell t1 points to.

Hint for Part B:

Looking at the diagram, we see that the cdr of t1 is t1. So, everytime we evaluate (cdr t1) we get t1. We can keep evaluating cdr forever, but never get to null.

Note that the primitive length procedure behaves differently:

> (length t1)

expects argument of type <proper list> given #0=(1 . #0#)

Question 3

We use append! since we want table-insert! to modify the table in place.

Hint 2 for Part A:

If we used append it would create a new list instead of modifying the old one. We could define table-insert! using append like this:

(define (table-insert! table entry)
  (assert (= (length entry) (length (table-fields table))))
    (set-car! table (append (table-entries table) (list entry))))
    

Hint 1 for Part B:

To mutate a list, we need a cons cell to modify. But, null is not a cons cell.

Hint 2 for Part B:

There is no way to mutate null — if we could, it would change the value of null everywhere! For append! to work, the list passed in must not be null, so append! has a cons cell to mutate using set-cdr!.

Question 4

Use table-insert!.

Hint 2 for Part A:

For post-item!, use table-insert! into the items table to insert (list something something-else).

Question 5

What is the running time of append!? Since it is built-in, we have to guess at its running time. See Section 3.3 of the Wizard book (the optional textbook for this class: click on the "book" heading at the top of this page to get there) for an example definition.

Hint 2:

If we use this definition for append! ...

(define (last-pair x)
  (if (null? (cdr x)) x (last-pair (cdr x))))

(define (append! x y)
  (set-cdr! (last-pair x) y) x)

Hint 3:

Our insert-bid! procedure applies table-insert! to the bids table and the new bid. Creating the new bid using list and the three operands is Θ(1). The table-insert! procedure calls (append! (table-entries table) (list entry))).

Question 6

Use list-filter.

Hint 2:

Use list-filter on the list of table-entries from the given table. Make a new table containign with the result.

Hint 3:

When you use list-filter, you need a predicate. Consider this helper function:

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

Question 7

Give your answer in terms of n, the number of entries in the input table, and f, the number of fields in the input table.

Hint 1:

If the number of fields is not constant, then we need to consider how the work required by find-field-number and get-nth scales with the selected field. Both procedures need to cdr down a list until the matching entry is found. Hence, they are Θ(m) where m is the number of elements in the input list. As used in table-select, m is the number of fields in the table in both cases.

Question 8

Try sorting all of the bids by the bid amount, and then selecting the first one. You could also use find-best.

Hint 2:

Use something like (if (> (length sorted-bids) 0) (car sorted-bids) ...) to handle the no-bid case.

Question 9

Use let to make a variable called bidder-entry that holds the table-entries from a table-select of the bidders table where 'name matches (make-string-selector bidder).

Hint 2:

You can check the length of bidder-entry to find invalid bidders and multiple matching bidders.

Hint 3:

Use let to make a variable called item-entry that holds the table-entries from a table-select of the items table where 'item-name matches (make-string-selector item).

Hint 4:

You can check the length of item-entry to find invalid items and multiple matching items.

Hint 5:

Use get-highest-bid. You have the new high bid if the result is null or if (> amount (get-nth highest-bid (find-field-number bids 'amount))).

Question 10

Use list-filter.

Hint 2:

Make a new table where the entries are determined by list-filter with a custom predicate. From each entry, extract the item name and the current bid. Then call get-highest-bid. If the current bid is equal to the highest bid, keep that entry!

Question 11

Use these two variables:

• m — the total number of items in the auction
• b — the total number of bids in the auction

[an error occurred while processing this directive]