[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[On Teaching and Learning]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[SamR]
[Java 1.5 API]
[Espresso]
[TAO of Java]
[CS152 2004F]
Distributed: Friday, 4 November 2005
Due: 11:00 a.m., Friday, 11 November 2005
No extensions.
This page may be found online at
http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2005F/Exams/exam.02.html
.
Contents
There are four problems on the exam. Some problems have subproblems. Each problem is worth twenty-five (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 as restricted by 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.
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. In particular, 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 75 points on this exam.
I would also 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. 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 the various parts of 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. Failing to do so will lead to a penalty of two points.
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 to five points.
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: ADT design, Vectors, arrays, exceptions.
As you may have noted, there are problems with both arrays and Vectors. Both are nice because they are efficient. Arrays seem to have too few operators (e.g., they don't expand). Vectors have the added benefit that they can expand when necessary. Vectors also have the disadvantage that they include way too many operations, operations which do not always have clear running times.
The minimalist philosophy of ADT design suggests that you design ADTs
with only a few key operations, rather than a wide variety. As we
saw in the Fibonacci example, it is often useful to have array-like structures,
but to have those structures automatically
expand to whatever
size is necessary. Let us call such structures arbitrarily-large arrays.
Because parameterized types are complex, we'll look at a particular kind
of array, the arbitrarily-large array of integers, which we will call
ArbitrarilyLargeIntegerArray
.
Implement an ArbitrarilyLargeIntegerArray
class that provides the
following constructors and methods.
ArbitrarilyLargeIntegerArray()
, which creates a new, empty
arbitrarily-large array of integers.
ArbitrarilyLargeIntegerArray(int size)
, which creates a new
arbitrarily-large array of integers with size size
.
void set(int pos, Integer val)
, which sets the value at
position pos
to val
. (If pos
is negative, set
should throw an exception. That condition,
and an out-of-memory situation, are the only times that set
should throw an exception.)
Integer get(int pos)
, which returns the value last set
with set(int pos, Integer val)
with the same pos
.
(If pos
is negative, get
should throw an
exception. If there has been no previous call to set
at
that position, get
should return null
.
long size()
, which should return the larger of (a)
the size
given as a parameter to the unary constructor;
(b) the largest index used for set
.
String toString()
, which should return a string of
position:value pairs for all non-null positions in the array. For
example, if we've set position 3 to 18, position 11 to -2, and
position 1000 to 0, toString
should return
"[3:18, 11:-2, 1000:0]"
.
Note that your implementation will be much like that of Vectors. That
is, you'll have an underlying array that you will have to change whenever
the index in set
is too large.
Topics: Algorithm design, experimental algorithm analysis, Vectors, dynamic programming.
As you may recall, in the first exam you wrote a method that converted a numeric deposit into a corresponding set of coins. You may not realize it, but the strategy used for that method determined the fewest possible coins for the deposit.
That is, that method solved 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, 5, 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
.
Note that for some choices of denominations, it is not possible to
determine a number of coins that exactly make a particular value. For
example, for values of 2, 5, and 8, there is no way to make the values
1 or 3. The fewestCoins
method throws an exception in
such cases.
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.
As you saw in our discussion of Fibonacci numbers, we can make computations more efficient by caching previous results. This technique is called dynamic programming. For this particular example, we can remember 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 a Vector (or an
ArbitrarilyLargeIntegerArray) indexed by the price. We initialize each
cell to some value (say 0, -1, or null) to indicate not yet
computed
. How do we know the array is big enough? We allocate
it before the first (outermost) call to fewestCoinsHelper
.
Approximately,
public int fewestCoins(int price) throws Exception { // Build a sufficiently large vector. ... // Use the helper to do the real work return fewestCoinsHelper(price); } // fewestCoins(int) // Pre: this.previouslyComputed.size() > price public int fewestCoinsHelper(int price) throws Exception { // If we've previously determined that no such value exists, // throw an exception. if (this.previouslyComputed.get(price) == this.NO_SUCH_VALUE) { throw new Exception("No combination of coins works."); } // If we've previously found a number of coins, return it else if (this.previouslyComputed.get(price) != this.NOT_COMPUTED) { return this.previouslyComputed.get(price); } // Otherwise, compute and save the result else { ... } } // fewestCoinsHelper(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: Testers, arrays, the main
method.
One disadvantage of the tester for CoinCounter
is that we
have to change the code and recompile each time we want to try a different
set of values or different starting and ending price.
Write a new tester, TCC
which permits you to specify the
coin values and starting and ending price on the command line. For
example,
# ji TCC 10-20 5 2 1 Computing prices from 10 to 20 using values [5,2,1] A price of 10 cents requires 2 coins. A price of 11 cents requires 3 coins. ... A price of 20 cents requires 4 coins. # ji TCC 50-65 50 7 Computing prices from 50 to 65 using values [50,7] A price of 50 cents requires 1 coin. A price of 51 cents cannot be computed. A price of 52 cents cannot be computed. ... A price of 64 cents requires 3 coins. A price of 65 cents cannot be computed.
Topics: Parameterized types, binary search, reading documentation.
You may recall that we experimented with a form of binary search in the lab on algorithm analysis. That method looked something like the following:
/** * Search for val in an ordered vector. * * @param val * The value to search for * @param a * A vector of values to search * * @result * index, the index of val * @pre * a is in increasing order. * @post * If index >=0, a.get(index) = val. * If index is -1, there exists no i s.t. a.get(i) = val * Does not modify a. */ public int binarySearch(BigInteger val, Vector<BigInteger> a) { // Determine the lower-bound of the range on interest. int lb = 0; // Determine the upper-bound of the range of interest. int ub = a.size() - 1; // Repeatedly look in the middle and discard as necessary while (lb <= ub) { // Get the middle int mid = (lb+ub)/2; // Determine relationships int order = val.compareTo(a.get(mid)); // Best possible option: the middle matches if (order == 0) return mid; // Another option: the middle is too large else if (order < 0) { ub = mid-1; } // The last option: The middle is too small else { lb = mid + 1; } } // while // If we've reached this point, it's not there. return -1; } // binarySearch
After your experience with Scheme (and with polymorphism in Java), you should be a little bit upset by this method, since it works for only one type.
What should we do? We should generalize the method. How do we generalize
the method? We parameterize the class with the underlying type, and we
extend binarySearch
to take not only the value and the
vector, but also the comparator, as parameters. Here's the result
(with some additional stuff).
package rebelsky.exam2; import java.util.Comparator; import java.util.Vector; /** * Objects that know how to binary search ordered vectors which contain * values of type T. * * @author Samuel A. Rebelsky * @author YourNameHere * @version 0.1 of November 2005 */ public class BinarySearcher<T> { // +---------+------------------------------------------------- // | Methods | // +---------+ /** * Determine whether or not vec is ordered according to order. */ public boolean ordered(Vector<T> vec, Comparator<T> order) { int len = vec.size(); // Repeatedly compare neighboring elements. If any two are out // of place, vec is not ordered. for (int i = 0; i < len-1; i++) { if (order.compare(vec.get(i), vec.get(i+1)) > 0) { return false; } } // If we've made it this far, everything is in order. return true; } // ordered(Vector<T>, Comparator<T>) /** * Search for val in an ordered vector. * * @param val * The value to search for * @param vec * A vector of values to search * @param order * A comparator that specifies the underlying order of the Vector. * * @result * index, the index of val * @pre * a is in increasing order (according to the order of this searcher). * @post * If index >=0, a.get(index) = val. * If index is -1, there exists no i s.t. a.get(i) = val * Does not modify a. */ public int binarySearch(T val, Vector<T> vec, Comparator<T> order) { // STUB return -1; } // binarySearch(T, Vector<T>, Comparator<T>) } // class BinarySearcher<T>
a. Fill in the body of binarySearch
.
b. Test your binarySearch
for correctness using a variety
of types. (Search in arrays of Integer
s,
String
s, and BigInteger
s.) At least one
of these tests should be fairly comprehensive (that is, test not just
that it works with that type of parameter, but it seems to work universally).
Note that you may have to read the documentation for
java.util.Comparator
closely. You may also have to
implement your own comparators.
These are some of the questions students have asked about the exam and my answers to those questions.
int[]
or
Integer[]
?Integer[]
(and that's why I had Integer
s as parameters and
return types).get
?set
and the constructor so that you did not need to expand the array with
set
.
size()
should return?set
, return the
parameter used in the constructor. Otherwise, use the largest index
in a call to set
. For example, if we initially set it to
be size 100, and never used an index greater than 10, size()
should return 100. Similarly, if we set the initial size to 10 (or never
set an initial size), and used an index of 200, size()
should
return 200.Integer
s,
then any position that contains null
has not been set.null
in those positions?null
.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.
it is often to haveshould be
it is often useful to have. [EO, 1 point]
Late October, 2005 [Samuel A. Rebelsky]
Thursday, 3 November 2005 [Samuel A. Rebelsky]
Friday, 4 November 2005 [Samuel A. Rebelsky]
Wednesday, 9 November 2005 [Samuel A. Rebelsky]
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[On Teaching and Learning]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[SamR]
[Java 1.5 API]
[Espresso]
[TAO of Java]
[CS152 2004F]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue Dec 6 09:46:52 2005.
The source to the document was last modified on Wed Nov 9 08:38:52 2005.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2005F/Exams/exam.02.html
.
You may wish to validate this document's HTML ; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu