public static void main(String[] args) {
public class HW6StaticMethods {
public int pi;
public static int psi = 5;
public static int triple(int i) {
return 3*i;
}
public int quadruple(int i) {
return 4*pi;
}
public HW6StaticMethods(int i){
this.pi = i;
}
public static void main(String[] args){
HW6StaticMethods hw6 = new HW6StaticMethods(12);
/*1*/ System.out.println(pi);
/*2*/ System.out.println(psi);
/*3*/ System.out.println(quadruple(6));
/*4*/ System.out.println(triple(7));
/*5*/ System.out.println(hw6.pi);
/*6*/ System.out.println(hw6.psi);
/*7*/ System.out.println(hw6.quadruple(6));
/*8*/ System.out.println(hw6.triple(7));
}
Written problems
(12 points) Weiss problems 4.22 – 4.23 (page 157). Assume that all of the items are of the same type, and that this type IS-A Comparable.
(5 points) When the input size is N, algorithm A uses 5 N log N operations, while algorithm B uses N2 operations. For small values of N, algorithm B is faster; for large values of N, algorithm A is faster. Determine the smallest possible integer N0 such that for all N > N0 algorithm A is faster than algorithm B. Show how you know that this is the correct integer.
A lower-triangular matrix is a (we’ll restrict it to) square matrix (i.e., N x N for some N) in which every element above the main diagonal is zero. I drew a diagram of this on the board in the Day 17 class. By “above the main diagonal”, we mean an element whose column number is larger than its row number. The internal representation of a triangular matrix should be a one-dimensional array. Since almost half of the positions in the matrix are guaranteed to always be zero, it is not necessary to explicitly store them in the representation array, so we can save almost half of the space needed for a “normal” square matrix with the same number of rows and columns. Note that the sum, difference, or product of two lower triangular square matrices is lower triangular, so these operations can (and should!) do considerably less work than the corresponding operations for “normal” matrices.
(a) (5 points) Show the order in which the elements of an N x N lower-triangular matrix can be stored in the computer's (one-dimensional) memory.
(b) (10 points) Given your storage scheme, give the formula for calculating the address in memory of A[i][j] where j ≤ i. Use A, L, and b to represent the same things as in the formula from the first paragraph of this problem. Your formula should be computable in constant time.
1. (8 points) Weiss problem 5.17, p 195.
2. (6 points) Weiss Exercise 6.12 (a)(b), p 248. You do not need to actually implement it.
3. (6 points) Weiss Exercise 6.13 (a)(b), p 248. You do not need to actually implement it.
4. (6 points) Weiss Exercise 6.14 (a)(b), p 248. You do not need to actually implement it.
1. (12 points) Weiss problem 5.15, fragments 1-4 only, part (a) only for each fragment. P 194-195
2. (12 points) Weiss Exercise 5.21 (Worst-case running time for each part).
3. (15 points) Weiss Exercise 6.5. Be sure to begin thinking about this one early. You may have to come back to it a few times before you figure out what to do. P 247. Here is a longer explanation:
The goal of this problem is to implement a collection data type that provides three operations and does them efficiently:
push(obj); adds obj to the collection.
obj = pop(); removes and returns the most recently-added object.
obj = findMin(); returns the smallest object (assume that all
of the objects in the collection are comparable).
A single stack
can do the first two operations in constant time, but not the third.
But if our implementation uses TWO stacks to represent a collection,
it is possible to do each of the three operations in constant time.
Is should be obvious that our new data structure's push
method will have to do more work (than the push operation for
an ordinary stack would have to do) in order for findMin to
also be a constant-time operation. All you need to do is show the
code for a constructor and the three operations. You may assume that
there is already a Stack class that has its own push, pop, and top
methods. The code for each of the three methods that you must
provide is short. I hope that by making things a bit more specific,
it will make it easier for you to get started on this problem.
To further assist you in understanding this problem, I am giving you
a framework in which your answers could go: A class declaration with
stubs for the three methods you are supposed to write. Each of
those methods should be constant time (no loops or recursion)
public
class
StackWithMin<E> {
private Stack<E>
stack1,
stack2;
// You
should give these two stacks names that indicate what they are used
for
public
StackWithMin() {
this.stack1
=
new
Stack<E>();
this.stack2
=
new
Stack<E>();
}
public
void
push(E element) {
/* You fill in the details */
}
public
E pop() {/*
You fill in the details */
}
public
E findMin() {/*
You fill in the details */
}
}
a. (15 pts) Write a recursive method to compute the Nth number in the Fibonacci sequence. The 0th Fibonacci number is 0, the 1st Fib # is 1, and each successive one is defined as the sum of the two previous ones. Thus the sequence is: 0 1 1 2 3 5 8 13 21 34 55 89 ... (If you compute Fib(10) == 55, you don't have any off-by-one errors.)
b.
(15 points) In Weiss exercise5.8, you examined the efficiency of
computing XN, where X is a double value and N is an
integer. That algorithm is O(N) if we ignore the increasing size of
the numbers to be multiplied. It turns out we can do a lot better;
there is an algorithm that is O(log N). Write and test code that
does this. Hint: Base your algorithm on the binary
representation of N. For example, X11 = X1*X2*X8
(Note that 11has one-bits representing 1, 2, and 8). So you can write N as a sum of powers of 2. Start with
power=X,
and keep squaring
power
to get the original
X
to those powers of 2. Only multiply X^(2^i) into
the product if the ith bit of the binary representation
of N is 1. Your program should ask the user for X and N, and print
XN.
You can just write the code out by hand if you wish, but I recommend getting it working in Eclipse and printing out your code.
Bonus: Write part (b) recursively.
public static void
main(String[] args) {
Collection<Collection<String>> a = new
ArrayList<Collection<String>>();
String[][] arrays = {{"abc", "def", "ghi"},
{"xyz", "uvw", "abc", "abc"},
{"a", "ab", "abc", "xyz", "abc"}};
for (String[] sArray : arrays){
Collection<String> a1 = new ArrayList<String>();
for (String s: sArray)
a1.add(s);
a.add(a1);
}
System.out.println(count(a, "abc"));
}
2. (5 points) Weiss exercise 6.4.
3. Weiss Exercise 6.7
4. Weiss Exercise 6.18
Your program should read strings (one per line) form standard input, and write Strings (one per line) to standard output. The alphabetical part of the sort should ignore case. Hint: Use java.util.Collections.sort().
SAMPLE RUN:
Enter the strings, one
per line (CRTL Z to end):
Come
and
sit
by
my
side,
if
you
love
me
Do
not
hasten
to
bid
me
adieu
Just
remember
the
Red
River
Valley
And
the
cowboy
who
loved
you
so
true
SORTED LIST OF STRINGS:
by
Do
if
me
me
my
so
to
and
And
bid
not
Red
sit
the
the
who
you
you
Come
Just
love
true
adieu
loved
River
side,
cowboy
hasten
Valley
Remember
6.14, 6.15, 6.17, 6.19, 6.20, 6.21, 6.22
8.1abc, 8.4abc, 8.5abc, 8.6abc
15.9
16.1, 16.3, 16.6, 16.7, 16.9
17.5, 17.6, 17.12, 17.17, 17.18