Problem 1
Brookshear, Chapter Five Review Problem 4, (pg 278), but first ...
Part a Before writing the machine language requested by
Brookshear, write the Java statement.
Note that in Java, the symbol "=" is used only for assignment -- "let
x take on the value of y" becomes "x = y". To test equality, the notation
"==" is used, so "if i equals n" becomes "if (i == n)".
Part b Write the machine language as requested by Brookshear
Problem 2
Problem 3
Brookshear, Chapter Eleven Review Problem 14, (pg 533),
Problem 4
Brookshear, Chapter Eleven Review Problem 19, (pg 533).
The Brookshear reading may be a bit misleading in answering whether your algorithm is a polynomial or nonpolynomial algorithm. We measure the complexity of an algorithm relative to the size or length of the input to the algorithm. In class, we have always been dicussing the running times of algorithms that work on lists of items. So the length of the input is proportional to the size of the list, e.g. a list of n names, each no more than 100 characters long, would take space about 800n bits (the `8' comes from 8 bits per ASCII character). (One exception was on Problem Set 8, where the extra credit asked you figured out the running time of Euclid's GCD algorithm as a function of the magnitude of the larger input.)
In this problem, there is only one positive integer as input. We want to consider arbitrarily large integers. Therefore, if the number's magnitude is M, the length of the input is about log M. For example, it takes 30 bits to represent 1 billion. Your algorithm should not worry about the practicalities of representing arbitrarily large magnitudes by a real computer -- just write it as if any size integer can be stored. (There are applications that allow arbitrarily large magnitudes, but they don't do arithmetic operations in one "tick of the clock".) To find the complexity of your algorithm, it will probably be easier to first figure out its running time in terms of the magnitude of the input integer; then convert this running time to a running time with respect to the length of the input.