Summer 2016 COP3530 Final Exam Key

Q1:

What is the computational complexity (Big-O Notation) of the following Javascript function

 

function go(n) {
  var c = 0;
  for (var i = 1; i < n; i ++) {
    for (var j = 1; j < n; j *= 2 ){
    c++;
   }
 }

Answer:

There are 2 loops, one does n, the other does log n, so O(n log n)

 

Question 2

You are going to implement a binary addition module in Javascript (as part of the exam). This will be a Linked List (a Stack works well for this) implementation with two functions addBit() and print(). AddBit will go to the last node in the list.

- If the value of that node is null or 0 - then it will flipped.

- If the value of the node is 1, it will be changed to 0, and the node before it will flipped.

- Flipping a Node;

 > If the value is 0 or null, it becomes 1

 > If the value is 1, it becomes 0 and the preceding node is flipped.

- If there is no preceding node (top of stack) - a node is pushed onto the stack with value 1.

The counter should give the following values each time a bit is added (you can go left to right or right to left);

1           1

0,1         1,0

1,1         1,1

0,0,1      1,0,0

1,0,1      1,0,1

0,1,1      1,1,0

1,1,1      1,1,1

0,0,0,1    1,0,0,0

Answer:

var stack = []; // can use any stack here

function addBit() {
  if (stack.length == 0) {
    stack.push("1");
    print();
    return;
  }
  stack.flip(0);
  print();
}

function print() {
  document.getElementById("output").innerHTML = stack;
}

Array.prototype.flip = function(n) {
if (n == stack.length) {
    stack.push("1");
    return;
  } 

  if (stack[n] == "0") {
    stack[n] = "1";
    return;
  } 

  if (stack[n] == "1") {
     stack[n] = "0";
     stack.flip(n+1);
     return;
  }
}

 

Question 3

A recursive function is an excellent example of the the computer implements function calls using what Data Structure? The _______

 

Answer:  Stack

 

Question 4

We are going to create a Hash Table and fill in the hash table using the hash function 

h(x) = x mod 10 and linear probing 

Fill in the hash table below applying the hash function with these values being inserted in this order;

35, 48, 25, 31, 40, 41, 33, 46, 39, 44 

 

Answer

0:40   (5) 40 mod 10 = 0
1:31   (4) 31 mod 10 = 1
2:41   (6) 41 mod 10 = 1, use, use next slot
3:33   (7) 33 mod 10 = 3
4:44   (10) 44 mod 10 = 4
5:35   (1) 35 mod 10 = 5
6:25   (3) 25 mod 10 = 5, full, use next slot
7:46   (8) 46 mod 10 = 6
8:48   (2) 48 mod 10 = 8
9:39   (9) 39 mod 10 = 9

 

Question 5:

In performing a non-recursive Depth First Search algorithm on a graph, what data structure is most useful for keeping track of the search?

 

Answer: Stack

 

Question 6:

The following is a recursive implementation of the Quicksort algorithm. What is the Big-O complexity of this approach.

 

function quicksort(data) {

    if(data.length == 0) return[];

 

    varleft = [], right = [], pivot = data[0];

 

    for(vari = 1; i < data.length; i++) {

        if(data[i] < pivot)

            left.push(data[i])

        else

            right.push(data[i]);

    }

 

    return quicksort(left).concat(pivot, quicksort(right));

}

 

Answer:

 

Average complexity is O(n log n), Worst case complexity is O(n^2), however the worst case is unlikely in most scenarios – both answers are acceptable.

 

Question 7:

 

What is value of output of the following function call with the given JavaScript function?

 

var output = myFunction(25,'');

function myFunction(n, s){
  if (n == 0) return s;

  s += n%2;
  return myFunction(Math.floor(n/2), s);
}

Answer:   10011

 

Note that this is an implementation of a binary conversion, simply reverse the string (11001) and you have the binary representation of 25.

 

Question 8:

 

Part 1 –

 

How many undirected graphs can be constructed from the 4 vertices A, B, C, D? This includes all graphs with connected and unconnected edges? (1 point)

 

This was from a previous exam (and also a question on Geeksquiz) – the formula for this is the graph enumeration formula (also pointed out in the previous published exam). The formula for the various cases are available at https://en.wikipedia.org/wiki/Graph_enumeration - the answer is 38. I also was accepting 64 (2^4*3/2) = 64 for half credit.

 

Part 2 -

 

List the set of edges for each of these undirected graphs where all edges are connected (no unconnected vertices). Example if an undirected graph is made by connecting A to B to C to D (a square).  The edges would be

 

AB, BC, CD, DA

 

There are 3 possible graphs that use ALL edges and there are no unconnected vertices.

AB, BC, CD, DA
AB, BD, DC, CA
AC, CB, BD, DA

 

This is sometimes easier to see graphically. You can make other graphs for example the first one ABCD is identical undirected to BCDA

 

A --- B

|     |

D --- C

 

A --- B

   X

D --- C

 

A     B

|  X  |

D     C