Distributed: Friday, April 8, 2005
Due: 11:00 a.m., Friday, April 15, 2005
No extensions.
This page may be found online at
http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2005S/Exams/exam.02.html.
Contents
There are four problems on the exam. Some problems have subproblems.
Each problem is worth 25 points.
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.
This examination is open book, open notes, open mind, open computer,
open Web. However, it is closed person. That means you should not talk
to other people about the exam. Other than that limitation, you should
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.
Although you may use the Web for this exam, you may not post your answers
to this examination on the Web (at least not until after I return exams
to you). And, in case it's not clear, you may not ask others (in person,
via email, via IM, by posting a please help
message, or in any
other way) to put answers on the Web.
This is a take-home examination. You may use any time or times you deem
appropriate to complete the exam, provided you return it to me by the
due date.
This exam is likely to take you about four to six hours, depending on
how well you've learned topics and how fast you work. You should not
work more than eight hours on this exam. Stop at eight hours and
write There's more to life than CS
and you will earn at
least 80 points on this exam. I would appreciate it if
you would write down the amount of time each problem takes. Each person
who does so will earn two points of extra credit. I expect that
someone who has mastered the material and works at a moderate rate should
have little trouble completing the exam in a reasonable amount of time.
Since I worry about the amount of time my exams take, I will give two
points of extra credit to the first two people who honestly report that
they've spent at least five hours on the exam or completed the exam.
(At that point, I may then change the exam.)
You must include both of the following statements on the cover sheet of the
examination. Please sign and date each statement. Note that the
statements must be true; if you are unable to sign either statement,
please talk to me at your earliest convenience. You need not reveal
the particulars of the dishonesty, simply that it happened. Note also that
inappropriate assistance
is assistance from (or to) anyone
other than Professor Rebelsky (that's me).
1. I have neither received nor given inappropriate assistance on this
examination.
2. I am not aware of any other students who have given
or received inappropriate assistance on this examination.
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 will have no chance of
finishing the exam.
You may also summarize these policies.
You may not tell other students which problems you've finished.
You may not tell other students how long you've spent on the exam.
You must both answer all of your questions electronically and turn in a
printed version of your exam. That is, you must write all of your answers
on the computer, print them out, number the pages, put your name on
every page, and hand me the printed copy. You must also email me a copy
of your exam by copying your exam and pasting it into an email message.
Put your answers in the same order as the problems. Please write your
name at the top of each sheet of the printed copy. Doing so will earn
you two points of extra credit.
In many problems, I ask you to write code. Unless I specify otherwise
in a problem, you should write working code and include examples that show
that you've tested the code.
Just as you should be careful and precise when you write code and
documentation, so should you be careful and precise when you write prose.
Please check your spelling and grammar. Since I should be equally
careful, the whole class will receive one point of extra credit for each
error in spelling or grammar you identify on this exam. I will limit
that form 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 you
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.
Topics: Data structure design, Linked structures, Arrays
At this point, you've seen three basic techniques for building
data structures:
- You can use an array to hold data. We used an array to implement stacks.
- You can use a collection of
nodes
, each of which has a link to another node. We used linked nodes to implement queues.
- You can use a collection of more complex
nodes
, each of which may have links to multiple nodes. We used these more complex linked nodes to build the trees underlying heaps.
Suppose you are presented with a new data structure implementation
technique. You will need to select one of these techniques. What
are some advantages and disadvantages of each? (You should list
at least two advantages and two disadvantages for each technique.)
Topics: Algorithm design, experimental algorithm analysis, arrays
As you may recall, in the first exam you wrote a method that figured
out the fewest coins that make a particular price. That method
was a particular instance of a famous computer science problem known as
the coin minimization problem. Given a set of coin values
(e.g., 1, 5, 10, 25, 50 or 2, 3, 8, 25, 40), and a particular price,
find the fewest coins that make that particular value. For example,
given coin values of 2, 3, 8, 25, 40, the fewest coins to make a
value of 19 is 3 (8, 8, and 3) and the fewest coins to make a value
of 50 is 2 (25 and 25).
How do you figure out the fewest coins? One possible solution is
the greedy solution: To find the fewest coins, assume you
use as many as possible of the most expensive coin, and then as many
as possible of the next most expensive coin, and so on and so forth.
You used that solution on the previous exam. Unfortunately, that
solution won't work for all combinations of coins. For example, if the
coins have values 2, 3, 8, 25, and 40, the greedy solution will
select 40, 8, and 2 to make 50 cents, when the best solution is
to use 25 and 25.
A more correct solution is the exhaustive search
solution.
For each denomination, we assume that we use one of that
denomination, reduce the amount appropriately, and recurse. We then
take the smallest of those solutions. Here is an implementation
of that solution:
package rebelsky.exam2;
/**
* Something that helps us count coins.
*
* @author Samuel A. Rebelsky
* @author YOUR NAME HERE
*/
public class CoinCounter
{
// +--------+--------------------------------------------------
// | Fields |
// +--------+
/**
* The valid coin values.
*/
int[] denominations;
// +--------------+--------------------------------------------
// | Constructors |
// +--------------+
/**
* Build a new coin counter for a particular set of denominations.
*
* @pre
* The values in _denominations must be stored in
* decreasing order.
* @pre
* All values in _denominations must be positive.
*/
public CoinCounter(int[] _denominations)
{
this.denominations = _denominations;
} // CoinCounter(int[])
// +----------------+------------------------------------------
// | Public Methods |
// +----------------+
/**
* Determine the fewest number of coins necessary to
* make a particular price.
*
* @exception Exception
* If it is not possible to make that price.
*/
public int fewestCoins(int price)
throws Exception
{
// Simple solution: No coins needed for no price.
if (price == 0)
return 0;
// Fewest represents the fewest coins we've done so far
int fewest = Integer.MAX_VALUE;
for (int i = 0; i < this.denominations.length; i++) {
int coin = this.denominations[i];
if (coin <= price) {
try {
int sub = this.fewestCoins(price-coin);
if (sub+1 < fewest)
fewest = sub+1;
} // try
catch (Exception e) {
// It's okay we failed, we'll just
// try a different denomination.
} // catch
} // if (coin <= price)
} // for
// Make sure that we found a solution
if (fewest == Integer.MAX_VALUE)
throw new Exception("Can't make change for " + price);
return fewest;
} // fewestCoins(int)
} // class CoinCounter
You may find it useful to test the program with
TestCoinCounter.java.
a. Extend CoinCounter so that it lets you count the
number of recursive calls that the fewestCoins does.
Make a chart to show the growth in the number of recursive calls
as the price increases.
As you may have noted, that implementation is not very efficient
because we repeatedly compute the same value again and again and
again. For example, in computing the number of coins for 40 cents
using denominations of 2, 3, and 5, we check the number of coins for
35 cents
at least three times (40-5, 40-2-3, 40-3-2). As importantly, each
of those three computations requires at least three computations
of the number of coins to make 30 cents (35-5, 35-2-3, 35-3-2).
Hence, we do at least nine calls to fewestCoins(30).
Similarly, we do at least twenty-seven calls to
fewestCoins(25), at least 81 calls to
fewestCoins(20), and so on and so forth.
We can make this computation significantly more efficient by
remembering the number of coins for a particular price the
first time we compute it and then checking it the next time.
In pseudocode:
To compute the number of coins to make N cents
if we have previously computed that result
return the previously computed result
otherwise
BEST = N+1 // A very large number
for each coin value, V
compute C, the number of coins to make N-V
if (C+1 < BEST)
BEST = C+1
remember that BEST coins are needed to make N cents
return BEST
How do we remember the number of coins? We use an array
indexed by the price. We initialize each cell to some value (say
0 or -1) to indicate not yet computed
. How do we know
the array is big enough? We allocate it at the first (outermost)
call to fewestCoins. Approximately,
public int fewestCoins(int price)
throws Exception
{
// If the array of previously computed values is not big
// enough, build one.
if ( (this.previouslyComputed == null)
|| (this.previouslyComputed.length <= price) ) {
this.previouslyComputed = new int[price+1];
for (int i = 0; i < price; i++) {
this.previouslyComputed[i] = this.NOT_COMPUTED;
}
} // if
// If we've previously determined that no such value exists,
// throw an exception.
if (this.previouslyComputed[price] == this.NO_SUCH_VALUE)
throw new Exception("No combination of coins works.");
// If we've previously found a number of coins, return it
if (this.previouslyComputed[price] != this.NOT_COMPUTED)
return this.previouslyComputed[price];
// ...
} // fewestCoins(int)
b. Rewrite fewestCoins to use this improvement.
c. Make a chart to show the growth in the number of recursive calls as
the price increases. What does the new growth curve look like?
Topics: Linear structures, Randomness, Implementing ADTs, Asymptotic analysis
An interesting (and perhaps even useful) kind of linear structure
is the Random List. A random list is one in which the
value returned by get is difficult to predict. (In
particular, it should be equally likely that any member of the
structure be returned.)
a. Write a RandomList interface. For this part of
the problem, you should focus on writing good documentation.
b. Implement random lists, either using linked nodes or an array.
c. Indicate the running time of put, get,
peek, and isEmpty for your data
structure.
Topics: Heaps, Trees, Comparing objects
In a class and laboratory, you have learned about and contributed
to the implementation of a heap of integers.
Generalize that implementation to permit a heap of any kind of
comparable value.
These are some of the questions students have asked about the
exam and my answers to those questions.
Here you will find errors of spelling, grammar, and design that
students have noted. Remember, each error found corresponds to a
point of extra credit for everyone. I limit such extra credit to
five points.
- Sam appears to be unable to number the exams in sequence [RH, 1 point]
- Sam has not learned that when you copy and paste from a previous exam, you should correct errors you saw in that previous exam, even if the previous students did not see those errors. [EG, 1 point]
- Sam wrote a confusing sentence in the first paragraph of Problem 2. [Various, 1 point]
- HTML error:
lt; instead of <. The former appears as lt;, the latter as <. [DD, 1 point]
- Although the constructor for
CoinCounter requires that the values be in strictly decreasing order, the call to that constructor in TestCoinCounter supplies the values in increasing order. I've left the precondition to better support the greedy algorithm and fixed TestCoinCounter. [EB, 1 point]
- Missing question mark in problem 1. [EG, RH, BB, and more, 0 points]
- Extra open paren in discussion of greed. [RH, BB, 0 points]
March and April 2005 [Samuel A. Rebelsky]
- Began considering problems.
Thursday, 7 April 2005 [Samuel A. Rebelsky]
- Finished design and selection of problems.
- Copied and rewrote the coin counting problem from a previous exam.
Friday, 8 April 2005 [Samuel A. Rebelsky]
- Finished writing.
- Distributed.
Monday, 11 April 2005 [Samuel A. Rebelsky]
Wednesday, 13 April 2005 [Samuel A. Rebelsky]
;
Check with Bobby