CS61B Summer 2000, Final Exam TA Submitted Review Problems Solutions

This will be updated as TA's submit their questions.


1) I created an auxilliary class:

class Board {
int[][] myBoard;
int nextRow;
int nextCol;
public Board(int [][] b, int r, int c) {
myBoard = b;
nextRow = r;
nextCol = c;
}
//nextRow and nextCol store the next place to test
public Board clone() {
int[][] a = new int[myBoard.length][myBoard.length];
for (int i = 0; i < a.length; i++) 
        for (int j = 0; j < a.length; j++)
            a[i][j] = myBoard[i][j];
return new Board(a, nextRow, nextCol);
}

public boolean illegalMove(row, col) {
//assume this works.  it tests to see if a move can be made
//without interfering with another queen
}
}

now the main function

int[][] nqueens(int n) {
Board b = new Board(new int[n][n], 0, 0);
Stack s = new Stack();
int col = b.nextCol;
while (col < n)  {
    boolean foundRow = false;
    for (int row = b.nextRow; row < n; row++){
        if (b.myBoard[row][col] == 0) {~
            if (!b.illegalMove(row, col)) {
                b.nextRow = row + 1;
                b.nextCol = col + 1;
                s.push(b);
                b = b.clone();
                b.myBoard[row][col] = 1;
                b.nextRow = 0;
                b.nextCol++;
                foundRow = true;
                break;
}}}
if (!foundRow) 
    b = s.pop();
col = b.nextCol;
}
return b.myBoard;
}


2) First find a minimum spanning tree T of the graph G with n edges.  Then
for i = 1 to n - 1, only delete the ith edge of T from G and find a
minimum spanning tree of the remaining graph.  Pick the one of these n - 1
trees with the shortest length. 

3)

char* braceAndParensNotMatched(char* string){
  int i=1;
  char* stack=string;
  while(*stack){
   i++;
   stack++;
  }
  stack=(char*)malloc(i*sizeof(char));
  i=0;
  while(*string){
    switch(*string){
     case '(':
     case '[':
     case '{': stack[i]=*string;
               i++;
               break;
     case ')': if(i==0||stack[i-1]!=(*string)-1){   /*')'-1=='('*/
                 free(stack);
                 return string;
              } else {
                 i--;
                 break;
               }
     case ']':
     case '}': if(i==0||stack[i-1]!=(*string)-2){ /*'}'-2=='{',']'-2=='['*/ 
                 free(stack);
                 return string;
               } else {
                 i--;
                 break;
               }
     }
   string++;
  }
  free(stack);
  return (*string)?string:(char*)*string;  /* return address or null pointer */
}


4) The statement is false.  Counterexample:

Let G be a complete graph of four vertices, A, B, C, and D, where all edge
weights are 0.  Then AB, AD, BC is a shortest paths tree, and AC, CD, DB
is an MST and the two sets are disjoint.

5) Awaiting correct solution.

6) Returns an array of size x with each element initialized to y.

7)
struct List* reverse(struct List* L) {
  struct List *result, *p, *temp;
  for (result=NULL, p=L; p!=NULL; p=p->tail) {
    temp=result;
    result=(struct List *)malloc(sizeof(struct List));
    result->head=p->head;
    result->tail=temp;
  }
  return result;
}

8.

         +
spanish  | -------------------------\  Stack
german   | -----------------------\ |
i        | 3                      | |
iArr     | 3                      | |
         | 4                      | |
         | 7                      | |
         | ?			  | |
pi       | |              	  | |
	   |			  | |
	   V        		  | |
         | ?			  | |  Heap
         | ?			  | |
         | 7			  | |
	 | 9			  | |
	 | ?			  | |
				  | |
				  | |  
title    | "Greetings"		  | |  Static Storage
         | "Hola"		  | |
	 | "Buenos Dias" <----------/
         | "Guten Tag" <----------/ 

9.

Java must have a static void main(String[] args) function that is
accessible by the java runtime.  C must have a void main or
int main function.

10. 

a.  You will get a compiler warning for not casting from the
void * to the int *.

b.  Everything will be fine.  Like Java, C allows this to 
happen.  The 5.6 will simply be truncated to 5.

c.  This will cause "strange" behavior.  There's no actual
memory location for 5.6 to go into.  f starts out being some
arbitrary memory location.  However, C will not complain about
doing this on compile time.  You will however get a casting warning
for the thrird line.

d.  Yes, this is ok as well.  The program will end up printing
Hey!.  Remember, it first sets x to 3.  Next, it evaluates the 
expression which results in 3, which is true since all non-zero
integers evaluate to true.

e.  Yes, this is ok.  They look very bizarre, but negative array
indexes are legal.


11.

a.  n is only the best case scenario.  Worst case running time of
this algorithm is O(n^2).  When we use O() notation, the worst
case is always considered.

b.  Heap sort often has a higher overhead since a heap must be
created.  At the same time merge sort often has a high recursive
overhead.

O notation only specifies how quickly something grows, not how
large in actually is.  While they both grow at the same rate
(n * log n), one could have a large C or k dependent on
implementation.

c.  In an already sorted (or close to being already sorted) array,
bad pivots can be chosen quite easily by quicksort.  The division
of the array into halves is based only upon the probabilistic
assumption that the pivot will more often that not be near the
median.  Merge sort on the other hand always manages to divide
in half.  If quicksort consistently picks bad pivots, it's running
time can decay to O(n^2).

