COS 111, Fall 2000 - Problem Set 6

Solution set

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?

(b) Describe as precisely as you can the search algorithm that you would use for your organization of the names.

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.

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.)

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"