CS1321 Fall 2002
Homework 16

Due before 8 a.m. Wednesday, Dec. 5, 2001

Instructions:

TURN IN THIS ASSIGNMENT USING WEBWORK!!!
Do this homework using DrScheme. (Save the file as a ".scm" file--that is, with a .scm extension.)
At the top of your file, include the student info portion of the HW Skeleton (Name, GT Number, HW, Course, Instructor, Lecture Time).

Note:

Your parameters must be in the same order as they are shown here. If you are unsure, ask your TA. You will lose credit otherwise.
Your functions should be named exactly as they are shown in each problem.
Follow the HW Skeleton, these homeworks will be autograded and must be in the specified format. You will lose credit otherwise.
Any submissions which don't execute cleanly (i.e. no errors when you click Execute) may receive a grade of zero.
If you do not submit a .scm file, you may receive a grade of zero.
Remember that you must be in "Advanced Student Mode ".
For all problems, you should read the words program and function to mean "program or group of programs," or "function or group of functions."

Problem 1

Do ~~29.4.7~~ 29.4.7 from the hardbound book/ 29.3.7 from the online book. Name your function norm.

Problem 2

Do ~~29.4.9~~ 29.4.9 from the hardbound book/ 29.3.9 from the online book. Name your function binary-contains?.
The signature for the function looks like this:
;; binary-contains? : (vectorof number) number -> number or false

You are to assume that the vector of numbers passed in is already sorted in ascending (increasing) order. Return the index of the second parameter if that number is indeed found in the vector. If it is not, return false.

You are required to use a binary-search of the vector to find the number in the vector.

Problem 3

Develop a program that manages a stack data structure. Provide the following functions:

push
pop
is_empty?

push allows you to add something to the stack. pop removes and returns the top item from the stack. is_empty? is a predicate function that returns true if the number of items in the stack is 0, false otherwise.

Use a vector to implement your stack. Create your stack with a call to the function create-a-stack, which takes one parameter - the maximum size allowed for your stack. Use lexical closure as covered in the lecture on November 20, 2001 to maintain the state of your stack, which will include not only the vector that is used to hold the data of the stack, but also the number of elements currently in the stack (starts off at 0), and perhaps also the max size the stack is allowed to reach. (This problem is similar to problem 37.4.2 in the book.)

If push is unable to add the item to the underlying vector (because it is full for example) then it should return false (when successful, have it return true). Likewise if one requests a pop operation on an empty stack, return false. (A successful pop operation returns the top item from the stack.)

To create a stack from your function, create-a-stack, you should be able to make a call like the following. You also add items and remove items from the stack as shown.

