Com S 228 --- Introduction to Data Structures HOMEWORK 14: Test Preparation (File $Date: 1995/05/02 03:56:38 $) This homework is a review for the final exam on Tuesday, May 9, 9:45-11:45. It is all suggested practice, nothing is due, although we will review it during class and/or discussion sections on May 4-5. The readings are those from the syllabus in the units: Design/Impl. of ADTs, Searching & Hashing, Sorting, Trees, and File I/O. The collected readings are thus as follows. HEADINGTON & RILEY: 9, 12.4-8, 12.10, 13, Appendix C, pages A-93-95, A-101-111 DEITEL & DEITEL: 14.7-11, 15.5-7 Of the above readings, the HR Appendix readings and the ones from DD chapter 15 are only recommended. The final exam is comprehensive in the sense that you are expected to be familiar with the material from earlier in the course. However, it will focus on the following topics from the readings above. I. ADT Design and implementation A. How to design an ADT's operations? 1. idea of an abstract domain, and its purpose 2. kinds of operations - classification, - how to use as an aid to designing operations 3. completeness and testability - deciding when have a minimal set of operations - deciding when a set of operations is effectively complete B. How to implement an ADT correctly? 1. Choosing a reprsentation 2. Abstraction map - purpose and use 3. Abstract vs concrete assertions, - purpose and use II. Searching and Hashing A. linear search - when to use - efficiency - how to write the code B. binary search - when to use and restrictions - efficiency - how to write the code C. hashing - when to use, and restrictions - efficiency - how to write code for chained hash tables - variations III. Sorting A. Bubble sort - when to use - efficiency (average, worst, best) - how to write the code B. selection - when to use - efficiency (average, worst, best) - how to write the code C. quicksort - when to use - efficiency (average, worst, best) - how to write the code - partitioning code IV. Trees A. Terminology - be able to use the terms, and understand them in problems B. Data structures - dynamic data implementation (C++ structs) - array implementation C. Binary search trees - definition - purpose, when to use - insertion efficiency, how to write the code - searching efficiency, how to write the code D. Treesort - efficiency (average, worst, best) E. Heapsort - efficiency (average, worst, best) - how to write the code V. File I/O A. files and streams - creation of files - opening files for output and input - closing files B. Access - sequential access - random access The topics really falls into three parts. The ADT design and implementation unit is foundational, and summarizes the earlier material in the course. The rest of the material, except for file I/O, is concerned with high-level data structures and algorithms. I'd rank the importance of topics as follows. Important: * How to implement an ADT correctly * Searching (both linear and binary) * Hashing (esp. chained hash tables) * Binary search trees * How to design an ADT's operations? Less important: - Heapsort - Array implementation of binary trees - Quicksort - File I/O 1. (suggested practice) For each of the specific topics above, write down where you think they would appear on the test. That is group the topics above as to where in the 5 problem kinds listed below they are to appear. (So an answer would be a list with parts numbered 1 to 5.) (1) an easy problem, perhaps a brief essay answer in English to a conceptual question, or a simple function to implement. (2) a short conceptual problem, probably asking about when to use some data structure compared to some other. This may touch on topics of lesser importance. (3) a short programming problem, probably implementing some function over one of the kinds of data structures studied. (4) a medium-sized programming or design problem, this should be on an important topic, possibly involving material from earlier in the course. (5) a harder problem, perhaps one that combines several topics into one. (An example of combining several topics was the "implement class CharStack using class CharList problem on test 2.) This should be on an important topic or combination of important topics. 2. (suggested practice) Design a practice test consisting of five (4) problems (of the kind described above in problem 1 of this homework). Write out the problems with the kind of detail seen on previous tests. Don't make the problems too easy, it's best to actually pick topics that (a) are important, and (b) are something you feel a bit unsure about. (If you are stumped, you can use some of the suggested practice problems.) However, don't make them so that they are so involved they take too long to describe and answer. See the appendix below for the subset of C++ you will be able to use on the test, and for the parts of C++ you may *not use on the test. Then take 110 minutes, and write out the practice test by hand on paper. Do *not* use a computer. Then check your answers to the practice test on the computer. You may need to write test harnesses for some of the problems. 3. (suggested practice) If you haven't done the suggested practice problems from homeworks 12-13, now is the time to do them. They will make good practice for the test. APPENDIX: directions about C++ that will appear on the test. Subset of C++ You May Use You may use recursion on this test. Unless otherwise stated in a problem, when solving problems you may only use standard features of the language that we discussed in class, classes and utilities we discussed in class, and helping functions that you define yourself. So for headers, you may only use macros, objects, and functions declared in the following header files (see HR appendix G, DD appendix B). "Deallocate.h" "IntFlexVec.h" "String.h" "ask_yn.h" "bool.h" "clist.h" "cqueue.h" "cset.h" "cstack.h" "password.h" "pretend_bool.h" "prompt.h" "rand2.h" "swap.h" "vector.h" Parts of C++ You May *Not* Use Unless otherwise stated in a problem, you are prohibited from using derived classes (don't worry if you don't know what that is) and the following C++ keywords. asm catch goto template throw try virtual