Fundamentals of Computer Science II (CSC-152 2000F)


Exam 3: Data Structures

Distributed: Wednesday, November 22, 2000
Due: 9 a.m., Wednesday, November 29, 2000
Free extension until Monday, December 4, 2000
Those taking the free extension may not have their exams graded before the end of the semester.

This page may be found online at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Exams/exam.03.html.

Preliminaries

There are three long problems and five short problems on the exam. Each long problem is worth twenty-five points. Each short problem is worth five points.

For convenience, the questions are divided into sections. The point value associated with a problem does not necessarily correspond to the complexity of the problem or the time required to solve the problem. If you write down the amount of time you spend on each question, I'll give you three points of extra credit.

This examination is open book, open notes, open mind, open computer, open Web. Feel free to use all reasonable resources available to you. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

This is a take-home examination. It is likely to take you about five to ten hours, depending on how well you've learned topics and how fast your work. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted.

You must include the following statement on the cover sheet of the examination. Please sign and date the statement. Note that the statement must be true; if you are unable to sign the statement, please talk to me at your earliest convenience. Note also that ``inappropriate assistance'' is assistance from (or to) anyone other than myself or our teaching assistant.

I have neither given nor received inappropriate assistance on this examination. I am not aware of any other students who have given or received inappropriate assistance on this examinatino.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is among the hardest exams I have ever taken. If you don't start it early, you'll have no chance of finishing the exam.'' You may also summarize these policies.

Answer all of your questions electronically and turn them in in hardcopy. That is, you must write all of your answers on the computer and print them out. You should also email me a copy of your exam (a plain text file, please). Put your answers in the same order that the problems appear in. If you give an example of one of "Sam's easy to misinterpret scribbles" (that is, the scrawl I write on the board) along with the actual meaning and the interpreted meaning, I'll give you three points of extra credit.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by emphasizing your answer and including a clear set of work that you used to derive the answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem yo u have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

I will also reserve time at the start of classes next week to discuss any general questions you have on the exam.


Problems

Problem 1: Heaps and Nodes

In our discussion of heaps, we found that it is fairly natural to implement heaps with arrays. That implementation makes it easy to find the index of the last element in the heap (useful when you want to delete an element) and the index of the first free space (useful when you want to add an element). In particular, the last element is at index size-1 and the first free space is at index size.

In our discussion of trees, we noted that it is often convenient to implement binary trees with simple node structures. Each node contains a value and links to parent, left child, and right child. A wrapper class contains a reference to the root of the tree.

Suppose we decided to implement heaps using binary tree nodes along with a wrapper class that keeps track of the root of the heap. Explain, in English, how to find the last element and the first free space. If you rely on additional fields to keep track of these values, explain how you update them during calls to put and get.

Problem 2: Sorted Lists

Many textbooks for courses like CSC152 include a data structure they call the sorted list. Sorted lists are lists that are implemented by an array in which the elements are stored in order (where that order is given by a comparator). Those who design sorted lists suggest that the key operations for lists are

As the description suggests, these sorted lists are clearly data structures and not abstract data types, since the emphasis is on the implementation (with a sorted array). However, it also seems that it should be possible to design a more general sorted list abstract data type. What is a sorted list? Here's my ADT philosophy: A sorted list is a list that you iterate in order.

Using this philosophy as the basis (along with your own decisions as to what operations are important), design a SortedList interface and a SortedListIterator interface. Make sure to carefully document the six Ps for each of these interfaces.

Note that you need not write compilable code; I'm primarily interested in the methods you choose and the ways in which you document these methods.

Problem 3: Sets

Most of the collections we've studied so far are used primarily for storing elements that we can step through (by iteration in a list; by repeated deletion in a linear structure; by a traversal algorithm in a tree). However, other kinds of collections naturally appear in computation. For example, mathematical sets are a common ADT. A set is a collection of elements whose primary operation is contains (is a value in the set). While a value may appear more than once in a list, it doesn't really make sense for a value to appear more than once in a set (since you can't step through the members of a set).

As with the more mathematical sets, you might intersect, union, or otherwise combine pairs of sets.

Write a Set interface. Make sure to carefully consider what methods are appropriate and what form those methods should take. As before, be careful to document your methods clearly (with the six P's).

Problem 4: Short Questions

Problem 4.1: Lists vs. Queues

As I've suggested in the past, it often makes sense to place classes and interfaces in a hierarchy. Would you make Queue a subinterface of List, List a subinterface of Queue, or make the two interfaces independent? Suggest why in a few sentences.

Problem 4.2: Data Structure Design Techniques

In our discussions of algorithms, we saw a number of general algorithm design techniques, including divide-and-conquer, dynamic programming, and greed. Summarize the general data structure design techniques you've learned.

Problem 4.3: Ordered Structures

In section 9.2.4, Bailey describes an OrderedList structure. He uses that structure in his implementation of Huffman coding. Yet, as we saw in class, it may also make sense to use a priority queue to keep track of the trees.

Explain the key differences between Bailey's OrderedList and our own PriorityQueue structures.

Problem 4.4: Vectors and Arrays

Java's built-in arrays and Java's utility class java.util.Vector have many similarities. For example, both are used to store collections of values that can be indexed by numbers. Summarize the key differences between vectors and arrays.

Problem 4.5: The Principled Programmer

Throughout Java Structures, Bailey suggests a number of programming principles. He summarizes these in appendix C on pp. 349-350. Pick your favorite principle, give a short example of its application, and explain (in a few sentences) why you like the principle.

History

Thursday, 17 November 2000

Tuesday, 21 November 2000


Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Exams/exam.03.html

Source text last modified Tue Nov 21 23:26:02 2000.

This page generated on Tue Nov 21 23:27:44 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu