DOC PREVIEW
UMD CMSC 132 - Partial Solutions to Final Exam Practice Questions

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 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 16 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 16 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 16 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 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1CMSC132 Partial Solutions to Final Exam Practice Questions Problem 1 Software Engineering & Object Oriented Design A. Software Development and Testing a. Software is difficult because programmers are slow T or F b. Software life cycle refers to how software is used T or F c. Problem specification is a component of software development T or F d. Problem specification is less important than program testing T or F e. Iterative development is a software development methodology T or F f. Black box testing is usually easier than clear box testing T or F g. Integration tests are usually more important than unit tests T or F h. Test coverage includes consideration of lines of code tested T or F i. Test drivers are only found on NASCAR training tracks T or F B. 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. List two main principles of object-oriented design? Abstraction & encapsulation d. Inheritance describes a relationship between classes T or F e. Inheritance discourages code reuse T or F f. Extension is a form of inheritance T or F C. 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? Conference, Team, Player, ScholarshipPlayer b. What are the interactions between your objects? Play Game, Transfer c. Which objects “have” other objects? (Also list target object) Conferences have Teams, Teams have Players, d. Which objects “use” other objects? (Also list target object) None e. Which objects “are” other objects? (Also list target object)2ScholarshipPlayers are Players f. Draw a UML diagram of your solution. TeammyPlayers[12] : Player playGame() ConferencemyTeams[10] : Team PlayermyTeam : Team height speed accuracytransfer()ScholarshipPlayerGPA101 12TeammyPlayers[12] : Player playGame() ConferencemyTeams[10] : Team PlayermyTeam : Team height speed accuracytransfer()ScholarshipPlayerGPA101 12 Problem 2 Algorithmic Complexity D. Algorithmic complexity a. What is algorithmic complexity? Amount of resources required by algorithm with respect to problem size b. List a reason benchmarking is better than analyzing complexity Measures performance for a particular hardware c. What is the difference between best case, worst case, and average case? Minimum, maximum, and typical number of steps required by algorithm d. What does the Big-O notation represent? Upper bound on the number of steps required by algorithm e. Why are O(n2) and O(n) not considered equivalent? The number of steps required by each algorithm grows at a different rate with respect to the problem size E. 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( nlog(n) ) for (j = 1; j < n; j++) { ... } } b. for (i = 0; i < n-2; i++) { f(n) = O( n2 ) for (j = 0; j < n; j=j*2) { for (k = 1; k < 5000; k=k*5) { ... }3 } for (j = 0; j < 1000*n; j=j+1) { ... } for (j = 0; j < n/5; j=j+5) { ... } } Problem 3 Data Structures and Recursion F. Taxonomy & properties a. Describe the main difference between linear and hierarchical data structures Single successor vs. multiple successors b. What is the key property of a binary search tree? Smaller values in left subtree, larger values in right subtree c. On average, what is the complexity of doing an insertion in a binary search tree? O(log(n)) 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? find( n ) f. What is the difference between a set and a map? Maps have keys to their elements g. What happens when an open addressing hash table is close to full? Operations take more steps h. Describe the 2 main parts of a recursive algorithm Base case and recursive step Problem 4 Graph Algorithms G. Properties a. Describe the main difference between hierarchical and graph data structures Single predecessor vs. multiple predecessors b. Describe the difference between a directed and undirected graph Edges are one-way or bi-directional c. Describe the difference between a path and a cycle Cycle returns to its starting node d. Describe two methods of storing edges in a graph. Which requires more space? Edge list & adjacency matrix Space usage depends on Edge/Node ratio of graph H. Traversals a. Why is graph traversal more difficult than a tree traversal? May encounter cycles b. Describe the difference between a breadth-first and depth-first traversal of a graph4Breadth-first visits closer neighbors first, depth-first finishes exploring all reachable nodes from current node first I. Minimum spanning trees a. Given the following Java class definition for a graph public class MyGraph<E> { public class Node<E> { E myValue; boolean tag; ArrayList<Node> myNeighbors; } 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 */ } } i. Write code for the method depthFirstSearch( n ) that performs a depth first traversal starting at node n. ii. Write code for the method breadthFirstSearch(n) that performs a breadth first traversal starting at node n. J. Minimum spanning trees a. What is a spanning tree? Tree connecting all nodes in graph (no cycles, n-1 edges) b. Describe Kruskal’s algorithm for finding minimum


View Full Document

UMD CMSC 132 - Partial Solutions to Final Exam Practice Questions

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 Partial Solutions to Final Exam Practice Questions
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 Partial Solutions to Final Exam Practice Questions 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 Partial Solutions to Final Exam Practice Questions 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?