University of Washington
CSE 326, Data Structures
Homework #2
Due: Monday, January 29, 2001, 1:30pm

Winter 2001								January 22, 2001
Donald Chinn

	Homework is due at the beginning of class on the day specified.
Any homework turned in after the deadline will be considered late.
Late homework policy: You may turn in your homework after the deadline
but before the beginning of the next lecture after it is due, but at a
cost of a 20% penalty.
	Please staple all of your pages together (and order them
according to the order of the problems below) and have your name on
each page, just in case the pages get separated.  Write legibly
(or type) and organize your answers in a way that is easy to read.
Neatness counts!  Also, show your work and explain your reasoning.
	For each problem, make sure you have acknowledged all persons
with which you worked.  Even though you are encouraged to work
together on problems, the work you turn in is expected to be your own.
When in doubt, invoke the Gilligan's Island rule (see the course
organization handout). 

* * *
Regular problems (to be turned in) :

1. Weiss, 2.5.  This is the same problem as in HW #1, except find f(N) and g(N) such that:
f(N) > 0 for all N > 0, and g(N) > 0 for all N > 0.
    (The functions are always positive for N > 0.)
and
  lim_{N->infinity} f(N) = infinity
and
  lim_{N->infinity} g(N) = infinity .
    (The functions tend to grow to infinity as N grows to infinity.)

2. Suppose you have a list of 10,000 names in alphabetical order in
an array, and you must frequently look for various names.  It turns
out that 20% of the names account for 80% of the table lookups.
Instead of doing binary search over all 10,000 names every time,
consider the possibility of splitting the table into two, a
high-frequency table of 2000 names, and a low-frequency table of the
remaining 8000 names.  To look up a name, you will first use binary
search on the high-frequency table, and 80% of the time you will not
need to go on to the second stage, where you use binary search on the
low-frequency table.  Is this scheme worth the effort?  Justify your
answer by finding the number of iterations that are executed in the
binary search algorithm (on average for names in the array), both in
the new scheme and in a binary search of a single table of 10,000 names.

3. 3.34b.  (Please look at 3.34a first.)  Explain why your
algorithm works.

4. 4.4.  Prove the statement by induction on N.
(Problem #5 is on the next page.)

5. 4.40.  You do not need to write C++ code: pseudocode and/or an
explanation for how the code works is sufficient (be clear, however).
You do not need to prove the linear time bound.  Instead, explain why
your algorithm runs in linear time.

* * *

Suggested problems (highly recommended, but not to be turned in) :
1.  Weiss, 3.9.
2.  3.10.
3.  3.17a, b.
4.  3.25a.
5.  3.34a.
6.  4.6.
7.  4.22.
8.  4.31.
9   4.32.