Assignment 1, due Jan 23

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

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (usually Friday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

  1. 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
          j = f( i/4 )
          if i < (2*j + 1)*(2*j + 1)
             return 2*j
             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)
    c) What is the value of f(36)? (0.2 point)
    d) What is the value of f(144)? (0.2 point)
    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)

  2. 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
   = null
            return y
            if x.value < y.value
       = x
                return y
       = f(, 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)

  3. 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)