Com S 228 --- Introduction to Data Structures

			     HOMEWORK 10:
			     Linked Lists
		 (File $Date: 95/04/07 09:24:56 $)

Due: problem 2, at the beginning of your discussion section week of April 6,
     you might also want to look at problem 3 for your discussion section;
     problem 4, at the beginning of lecture, April 10

In this homework, you will learn about linked lists.
You will note that with this homework, our study of data structures
no longer requires new features of C++.  However, it builds on our study
of pointers and dynamic data.

You are now allowed to freely use recursion in your homework solutions.
The use of recursion is often appropriate for list algorithms.

PLEASE NOTE: For each programming problem, hand in a printout of
your code files, and your transcript of testing.
Your code must only use standard features of C++,
and your transcript must demonstrate that it would work on the Com S machines.
We recommend testing on the Com S department machines to ensure this
(use the Unix command ``script'').
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 are 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: 8.1-6, 8.8, pp.366-73

1. (suggested practice)
   Do some of the exercises in Headington and Riley's book for chapter 8
   (pp. 377-381).  I suggest at least exercises 8.1(a,b), 8.2(a,b),
   8.3(a), 8.4(a,c), 8.6(a), 8.9(b) and 8.11(a).
   Do what parts seem useful to you, then look at the answers,
   which are at the end of the book in pages A-179 to A-181 for these problems.

2. (40 points) 
   Do exercise 8.11, parts b and c on page 381 of Headington
   and Riley's book.  Clearly label each part.

   As usual, hand in a printout of your code, test harness, and test output.

   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.  As usual for problems handed in
   during discussions, we won't check the details of your work,
   because 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. (suggested practice)
   Design a program to solve the problem posed in Headington and Riley's
   programming project 8.5 on pages 384-5.  The design should be documented
   by (a) a description (or declaration) of the main data structures, and
   (b) PRE, MODIFIES, and POST comments for the main program,
   and for each helping function.  (This is as we did for homework 4.)
   (c) You must also write stubs for each function, and (d) do top-down testing
   (see p. HR 40-41).

   Hint: you may use a doubly-linked list for this problem if you wish.

4. (100 points)
   Finish the implementation of programming project 8.5 on page 384-5
   of Headington and Riley's book.
   (Hint: you may use a doubly-linked list for this problem if you wish.)

   As usual, hand in a printout of your code and test output.

   As part (or all) of your test output, you must run the test input
   in /home/cs228/public/homework/hw10.dat.  You can do this, on Unix,
   if your executable is called LineEdit.exe, by running the following
   command.

	./LineEdit.exe < /home/cs228/public/homework/hw10.dat


HEADINGTON & RILEY: 8.7 (throuigh p. 366)

5. (suggested practice)
   Do some of the exercises in Headington and Riley's book for chapter 8
   (pp. 377-381), number 8.7.  I suggest at least part (a).
   Do what parts seem useful to you, then look at the answers,
   which are at the end of the book in page A-180 for this problem.

6. (40 points extra credit only)
   Do programming project 8.3, parts b and c, in Headington and Riley's book
   page 382.  That is, implement the specification in
   /home/cs228/public/HR/clist.h (the abstract list type from chapter 4)
   using a singly-linked list and the appay implementation of singly-linked
   lists.

7. (80 points extra credit only)
   Do programming project 8.4 in Headington and Riley's book pages 382-4.

HEADINGTON & RILEY: 7

8. (extra credit)
   Run your test harness for the String class against the String class
   in the Com S 228 library (use -L/home/cs228/public/lib -lcs228 to link).
   If you are the first person to report an error in the implementation of
   the class String by email to leavens@cs.iastate.edu, you will get 10 points
   extra credit.  Be sure that the error is an error in the implementation,
   and not in your test harness!

9. (extra credit)
   Look at the specification and implementation of the class IntFlexVec
   in /home/cs228/public/examples/IntFlexVec.
   If you are the first person to report an error in either the specification
   or in the the implementation of the class IntFlexVec by email to
   leavens@cs.iastate.edu, you will get 10 points extra credit.
   Be sure that the error is really an error first!