[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]
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
.
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.
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
.
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
void add(Object)
, which adds an element to the list;
boolean contains(Object)
, which determines if the
list contains an element; and
Object delete(Object)
, which deletes the specified
element from the list.
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.
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).
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.
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.
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.
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.
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.
Thursday, 17 November 2000
Tuesday, 21 November 2000
[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]
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