DOC PREVIEW
UMD CMSC 132 - Final Exam

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC132 Spring 2007Final 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 and wait for us to come to you.c. Total point value is 122 points. d. 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 eachc. Incorrect answers to True/False questions are penalized 1 point each (-1pt)e. Answer fill-in-the blank questions using 1-2 words only. Longer answers will be penalized.f. Answer essay questions concisely using 1 or 2 sentences. Longer answers will be penalized.g. WRITE NEATLY. If we cannot read your handwriting, you will receive no credit.h. Honors section questions only count for credit for students in the honors section1Grader Use Only:#1 (15)#2 (10)#3 (10)#4 (10)#5 (10)#6 (7)#7 (6)#8 (8)#9 (5)#10 (18)#11 (12)#12 (11)Total (122)# 13 Honors (16)2Problem 1 (15 pts) Software Engineering & Object Oriented DesignA. (5 pts) Software Development and Testinga. Actions may be abstracted to reduce complexity T or Fb. Integration tests are applied after unit tests T or Fc. Unit tests may be created before code is written T or Fd. Logic errors are easier to find than run-time errors T or Fe. Java packages support encapsulation T or FB. (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 ofthreads. Threads display a title and 1 or more posts. Posts display the user and text of thepost. Users may be instructors or students. All users may view threads and add posts to athread. Only instructors may create threads.3Problem 2 (10 pts) Algorithmic ComplexityC. (7 pts) Algorithmic Complexitya. Benchmarking measures # steps used by algorithm T or Fb. Asymptotic complexity measures # steps used by algorithm T or Fc. Big-O notation represents the minimum # of steps required by an algorithm T or Fd. O(n2) algorithms always requires more steps than O(n) algorithms T or Fe. (3 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)D. (3 pts) Finding Critical RegionsCalculate 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++) f(n) = O( ) for (int k=2; k<i; k++) …b. for (int i=2; i<=n/2; i=i*2) f(n) = O( ) for (int j=1; j<=n; j=j*2) ...c. for (int i=1; i<=n; i=i+4) f(n) = O( ) ...Problem 3 (10 pts) TreesE. (8 pts) Binary trees a. (2 pts) Write the order nodes are visited in an postorder traversal of the binary tree aboveD KAM=NZYCE4b. (8 pts) Given the following Java class definition for a binary search tree, implement themethod twoChildVisit that invokes the visit( ) method on nodes in the tree with exactly twochildren. The nodes must be visited in order, and the method should return the number ofsuch 2-child nodes visited. You may add auxiliary/helper methodspublic class BinarySearchTree <E> {private class Node {E data;Node left, right;void visit( ) {…} // Method to invoke in order on 2-child nodes}Node root;public int twoChildVisit( ) { // Method you need to implement}5Problem 4 (10 pts) Java Collections FrameworkThe 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. Theset of songs will be represented using a HashSet.public class SongsDatabase {private Map<String,Set<String>> map = // You must provide the initializationpublic void addSong(String genre, String songTitle) {// You must implement this method}public String getGenreOfSong(String songTitle) {// You must implement this method}}What You Must Implement1. Provide a definition for the required map. This definition would appear where you see the comments// You must provide the initialization2. 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 thesong 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 presentUSE THE NEXT PAGE TO PROVIDE YOUR ANSWERSPAGE FOR ANSWERS OF PREVIOUS QUESTION67Problem 5 (10 pts) GraphsF. (2 pts) Graph traversalsa. (1 pts) List the set of nodes visited (in the order first visited) while performing aBreadth First Search starting at E. Use alphabetical order to choose the next node toprocess, when several successors are available.b. (1 pts) List the set of nodes visited (in the order first visited) while performing a DepthFirst Search starting at E. Use alphabetical order to choose the next node to process,when several successors are available.G. (4 pts) Minimal spanning treesa. (2 pts) Apply Kruskal’s minimum spanning tree algorithm to the above graph. List theedges (e.g., AF) in the minimum spanning tree created, in the order they are added to thetree.b. (2 pts) Apply Prim’s minimum spanning tree algorithm to the above graph starting fromvertex A. List the edges of the minimum spanning tree created, in the order they areadded to the tree.AFDBEC2145742 12AFDCE18614B13942221338H. (4 pts) Single source shortest pathsRun Dijkstra’s shortest path algorithm on the previous


View Full Document

UMD CMSC 132 - Final Exam

Documents in this Course
Notes

Notes

8 pages

Recursion

Recursion

12 pages

Sorting

Sorting

31 pages

HTML

HTML

7 pages

Trees

Trees

19 pages

HTML

HTML

18 pages

Trees

Trees

19 pages

Honors

Honors

19 pages

Lecture 1

Lecture 1

11 pages

Quiz #3

Quiz #3

2 pages

Hashing

Hashing

21 pages

Load more
Download Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?