xc3bgr7j

1Problem 1 (Software Development & Testing)
2
31. What is the main reason many software projects fail?
4a. Poorly trained programmers
5b. Insufficient project funding
6c. Complexity of projects
7d. Slow computers
8e. Insufficient computer memory
9
10C
11
122. What is the software life cycle?
13
14The process by which quality software is produced
15
163. What is the first phase of the software life cycle?
17a. Testing
18b. Coding
19c. Design
20d. Specification
21e. Documentation
22
23D
24
254. True or False
26According to the waterfall model…
27a. Design all algorithms before coding
28b. Write test cases before coding
29c. Use prototype implementation to refine design
30
31A true, B false, C false
32
335. True or False
34According to the unified model…
35a. Design all algorithms before coding
36b. Write test cases before coding
37c. Use prototype implementation to refine design
38
39A false, B false, C true
40
416. True or False
42Compared to program verification, empirical testing…
43a. Handles larger programs
44b. Always catches more errors
45c. Ensures code is correct
46d. Can be applied without examining code
47
48A true, B false, C false, D true
49
507. Given the following problem description, produce an object-oriented solution.
51Design a simulation of a basketball conference. Each conference has 10 teams. Each team has 12 players. Each
52player has a specific height, speed, and accuracy. Players know which team they belong to. Some players are
53scholarship players. Scholarship players need to record their current grade-point average. Players may be transferred
54between teams. Teams play basketball games against other teams in the conference. The result of each game is
55determined using a function based on the height, strength, speed, and accuracy of the players on each team.
56a. What are the objects in your object-oriented solution?
57Conference, Team, Player, ScholarshipPlayer extends Player
58b. What are the interactions between your objects?
59Conference: PlayGame between teams, Teams: transfer player to other team 
60c. Which objects “have” other objects? (Also list target object)
61Conferences have Teams, Teams have Players
62d. Which objects “use” other objects? (Also list target object)
63Conferences use Teams, Teams use Players
64e. Which objects “are” other objects? (Also list target object)
65ScholarshipPlayers are Players
66
67Problem 2 (Trees)
68
691. Binary search trees (BST)
70a. What is the key property of a binary search tree?
71It is sorted by direction: all the left, right children have smaller, larger respectively values than the root, and this applies to any subtree of the BST as well.
72b. On average, what is the complexity of doing an insertion in a binary search tree?
73O(log n)
74c. On average, what is the complexity of doing a find in a binary search tree?
75O(log n)
76d. What is the worst-case complexity of doing a find in a binary search tree?
77O(n)
78e. What can cause worst-case behavior in a binary search tree?
79The tree degenerates into a linked list. This can happen if the elements added in the order 1, 2, 3, 4, ... for example
80
812. Binary search trees examples
82a. Draw the binary search tree created when the following values are inserted in order: 6, 5, 2, 8, 10, 3
836-L->5; 6 -R->8; 5 -L-> 2; 2 -R-> 3; 8 -R-> 10
84b. Given the previous BST, draw the tree created when the node 5 is removed
856-L->3; 6 -R->8; 3 -L-> 2; 8 -R-> 10
86
873. Traversals
88a. What is a tree traversal?
89A way to go through the nodes of a tree to perform a given task on the tree
90b. What is the difference between a depth-first and breadth-first traversal?
91Depth first search tries to go as far into the tree as possible before backtracking. Breadth first search looks at all the nodes adjacent to the start node, then the nodes 2 away from the start node, 3 away from the start node etc.
92c. Pre-order, in-order, and post-order are all depth-first traversals T or F
93True
94d. Pre-order traversals are faster than post-order traversals T or F
95False
96e. For the following binary tree, provide an example of a
97i. Preorder traversal
98152243
99ii. Postorder traversal
100225341
101iii. Breadth-first traversal
102154223
103
1044. Given the following Java class definition for a binary tree
105public class BinarySearchTree <K extends Comparable<K>, V> {
106	private class Node {
107		private K key;
108		private V data;
109		private Node left, right;
110		public Node(K key, V data) {
111			this.key = key;
112			this.data = data;
113		}
114	}
115	private Node root;
116}
117 Write the following code:
118a. find(K key) – Use a recursive algorithm to find a node with a key value that corresponds to key in tree
119public Node find(K key) {
120	findAux(key, root);
121}
122public Node findAux(K key, Node n) {
123	if(n == null) {
124		//key not found
125		return null;
126	}
127	int compare = n.key.compareTo(key)
128	if(compare==0) {
129		return n;
130	}
131	if(compare>0) {
132		return findAux(key,n.right);
133	}
134	return findAux(key,n.left);
135}
136b. treeHeight( ) – Use a recursive algorithm to find the height of a tree
137public int treeHeight() {
138	return height(root);
139}
140public int height(Node n) {
141	return n == null ? 0 : 1 + Math.max(height(n.left),height(n.right));
142}
143c. preorderPrint( ) – Use a recursive algorithm to print the key and data for each node using a preorder
144traversal of the tree, starting from the root.
145public void preorderPrint() {
146	preorderAux(root);
147}
148public void preorderAux(Node n) {
149	if(n != null) {
150		System.out.println("key "+n.key+", data "+n.data);
151		preorderAux(n.left);
152		preorderAux(n.right);	
153	}
154}
155d. subMap(K lower, K upper) – Use a recursive algorithm to implement a method that returns a
156BinarySearchTree with elements that have a key value between lower (inclusive) and upper (inclusive).
157public BinarySearchTree<K, V> subMap(K lower, K upper) {
158	BinarySearchTree<K, V> tree = new BinarySearchTree<K,V>();
159	tree.root = subMapAux(lower, upper);
160	return tree;
161}
162public Node subMapAux(K lower, K upper) {
163
164}
165e. retrieveLeaves(Map<K,V> map) – Use a recursive algorithm to implement a method that initializes the map
166with elements that are leaf nodes. The leaves must be removed from the original tree.
167f. size() – Implement the size method without using recursion.
168g. thread() – Add an additional Node reference (e.g., Node thread) to the BinarySearchTree and implement a
169method that threads the tree based on different criteria. For example, given a tree, the thread() method can
170set the thread reference of every node to point to the next element in an inorder traversal.
171
172Problem 3 (Heaps)
1731. Properties & characteristics
174a. What are two key properties of a heap?
175In a min, max heap, the root is the minimum, maximum respectively of all elements in the heap. This applies to any subheap of the heap too. The shape of the heap is a complete binary tree. 
176b. What operation(s) supported by binary search trees are not supported by heaps?
177You cannot search for an element in a heap efficiently
178c. On average, what is the complexity of doing an insertion in a heap?
179O(logn)
180d. On average, what is the complexity of doing a find in a heap?
181O(logn)
182e. How can heaps be stored in a compact array representation?
183As an array
184f. Why are heaps used to implement priority queues?
185Elements with higher, lower priority can be placed closer to the top, bottom of the heap respectively.
186
1872. Examples
188a. Draw the heap created when the following values are inserted in order: 6, 5, 2, 8, 10, 3
189
190b. Given the previous heap, draw the heap produced when the smallest value is removed
191
192c. Show the tree representation of the following heap (in array representation)
193
194d. Show the array representation of the following heap (in tree representation)
195
196Problem 4 (Algorithmic Complexity)
1971. Algorithmic complexity
198a. What is algorithmic complexity?
199A measure of the asymptotic speed at which an algorithm runs
200b. List a reason benchmarking is better than analyzing complexity
201Complexity only applies to very large inputs since it is asymptotic. Benchmarking can measure the speed of the program for small inputs and see how fast it is for actual data sets.
202c. What is the difference between best case, worst case, and average case?
203Best/worst case of n: how fast the program runs for the fastest, slowest possible input of size n. Average case of n: how fast the program runs on average for an input of size n
204d. What does the Big-O notation represent?
205
206
2072. Finding critical regions
208Calculate the asymptotic complexity of the code snippets below (using Big-O notation) with respect to the problem size n:
209a. for (i = 1; i < n; i = i * 2) {
210 	for (j = 1; j < n; j++) {
211 		...//critical section
212 	}
213}
214
215f(n) = O(nlogn)
216
217b. for (i = 0; i < n - 2; i++) {
218	 for (j = 0; j < n; j = j * 2) {
219	 	for (k = 1; k < 5000; k = k * 5) {
220 			...
221		 }
222 }
223 for (j = 0; j < 1000 * n; j = j + ) {
224 	...//critical section 1
225 }
226 for (j = 0; j < n / 5; j = j + 5) {
227 	...//critical section 2
228 }
229}
230
231f(n) = O(n^2)
232
233Problem 5 (Graphs)
2341. Properties
235a. Describe the difference between a directed and undirected graph
236In an undirected graph, an edge between vertices u and v can be taken from u to v or from v to u. In a directed graph, the edge only points in one direction, so exactly one of u to v or v to u is possible.
237b. Describe the difference between a path and a cycle
238A cycle is a path that starts and ends at the same vertex
239c. Describe two methods of storing edges in a graph. Which requires more space?
240Store as adjacency matrix, which can be implemented as a 2D array. Or store as a hashmap where the key is vertices and the data to each key are the neighbors of that vertex. The adjacency matrix requires more space since we have to store all of the nonedges as zeroes.
2412. Traversals
242a. Why is graph traversal more difficult than a tree traversal?
243Graphs can have cycles, so we can stumble upon the same vertex more than once.
244b. Describe the difference between a breadth-first and depth-first traversal of a graph
245Same as difference between BFS and DFS for trees
246c. Given the following Java class definition for a graph
247public class MyGraph<E> {
248	public class Node<E> {
249		E myValue;
250		boolean tag;
251		ArrayList<Node> myNeighbors;
252	}
253	ArrayList<Node> myNodes;
254 	void visitNode(Node n) {/* Action to be performed when traversing node */}
255 	void deptFirstSearch(Node n) { /* Perform depth-first search of graph starting at n */ }
256}
257i. Write code for the method depthFirstSearch(n) that performs a depth first traversal starting at node n.
258
259ii. Write code for the method breadthFirstSearch(n) that performs a breadth first traversal starting at node n.
260
2613. Graph traversals
262a. Give two different possible orders in which the nodes of this graph could be visited in performing a
263breadth-first search (BFS) starting at node A. Note: there may be more than two possible orders that
264BFS could visit the nodes; you only have to give two orders.
265
266b. Give two different possible orders in which the nodes of this graph could be visited in performing a
267depth-first search (DFS) starting at node A. Note: there may be more than two possible orders that DFS
268could visit the nodes; you only have to give two orders.
269
270
2714. Single source shortest paths
272Apply Dijkstra’s algorithm using A as the starting (source) node. Indicate the cost and predecessor for each node
273in the graph after processing two nodes (A and another node). Remember to update the appropriate table entries
274after processing a node (after it has been added to the set of processed nodes). An empty table entry implies an
275infinite cost or no predecessor.
276After processing the first node. Write the name of the node you are processing here: A
277After processing the second node. Write the name of the node you are processing here: ________
278Problem 6 (Java Language Features)
2791. Java Inner Classes
280a. What are inner classes?
281b. What are nested classes?
282c. When should inner classes be used?
283d. When should anonymous inner classes be used?
284e. What relationship exists between lambda expressions and anonymous inner class?
285f. Write an example anonymous inner class in Java.
2862. Java support for Object-Oriented programming
287a. All non-static initialization blocks are executed when objects are created T or F
288b. Code in initialization blocks are executed at the end of every constructor T or F
289c. If no visibility modifier is specified, methods are private by default T or F
290d. Protected access is less visible than package access T or F
2913. Generics
292a. What are the advantages of using generics?
293b. Define a class that implements a double-ended queue (dequeue) for integer values. Modify the class so it
294becomes a generic class.
2954. Lambda Expressions
296a. What is a lambda expression?
297b. Write a lambda expression for the Runnable interface. The run() method will print even values between 1
298and 100.
299c. What property must an interface have in order to be used with a lambda expression?
300d. Provide a listener (e.g., for a JavaFX button) that relies on an inner class, an anonymous inner class, and a
301lambda expression.
3025. Exceptions in Java
303a. What are exceptions?
304b. How are exceptions used in Java?
305c. What should be made an exception in Java?
306d. What are the differences between try, catch, and finally in Java?
307e. What is the difference between checked and unchecked exceptions?
308f. Given the following code
309public static void f( int y ) {
310 try {
311 System.out.print(“A”);
312 int x = 1 / y ; // generates ArithmeticException if y == 0
313 System.out.print(“B”);
314 }
315 catch (ArithmeticException e) {
316 System.out.print(“C”);
317 }
318 finally {
319 System.out.print(“D”);
320 }
321}
322What will be printed for the following method calls?
3231. f(1)
3242. f(0)
325Problem 7 (Multithreading & Synchronization)
3261. Multithreading
327a. What is the motivation for writing multithreaded Java code?
328b. What are possible states for Java threads?
329c. What is the effect of invoking the start() method of the Thread class?
330d. What is the effect of invoking the join() method of the Thread class?
331e. What is scheduling?
332f. What is the difference between preemptive and non-preemptive scheduling?
333g. What are data races?
334h. Write a Java program that can experience a data race
335i. Why should programs avoid data races?
3362. Synchronization & deadlocks
337a. What is synchronization?
338b. Why should programs use synchronization?
339c. What are Java locks?
340d. How may Java locks be used?
341e. What are deadlocks?
342f. Write a Java program that can experience deadlock.
3433. Multithreading code
344Consider the following code:
345public class mySet {
346 List myElements = new ArrayList( );
347 public boolean add( Object o ) {
348 myElements.add( o );
349 }
350 public Object remove( ) {
351 if (myElements.isEmpty( ) == false)
352 return myElements.remove( 0 ); // removes & returns object at position 0
353 return null;
354 }
355}
356a. What may happen if an object of the class mySet is used by multiple threads calling add( ) and remove( ) at
357the same time?
358b. Change the add( ) and remove( ) methods so that the class mySet can be safely used by multiple threads at
359once.
3604. Implement a Java program that increases the value of each entry of a two-dimensional array using threads. For
361example, each row can be processed by a different thread. Once all the entries have been increased, the program
362will print the sum of all the updated entries.
3635. How can you use threads to speed up the processing of a search operation in a binary search tree?
364Problem 8 (Graphic User Interfaces)
3651. In a GUI, what is the model? The view? The controller?
3662. Why should they be kept separate?
3673. What are events?
3684. Why are events used in GUIs?
369Problem 9 (Sorting & Algorithm Strategies)
3701. Sorting algorithms
371a. What is a comparison sort?
372b. When is a sorting algorithm not a comparison sort?
373c. What is a stable sort?
374d. What is an in-place sort?
375e. What is an external sort?
376f. What is the average case complexity of sorting using
377i. bubble sort
378ii. heap sort
379iii. quick sort
380iv. counting sort
381g. What is the worst case complexity of sorting using
382i. selection sort
383ii. tree sort
384iii. heap sort
385iv. radix sort
386h. Can the following sort be performed in a stable manner?
387i. bubble sort
388ii. quick sort
389iii. counting sort
390i. Can the following sort be performed using an in-place algorithm?
391i. selection sort
392ii. tree sort
393iii. merge sort
3942. Algorithm strategies
395a. What is divide-and-conquer?
396b. What is dynamic programming?
397c. What is the difference between divide-and-conquer and dynamic programming?
398d. What is the difference between recursive and backtracking algorithms?
399e. What is the difference between a greedy algorithm and heuristics?
400f. What is the difference between brute force and branch-and-bound algorithms?
401g. List a reason to use dynamic programming
402h. List a reason to use backtracking
403i. List a reason to use a brute force algorithm
404j. What type of algorithm is Kruskal’s algorithm for finding minimum spanning trees?
405k. A new graph algorithm can find the best set of nodes that solve a problem by selecting each time the node
406that have the lowest number of neighbors until no more nodes are left. Which algorithm strategy is this
407algorithm relying on?
408l. Which algorithm strategy (in addition to recursion) can be used to efficiently compute Fibonacci numbers?
409Select only one.
410Problem 10 (Hashing)
4111. What are the advantages of hashing?
4122. Describe the Java Hash Code Contract.
4133. A class has as instance variables a string, an integer, a float and a StringBuffer object reference. Define possible
414hashCode methods for this class.
4154. What would happen if you use a HashMap or HashSet with a class that does not implement the Java Hash Code
416Contract?
417Problem 11 (Design Patterns)
4181. Design patterns
419a. What is a design pattern?
420b. When are design patterns used?
421c. List 3 types of design patterns. Give 2 example patterns for each type.
422d. Write a Java example of the Singleton pattern
423e. Write a Java example of the State pattern
424f. List 2 examples of design patterns used in the Java class libraries
425g. Based on the following code, use the Decorator design pattern to
426i. Add a BoatDecorator class implementing the Boat interface
427ii. Create two BoatDecorators withBarnacle( ) and withTurboEngine( ) that change the result returned
428by topSpeed( ) by –1 and +10, respectively
429iii. Use BoatDecorators to create a Boat object for a SpeedBoat with 2 barnacles and 1 turbo engine
430whose topSpeed( ) method returns 48.
431public interface Boat {
432 int maxCapacity;
433 int topSpeed( )
434}
435class CruiseShip implements Boat { // big boat
436 int topSpeed( ) { return 20; }
437}
438class SpeedBoat implements Boat { // small boat
439 int topSpeed( ) { return 40; }
440}
441Boat myBigBoat = BoatFactory.create(“big”);
442Boat mySmallBoat = BoatFactory.create(“small”);
443public class BoatFactory {
444 static Boat create(String s) {
445// your code here
446 }
447}
448Problem 12 (Linear Data Structures)
4491. Name three kinds of linked lists traversals we saw in class.
4502. Name one advantage of a linked list over an array list.
4513. Given the following Java class definition for a linked list
452public class LinkedList<T extends Comparable<T>> {
453 private class Node {
454 private T data;
455 private Node next, thread;
456 private Node(T data) {
457 this.data = data;
458 next = thread = null;
459 }
460 }
461 private Node head, tail;
462 public LinkedList() {
463 head = tail = null;
464 }
465}
466 Write the following code:
467a. find(K key) – Use a recursive algorithm to find a node with a key value that corresponds to key in the list
468b. printListReverse – Use a recursive algorithm to print the list in reverse order
469c. removeEvenNumberedNodes – Use a recursive algorithm to remove even-numbered nodes from a list. Reimplement your code using a non-recursive algorithm
470d. removeDuplicates() – Use a recursive algorithm to remove duplicates from the list
471e. removeInRange(T lower, T upper) – Use a recursive algorithm to remove nodes present in the range defined
472by lower (inclusive) and upper (inclusive). Elements removed must be placed in a set