Problem 1
Suppose you have a big stack of 4500 index cards, each one containing the
first name and last name of a Princeton undergrad. If the cards
are sorted in alphabetical order by last name, you could use binary search
to find any specific last name quickly.
Suppose instead that people want to do lots of searches that find everyone with a specific first name. ("I want a list of all people named Jennifer." "I need to find everyone named William.")
(a) In what order would you arrange the index cards so that such first-name searches are as efficient as possible?
One good method is to sort the index cards alphabetically by first name.
(b) Describe as precisely as you can the search algorithm that you would use for your organization of the names.
Assuming the index cards are sorted alphabetically by first name, I would use the binary search algorithm to find one card with the requested first name. I would then search backward sequentially until I found the first card with the requested name; then search forward sequentially from the result of the binary search until I found the last card with the requested name; then I would output all of cards between the "first" one and the "last" one.
Problem 2
Suppose that you want to make a database of Princeton undergrads, and you
want to be able to search for a person with a given first name,
or with a given last name.
That is, some of your "customers" will want to search
for a specific first name, and some will want to search for a specific last
name. Explain how you would organize your data, and how you would conduct
your searches, to allow both kinds of searches to be efficient.
The easiest solution is to make two piles of cards, with each pile containing a card for each student. Then we can sort one pile by first names, and sort the other pile by last names. When we get a request for a first name, we search the first pile (by binary search); when we get a request for a last name, we search the second pile (by binary search).
Problem 3
Selection sort is a sorting algorithm that works like this: start with all
items in a pile; look through all of the items in the pile to find the
smallest one, then remove it; search through the remaining pile to
find the smallest remaining item, and remove it; and so on, removing items
from the pile one by one until the pile is empty. Place the removed items
in a line, in the order in which you remove them.
Roughly how many total steps does selection sort require to get the full sorted list? (Hint: if there are N items, the size of the pile will go down from N to zero; the average size of the pile is N/2.)
We have to look through the pile about N times: once with N items in the pile, then with N-1 items in the pile, then with N-2 items, then N-3, and so on down to one. On average, there are N/2 items in the pile, so on average each time we look through the pile takes about N/2 steps. To get the total number of steps, we multiply the number of times we go through the pile (N) by the number of steps for each time through the pile (N/2), to get N squared, divided by 2.
Problem 4
Here is a recursive program. Assume that it is originally given a positive
value of n. What does it do?
function mystery(n)
if (n=0) then return;
else
if (n is even) then
mystery(n/2)
print "0"
else
mystery((n-1)/2)
print "1"
(Hint: try it for some (small) examples of n, and try to spot the
pattern. Then convince yourself that your pattern is the right one.)
This program prints out n in base-2 notation. We can guess the pattern after trying it for n=1 (prints "1"), n=2 (prints "10"), n=3 (prints "11"), n=4 (prints "100"), and so on.
Intuitively, the algorithm works by first figuring out what number goes in the last position (the ones place), and then calling itself recursively to figure out the higher digits. Once it's done figuring out and printing the higher digits, it prints the value of the ones place; that puts the value of the ones place at the end of the number, where it belongs.