Assignment 1, due Aug 29

function f( i ) -- i is positive integer parameter
                -- the return value is an integer!
   r = i mod 10
   q = i / 10   -- r and q are the integer remainder and quotient
   if q > 0
      return (f(q) × 8) + r
   else
      return r

a) What is the value of f(10)? (0.2 point)

f(10) = 8

b) What is the value of f(62)? (0.2 point)

f(62) = 50

c) What is the value of f(100)? (0.2 point)

f(100) = 64

d) What is the value of f(144)? (0.2 point)

f(144) = 100

e) Give a short (in longer than 20 words) intuitive description of what this does? You might find that it is easier to describe the function if you ignore the "code" and pay attention only to the inputs and outputs you gave in parts a through e. (0.2 point)

Convert an octal number (represented in decimal, strangely) to decimal.

(Not part of the answer: You might do this if you were writing code in a language where the only numeric input supported was decimal input, but you wanted the user to enter an octal number. Of course, it gives nonsense answers if the user happens to enter digits greater than 7, although this error could be fixed.)

function f(x) -- x is either null or it refers to an object
              -- the function has no return value but has
              -- side effects through its call to output()
    if x ≠ null
        f( x.right )
        output( x.value )
        f( x.left )

A Question: The above code performs an elementary operation on a common data structure. Name that operaton and name the data structure. (A gramatically correct answer can be given in about 10 words; an excellent but non gramattical answer takes answer can be given in 5 words.) (1 point)

In-order binary-tree traversal.

This code traverses a binary tree in lexicographic order. (Actually, it is reverse lexicographic order, since it is right to left and not left to right, but that is quibbling with the main issues heere.)

Homework questions based Chapter 2 of the text:

Note: Some homework questions encourage you to read ahead by covering things before they are covered in lecture.

1 0 0 0 0 0 1    A
1 1 1 0 1 0 1    u
1 1 0 0 1 1 1    g
0 1 0 1 1 1 0    .
0 1 0 0 0 0 0
0 1 1 0 0 1 0    2
0 1 1 1 0 0 1    9
0 1 0 1 1 0 0    ,
0 1 0 0 0 0 0
0 1 1 0 0 1 0    2
0 1 1 0 0 0 0    0
0 1 1 0 0 0 1    1
0 1 1 0 1 0 0    4