Com S 228 --- Introduction to Data Structures

			     HOMEWORK 6:
	       Structured ADTs and Algorithm Efficiency
		 (File $Date: 1995/03/03 17:46:25 $)

Due: problem 2, at the beginning of your discussion section week of March 2;
     problem 5, at the beginning of class on March 6.

In this homework, you will learn about the client-side view of structured ADTs.
The idea is to give you a framework for the material to follow in subsequent
chapters, which focuses more on the implementation-side view.
You'll also learn about how to estimate the efficiency of algorithms.

PLEASE NOTE: For each programming problem, hand in a printout of
your code files, and your transcript of testing.
Your transcript must be run on the Com S department machines
(use the Unix command ``script''); it should show your testing.
Your transcript and each file you print should have the file name
and your information (your ~/.me file as in HW0) at the top as comments.
You must use comments as we are doing in class
(see /home/cs228/public/assertion-notation.txt for details).
We will be grading on these comments now.

For additional practice, we suggest that for at least some of the problems,
you write out a solution on paper first.  This is more like what the test
will be.  When you are happy with your paper version, try it on the
computer.  (Note that you must hand in a printout and a transcript, however.)


HEADINGTON & RILEY: 4

1. (suggested practice)
   Do some of the exercises in Headington and Riley's book for chapter 4
   (pp. 191-194).  I suggest at least exercises 4.1(a,c), 4.2(a,d), 4.3(a,d),
   4.4(a,b), 4.5(a,b), 4.6, 4.8.  Do what parts seem useful to you,
   then look at the answers, which are at the end of the book,
   in pages A-175 to A-176 for these problems.

2. (50 points)
   Do programming project 4.3 on pages 196-97 of Headington and Riley's book.
   The code for the CharStack class, in files cstack.h and cstack.C
   is in /home/cs228/public/HR; also the object module is in the library
   /home/cs228/public/lib/libcs228.a, and the header file is in the directory
   /home/cs228/public/include.  (So as in previous homeworks, you can link
   with the flags -L/home/cs228/public/lib -lcs228 and compile with the flag
   -I/home/cs228/public/include to get the header files.)
   You are *not* to modify cstack.h or cstack.C in any way.
   You *must* use at least one instance of CharStack
   in a significant way in your program (that's the whole point).

   Hand in a printout of your testing and the program files.

   In your discussion section, you'll discuss your solution
   with another class member, and will have an opportunity
   to ask questions and discuss solutions with the class as a whole.
   So be sure to write your code clearly, and pay particular attention to
   the specification comments.  We won't check the details
   of your work, as that will be the subject of the discussion.
   So don't worry (too much) if it isn't exactly right.
   We will check that what you hand in has the right parts
   (a printout of each file, labeled correctly with comments at the top,
   and a transcript).

3. (40 points extra credit)
   Do programming project 4.5 on page 197.  Look in /home/cs228/public/HR
   for versions of the class CharSet, in the files cset.h and cset.C.
   These are also in library (see the previous problem).  You must use
   the CharSet class in a significant way to solve this problem.


HEADINGTON & RILEY: 12.1-3, 12.9

4. (suggested practice)
   Do some of the exercises in Headington and Riley's book for sections 12.1-3
   (pp. 594-598).  I suggest at least exercises 12.1-2(a,c,e,g,j,l,o),
   12.3(a,c,e,g,i), 12.5(a,c,e,g), 12.6(a,d,h), 12.7(a,c).
   Do what parts seem useful to you,
   then look at the answers, which are at the end of the book,
   in pages A-184 to A-185 for these problems.

5. Do the following exercises in Headington and Riley's book (pp. 594-598).
   (10 points) 12.1(b,d,f,n,q)
   (10 points) 12.2(b,d,f,n,q)
   (10 points) 12.3
   (16 points) 12.5(b,d,f,i)
   (15 points) 12.6(b,e,f)  Consider the value of X to be input to each part;
                       as if ``cin >> X;'' was prefixed to each part of 12.6.
                       That is, do not treat X as a known constant in 12.6.
   Clearly label your answers with Headington and Riley's exercise number
   and parts.  (You don't have to type this.)

6. (20 points extra credit)
   Prove the statements in the box at the bottom of page 546 in Headington
   and Riley's book, and give a counterexample for those that are not true.
   (Hint: use the definition of big-O notation.)