home—info—lectures—hws—exams
hw08
running times, arithmetic
reading about sums, induction
Due 2007.Oct.23 (Tue).
(It looks like a lot of problems, but most of them are short
and/or just arithmetic.)
Although you are welcome to typeset your work nicely (using Microsoft Word
or LaTeX or whatever to get nice logic symbols),
it's probably much easier to write formulas by hand.
-
What is the largest integer value of n such that ...
-
n³ ≤ 3·109?
(This is the largest problem that can be
solved by an n³ algorithm
within a second, on a modern computer.)
-
n³ ≤ 3·1015?
(This is the largest problem that can be
solved by an n³ algorithm
within a semester, on a modern computer.)
-
n³ ≤ 3·1027?
(This is the largest problem that can be
solved by an n³ algorithm
on a modern computer running a hundred times longer than
the universe has existed.)
Any answer within 1050% of the exact solution will get full credit.
By the way, an example of an algorithm with running time of
n³
is finding the shortest path between every two points
in a network with n nodes
(a computer network, or a Halo 3 stargate system, or ...).
-
Answer the previous question, replacing
n³
with
10n (an algorithm with exponential running time;
an example would be looking at a chess game, and computing all
possible outcomes n moves ahead).
- 10n < 3·109
- 10n < 3·1015
- 10n < 3·1027
-
p.217 #4
(5ed: p167 #12): prime factorizations
-
p.229 #2a,b
(5ed: p179 #2a,b): int→string
Show your work:
either as a table with columns for the loop variables
(algorithm from book or from lecture),
or you can give a series of equalities, e.g.:
itos(27)
= itos(13) + "1" (where `+` means string-concatenation)
= itos(6) + "11"
= itos(3) + "011"
= itos(1) + "1011"
= itos(0) + "11011"
= "" + "11011"
= "11011"
(This is really the recursive version of the itos algorithm.)
-
p.229 #4a
(5ed: p179 #4a): string→int
Show your work.
-
p.229 #6 variant
(5ed: p179 #6 variant):
what binary numeral represents
the same number as
the hexadecimal numeral "ACED"?
-
p.230 #10
(5ed: p179 #10): binary numerals → hex numerals.
-
p.230 #20 variant
(5ed: p180 #20 variant):
Use Algorithm 5 of the book to compute
345138 mod 777.
Show your work,
as a table with columns for each variable
(Note that 138=128+8+2.)
-
p.230 #24
(5ed: p180 #22): gcd
Show your work;
your answer should be a series of equalities.
For example:
gcd(27,12)
= gcd(12,3)
= gcd(3,0)
= 3.
-
Read pp.153.5–157.5 (skim Theorem 1, though it's not bad),
and the first three examples in §4.1.
(5ed pp229.0-233.2, and the examples 1,2,4 in §3.3)
-
p.161 #14
(5ed: p.236 #14): sums over S={1,3,5,7}
-
p.280, #4:
Let P(n) = “1³+2³+...+n³ = (n(n+1)/2)²”.
- What is P(1)?
- Show P(1) is true, completing the base case.
- What is the inductive hypothesis?
- What do you need to prove in the inductive step?
- Complete the inductive step.
- Explain why these steps show
the formula holds for all postive integers n.
Don't worry if you trouble with the algebra (part (e));
that's the least important part of that problem.
If you see a few other problems in Rosen which catch your eye,
and you'd like to do them for extra credit, you are welcome to
(though you can ask me for how much; extra-credit is harder to earn
point-per-point than regular credit).
If you write your own html, you might be interested in this
page of useful html math (and other) entities
home—info—lectures—hws—exams
rad�ford.edu