12.
int main () {
    /* A is not a new type as it would be in a C++/Java class
    definition.  Rather it must always be referred to using the
    struct keyword!  Note that we are allocating this object on
    the stack. */
    /* A structVariable; */
    struct A structVariable;

    /* Not only do we need to say struct A here, but the * needs
    to appear between A and structPointer.  Note that all we are 
    doing here is creating a pointer variable on the stack. */
    /* A structPointer *; */
    struct A *structPointer;

    /* Here we are accessing the version of x inside the 
    structVariable object.  Remember that if the struct object is 
    identified by a regular variable, we will access the object
    using the '.'.  If we have a pointer to the object, then we
    will use the '->'. */
    /* structVariable->x = 13; */
    structVariable.x = 13;

    /* Two things are wrong here - first of all, the malloc function
    returns a pointer of void type (commonly referred to as a void
    pointer).  We should cast this.  More importantly, the 
    &structPointer construct is blatantly wrong.  We can't set the 
    address of any variable even if we wanted to.  What we are trying
    to do is get structPointer to point at the newly allocated object.
    We do this by setting its value with simple assignment.  Note
    that the newly created object will be placed in the heap. */
    /* &structPointer = malloc (sizeof (struct A)); */
    structPointer = (struct A *) malloc (sizeof (struct A));

    /* Two things wrong here.  First of all, structPointer points to
    an object of struct A type.  Therefore we would access the 'y'
    field using the '->' operator, not the '.' operator.  Secondly,
    using the pointer referencing operator like this is wrong.  Note
    that because of the parentheses, that we are trying to dereference
    a double, not a pointer.  So we have two possible solutions. */
    /* *(structPointer.y) = 13.2; */
    (*structPointer).y = 13.2;
    structPointer->y = 13.2;

    /* This is wrong.  We want to set structPointer to point at the 
    object identified by structVariable.  Therefore we need to set
    the value of structPointer to be the address of structVariable. */
    /* structPointer = *structVariable; */
    structPointer = &structVariable;

    /* Note that structPointer originally pointed to an object 
    created on the heap.  As of the last line of code, it now points
    at an object created on the stack.  The free function can only be
    used on dynamically allocated memory (heap memory).  There is no
    way to fix this other than to get rid of the line.  We are no
    longer able to free the dynamically allocated memory because we
    no longer have a pointer to it. */
    /* free (structPointer); */

    return 0;
}

13.

import java.util.*;

class mystack {

  // Pushes two ints onto a stack.
  static void push2 (Stack s, int a, int b) {
    s.push(new Integer (b));
    s.push(new Integer (a));
  }

  // Partitioning function.
  static int partition (int [] a, int l, int u) {
    int i = l-1;
    int j = u;
    int v = a[u];

    for (;;) {
      while (a[++i] < v);
      while (v < a[--j]) if (j == 0) break;
    
      if (i >= j) break;
      
      exch (a, i, j);
    }
        
    exch (a, i, u);
    return i;
  }

  // Helper function for partitioning.
  static void exch (int [] a, int b, int c) {
    int temp = a[b];
    a[b] = a[c];
    a[c] = temp;
  }

  // Here's the quicksort algorithm.
  static void qsort (int [] x, int l, int u) {
    Stack s = new Stack ();

    // Push the original bounds on the stack.
    push2 (s, l, u);

    while (!s.empty()) {
      // Get the new bounds of the stack.
      l = ((Integer)s.pop()).intValue();
      u = ((Integer)s.pop()).intValue();
      
      if (u <= l) continue;

      // Partition.
      int i = partition (x, l, u);

      // Push the range of the subfiles on the stack.  The if/else
      // logic is used to push the larger subfile on the stack first.
      // This ensures that the stack never has more than log N 
      // entries (N is the length of the array.
      if (i-1 > u-i) {
        push2 (s, l, i-1);
        push2 (s, i+1, u); 
      }
      else {
        push2 (s, i+1, u);
        push2 (s, l, i-1);
      }
    }
  }

  public static void main (String [] args) {
    int x [] = {1, 4, 6, 2, -3, 10, 39, 64, 0, 1, 0};
    qsort (x, 0, x.length-1);
    ArrayUtil.printArray (x);
  }
}    

14.

 Using pseudo-induction and contradiction. At the base case, we have
   non-connected nodes. Trivially, the we can compute the MST of each
   of these nodes (ie: there are no edges). The only question is: how
   do we know that when we merge two MST's together, that the
   resulting spanning tree is still minimum? In Kruskal's algorithm,
   we'd take the edge of least weight between the two MSTs (call this
   edge e1).  Suppose that taking edge e1 does NOT produce a MST. Then
   this means that another edge, e2, connects the two MSTs and creates
   an MST. For this to happen, that means that one (or more) edges of
   one of the two sub MSTs must have been composed of an edge of
   larger weight: ie: one of the sub "MSTs" isn't really a MST. Proof:
   we use our original MST and this is of less weight than our
   conjectured one! Therefore, contradiction.


15.


 We "expand" an edge of weight n into a line of n edges, each with
   weight 1 in between them. Then perform BFS on that. The advantage
   to Dijkstra's algorithm is that if you notice that when we perform
   the BFS, most of the calculation is very boring (ie: adding 1's to
   our current shortest path for any given node). Dijkstra essentially
   'notifies' us when the exciting stuff happens: ie: a node's value
   is changed as a result of a shorter path occurring.