University of Washington
CSE 326, Data Structures
Homework #1
Due: Friday, January 12, 2001, 1:30pm

Winter 2001								January 5, 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.  For this assignment, no late homework will
be accepted.  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!  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, 1.13
2.  a. 2.1
    b. 2.5
3.  2.12
4.  2.15.  Explain briefly why your algorithm works correctly.
5.  Consider the following problem that your boss at work has given you.  You are given
a file that contains approximately (but no more than) 4,000,000,000 32-bit unsigned
(i.e., positive) integers.  You are to devise an algorithm that produces a 32-bit unsigned
integer that is not in the file.

    An easy solution to this problem would be to create an array A of size 232 (one for
each integer) to keep track how many times integer i appears in the file.  Initially, the
array is all zeros.  The algorithm reads through the file sequentially and if it encounters
the integer i, it increments A_i.  When it reaches the end of the file, it then finds th
first element of A that is zero and returns that index as the answer.
    It is an easy solution, but it requires far too much space to be practical
(4 gigabytes if the array is composed of 8-bit integers — even with a bit array, it would
take 512MB).  You need to devise an algorithm that uses only a few extra bytes of memory,
but it is allowed to use some temporary scratch files.  (Hint: use a binary search
technique to eliminate half of the numbers in the file.)

    Let’s suppose that all in-memory computations take no time (compared to a disk read,
basic memory operations are very fast) but that reading an integer from a file and
writing an integer to a file each take one time unit.  If there are N integers in the file,
exactly (no big-Oh) how long does your algorithm take in the worst case?

* * *

Suggested problems (highly recommended, but not to be turned in) :
1. Prove by induction on n that
     n
   ----
   \     2       n (n+1) (2n+1)
   /    i   =    --------------
   ----                6
    i=1

2.  Weiss, 2.2
3.  2.4
4.  2.7
5.  2.11
6.  2.19
7.  2.20
8.  2.31
9.  2.32