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.

Current computers can have a clock speed of 3GHz — 3 billion bit-operations per second (!). Complete the following table with the most appropriate: ≤ one μs (one microsecond — ), ≤ one second, ≤ one day, ≤ one year, ≤ one millenium (=1000yrs), ≤ one universe-lifetime (=¹⁰yrs), longer, problem size bit operations needed problem size:
n log n n n² ⁿ³ ²ⁿ 10 100 1000 ¹⁰ (million) ¹⁰ (billion)

What is the largest integer value of n such that ... n≤ ¹⁰?
(This is the largest problem that can be solved by an n algorithm within a second, on a modern computer.) n³ ≤ 3·¹⁰? ⌊³√n⌋·¹⁰ = 1442.
(This is the largest problem that can be solved by an n³ algorithm within a second, on a modern computer.) n³ ≤ 3·¹⁰?
⌊³√n⌋·¹⁰ = 144324. (This is the largest problem that can be solved by an n³ algorithm within a semester, on a modern computer.) n³ ≤ 3·¹⁰?
⌊³√n⌋·¹⁰ = 1442249570 It's ridiculous to include so many digits of accuracy, esp. in a problem which is estimating current processor speed at 3GHz. (If the actual speed were 3.01GHz, then most of the digits of accuracy are suddently pointless.) (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 ¹⁰ (an algorithm with exponential running time; an example would be looking at a chess game, and computing all possible outcomes n moves ahead). ¹⁰ < 3·¹⁰ n=⌊_log(3·¹⁰)⌋ =⌊_log(3)+log(¹⁰)⌋ = ⌊_log(3)+9⌋ = 9. ¹⁰ < 3·¹⁰ n=⌊_log(3·¹⁰)⌋ =⌊_log(3)+log(¹⁰)⌋ = ⌊_log(3)+15⌋ = 15. ¹⁰ < 3·¹⁰ n=⌊_log(3·¹⁰)⌋ =⌊_log(3)+log(¹⁰)⌋ = ⌊_log(3)+27⌋ = 27. p.217 #4 (5ed: p167 #12): prime factorizations 39=3·13 81=3·3·3·3 101=101 143=11·13 289=17·17 899=900-1=(30-1)(30+1)=29·31 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, ⪚:
   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.)
   itos(321)
= itos(160)+"1"
= itos(80)+"01"
= itos(40)+"001"
= itos(20)+"0001"
= itos(10)+"00001"
= itos(5)+"000001"
= itos(2)+"1000001"
= itos(1)+"01000001"
= itos(0)+"101000001"
= ""+"101000001"
= "101000001"
   itos(1023)
= itos(511)+"1"
= itos(255)+"11"
= itos(127)+"111"
= itos(63)+"1111"
= itos(31)+"11111"
= itos(15)+"111111"
= itos(7)+"1111111"
= itos(3)+"11111111"
= itos(1)+"111111111"
= itos(0)+"1111111111"
= ""+"1111111111"
= "1111111111" p.229 #4a (5ed: p179 #4a): string→int Show your work. stoi("11011") = 1·² + 1·² + 0·² + 1·² + 1·² = 16+8+2+1 = 27. p.229 #6 variant (5ed: p179 #6 variant): what binary numeral represents the same number as the hexadecimal numeral "ACED"? _[ACED]16 = _{[1010 1100 1110 1101]2} (spaces included just for readability) p.230 #10 (5ed: p179 #10): binary numerals → hex numerals. _{[1 1000 0110 0011]2} = _[1863]16 p.230 #20 variant (5ed: p180 #20 variant): Use Algorithm 5 of the book to compute ³⁴⁵¹³⁸ mod 777.
Show your work, as a table with columns for each variable (Note that 138=128+8+2.) ipowerx 345 10144 1172972925347293 8177447507745 977467747747519774 (!)

Note that the last step is a bit surprising: 774·519 ≡774 (mod 777). In normal math, 774x=774 would mean that x=1, but not so mod 777! (Observe that 777 isn't a prime number (777=3·7·37). It turns out that modular arithmetic is better-behaved whenever the modulus is prime.) 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. gcd(1,5) = gcd(5,1) = gcd(1,0) = 1 gcd(100,101) = gcd(101,100) = gcd(100,1) = gcd(1,0) = 1 gcd(123,277) = gcd(277,123) = gcd(123,31) = gcd(31,30) = gcd(30,1) = gcd(1,0) = 1 gcd(1529,14039) = gcd(14039,1529) = gcd(1529,278) = gcd(278,17) = gcd(17,6)=gcd(6,5)=gcd(5,1)=gcd(1,0)=1 gcd(1529,14038) = gcd(14038,1529) = gcd(1529,277) = gcd(277,144) = gcd(144,133)=gcd(133,11)=gcd(11,1)=gcd(1,0)=1 gcd(11111,111111)=gcd(111111,11111)=gcd(11111,1)=gcd(1,0)=1

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 #2 (53d: p.236 #2): a_n p.161 #14 (5ed: p.236 #14): sums over S={1,3,5,7} Σj = 1+3+5+7 = 16 Σj = 1+3+5+7 = 1+9+25+49 = 84 Σ(1/j) = 1/1+1/3+1/5+1/7 = (105/105)+ (35/105) + (21/105) + (15/105) = 176/105 = 1+71/105 Σ1 = 1+1+1+1 = 4 p.280, #4: Let P(n) = 1³+2³+...+n³ = (n(n+1)/2)². What is P(1)? 1³ = (1·(1+1)/2)² Show P(1) is true, completing the base case. Easy arithmetic: (1·(1+1)/2)² = (1·(2/2))² = 1² = 1 = 1³, as desired. What is the inductive hypothesis? P(k), which is 1³+2³+...+k³ = (k(k+1)/2)² What do you need to prove in the inductive step? P(k+1), which is 1³+2³+...+k³+(k+1)³ = ((k+1)(k+2)/2)² Complete the inductive step. 1³+2³+...+k³ = (k(k+1)/2)² inductive hypothesis ⇔ 1³+2³+...+k³ +(k+1)³
= (k(k+1)/2)²+(k+1)³ add (k+1)³to both sides of an equality = ((k+1)/2)²k² + 4((k+1)/2)²(k+1) algebra = ((k+1)/2)²(k² + 4(k+1)) factor out ((k+1)/2)² = ((k+1)/2)²(k+2)² algebra = ((k+1)(k+2)/2)² algebra

Thus we have (from the 2nd and last lines) 1³+2³+...+k³ +(k+1)³
= ((k+1)(k+2)/2)², which is exactly P(k+1). Explain why these steps show ∀n∈^N+.P(n). the formula holds for all postive integers n. We showed P(1), and we showed that ∀k.(P(k)→P(k+1)). By the inference rule of mathematical induction, we can conclude ∀n.P(n) (for the domain of integers 1 or greater). 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