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

### 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 Saturday, 11 August 2018, at 22:52 hours.