Note: Credit will not be given just for answers - show all your
work: your reasoning, steps you took to get your answer etc.
- Read through
an example of how to go from a high-level idea to an actual
implementation.
- Pen-and-paper (submit as PDF) exercises:
- Find the appropriate "order" relationship between
\(n \log(n)\) and \(10n\) and find the constants
\(c\) and \(N\).
- Among the following functions, for each distinct pair
\(f_i(n)\) and \(f_j(n)\)
identify which of the possible "order" relationships are
satisfied: \(f_i(n) = O(f_j(n))\), \(f_i(n) = \Omega(f_j(n))\),
or \(f_i(n) = \Theta(f_j(n))\).
The functions are (use base-2 for logarithms).
$$\eqb{
f_1(n) & \eql & n \\
f_2(n) & \eql & n \log(n) \\
f_3(n) & \eql & n \log(n^2) \\
f_4(n) & \eql & n^{2.5} \\
f_5(n) & \eql & n \sqrt{n} \\
f_6(n) & \eql & n^2 \log(n) \\
}$$
You do not need to find \(c\) and \(N\) in every case (although you
certainly can), but you do need to provide reasoning (a few sentences).
For example, in comparing \(f_1(n)\) and \(f_2(n)\)
you could say:
- \(\log(n)\) is an increasing function, and \(\log(n) \gt 1\)
for \(n \gt 2\).
Therefore \(n \log(n) \gt n\) for \(n \gt 2\).
This means, at the very least, \(f_1(n) = O(f_2(n))\) and
\(f_2(n) = \Omega(f_1(n))\). But because the gap between
\(n \log(n)\) and \(n\) grows with \(n\), we can't find a
constant \(c\) such that \(n\log(n)\lt c n\). This means,
\(n\log(n) \neq O(n)\) and therefore \(f_1(n) \neq \Theta(f_2(n))\).
Summary: \(f_1(n) = O(f_2(n))\) and \(f_2(n) = \Omega(f_1(n))\)
- Analyze the following code and provide a "Big-Oh" estimate of
its running time. Explain your analysis.
for (int i=0; i < n; i++) {
for (int j=0; j < n*n*n; j++) {
sum += data[i] * j;
}
int k = 4*n*(n-1);
while (k > 0) {
sum += data[k % n];
k--;
}
}
- Consider an M×N matrix (or 2D array), with M rows, and N
columns. Now consider the four quadrants one gets by bisecting the
matrix vertically and horizontally. The four quadrants are of
equal size. Write pseudocode to determine if all four quadrants
are identical, making sure to account for the cases when M and N
are even or odd. In the case that M or N is odd, you'll have to
ignore the middle row (or column), as the case may be.
For example, the matrix on the left has four quadrants equal
(with one of those quadrants shown in bold),
while the one on the right fails the test:
6 5 3 6 5 3 4 2 3 4 2
7 7 3 7 7 1 2 2 1 2 2
8 2 9 8 2 3 4 2 3 4 2
6 5 1 6 5 1 2 2 1 1 2
7 7 1 7 7
8 2 0 8 2
Here, because the number of columns is odd, we ignore the middle
column for symmetry.
In Big-Oh notation, how long does your algorithm take
to execute when M=N?
- For the rest of the semester, it will be essential
to know how to work with Java interfaces, both with interfaces
created expressly for this course and the Java API's own interfaces.
- Review Java interfaces.
- Especially examine the
Comparable
interface. Try to find some examples using that interface.
- Write the few lines of code needed to make the
Comparable
interface work for the object
A
in this example:
CompInterfaceExample.java.
- In your PDF for this exercise, draw a memory diagram showing
the contents of the system stack (method stack) and heap
before the first call to
compareTo()
returns.
How does Java's sort method know how to sort the array of
A
instances, since the sort method was written and compiled
long before the code for class
A
was written?
Note: You will almost never write the code for
an interface. Instead, your classes will implement interfaces
that are already in algtest. For example, in the code below,
your sorting algorithm will need to implement the
Algorithm interface (among other interfaces).
You have
the link to the description of the interface (which
tells you what methods your class needs to implement), but
you don't write the interface code itself. That code is
already in algtest.jar.
- Implement the Insertion Sort method (see the Wikipedia entry)
and compare it to the SelectionSort technique in
Module 1. To implement, you will need to follow these steps:
- In this part of the exercise, you will write
code that takes as input an array of integers and
rearranges the array to have the following property:
- Suppose the first element in the original array has the value x.
- In the new array, suppose that x is in position
i, that is data[i] = x.
Then, we want the rearranged array to be such that
data[j] <= x for all j < i and
data[j] > x for all j > i.
Thus, informally, the rearranging places
all the values to the "left" of x
are less than (or equal to) x and all values to the right
are larger than x.
- Here's an example. Suppose the array has the elements in this
initial order:
4 3 9 2 7 6 5
After one possible (there are many)
partition, we get:
3 2 4 5 9 7 6
That is, the leftmost element, 4,
is positioned in the resulting array so that all elements less than
4 (that is, 2, 3) are to its left (in no particular order), and all
elements larger than 4 are to its right (again, in no particular order).
- This same idea, which we will call partitioning,
can be applied to a part of an array as well. For example,
suppose we partition the part of the array below in bold:
4 3 6 2 9 7 5
After partitioning that part, we will get something like:
4 3 2 6 9 7 5
(using 6 as the partitioning element).
Write your code in a file called MyPartition.java:
- Make your class it implement the PartitionAlgorithm interface.
- You will only need to write code for the
leftIncreasingPartition method. Provide an empty
implementation for the other - we will not test it.
Note: your partitioning code will be in this method.
- Observe that you are given a sub-range within the array
which you will re-arrange. Do NOT touch elements outside
the subrange.
- Use the hw1.props3 properties file for
this problem.
Note:
- What is an empty implementation of a method? For a void-returning method,
it means you write out the
method definition (with parameters) and curly braces,
but don't add any code in between
the braces. For a method that needs to return something, you can
return some default value. The purpose is just to let the result compile.
- In just about every algorithm you write, you will need
to have your class implement the
Algorithm interface.
This has two methods, both of which you must implement.
For the
getName() method, you
must return something sensible (with your name embedded).
For
setPropertyExtractor() method, you
will just provide an empty body, unless we specify otherwise.
- Unless otherwise specified we will assume that all sorting
algorithms in this course will sort in increasing order (smallest element first).
- For each of your algorithms, write a main
method in which you perform some testing independent of the
environment we provide you. You will be graded on the testing
you perform.
- The algorithm testing environment only helps with
testing - it does NOT help with debugging,
which you are expected to do on your own. In this regard,
the test-environment may indicate that your code has failed
a test, but will not provide additional detail (this is what
we mean by "helps with testing, but not debugging").
- For this assignment and others, we expect you to write
clean, documented code following the guidelines mentioned on the
homepage.
Submission: