Grader Use Only 1 2 3 4 5 6 7 8 Total Honors CMSC132 Spring 2006 Final Exam 12 9 20 12 12 6 15 14 100 8 First 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 b c d This exam is closed book and closed notes If you have a question please raise your hand Total point value is 100 points 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 for the 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 1 Problem 1 12 pts Algorithm Complexity a 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 for int k 0 k 20 k f n O ii for int i n 4 i n 2 i for int j 1 j n j j 2 f n O 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 2 Problem 2 9 pts Compression and Huffman Codes a 4 pts Consider the following Huffman tree P A 0 1 M F 0 0 1 0 i K 1 1 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 3 3 Problem 3 20 pts Binary Trees a 6 pts Answer the following questions based on the following binary tree 2 4 5 9 i 6 8 Write the postorder traversal for the tree ii 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 i 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 5 Problem 4 12 pts Graph Algorithms Consider 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 6 Consider the following graph 10 5 13 H B D 9 1 3 A 6 C E 4 8 7 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 LowestCost Predecessor 7 C D E Problem 5 12 pts Heaps Use the following heap to answer the questions that follow 6 1 0 1 6 2 4 1 1 1 4 1 5 1 3 2 1 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 8 c 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 9 Problem 6 6 pts Regular Expressions a 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 10 Problem 7 15 pts Multithreading and Synchronization a 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 11 b 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 0 return true return false public E getFirst synchronized this return list remove 0 removes first element and shift elements to the right public void offer E data synchronized this list add …
View Full Document
Unlocking...