Grader Use Only 1 2 3 4 5 6 7 8 9 10 11 12 Total 13 Honors CMSC132 Spring 2007 Final Exam First Name Last Name 15 10 10 10 10 7 6 8 5 18 12 11 122 16 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 e f g h This exam is closed book and closed notes If you have a question please raise your hand and wait for us to come to you Total point value is 122 points Answer True False questions by circling the T or F at the end of the question a Correct answers to True False questions receive 1 point each 1pt b Unanswered blank True False questions receive 0 points each c Incorrect answers to True False questions are penalized 1 point each 1pt Answer fill in the blank questions using 1 2 words only Longer answers will be penalized Answer essay questions concisely using 1 or 2 sentences Longer answers will be penalized WRITE NEATLY If we cannot read your handwriting you will receive no credit Honors section questions only count for credit for students in the honors section 1 2 Problem 1 15 pts Software Engineering Object Oriented Design A 5 pts Software Development and Testing a b c d e Actions may be abstracted to reduce complexity Integration tests are applied after unit tests Unit tests may be created before code is written Logic errors are easier to find than run time errors Java packages support encapsulation T or F T or F T or F T or F T or F B 10 pts Object Oriented Design a Given the following problem description produce an object oriented solution Draw a UML diagram of your object oriented solution Design a software forum supporting any number of users The forum displays a number of threads Threads display a title and 1 or more posts Posts display the user and text of the post Users may be instructors or students All users may view threads and add posts to a thread Only instructors may create threads 3 Problem 2 10 pts Algorithmic Complexity C 7 pts Algorithmic Complexity a b c d Benchmarking measures steps used by algorithm Asymptotic complexity measures steps used by algorithm Big O notation represents the minimum of steps required by an algorithm O n2 algorithms always requires more steps than O n algorithms T or F T or F T or F T or F e 3 pts List the following big O expressions in order of asymptotic complexity with the lowest complexity first O nlog n O 1 O 2n O log n O n2 D 3 pts Finding Critical Regions Calculate the asymptotic complexity of the code snippets below using big O notation with respect to the problem size n a for int i 2 i n 2 i for int k 2 k i k f n O b for int i 2 i n 2 i i 2 for int j 1 j n j j 2 f n O c for int i 1 i n i i 4 f n O Problem 3 10 pts Trees E 8 pts Binary trees Y D A K C Z M N E a 2 pts Write the order nodes are visited in an postorder traversal of the binary tree above 4 b 8 pts Given the following Java class definition for a binary search tree implement the method twoChildVisit that invokes the visit method on nodes in the tree with exactly two children The nodes must be visited in order and the method should return the number of such 2 child nodes visited You may add auxiliary helper methods public class BinarySearchTree E private class Node E data Node left right void visit Node root Method to invoke in order on 2 child nodes public int twoChildVisit Method you need to implement 5 Problem 4 10 pts Java Collections Framework The SongsDatabase class keeps tracks of song titles by classifying them according to genre e g Pop Rock etc The class uses a HashMap to map a genre with a set of songs that belong to such a genre The set of songs will be represented using a HashSet public class SongsDatabase private Map String Set String map You must provide the initialization public void addSong String genre String songTitle You must implement this method public String getGenreOfSong String songTitle You must implement this method What You Must Implement 1 Provide a definition for the required map This definition would appear where you see the comments You must provide the initialization 2 Implement the addSong method This method adds a song to the set associated with the specified genre If there is not set associated with the genre one will be added to the map 3 Implement the getGenreOfSong The method will return the genre for the specified song or null if the song is not part of the database The following are map methods that you may find helpful for this problem V get Object key Returns the value to which this map maps the specified key V put K key V value Associates the specified value with the specified key in this map Set K keySet Returns a set view of the keys contained in this map The following are set methods that you may find helpful for this problem boolean contains Object o Returns true if this set contains the specified element boolean add E o Adds the specified element to this set if it is not already present USE THE NEXT PAGE TO PROVIDE YOUR ANSWERS PAGE FOR ANSWERS OF PREVIOUS QUESTION 6 7 Problem 5 10 pts Graphs F 2 pts Graph traversals 1 D 2 2 A 4 E 7 B 1 F 2 C 5 4 a 1 pts List the set of nodes visited in the order first visited while performing a Breadth First Search starting at E Use alphabetical order to choose the next node to process when several successors are available b 1 pts List the set of nodes visited in the order first visited while performing a Depth First Search starting at E Use alphabetical order to choose the next node to process when several successors are available G 4 pts Minimal spanning trees 6 A 14 C 21 22 B 18 9 F 4 D E 13 33 a 2 pts Apply Kruskal s minimum spanning tree algorithm to the above graph List the edges e g AF in the minimum spanning tree created in the order they are added to the tree b 2 pts Apply Prim s minimum spanning tree algorithm to the above graph starting from vertex A List the edges of the minimum spanning tree created in the order they are added to the tree 8 H 4 pts Single source shortest paths D 1 2 2 A 4 E 2 7 B F 5 C 4 Run Dijkstra s shortest path algorithm on the previous graph using B …
View Full Document
Unlocking...