Assignment 1, due Jan 23Solutions
Part of
the homework for CS:2630, Spring 2015

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.
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).
1001010 1100001 1101110 0101110 0100000 0110010 0110011 0101100 0100000 0110010 0110000 0110001 0110101