CMSC132 Spring 2006Final ExamFirst Name: _______________________Last Name: _______________________Student ID: _______________________Section time ___________ TA: _____________________I pledge on my honor that I have not given or received any unauthorized assistance on this examination.Your signature: _____________________________________________________________General Rules (Read):a. This exam is closed book and closed notes.b. If you have a question, please raise your hand.c. Total point value is 100 points. d. The short answer questions are not essay questions. Strive to answer them in 1 or 2 sentences. Longer answers are not necessary and are discouraged.e. WRITE NEATLY. If we cannot understand your answer, we will not grade it (i.e., 0 credit).f. PUNT RULE:. For any question, you may write PUNT, and you will get ¼ of the points forthe question (rounded down). If you feel totally lost on a question, you are encouraged to punt rather than waste time writing down a bunch of vaguely related verbiage in hopes of getting some partial credit.g. Honors section questions only count for credit for students in the honors section.1Grader Use Only:#1 (12)#2 (9)#3 (20)#4 (12)#5 (12)#6 (6)#7 (15)#8 (14)Total (100)Honors (8)Problem 1 (12 pts) Algorithm Complexitya. (3 pts) Calculate the asymptotic complexity of the code snippets below (using big-O notation) with respect to the problem size n.i. for (int i=0; i<n/4; i++) { f(n) = O( ) for (int k=0; k<20; k++) { // … }}ii. for (int i=n/4; i<=n/2; i++) { f(n) = O( ) for (int j=1; j<=n; j=j*2) { // ... }}iii. for (int i=1; i<=100; i++) { f(n) = O( ) // ...}b. (2 pts) List the following big-O expressions in order of asymptotic complexity (with the lowest complexity first)O(nlog(n)) O(1) O(log(n)) O(2n) O(n2)c. (1 pt) What is the worst case complexity of sorting using quicksort?d. (2 pts) What can cause worst case behavior for quicksort?e. (2 pts) Name two representations used for the implementation of a graph (don’t name any that use Sets).f. (2 pts) For the two graph representations named above, which would be more efficient for performing a depth first search of the graph?2Problem 2 (9 pts) Compression and Huffman Codesa. (4 pts) Consider the following Huffman tree.i. (2 pts) Decode the sequence “1001000”ii. (2 pts) Encode the string “FAM”b. (5 pts) Create a Huffman tree for the symbols A, B, C, D, E and F which have the following frequencies:A : 7 B : 3 C : 4 D : 8 E : 2 F : 3MKF11101000AP3Problem 3 (20 pts) Binary Treesa.(6 pts) Answer the following questions based on the following binary tree:i. Write the postorder traversal for the treeii. Write the preorder traversal for the tree.iii. Write the inorder traversal for the tree.b. (14 pts) The following Java class definition for a binary tree will be use to answer the questions that follow. public class BinaryTree <E> {static class Node<T> {T data;Node <T> left, right;public Node(T data) {this.data = data;left = null;right = null;}}Node <E> root;public int interiorNodesCnt() {// Method you need to implement}public List<E> leafNodeValues() {// Method you need to implement}}4 59 8624i. Implement the method interiorNodesCnt that determines the number of interior nodes in the tree. An interior node is a node that is not a leaf node. A tree with only one node has no interior nodes. You may add auxiliary/helper methods.ii. Implement the method leafNodeValues that returns a list (ArrayList) of the data values present in the leaf nodes. You may add auxiliary/helper methods. 5Problem 4 (12 pts) Graph AlgorithmsConsider the following graph.a. (2 pts) List the set of nodes visited (in the order first visited) while performing a Depth First Search starting at A. Use alphabetical order to choose the next node to process, when several successors are available.b. (2 pts) List the set of nodes visited (in the order first visited) while performing a Breadth First Search starting at A. Use alphabetical order to choose the next node to process, when several successors are available.6Consider the following graph:c. (2 pts) Assume the above graph is an undirected graph. Run Kruskal’s minimum spanning tree algorithm in the above graph, and draw the tree we will have after four edges have been considered. d. (6 pts) Run Dijkstra’s shortest path algorithm on the previous graph using H as the start vertex. Show the entries in the following table after adding the first 3 nodes (H & 2 other nodes) to the set S of processed nodes (as defined by Djikstra’s algorithm). Keep in mind that after adding a node to the set S you must adjust the cost/predecessor of the appropriate successors nodes. In the table below, leaving a LowestCost entry blank represents an infinite cost, and leaving a Predecessor entry blank represents no predecessor. H A B C D ELowestCostPredecessor13B57HA C ED698431107Problem 5 (12 pts) HeapsUse the following heap to answer the questions that follow.a. (3 pts) Draw the heap that would result from inserting 8 in the above heap.b. (3 pts) Draw the heap that would result by deleting 6 from the original heap. 610162421141115138c. (6 pts) For this problem you will implement the method isMinHeap that has the following prototype:public static boolean isMinHeap(int[] array)The method determines whether the contents of the array have the heap property.9Problem 6 (6 pts) Regular Expressionsa. (3 pts) What will be printed by the following Java code fragment Pattern p = Pattern.compile("[a-z]+"); Matcher m = p.matcher("12abc ab12c"); while (m.find()) { System.out.println(m.group()); } b. (3 pts) Define a Java regular expression for the language that includes an odd number of a’s followed by a single b. 10Problem 7 (15 pts) Multithreading and Synchronizationa. (6 pts) Rewrite the following code so that the messages are printed by two different threads, with one thread printing the “UMCP” messages and the other thread printing the “Testudo” messages. Give two different possible outputs that could be generated by your rewritten code.public class MsgPrinting {public static void main(String[] args) {for (int i=0; i< 3; i++)System.out.println("UMCP"+i);for (int i=0; i<3; i++)System.out.println("Testudo"+i);}}11b. (9 pts) The following class implements a queue. public class MyQueue<E> {private ArrayList<E> list = new ArrayList<E>();public boolean isEmpty() {synchronized(this) {if (list.size()
View Full Document
Unlocking...