Assignment 1, due Aug 29

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 an integer!
      r = i mod 10
      q = i / 10   -- r and q are the integer remainder and quotient
      if q > 0
         return (f(q) × 8) + r
      else
         return r
   

   a) What is the falue of f(10)? (0.2 point)
   b) What is the falue of f(62)? (0.2 point)
   c) What is the falue of f(100)? (0.2 point)
   d) What is the falue of f(144)? (0.2 point)
   e) Give a short (in longer than 20 words) intuitive description of what this does? You might find that it is easier to describe the function if you ignore the "code" and pay attention only to the inputs and outputs you gave in parts a through e. (0.2 point)

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

   function f(x) -- x is either null or it refers to an object
                 -- the function has no return value but has
                 -- side effects through its call to output()
       if x ≠ null
           f( x.right )
           output( x.value )
           f( x.left )
   

   A Question: The above code performs an elementary operation on a common data structure. Name that operaton and name the data structure. (A gramatically correct answer can be given in about 10 words; an excellent but non gramattical answer takes answer can be given in 5 words.) (1 point)

   Homework questions based Chapter 2 of the text:

   Note: Some homework questions encourage you to read ahead by covering things before they are covered in lecture.

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