CSE 373, Autumn 2004: Assignment 3

Objectives

When and How

The Exercises

1. (10 points) Consider the following ADT for a one-dimensional array of strings.
   Data:

    a function whose domain is the set {0, 1, ..., n-1}
    and whose range is the set of strings (over the ASCII character set).
   

   Operations:

    STORE -- puts a string in a particular array location.
    ACCESS -- returns a string from a particular array location.
   

   
   (a) Let f_s be a function representing the STORE operation. Identify the domain and range of f_s. Give a formula that shows how f_s maps an element of its domain to the corresponding element of its range.
   (b) Let f_a be a function representing the ACCESS operation. Identify the domain and range of f_a. Give a formula that shows how f_a maps an element of its domain to the corresponding element of its range.
2. (10 points) Prove by induction that for all nonnegative integers n
   6(1²) + 6(2²) + ... + 6(n²) = n (n+1)(2n+1)
3. (10 points) Prove by induction that for all nonnegative integers n
   4(1³) + 4(2³) + ... + 4(n³) = n² (n+1)²
4. (10 points) Prove by induction that the INTERLEAVE algorithm (the one implemented in the sample solution to Assignment 1 below) correctly interleaves the elements of two lists for a pair of equal-length lists of length 0 or more.

   static Node interleave(Node listA, Node listB) {
     if (listA == null) return listB;
     if (listB == null) return listA;
     return addToFront(listA.data, 
                        (addToFront(listB.data,
                          interleave(listA.next, listB.next))));
   }
   

5. (a) (20 points; -2 for each incorrect entry) Fill in the following table Each entry should be either big O, Ω (big omega), Θ (big theta), or "incomparable." Since row 1 is already filled in for you, there should not be any ambiguity in what you need to do here.
    
   

   	f(n) = 5	f(n) = 10 log2 n	f(n) = sqrt n	f(n) = n / 100	f(n) = 50 n	f(n) = n log2 n	f(n) = 2n2	f(n) = 100n2	f(n) = 1.01n	f(n) = n!
   f(n) = 5	Θ	O	O	O	O	O	O	O	O	O
   f(n) = 10 log2 n
   f(n) = sqrt n
   f(n) = n / 100
   f(n) = 50 n
   f(n) = n log2 n
   f(n) = 2n2
   f(n) = 100n2
   f(n) = 1.01n
   f(n) = n!

   
    
   
   (b) (5 points) Justify your entry for the comparison between n log₂ n and 2n² (using the justification approach shown in Example 3.6 of Goodrich and Tamassia 3rd edition on page 118).
   (c) (5 points) Justify your entry for the comparison between 2n² and 100n².