CS 136 Tutorials - Spring 2007

CS 136 Tutorial 13: Final Exam Review (July 27)

Today's tutorial covers a few topics that are likely to appear on your final exam. These were covered in lecture modules throughout the year. (see handouts).

  1. List Mutation
  2. Given a list of lists in scheme. Write the following functions that will allow you to extend the 2D structure to be square.

      //max-sub-length: (listof (listof int)) -> int
      max-sub-length
      : returns an integer representing the length of the longest sub list.

      examples:

       (max-sub-length '(() ())) ;=> 0
       (max-sub-length '((1 2) (1))) ;=> 2
       (max-sub-length '((1 2) (1 2 3))) ;=> 3
       (max-sub-length '((1 2) (1 2 3 4) (0 1 2))) ;=> 4
      


      //extend-list: (listof int) int -> (listof int)
      extend-list
      : adds 0's to the end of the list (using mutation when possible) until the list has length k, and returns this longer list.

      examples:

       (extend-list '() 2) ;=> '(0 0)
       (extend-list '(1 2) 3) ;=> '(1 2 0)
       (extend-list '(0 1 2) 4) ;=> '(0 1 2 0)
       (extend-list '(1 2 3 4) 3) ;=> '(1 2 3 4)
      


      //square-the-lists: (listof (listof int)) -> (listof (listof int))
      square-the-lists
      : adds 0's until the list of lists is square.

      examples:

       (square-the-lists '(() ())) ;=> '((0 0) (0 0)))
       (square-the-lists '((1 2) (1))) ;=> '((1 2) (1 0))
       (square-the-lists '((1 2) (1 2 3))) ;=> '((1 2 0) (1 2 3) (0 0 0))
       (square-the-lists '((1 2) (1 2 3 4) (0 1 2))) ;=> '((1 2 0 0) (1 2 3 4) (0 1 2 0) (0 0 0 0))
      

    For some more review try the following:

    • complete the above using scheme's vectors
    • complete the above using java's GenList<GenList<int>>
    • complete the above using java's int[][]

  3. Code Visualization
  4. Draw out the following code, skipping over and explaining any lines that would cause an error:

      public class StringBox {
        private String str;
        
        public StringBox() {
         str = null; 
        } 
        public StringBox(String s) {
         str = s;
        }
      
        public String get() {
         return str;
        }
        public void set(String s) {
         str = s;
        }
        public boolean equals(StringBox sb) {
         return this.str .equals(sb.str);
        }
      }
      
      
      public class Visualize { 
        public static void main(String[] args) { 
      
         StringBox[][] strbArray; 
         strbArray = new StringBox[2][]; 
         strbArray[0] = ""; 
         strbArray[1] = new StringBox[1]; 
         strbArray[0] = new StringBox[2]; 
      
         strbArray[0][0] = "";
         strbArray[0][0] = new StringBox(""); 
         strbArray[1][0].equals(strbArray[0][0]); 
         strbArray[0][0].get().equals(strbArray[1][0]);
         strbArray[0][0].equals(strbArray[1][0]);
         
         strbArray[1][0] = new StringBox(""); 
         strbArray[1][0].get().equals(strbArray[0][0]);
         strbArray[1][0].equals(strbArray[0][0]);
      
         strbArray[0][0].set("a"); 
         strbArray[0][1].set("b"); 
         strbArray[1][0].set("c");
         strbArray[0][1] = new StringBox(""); 
      
         strbArray[0][0] = strbArray[0][1]; 
         strbArray[0][1] = strbArray[1][0]; 
         strbArray[1][0] = strbArray[0][0]; 
      
         System.out.println(strbArray[0][0].get()); 
         System.out.println(strbArray[0][1].get()); 
         System.out.println(strbArray[1][0].get()); 
      
         strbArray[0][0].set(strbArray[0][1].get()); 
         strbArray[0][1].set(strbArray[1][0].get()); 
         strbArray[1][0].set(strbArray[0][0].get()); 
      
         strbArray[1][0].set("not it");
         strbArray[1][0] = new StringBox("i'm it");
      
         System.out.println(strbArray[0][0].get()); 
         System.out.println(strbArray[0][1].get()); 
         System.out.println(strbArray[1][0].get()); 
        } 
      }
      

  5. Code Efficiency
  6. Without proof, determine the Efficiency of max-sub-length, extend-list and square-the-lists. Do these change when changing the data type?


    Determine the big-O expersion for the following functions:

      sqrt(n) + log(n)
      sqrt(n)/n + log(n)/sqrt(n) + sqrt(log(n))

      A few more difficult examples follow, they are interesting though they're to difficult to test on the exam ... try graphing them to compair the terms just to get a feel for them.

      n^(1/n) + log(n)
      log^n(n) + n^log(n)
      sqrt(log(n)) + log(sqrt(n))
 

Last modified on Saturday, 11 August 2018, at 22:52 hours.