ibarland

hw09
sums, induction

Due: 2008.Nov.14 (Fri)

(2pts) Express the numbers 0..15 as four-digit binary numerals (starting with "0000"), one per line.
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"
If you want to improve readability by grouping the bits into nibbles [four bits], that would be most welcome.
(2pts) p.229 #4a (5ed: p179 #4a): string→int Show your work.
(2pts) p.229 #6 variant (5ed: p179 #6 variant): what binary numeral represents the same number as the hexadecimal numeral "ACED"?
(2pts) p.230 #10 (5ed: p179 #10): binary numerals → hex numerals.
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.

(2pts) Without running it, figure out what the following nested-loop pseudocode prints out:

  for (int i=0; i<10; ++i) {
    for (int j=0; j<10; ++j) {
      print((i*j) mod 10);
      }
    print("\n"); // end the line.
    }

(2pt extra credit) Repeat the previous problem, changing all the '10' to '16', and printing the numbers as hexadecimal digits.

¹ Each equality includes the algorithm's numeralSoFar and num. Writing the answers as a series of equalities like this actually traces of the recursive formulation:

String itos(int n) {
  return (n==0) ? "" : itos(n/10) + dtos(n%10);
  }

(Well, it nearly traces that; we are actually simplifying the string-concatenation in a different order than the computer would. Take ITEC380, for more on the relation between loops and recursion.) ↩

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University
Last modified 2008.Dec.13 (Sat) Please mail any suggestions
(incl. typos, broken links)
to iba�rlandrad�ford.edu

hw09sums, induction

hw09
sums, induction