CS 112 Fall 2016-- Homework One Solution

 

Part A: Analytical Problems (20 pts)

  1. Give the following: log2(2) and log2(1024) and log2(1000) and floor( log2(1000) ) and ceiling( log2(1000) ) .

    21 = 2 so log2(2) = 1
    210 = 1024 so log2(1024) = 10
    log2(1000) = 9.9658
    floor( log2(1000) ) = 9
    ceiling( log2(1000) ) = 10


  2. For which values of N is log2(N) = floor( log2(N) ) ?
      floor(x) = x if and only if x is an integer, so this is true when N is an integer power of 2, 
          i.e., 1, 2, 4, 8, ......     
  3. For which values of N is (floor( log2(N) ) + 1) = ceiling( log2(N) ) ?
      Analogously with (2), ceiling(x) = x if and only if x is an integer; so
           if x is an integer then by (2), floor(x) + 1 != x = ceil(x).
      But if x is not an integer, then floor(x) is the integer just below x, 
           and ceiling(x) is the integer just above x, so floor(x) + 1 = ceiling(x);
      Therefore the statement is true when N is NOT an integer power of 2.  
  4. Suppose that a and b are int values. Simplify the following expressions to a boolean expression involving only a single operator:
    1. (!(a < b) && !(a > b)) Solution: (a == b)
    2. ( (a < b) == true ) Solution: (a < b)
    3. ( (a <= b) == false ) Solution: (a > b)
    4. (!(a > b) && !(a < a)) Solution: (a <= b)
    5. ( (b < b) || !(a <= b)) Solution: (a > b)

  5. Which of the following will create an error because of a misuse of types?
          (a)  int n = 3 + '3';                             // No error: '3' is coerced to int
          (b)  double x = (3.4 + (int) 2.1) * "3";          // Error: can't multiply a String!
          (c)  String s = "hi" + 5 + 't' + true + "there";  // No error: all types can be coerced to Strings.
        
    Solution: Only (b) causes an error!

  6. What do each of the following print? (Be sure you understand WHY!)
    1. System.out.println(2 + "bc");  prints: 2bc
    2. System.out.println(2 + 3 + "bc");  prints: 5bc
    3. System.out.println((2+3) + "bc");  prints: 5bc
    4. System.out.println("bc" + (2+3));  prints: bc5
    5. System.out.println("bc" + 2 + 3);  prints: bc23
  7. Consider the ordered list [ 2, 7, 12, 15, 19, 25, 26, 38, 45, 78 ] presented in lecture. During binary search, which numbers will take 3 comparisons to find (i.e., search for and return "Found!")?
    Solution: The list is:       2   7  12   15   19   25  26   38   45   78  
    
    Here is how many
    comparisons to find each:    3   2   3    4    1    3   4    2    3    4
    
    So the answer is:    2    12    25    45
    
  8. Again, considering binary search on the same list, will all unsuccessful searches (i.e., searching for a number not in the list) take the same number of comparisons (count only comparisons between n and a number in the list, not comparisons used to control the loop)? If not, give an example of two numbers (neither in the list) which prove your answer, and give the number of comparisons to do an unsuccessful search on each.
    Solution: NO!  To find a number not in the list, you would count the number of comparisons up to the last number
    examined, before left and right cross. So if you look at the list in the previous question, and the number of 
    comparisons for each, to search for 1 (and not find it) takes 3 comparisons, but to find 100 (and not find it) 
    takes 4. There are many such examples, obviously.  
    
  9. For the unordered list [ 78, 25, 2, 15, 26, 38, 7, 45, 12, 19 ] presented in lecture. Using linear search, what is the average number of comparisons to search for the even numbers in the list only (assume each even number is searched for once)?
    Solution: The list is:      78  25   2   15   26   38   7   45   12   19  
    
    Here are the even numbers
    and the number of 
    comparisons to find them:   78       2        26   38            12
                                 1       3         5    6             9
    
    Thus  (1 + 3 + 5 + 6 + 9) / 5 = 24/5 = 4.8
  10. Consider the following unordered list of integers: [ 2, 6, 3, 8, 6, 1, 3, 9, 3, 2]. What is the average number of comparisons to search for each of the numbers which occurs in the list? [Hint: when you search for a number, you only find the first occurrence of the number, never later duplicates.]
    Solution: The point is that 2, 3, and 6 occur more than once, and the second and third occurrences will never be touched!
    
    The list is:                 2   6   3   8   6   1   3   9   3   2     
    
    Here is how many
    comparisons to find each
    of the first occurrences:    1   2   3   4   x   6   x   8   x   x
    
    So the answer is:  (1 + 2 + 3 + 4 + 6 + 8) / 6 = 24/6 = 4