8:00 Quiz 6

Statistics:

(including the 2-point curve)

mean     22.615 (804.000/39)
stddev   5.246
median   22.000
midrange 19.750-26.250

#  avg
1  7.26 / 10
2  2.33 /  5
3 10.92 / 15
 + 2-point curve

Question 6-1

[10 pts] Suppose we have the class defined as below.

class C {
    static int x = 0;
    int y;

    C() {
        y = 0;
    }
    void incrX() {
        x++;
        IO.println(x);
    }
    void incrY() {
        y++;
        IO.println(y);
    }
    void incrZ() {
        int z = 0;
        z++;
        IO.println(z);
    }
}

public class Example {
    public static void run() {
        C a = new C();
        C b = new C();
        a.incrX();
        a.incrX();
        b.incrX();
        a.incrY();
        a.incrY();
        b.incrY();
        a.incrZ();
        a.incrZ();
        b.incrZ();
    }
}

What would the computer print when it executes the Example class's run() method?

Question 6-2

[5 pts] Consider the following method.

public static void sortBadly(double[] to_sort) {
  for(int i = 0; i < to_sort.length; i++) {
    int item = to_sort[i];
    int dest = 0;
    while(to_sort[dest] < item) {
      dest++;
    }
    for(int j = i; j > dest; j--) {
      to_sort[j] = to_sort[j - 1];
    }
    to_sort[dest] = item;
  }
}

Let n represent the length of to_sort. In terms of n, how much time does the above method take? Use Big-O notation to express your answer, and provide the tightest bound that you can.

Question 6-3

[15 pts] A matrix is symmetric if, for each i and j, a_i,j = a_j,i. The following is an example of a symmetric matrix.

0	23	45
23	10	36
46	36	20

Another way of defining it: A symmetric matrix can be reflected across its main diagonal (top left corner to bottom right corner) to obtain the same matrix.

Complete the following method so that it returns true only if the two-dimensional array parameter mat is symmetric. Your solution may assume that the matrix is square (as many columns as rows).

public static boolean isSymmetric(int[][] mat) {



}

(Your solution shouldn't really be this long!)

Solutions

Solution 6-1

Solution 6-2

O(n²)

Solution 6-3

public static boolean isSymmetric(int[][] mat) {
    for(int i = 0; i < mat.length; i++) {
        for(int j = 0; j < mat.length; j++) {
            if(mat[i][j] != mat[j][i]) return false;
        }
    }
    return true;
}