Handle[] handles = new Handle[5];Note: Some students have had trouble making Handle an innerclass of BinaryHeap. A common problem is to have a class, call it BinaryHeapNode, which is NOT an innerclass of BinaryHeap but uses the Handle class. Both Handle and BinaryHeapNode should be an innerclass of BinaryHeap. As stated on the FAQ page (since early last week), if you do not want to use inner classes, you can change both occurences of BinaryHeap.Handle in the provided Driver to Handle.
Terminal.readInputFromFile("inputFileName");
Terminal.startTranscript("transcriptFileName");
int i = Terminal.readInt();
double d = Terminal.readDouble();
Note that inputFileName, transcriptFileName, i and d can be placed by
whatever names you want. Full documentation for the Terminal class is on the course web page.
This should be very easy to do.
for (i=0; i<=n-1; i++){
for (j=i+1; j<=n-1; j++){
loop body
}
}
Let's figure out how many times the loop body is executed for each
value of i. Here's a table to show that:
i # times loop body executed for that i ------- ------------------------------------- 0 n-1 (j goes from 1 to n-1) 1 n-2 . . . . . . n-2 1 n-1 0Hence the number of times the loop body is executed is given by
(n-1) + (n-2) + ... + 1 = (n-1)n/2 = n^2/2 - n/2 = Theta(n^2)If you understand this you may find it useful to compare this to the solution that uses summations to see that they are really doing exactly the same thing.
(1) f(n) + g(n) = O(g(n)), and (2) f(n) + g(n) = Omega(g(n))Think of these as two independent proofs. If either is false (as demonstrated by a counterexample) then you will have a counterexample to the original statement that f(n) + g(n) = Theta(g(n)). And of course if you prove (1) and (2) above are both true then you have proven that
Also for Problem #4, remember that if you, for example, are showing that
If f(n) = O(g(n)) then g(n) = Omega(f(n))then you first assume that f(n) = O(g(n)). This means that there exists constants c>1 and n0 such that for all n >= n0 f(n) <= c g(n).
Remember, you CANNOT pick a value for c and n0. You just know that they exist.
To prove that this is true, you must show that there exists constants c' and n0' such that for all n >= n0', g(n) >= c' f(n).
You can pick c' and n0' to be any constants that you want since you just need to prove the existence of such constants. They may depend on c and n0 but don't have to.
Hence f(n) = O(g(n)), yet f(n) != Omega(g(n)) and f(n) != Theta(g(n)).
Similarly, if lim as n -> infinity of f(n)/g(n) = infinity then f(n) is
the asymptotically FASTER growing function.
Informally, f(n) asymptotically > g(n).
Hence f(n) != O(g(n)), yet f(n) = Omega(g(n)) and f(n) != Theta(g(n)).
Finally if the limit goes to a constant then f(n) and g(n) grow asymptotically at the same rate so
f(n) = O(g(n)), f(n) = Omega(g(n)) and f(n) = Theta(g(n)).
Don't forget about the practice problems.
new Plotter(ptsByX,0,0,100000,300000,true,"Sorted by X-coordinate");
new Plotter(ptsByY,0,0,100000,300000,true,"Sorted by Y-coordinate");
new Plotter(ptsByX,0,0,100000,300000,false,"Output");
correspondingly to
new Plotter(ptsByX,0,0,300000,300000,true,"Sorted by X-coordinate");
new Plotter(ptsByY,0,0,300000,300000,true,"Sorted by Y-coordinate");
new Plotter(ptsByX,0,0,300000,300000,false,"Output");
the distortion will no longer be there. Of course you'll see that all
of the x-coordinates are on the leftmost third of the plot -- this is
just the way the data is.
p->y(200000 - p->x);
p->y(p->y + randint(-100000,100000));
by
p->y(200000 - p->x());
p->y(p->y() + randint(-100000,100000));
Each of those lines was missing a set of parentheses (in the first after the
p->x and in the second after the second occurence of p->y).
The provided
code has been changed if you would find it easy to just get a new copy.
Java Lab1 transcript.txtwill create the transcript file "transcript.txt". In the PC environments there should be a menu item to give a command line argument.
If you do not know how to give a command line argument then you can just add the following line to your program:
Terminal.startTranscript("transcript.txt");
and the output will be saved in the file transcript.txt.
Of course you can pick any file name that you like. Just put this
line before the line that starts java.util.Random or anywhere
before the first println occurs.
public static double closestPair(XYPoint[] ptsByX, XYPoint[] ptsByY){
Put your method here... Also, of course you can pick whatever
variable names you want for the two arrays.
}
Then, for example, your call from Lab1.java would look like:
double ans = FastClosestPair.closestPair(ptsByX,ptsByY);
While these times will vary based on the hardware you use, if you plot a graph of time versus the number of points the only thing that really differs is the scale for the y-axis.
Recall that in C++ when you access an array out of bounds, if the memory address you are accessing is allocated to your process (although not in the array you intended to access) then there will be no run-time error generated. Nevertheless, you may still be accessing an array out of bounds.
In your C++ lab if you are getting a segmentation fault then I would be willing to bet (with a good stake) that you are accessing an array out of bounds. Furthermore, you are probably doing this for small values of n even if the segmentation fault isn't occuring. So how do you find this if you don't see it in the code? What I suggest is that EVERY time you access an array, print out the name of the array, the size you allocated for it and the index you are accessing. The index should be between 0 and the size of the array-1.
for (i=0; i < n; i++){
loop body
}
Remember that the value of i
in the last iteration of the loop
is n-1 (since it is the last integer
value less than n). Recall that the above loop is equivalent to:
i=0;
while (i < n){
loop body
i++;
}
I personally discourage the use of less than above but rather recommend
the for loop is written like:
for (i=0; i <= n-1; i++){
loop body
}
The most common place where I'm seeing this error is in the final loop. In class I
put:
for i = 0 to |Y'|-2
First, by |Y'| I mean the number of elements placed into the Y' array. In the above
for loop i should go from 0 (the lowest point) to |Y'|-2 (the second to highest
point).
For timing the naive routine, notice that the sort routine is no longer needed and thus the calls to it (and the prototype at the top) should be removed.
Return to the CS 241 Home Page