Assignment 1, due Jan 24

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!

Homework questions based on prerequisite material:

1. Background: Consider this recursive function, expressed informally:

   function f( i ) -- i is positive integer parameter
                   -- the return value is a character string
      r = i mod 10
      q = i / 10   -- r and q are the integer remainder and quotient
      if q > 0
         return f(q) concatenated with the character '0'+r
      else
         return '0'+r -- a single character
   

   Problem: What is the falue of f(1024). (1 point)

   In short, f(1024) = the string "1024"

   At greater length,

   f(1024) = f(102) concatenated with the character '0'+4

   f(102) = f(10) concatenated with the character '0'+2

   f(10) = f(1) concatenated with the character '0'+0

   f(1) = the character '0'+1 = the character '1' or the string "1"

   f(10) = "1" concatenated with the character '0'+0 = the string "10"

   f(102) = "10" concatenated with the character '0'+2 = the string "102"

   f(1024) = "102" concatenated with the character '0'+4 = the string "1024"

   Despite the prefix "the character" some students tried to interpret the operator in '0'+r as meaning some kind of string concatenation.

2. Background: Here is a fragment of informal (not a real programming language) code:

       a = head
       while a.value < b.value do a = a.next
       b.next = a.next
       a.next = b
   

   A Question: The above code inserts items into a data structure. In English, this description has a very simple description. (as in "a lexicographic binary tree" or "an unsorted doubly-linked list", neither of which applies in this case.) What is the simple description? (1 point)

   There was an error in the problem statement. A quick and careless reading (matching the quick and careless writing of the problem statement) suggests that the answer should be "a sorted linear list", however, the operator < was used when ≤ should have been used. As a result, full credit was given only to those who caught the error and did not assert that the list was fully sorted.

   Homework questions based Chapter 2 of the text:

3. A Problem: Give the 7-bit ASCII representation of the text "Jan. 24, 2014" Don't include the quotes. Give your result as a column of binary numbers, one per character. (1 point)

   J	1001010
   a	1100001
   n	1101110
   .	0101110
   SP	0100000
   2	0110010
   4	0110100
   ,	0101100
   SP	0100000
   2	0110010
   0	0110000
   1	0110001
   4	0110100