Com S 228 --- Introduction to Data Structures HOMEWORK 12: Design and Implementation of ADTs and Searching and Hashing (File $Date: 1995/04/23 21:50:07 $) Due: problems 2-3, at the beginning of your discussion section week of Apr. 20, problem 6, at the beginning of lecture, April 25. In this homework, the design of ADTs, and about searching and hashing. 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: 9 1. (suggested practice) Do some of the exercises in Headington and Riley's book for chapter 9 (pp. 432-436). I suggest at least exercises 9.1(a,b), 9.3, 9.5, 9.6, and 9.13(a,c,e,i). Do what parts seem useful to you, then look at the answers, which are at the end of the book in page A-181 for these problems. 2. (20 points) The following questions are to be written out and brought to your discussion section. (a) Is Stack, as specified in HR chapter 4, complete in the sense discussed in class? Why or why not? (b) Several of the ADTs in the book have operations like ``IsFull''. (See, for example, chapter 4's types List, Stack, and Queue.) What is the purpose of such an operation? Do you think they are a good idea, or would the ADTs be better off without having them? What would the consequences of omitting them be for a correct implementation? (optional:) Can you think of a better way to accomplish the same thing without forcing the client to check IsFull? In your discussion section, you'll discuss your answers with another class member, and will have an opportunity to ask questions and discuss answers with the class as a whole. 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. We will check that you made an honest effort on these problems, and will take off points if we believe you are not. 3. (30 points) Quite often in this class we have had occasion to pass an array and its size to a function as arguments. (a) Design a class Array that puts together an array and its size as one object. Make the data members private, and specify a minimal but complete set of operations, using sequences or tuples (or some combination of both) as a primitive model. (b) Do you think that the Array class you designed is useful? (That is, would other people want to use it? Would you?) In your discussion section, you'll discuss your answers with another class member, and will have an opportunity to ask questions and discuss answers with the class as a whole. 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. We will check that you made an honest effort on these problems, and will take off points if we believe you are not. 4. (20 points; extra credit) Implement your design in problem 3, and test it. As usual, hand in a printout of your code, test harness, and test output. 5. (40 points; extra credit) Solve programming project 9.6 on page 437 of Headington and Riley's book. HEADINGTON & RILEY: 12.4-6 5. (suggested practice) Do some of the exercises in Headington and Riley's book for chapter 12, sections 4-6 (p. 599). I suggest at least doing 12.8(a,b,f), and 12.9 is also a candidate. Do what parts seem useful to you, then look at the answers, which are at the end of the book in page A-185 for problem 12.8. 6. (60 points) A bag (or multi-set) is like a set, but the same element can appear many times. For example, a shopping bag can hold six cans of coke (which is much better than a "shopping set", into which you might put six cans of coke and only get one out!) In this problem, you are to use a hash table to implement the specification of the type Bag found in the file /home/cs228/public/homework/Bag.h You must use a hash table, with chaining, in an essential way in your implementation. (Hint: you can either store the item as many times as it occurs in the bag, or you can store the item once, and a count of how many times it occurs.) You must use concrete PRE, MODIFIES, and POST comments in your Bag.C file, and you must also use an ABSTRACTION MAP in your Bag.pri file. You will likely also need to have a CLASS INV comment in the Bag.pri file. You will be graded on these comments. See HR chapter 9 and /home/cs228/public/docs/assertion-notation.txt for details on these. You must run our test driver for this problem, which is in the file /home/cs228/public/homework/hw12_driver.C