CS61B Summer 2000, Final Exam TA Submitted Review Problems

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


1)  The n-queens problem asks how n queens can be placed on an n x n
chessboard so that no two queens can attack one another.  (Queens can move
horizontally, vertically, and diagonally.)  Design a solution to the
n-queens problem. Think depth first search and consider using a stack.
 
This is the function prototype.
 
int [][] nqueens(int n)
 
The 2-d int array you return should be n x n, and it should contain 1 if
the location of a queen, and 0 where there is no piece.

 
2)  Devise an algorithm to find the second shortest spanning tree in a
connected weighted graph.


3) Write a function in C that, given a pointer to a null terminated
sequence of characters, determines whether the {,[,and ( in the sequence
are appropriately matched.  The function returns false if the delimiters
are matched, and a pointer to the first offending delimiter otherwise.

       braceAndParensNotMatched(


4) Prove or disprove: A shortest paths set of edges in a graph G contains
at least one edge in common with any Minimum Spanning Tree in G.


5) Implement a D-ary Heap class.


class dheap{

~  //Some number of variables.
  //Fill this in.

  public dheap(int somed){






  public dheap(int somed, Comparable[] cosas){





 public void toss(Comparable x){



  public void insert(Comparable x){



  public Comparable deleteMax(){



  private void fixheap(){




  private void percolateDown(int hole){






}


6) What does the follow C code do?

int* foo (int x, int y) {
  int *z;
  z=(int *)malloc(x*sizeof(int));
  for (int i=z; i<z+x; i++) {
    *i=y;
  }
  return z;
}


7) Convert the following Java code to its equivalent in C:
  
static List reverse(List L) {
  List result, p;
  for (result=null, p=L; p!=null; p=p.tail)
    result=new List(p.head, result);
  return result;
}

Assume you are given the following struct definition:

struct List {
  int head;
  struct List *tail;
};

8.  Draw a box and pointer diagram of the results from the following
C code.  Your diagram should also include a representation of the
system's memory, its components (stack, heap, etc.), and how it
is all connected.  All boxes you draw should contain an arrow
or a value.  Use a ? to mark boxes with unknown values.

char title[] = "Greetings";

void greeting() {
    char *spanish = "Hola";
    char *german;

    int i = 3;
    int iArr[4];
    int *pi;
    
    iArr[2] = 7;
    pi = iArr;

    *pi = 3;
    pi++;
    *pi = 4;
    pi = pi - 2;

    pi = (int *)malloc(sizeof(int) * 5);

    pi[3] = 9;
    *(pi+2) = 7;

    spanish = "Buenos Dias";
    german = "Guten Tag";
}

9.  C and Java have different ways for coding the start of a program.
What must every Java class have in order to be run?  C program?

10. Explain what would happen in the following C snippets:
compiler error, compiler warning, strange behavior, will crash
the program and/or your computer, implementation dependent, or
everything will be fine

a.

int *i = malloc(sizeof(float) * 7);

b.

float f = 5.6;
int j = f;

c.

float *f;
*f = 5.6;
int *pi = f;

d.

int x;
if (x = 3) printf("%s","Hey!");

e.

int arr[10];
int *p = arr + 5;
printf("%d", p[-2]);


11.  Sorting short answer

a.  Ben Bitdiddle claims that bubble sort runs in O(n) time.  After
all, [0 1 2 3 4 5] only takes n steps to sort with his algorithm.
Do you agree with him or not?  Why?

b.  Cy D. Fect claims merge sort and heap sort both have the same
running time, so we only need to know one or the other.  What are
the downsides to each algorithm?  To further bolster his argument, 
he claims that since  they have the same running time, they will 
take the same amount of  time to run.  Do you agree or disagree? 
Why?

c.  Quicksort and merge sort both use a divide-and-conquer type
algorithm.  Why then can quicksort in certain instances have 
worse complexity than merge sort?

12.  In each of the lines of the main function there are one or more 
problems which will cause an error (or atleast a warning).  Identify
and fix each in succession.

#include <stdlib.h>             /* Contains declaration of malloc. */
#include <stdio.h>              /* Declaration of printf. */

struct A {
   int x;
   double y;
};

int main () {
   /* Each line is problematic. */       
   A structVariable;
   A structPointer *;

   structVariable->x = 13;

   &structPointer = malloc (sizeof (struct A));
   *(structPointer.y) = 13.2;

   structPointer = *structVariable;

   free (structPointer);

   /* The return is fine. */
   return 0;
}

13.  This problem is taken from "Algorithms in C++", written
by Robert Sedgewick.  Write a non-recursive quicksort algorithm
using a stack.  Assume that you will be sorting integers and that
you can use the java Stack class.  Also assume the existence of 
a partitioning function which takes an array of ints, an upper and
lower bound, and returns the final index of the partitioned element.

14.  Prove the correctness of Kruskal's algorithm.

15.  In the lecture notes, Mike talked about using BFS to find the
   shortest path between nodes on an unweighted graph. However, we can
   in fact use BFS to find the shortest path between nodes on a
   WEIGHTED path. Explain how this can be done. How does Dijkstra's
   algorithm speed up your algorithm?