CS 37

Clab 10:

We ended last clab looking at the text's permutations function. If you are not clear on it, please stop one of us with questions after I finish talking.

If you have not already done so, make a week4 subdirectory in your cs37 directory (mkdir week4) and move into that directory (cd week4). Now copy all the files from my pub subdirectory: ~cfk/pub/cs37/week4/ as shown below.

thyme.cs.swarthmore.edu% cd cs37 thyme.cs.swarthmore.edu% mkdir week4 thyme.cs.swarthmore.edu% cd week4 thyme.cs.swarthmore.edu% cp ~cfk/pub/cs37/week4/* . thyme.cs.swarthmore.edu% ls bigdb.txt ltdb.txt queenspart.scm rost1.txt thyme.cs.swarthmore.edu%

Now a challange

Finish the 8-queens problem, ex 2.42 page 124-126. You can find it by scrolling up a couple of screens from: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.4
They give you: (define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size)) All you have to do is supply the missing functions. :-) I'll say a few words about this. The material in queenspart.scm should help you out. However, I don't want you to work on it in this clab unless you have finished everything else.

Take a look at the contents of ltdb.txt and bigdb.txt. To do this you can use cat or more or less.

Now start up drscheme. Put the following in the definitions window and save it in your week4 subdirectory.

(define inport (open-input-file "bigdb.txt")) (define bigdb (read inport)) (close-input-port inport) (define inport (open-input-file "ltdb.txt")) (define litdb (read inport)) (close-input-port inport) Now press the run button and then evaluate bigdb and litdb in the interaction window. They look like a mess but I'll explain them.

Professor K maintains a database of students in his class as a binary search tree (BST) organized by student number (as key value). bigdb.txt is such a BST with student numbers and homework grades generated by a random number generator. From time to time students ask Professor K what their homework average is. The kind hearted professor has asked you to implement some procedures to handle this and some other tasks. Fortunately for you (at this point in the course), Professor K is so wonderful that no students ever drop his course nor will you ever have to change an existing record. All you have to do is implement the procedures requested in Lab4 . This is still not simple so you may want to start this assignment earlier than the previous ones and make sure you use abstraction barriers. findbykey should be fast because it should exploit the BST property. findbyname will have to possibly look at every node and will not be as fast. This assignment is not exactly like any of the programs on pp. 155-159, but a good understanding of the material there will go a long way to helping you with this assignment.

We'll take a look at litdb together and I'll demonstrate a couple of the functions requested.

A good warm-up for the Lab4 is to do exercises 2.63 and 2.64. We'll do them next clab. Since they are for set representations, let's play with simpler set representations by doing exercise 2.59 on page 153 and exercise 2.61 on page 155 today.

ask any questions you may have.