[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]
Distributed: Friday, October 13, 2000
Due: 9 a.m., Friday, October 27, 2000
No extensions!
This page may be found online at
http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Exams/exam.02.html
.
Code files:
You may want to use the online version of the exam to gain access to these files.
Array.java
(Note that this class is not the same as the standard Java array
class.)
CompareComparable.java
IncomparableException.java
NotFoundException.java
Searcher.java
TestSearcher.java
SimpleOutput.java
There are ten problems on the exam. Each problem is worth ten 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 except for other people and for exam and homework solutions. 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. Do not use exam or homework solutions you find on the Web.
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. Plesae 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.
I have neither given nor received help on this examination (other than from Sam Rebelsky). I am not aware of any other students who have given or received help on this examination (other than from Sam Rebelsky).
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" 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.
Read the Java documentation on the
Comparable
and
Comparator
interfaces.
a. Design a simple Course
class for information about a course.
Minimally, this should contain number, title, and instructor. It should
also have a toString
method.
b. Write a Comparator
that orders courses by title.
c. Write a Comparator
that orders courses by instructor.
Your colleagues, Carla and Carl Caffeinated, have come up with the following implementation of binary search.
public static Object binarySearch(Object value, Array stuff, Comparator order) throws IncomparableException, NotFoundException { // Determine the length of the array. int length = stuff.size(); // If there's only one element in the array ... if (length == 1) { // See if it's what we're looking for. if (order.compare(value, stuff.get(0)) == 0) { // If so, return it. return stuff.get(0); } else { // If not, give up. throw new NotFoundException(); } } // only one element in the array // If there are multiple elements in the array ... else { // Compare to the middle element. int comp = order.compare(value,stuff.get(length/2)); // Equal: We're done. if (comp == 0) { return stuff.get(length/2); } // Value is smaller; Search the left half. else if (comp < 0) { return binarySearch(value, new Array(stuff, 1, length/2), order); } // Value is larger: Search the right half. else { return binarySearch(value, new Array(stuff,length/2,length-1), order); } } // multiple elements in the array } // binarySearch(Object, Array, Comparator)
As you can tell, they need a new constructor for the Array class that builds a subarray of an existing array in constant time. Here's the sketch of that constructor.
/** * Build a new subarray which holds the elements in positions * start .. finish of stuff. Modifications to the subarray should * affect the original array and vice versa. */ public Array(Array stuff, int start, int finish) { // STUB. Write this. } // Array(stuff, start, finish)
Implement that constructor.
Unfortunately, even if you implement that constructor correctly, binary search will not work correctly because Carl and Carl have failed to follow proper design for the procedure. For example, they haven't worried about special cases and they haven't ensured that every recursive call is on a smaller array (or have they?).
Repair their code.
You may find
TestSearcher.java
helpful for this portion of the exam.
Test binarySearch
using courses, rather than integers.
Preferably, you'll be able to take just the name of a class and search
for the full class record.
Now that you've done all the hard work, Carl and Carla decide to
``improve'' your code by adding a test for the precondition of
binarySearch
. The first lines of binarySearch
are now
// Test the precondition. if (!Searcher.inorder(stuff)) { throw new IncomparableException("Can't binary search unordered lists"); }
When I look at their code, I scream. Why?
Carl and Carla have decided to try their hands at algorithm design. They've been thinking about things that might help a professor with grading. They decide that two useful algorithms will be to find the largest and smallest differences between grades in the class.
Here are their initial formulations.
To find the smallest difference between any two different numbers in a collection ... Set estimate to ``infinity'' For each value, v, in the collection For each value, u, not equal to v If |u-v| < estimate then Set estimate to |u-v| Return estimate
To find the greatest difference between any two different numbers in a collection ... Set estimate to -1 For each value, v, in the collection For each value, u, not equal to v If |u-v| > estimate then Set estimate to |u-v| Return estimate
What is the running time of their algorithms? Use Big O notation.
Theodore and Thelma Theoretician suggest that there should be an O(n*log_{2}n) algorithm for smallest difference. Come up with that algorithm.
Theodore and Thelma Theoretician suggest that there should be an O(n) algorithm for greatest difference. Come up with that algorithm.
Here's an iterative algorithm that finds the square root of a value to a specified accuracy.
/** * Compute the square root of val to accuracy 1/n. * Pre: (1) val >= 0 * (2) n > 0 * (3) The square root of val can be represented. * Post: (1) Returns a value v such that |v-sqrt(val)| < 1/n. */ public static double sqrt(double val, long n) { // Compute 1/nth of the range of possible values double accuracy = 1.0/((double) n); // Start with an initial guess double guess = 0; // Determine the difference between the square of the guess // and the actual square root. double diffsquared = val; // Step through all the possible values between 0 and val. for (double nextguess = 0.0; nextguess <= val; nextguess = nextguess + accuracy) { // Compute the difference between the square of the guess // and the actual value. double nextdiff = Math.abs(nextguess*nextguess-val); // If it's better, use it. if (nextdiff < diffsquared) { guess = nextguess; diffsquared = nextdiff; } } // for } // sqrt(double,double)
As you might be able to tell, what this algorithm basically does is divide the interval between 0 and val into potential guesses that occur every 1/n units. It then tries each of these guesses and uses the best. Why 0 and val? Because we know that the square root of val is at least 0 and no more than val.
The running time of this algorithm is somewhat strange. It's based on both n and val. More or less, this algorithm is O(n*val).
Make the algorithm more efficient by using a divide-and-conquer strategy. You need not write working Java code, although you will receive a modicum of extra credit for writing working code.
Determine the running time of the revised algorithm.
Tuesday, 10 October 2000
Thursday, 12 October 2000
Friday, 13 October 2000
Sunday, 22 October 2000
Wednesday, 24 October 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.02.html
Source text last modified Wed Oct 25 15:04:03 2000.
This page generated on Wed Oct 25 15:07:02 2000 by Siteweaver. Validate this page's HTML.
Contact our webmaster at rebelsky@grinnell.edu