1CMSC132 Fall 2005 Final Exam 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): • This exam is closed book and closed notes. • If you have a question, please raise your hand. • Total point value is 200 points. • Answer True/False questions by circling the T or F at the end of the question. • Answer essay questions concisely using 1 or 2 sentences. Longer answers are not necessary and are discouraged. • WRITE NEATLY. If we cannot read your answer, it will not be graded (i.e., 0 credit). Grader Use Only: #1 (20)#2 (20)#3 (20)#4 (20)#5 (20)#6 (20)#7 (20)#8 (20)#9 (20)#10 (20)Total (200)Honors (20)2 Problem 1 Software Engineering & Object Oriented Design (20 pts) A. (4 pts) Software engineering a. What is the main reason many software projects fail? b. What is the software life cycle? c. According to the waterfall model, design all algorithms before coding T or F d. According to the unified model, design all algorithms before coding T or F e. What is the difference between program verification and empirical testing? B. (4 pts) Object-oriented design a. State, behavior, and identity are the main qualities of objects T or F b. Object oriented design produces faster programs T or F c. What are two main principles of object-oriented design? C. (4 pts) Object-oriented design II. Given the following problem description, produce an object-oriented solution. Answer the following questions about your object-oriented solution. Design a simulation of a basketball conference. Each conference has 10 teams. Each team has 12 players. Each player has a specific height, speed, and accuracy. Players know which team they belong to. Some players are scholarship players. Scholarship players need to record their current grade-point average. Players may be transferred between teams. Teams play basketball games against other teams in the conference. The result of each game is determined using a function based on the height, strength, speed, and accuracy of the players on each team. a. What are the objects in your object-oriented solution? b. What are the interactions between your objects? c. Which objects “have” other objects? (Also list target object) d. Which objects “use” other objects? (Also list target object) e. Which objects “are” other objects? (Also list target object)3 D. (4 pts) UML. Given the following Java code, draw its UML class diagram. Provide as many details as possible public class Propeller { public double thrust; public int mileage; } public class Engine { public double power; public int mileage; } public class Plane { public Propeller[] myPropellers; public Engine myEngine; } public class Pilot { public int flightHours; public void fly(Plane p) { ... } } public class FighterPilot extends Pilot { public int rank; } Problem 2 Algorithmic Complexity (20 pts) E. (4 pts) Algorithmic complexity a. What is algorithmic complexity? b. List a reason benchmarking is better than analyzing complexity c. What is the difference between best case, worst case, and average case? d. What does the Big-O notation represent? e. Why are O(n2) and O(n) not considered equivalent? F. (4 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 (i = 0; i < n; i=i*2) { f(n) = O( ) for (j = 1; j < n; j++) { ... } }4b. for (i = 0; i < n-2; i++) { f(n) = O( ) for (j = 0; j < n; j=j*2) { for (k = 1; k < 5000; k=k*5) { ... } } for (j = 0; j < 1000*n; j=j+1) { ... } for (j = 0; j < n/5; j=j+5) { ... } } Problem 3 Data Structures and Recursion (20 pts) G. (4 pts) Taxonomy & properties a. Describe the main difference between linear and hierarchical data structures b. What is the key property of a binary search tree? c. On average, what is the complexity of doing an insertion in a binary search tree? d. Pre-order, in-order, and post-order are all depth-first traversals T or F e. What operation(s) supported by binary search trees are not supported by heaps? f. What is the difference between a set and a map? g. What happens when an open addressing hash table is close to full? h. Describe the 2 main parts of a recursive algorithm Problem 4 Graph Algorithms (20 pts) H. (4 pts) Properties a. Describe the main difference between hierarchical and graph data structures b. Describe the difference between a directed and undirected graph c. Describe the difference between a path and a cycle d. Describe two methods of storing edges in a graph e. Which method of storing edges in a graph requires more space?5 I. (4 pts) Traversals a. Why is graph traversal more difficult than a tree traversal? b. Describe the difference between a breadth-first and depth-first traversal of a graph c. Given the following Java class definition for a graph public class Node { Object myValue; boolean tag; ArrayList<Node> myNeighbors; } public class myGraph { ArrayList<Node> myNodes; void visitNode(Node n) { … } – Action to be performed when traversing node void deptFirstSearch(Node n) { … } – Perform depth-first search of graph starting at n } Write code for deptFirstSearch( n ) to perform a depth first traversal of nodes in the graph, invoking visitNode( ) for each node once J. (4 pts) Minimum spanning trees a. What is a spanning tree? b. Describe Kruskal’s algorithm for finding minimum spanning trees c. Describe two methods for finding connected subgraphs d. Consider the following graph. Using Kruskal’s algorithm, calculate the minimum spanning tree, listing edges in the minimal spanning tree in the order they are added to the tree. A EB FH DC G S 10 14 12816 13 57415 963116 K. (4 pts) Single source shortest path a. Describe Djikstra’s algorithm for finding shortest paths in a graph b. Consider the previous graph. Apply Djikstra’s algorithm for this graph to calculate
View Full Document
Unlocking...