CS 136 Tutorials - Spring 2007

Tutorials »

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).

List Mutation

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[][]

Code Visualization

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()); 
  } 
}

Code Efficiency

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 Friday, 19 August 2011, at 18:05 hours.