(define to-do-stack (create-a-stack 50))
((to-do-stack 'push) 'laundry)
> true
((to-do-stack 'push) 'wash-car)
> true
((to-do-stack 'pop))
> 'wash-car
((to-do-stack 'push) 'vacuum)
> true
((to-do-stack 'pop))
> 'vacuum
((to-do-stack 'pop))
> 'laundry

You will be able to also create a different stack by calling create-a-stack again.

(define phone-calls-to-make (create-a-stack 20))
((phone-calls-to-make 'push) 'rents)
> true
((phone-calls-to-make 'push) 'santa)
> true
((phone-calls-to-make 'is_empty?))
> false

(define will-fill-up-stack (create-a-stack 2))
((will-fill-up-stack 'push) 'one)
> true
((will-fill-up-stack 'push) 'two)
> true
((will-fill-up-stack 'push) 'three)
> false

Problem 4

Add a display routine to the address book example of figure 115 (p. 583) in the book. Call that function display_book. 'display must be allowed as a message possibility for the service-manager, and when given, 'display should invoke a function that will return the entire contents of the phonebook specified. To implement this function, just return literally the address-book list from that particular phonebook. (Do not do any formatting.)

Creating two distinct phonebooks called friends and business is achieved by the following:
(define friends (make-address-book "Friends of Mine"))
(define business (make-address-book "Colleagues of Mine"))

Adding some entries into the various books can be done thusly:
((friends 'add) 'Toni 311)
((friends 'add) 'Eric 345)
((friends 'add) 'Jason 21)
((business 'add) 'Bill 2)
((business 'add) 'Dan 99)

Calls to invoke your newly added feature will look like the following:
((friends 'display))
((business 'display))

Problem 5

To your address book code resulting from your answer to #4 above, allow the message 'update to be handled. Update has this meaning - update the phone number associated with the given name if it is in the phone book and return 'okay. If the name given is not in the phone book, return 'name-not-found.

Just as above, creating two distinct phonebooks called friends and business is achieved by the following:
(define friends (make-address-book "Friends of Mine"))
(define business (make-address-book "Colleagues of Mine"))

Adding some entries into the books can be done thusly:
((friends 'add) 'Toni 311)
((friends 'add) 'Eric 345)
((friends 'add) 'Jason 21)
((business 'add) 'Bill 2)
((business 'add) 'Dan 99)

Calls to invoke your newly added feature and their expected results will look like the following:
((friends 'update) 'Bill 1)
> 'name-not-found
((friends 'update) 'TomCruise 16)
> 'name-not-found
((friends 'update) 'Toni 10)
> 'okay
((business 'update) 'Bill 100)
> 'okay
((business 'update) 'Dan 100)
> 'okay
((business 'update) 'Bubba 10)
> 'name-not-found

In addition to that level of testing of this new feature, double check in your testing section that both phonebooks ended up being updated correctly, send the message 'display to each phonebook. ((friends 'display)) ((business 'display))

Problem 6

Do 40.4.2 from the book with this change: write your function so that it works for any length vector. It is to accept a vector of an unknown length and set all slots to 0. Use a do loop to do this. (p. 603) Make sure your function will even work for a vector of length zero.

(clear (make-vector 100 5))
> #100(0)
(clear (vector 15 16 99 26))
> #4(0)
(clear (vector))
>#0()

Problem 7

Do 41.2.7 being sure to use the appropriate mutator as discussed in the text prior to the problem. That is, do not rebuild the structure - instead use the appropriate set-whatever-style mutator. (p. 612)

Problem 8

Do 41.2.20 http://www.htdp.org/2001-11-21/Book/node210.htm#pgcountvowels from the text with this difference.Instead of doing a histogram of the scores directly, divide the score by 10 (integer division, no rounding) and then record the result of that division into your vector of only size 11 rather than 101. (This will help cut down on the size of your test case expected results!) Basically you are forming several groups of scores:
grouping together the scores = 100 (index = 10), the scores 90 <= score < 100 (index = 9), the scores 80 <= score < 90 (index = 8), the scores 70 <= score < 80 (index=7), the scores 60 <= score < 70 (index=6), and so forth down to the scores 0 <= score < 10 (index = 0). For each value you calcualate, increment the count in the vector at the corresponding index.

(histogram '(20 100 100 80 89 99 65 78 98 100 99 98 100 99 0))
> #11(1 0 1 0 0 0 1 1 2 5 4)

(histogram '())
> #11(0)

(histogram '(0 15 25 35 45 55 65 75 85 95 100))
>#11(1 1 1 1 1 1 1 1 1 1 1)

Problem 9

Do 43.1.5 from the text. You are required to use a do loop to perform an in-place reversal of the vector passed into the function as a parameter. (That is, you are not allowed to use a second vector - do the work within the one vector that you have.)

vector-reverse! accepts a vector of any length (0 or greater) and returns the same vector having it's contents reversed. (p. 657)

Example calls:
(vector-reverse! (vector 1 2 3 4 5))
> #5(5 4 3 2 1)

(vector-reverse! (vector 10 20 30 40))
> #4(40 30 20 10))

(vector-reverse! (vector 99 17 16 23 62))
> #5(62 23 16 17 99)

(vector-reverse! (vector 2 2 2 2 2))
> #5(2)

(Parts of this assignment were taken from HtDP, and are the work of Felleisen, Findler, Flatt and Krishnamurthi. However, modifications have been made by the College of Computing, Georgia Tech; for educational purposes, as are necessitated for their introductory CS class.)

CS1321 Fall 2002 Homework 16