Assignment 1, due Jan 23

Solutions

Part of the homework for CS:2630, Spring 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

A test of your understanding of the prerequisites: Consider this recursive integer function. All operators here are integer operations. This is an informal expression of the function, that is, pseudocode; it is not coded in a real programming language:
```
function f( i )
   if i = 0
      return 0
   else
      j = f( i/4 )
      if i < (2*j + 1)*(2*j + 1)
         return 2*j
      else
         return 2*j + 1
```
a) What is the value of f(2)? (0.2 point)
b) What is the value of f(9)? (0.2 point)

f(0) = 0
f(1) = 1
f(2) = 1
f(3) = 1
f(4) = 2
f(5) = 2
f(6) = 2
f(7) = 2
f(8) = 2
f(9) = 3

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

f(36) = 6

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

f(144) = 12

e) Give a short (20 words suffice) intuitive description of what this does, not how it does it. (Ignore the code, look at your answers to parts a to e.) (0.2 point)

It computes the integer square root.
A test of your understanding of the prerequisites: Here is another pseudocode fragment:
```
function f(x,y) -- x may be null, y must not be null
    if x = null
        y.next = null
        return y
    else
        if x.value < y.value
            y.next = x
            return y
        else
            x.next = f( x.next, y )
            return x
```
A Question: This code performs an elementary operation on a common data structure. Name that operaton and name the data structure. (A 5 to 10 word answer will suffice.) (1 point)

Sort y into list x (in descending order).
A Problem based on Chapter 2 of the text: Give the 7-bit ASCII representation of the text "Jan. 23, 2015" Don't include the quotes. Give your result as a column of binary numbers, one per character. (1 point)
```
1001010
1100001
1101110
0101110
0100000
0110010
0110011
0101100
0100000
0110010
0110000
0110001
0110101
```