See submission instructions below: one to a special dropbox, and most to the regular dropbox.
[Numbers in brackets] are problem numbers from the third edition of the Weiss textbook.
The following formulas for series sums may be helpful:
The ACM's Code of Ethics states in section 1.5: Honor property rights including copyrights and patent
If you prefer, you may select another section of the ACM Code of Ethics as the basis for your essay. If you do this, be sure to indicate which section you chose to elaborate.
You will submit problems 2-5 to the WA3 dropbox:
(15 points) Weiss Exercise 5.30 [5.23]. Note that your method is supposed to efficiently search the sorted (increasing) array
a
of integers, looking for an integer
i
for which a[i] == i
and return
true
if and only if there is such an
i
.
You may assume that the array has no duplicate entries, and therefore is strictly increasing. I.e.
a[j-1] < a[j]
for all
j
with
0 < j < a.length
. You may
not
assume that all of the integers in the array are non-negative, because then the problem would be boring.
Show your algorithm and the results of your analysis. Obviously you should try to come up with an efficient algorithm; some of the credit for this problem will be based on your algorithm's efficiency. (Think about it carefully—is O(N) "efficient" for this task? Anyone can write a loop from 0 to a.length.)
(15 points) Weiss Problem 5.21 [5.16]. You only need to do the analysis,
not an implementation. This one is more complex than any of the parts of problem
5.20 [5.15]. As with our analysis of the cubic algorithm for MCSS in class, you should first derive a (closed-form, no-summation notation) formula for the exact number of times that the
sum++
statement executes. Be sure to explain what you are doing, not just write equations. Use your derived formula to state a big-Oh estimate; you can use the usual shortcut of dropping lower-order terms and constant factors only at this last stage.
You do not have to implement and run the code.
These problems are for you to think about and convince yourself that you could do them. It would be good practice to actually do them, but you are not required to turn them in.
This problem is inspired by Weiss exercise 5.11 [5.8], but is different. That problem examines the efficiency of computing XN, where X is a double value and N is an integer. That algorithm is O(N). 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 11 has 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(2i)
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.
Another hint: It is probably easier to do this recursively.
You can just write the code out by hand if you wish, but I recommend getting it working in Eclipse.
Weiss Exercise 6.33 [6.18]. Your program should read strings (one per line) form standard input, and write
String
s (one per line) to standard output. The alphabetical part of the sort should ignore case. Hint: Use a two-argument overloaded version of
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