int[] A = new int[5]; // A is an integer array with five elements for(int i = 0; i < n; i++) { if(i == A.length) A = resize(A, A.length+1); A[i] = 10; }
Solution: O(n^2).
For values of i = 0, 1, 2, 3, and 4, each execution of the body of the for-loop
takes a constant, say c, number of steps because the condition in the if-statement
evaluates to false.
For values of i, greater than 4, each execution of the body of the for-loop
takes time proportional to i.
This is because the condition inside the for-loop evaluates to true and the
call to the resize function, which resizes A from size i to size (i+1),
takes time proportional to i.
Thus the total running time is:
O(1) + (5 + 6 + ... + n-1) = O(n^2)
Solution: There are two different changes we could make to get the running time of the code fragment down to O(n). Either of these changes is a correct answer to this question.
int[] A = new int[n]If we do this, then no calls to the resize function will be made.
A = resize(A, 2*A.length);As discussed many times in class, doing this ensures that we make only a small number of calls to resize and the overall running time is O(n).
Notes: If you want to look at the code for a specific resize function, see the end of the exam.
public void allConnected() { // Start depth first traversal from the vertex in // slot 0 in the array of Vertices depthFirstTraversal(Vertices[0]); // Generate pairs of vertices for(int i = 0; i < numVertices-1; i++) for(int j = i+1; j < numVertices; j++) { // Use the data structure dFTTree to determine // if vertex i and vertex j lie in the same // connected component or not. There is no need to // call depthFirstTraversal again. // Find the root of i's connected component int rootI = i; while(rootI != dFTTree[rootI]) rootI = dFTTree[rootI]; // Find the root of j's connected component int rootJ = j; while(rootJ != dFTTree[rootJ]) rootJ = dFTTree[rootJ]; // Print message System.out.print(i, j, ":"); if(rootI == rootJ) System.out.println("Reachable"); else System.out.println("Not reachable"); } }
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5Note that the order in which the subsets are generated is not important. Similarly, the order in which elements in each subset are listed, is not important.
The function genKSubsets takes two non-negative integers n and k, does some initialization and calls the recursive function recursiveGenKSubsets.
public void genKSubsets(int n, int k) { boolean[] subset = new boolean[n]; recursiveGenKSubsets(subset, n, k); }The code for recursiveGenKSubsets shown below is incomplete. The idea used here is very similar to what is used in generating all subsets of {1, 2, ..., n} (Homework 2). To generate all subsets of size k of {1, 2, ..., n}, first put n into the current subset being generated and generate all subsets of size k-1 of {1, 2, ..., n-1}. Then, skipping over element n, generate all subsets of size k of {1, 2, ..., n-1}. The base cases of the function are shown, but the recursive case is missing some code. Your task is to supply this code.
public static void recursiveGenKSubsets(boolean[] subset, int n, int k) { // Base case 1: Since n equals k, the entire set needs to // be generated. Set the remaining elements true and // print out the set. if(n == k) { for(int i = 0; i < n; i++) subset[i] = true; printSubset(subset); return; } // Base case 2: Since k equals 0, it means that the subset // has been completely generated. Set the remaining elements // false and print out the subset. if (k == 0) { for(int i = 0; i < n; i++) subset[i] = false; printSubset(subset); return; } // Recursive case if(k > 0 && n > k) { // Missing code for recursive call 1 subset[n-1] = true; recursiveGenKSubsets(subset, n-1, k-1); // Missing code for recursive call 2 subset[n-1] = false; recursiveGenKSubsets(subset, n-1, k); } }
5 1 9 2 11 6Further suppose that the value of pivot is 4. Show the arrangement of the elements in theArray at the beginning of each execution of the while-true loop.
Notes: I have attached a copy of Lafore's partition function at the end of the exam.
Solution: We get to the beginning of the while-true loop only twice and this is how the array looks at each of these instances.
5 1 9 2 11 6 2 1 9 5 11 6
An example is shown in the following figure. The vertex B has index 1 and degree 2. Therefore, the first element in row 1 is 2. This is followed by the indices of the neighbors of B, namely A (index 0) and D (index 3).
The new myGraph class has the following data members. The only difference relative to the original myGraph class is that we are using a 2-dimensional array of integers, rather than a 2-dimensional array of booleans.
String[] Vertices; int numVertices; int numEdges; int[][] Edges; // different from before
Write the implementation of the addEdge function. Assume that it has the following function header.
public static void addEdge(String vertex1, String vertex2)In the interests of time, do not bother to do any error checking in your function. You may assume that both vertex1 and vertex2 exist and you may also assume that the edge connecting these two vertices does not already exist.
Solution: Here is the code for addEdge.
public static void addEdge(String vertex1, String vertex2) { int index1 = getIndex(vertex1); int index2 = getIndex(vertex2); // Add index2 to the row corresponding to index1 // But, first resize the row corresponding to index1, if necessary if(Edges[index1][0]+1 == Edges[index1].length) Edges[index1] = resize(Edges[index1], 2*Edges[index1].length); Edges[index1][Edges[index1][0]+1] = index2; Edges[index1][0]++; // Add index1 to the row corresponding to index2 // But, first resize the row corresponding to index1, if necessary // This is the same code as above, but with index1 and index2 switched if(Edges[index2][0]+1 == Edges[index2].length) Edges[index2] = resize(Edges[index2], 2*Edges[index2].length); Edges[index2][Edges[index2][0]+1] = index1; Edges[index2][0]++; }
The resize function.
// Resizes an array of integers. Can make it larger or smaller, // depending on what newSize is. public static int[] resize(int[] data, int newSize) { String[] temp = new String[newSize]; int smallerSize = newSize; if(data.length < smallerSize) smallerSize = data.length; for(int i = 0; i < smallerSize; i++) temp[i] = data[i]; return temp; }
Lafore's partition function.
public int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1; // right of first elem int rightPtr = right + 1; // left of pivot while(true) { while(leftPtr < right && // find bigger item theArray[++leftPtr] < pivot) ; // (nop) while(rightPtr > left && // find smaller item theArray[--rightPtr] > pivot) ; // (nop) if(leftPtr >= rightPtr) // if pointers cross, break; // partition done else // not crossed, so swap(leftPtr, rightPtr); // swap elements } // end while(true) return leftPtr; // return partition } // end partitionIt()