Assignment 1, due Jun 12

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 (Tuesday or Thursday). 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, j )
      if i = 0
         return j
      else
         return f( j, i-1 ) + 1
   

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

   f(1,1) = f(1,0) + 1 = (f(0,0) + 1) + 1 = (0 + 1) + 1 = 2

   b) What is the value of f(2,3)? (0.2 point)

   f(2,3) = f(3,1) + 1 = (f(1,2) + 1) + 1 = ((f(2,0) + 1) + 1) + 1 =
   (((f(0,1) + 1) + 1) + 1) + 1 = (((1) + 1) + 1) + 1) + 1 = 5

   c) What is the value of f(5,8)? (0.2 point)

   13

   d) What is the value of f(13,21)? (0.2 point)

   34

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

   This function adds its arguments.

2. A test of your understanding of the prerequisites: Here is another pseudocode fragment:

   operation o(x,y) -- neither x nor y may be null
       temp = x.next
       x.next = y
       y.next = temp
       y.back = x
       temp.back = y
   

   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.) (0.5 points)

   Insert into a doubly-linked list.

3. A problem based on Chapter 2: Give the 7-bit ASCII representation of the text "Jun. 14, 2018" Don't include the quotation marks. Give your result as a column of binary numbers, one per character. (0.7 points)

   1001010
   1110101
   1101110
   0101110
   0100000
   0110001
   0110100
   0101100
   0100000
   0110010
   0110000
   0110001
   0111000
   0000000 -- C would put a null here, so if you did, that's OK.
   

4. Background: Take the due date, 06/12/2018, take out the slashes and interpret it as the decimal number 6122018.

   a) Convert this to binary using the pen and paper method shown in Chapter 2. Show your work! (0.4 points)

   6122018
   3061009 0
   1530504 1
    765252 0
    382626 0
    191313 0
     95656 1
     47828 0
     23914 0
     11957 0
      5978 1
      2989 0
      1494 1
       747 0
       373 1
       186 1
        93 0
        46 1
        23 0
        11 1
         5 1
         2 1
         1 0
         0 1
            10111010110101000100010
   

   b) Convert your answer from part A to hexadecimal. (0.4 points)

            101 1101 0110 1010 0010 0010
             5    D    6    A    2    2
   

   You can check your work in the above conversion problems by using any binary-hex-decimal conversion calculator, but you will be expected to be able to do such conversions by hand.