CMSC132 Spring 2007 Midterm #1 - Key1. (5 pts) Object-Oriented Programming and Javaa. Procedural abstraction makes it clear what algorithm is used by a program T or Fb. Java interfaces are examples of data abstraction T or Fc. Java requires a list of all possible values for an enumerated type T or Fd. Using Java generics can cause more errors to appear during compilation T or Fe. The Java Comparator interface supports generics T or F2. (6 pts) Testing & Program Correctnessa. Compile-time errors may cause exceptions to be thrown in Java T or Fb. An interactive debugger can display the value of variables in a program T or Fc. Breakpoints mark where run-time errors may occur in a program T or Fd. Empirical testing will find all run-time errors in a program T or Fe. Integration testing tests individual classes T or Ff. Test coverage measures whether code is executed by some test case T or F3. (13 pts) Algorithmic Complexitya. Asymptotic complexity is more accurate than benchmarking T or Fb. Worst case analysis is more useful than best case analysis T or Fc. Critical sections are never found outside loops T or Fd. O(n) is more complex than O( log(n) ) T or Fe. O(n log(n) ) is more complex than O(n2) T or F(2 pts each) Give the complexity of an algorithm for problem size n whose running time: f. Triples when n triples O( n )g. Quadruples when n doubles O( n2)h. Is unchanged when n triples O( 1 )i. Increases by 3 when n triples O( log(n) )4. (4 pts) Critical SectionsCalculate the asymptotic complexity of the code snippets below (using big-O notation) withrespect to the problem size n: a. for (i = 1; i < n; i=i*2) { f(n) = O( log(n) ) for (k = 1; k < 1000; k=k+2) {…} }b. for (i = n; i > 0; i=i-1) { f(n) = O( n2) for (j = 2; j < n-2; j=j+2) { ...} }15. (4 pts) Recursion(2 pts each) For each of the following codes, describe whether the function foo(n) willreturn a result when it is invoked as foo(4). If it returns a result, what is the value returned?If no result is returned, explain why.a. int foo (int n) { foo(4) = 4 if (n > 0) If no result, explain why return 1+foo(n-1);return 0;}b. int foo (int n) { foo(4) = no resultreturn foo(n-1) + foo(n-2); If no result, explain why} no base case6. (10 pts) Data Structuresa. Data structures differ mainly in the amount of storage required T or Fb. A queue is a restricted version of a list T or Fc. Elements are removed from a stack in reverse order of insertion T or Fd. Sets may contain duplicate elements T or Fe. Maps may contain more keys than values T or Ff. A key may be used to retrieve multiple values from a map T or Fg. Removing a key from a map also removes its associated value T or Fh. Collisions may cause run-time errors in open addressing hash tables T or Fi. Markers are needed for previously-filled hash locations for open addressing T or Fj. In Java, if a.equals(b) is false, then a.hashCode( ) != b.hashCode( ) is true T or F7. (12 pts) Operations on Data Structures(2 pts each) What is the average # of comparisons needed to find an element k in the following data structure, assuming k is stored in the data structure? Circle the closest value:a. A sorted array with 16 elements (using binary search) 1 2 4 8 16b. A linked list with 16 elements 1 2 4 8 16c. A sorted linked list with 16 elements 1 2 4 8 16d. A chained hash table of size 8 with 16 elements 1 2 4 8 16(1 pt each) For a data structure containing n elements, the complexity of:e. Finding the 5th element in an array is O( 1 )f. Finding the (n-5)th element in a linked list is O( n )g. Deleting the 5th element in an array is O( n )h. Deleting the 5th element in a linked list is O( 1 )28. (26 pts) Generic Programming & Data StructuresYou are asked to count the number of times each String occurs in an array. You realize youcan build a map from Strings to Integers to keep count of the number of occurrences foreach word. You start writing a class implementing the map, using linked lists with an extrakey field per node:a. (4 pts) Using your knowledge of generic programming, modify the MyListMap classso it supports generics (e.g., MyListMap<String,Integer>).public class MyLinkedMap<K,V> { private class Node {K key;V val;Node next; } Node head; public V get(K key) { … } public V put(K key, V val) { … }}b. (12 pts) Implement the put( ) method for the MyListMap class, using only a linked listformed from the inner Node class. public V put(K key, V val) {Node n = head;while (n != null) {if (n.key.equals(key)) { V oldVal = n.val; n.val = val; return oldVal;}n = n.next; }n = new Node();n.key = key; n.val = val; n.next = head; head = n;return null; }3c. (10 pts) Implement the following countStrings( ) method so that it returns a map fromStrings to Integers that counts the number of times each string occurs in the Stringarray strs. You must iterate through the Strings in the strs array using the enhancedJava for loop. You must create a MyListMap object using generics and use only its get() and put( ) methods to count strings.public static Map<String,Integer> count(String[ ] strs) {MyLinkedMap<String,Integer> cmap = new MyLinkedMap<String,Integer>(); for (String s : strs) {Integer i = cmap.get(s);if (i == null) cmap.put(s, 1);else count.put(s, i+1);}return cmap;}Honors Section – Credit is given only for Honors Section students!9. (14 pts) Honors a. An (n2) algorithm can require O(n3) steps to solve T or Fb. A polynomial time algorithm is one that can be solved in O(nk) steps T or F(2 pts each) Give the complexity of an algorithm for problem size n whose running time: c. Triples when n increases by 1 O( 3n)(2 pts) Calculate the asymptotic complexity of the code snippets below (using big-O notation) with respect to the problem size n: d. for (i = n; i > 0; i=i-1) { f(n) = O( n2) for (j = 2; j < i; j=j+2) { ... } }e. for (i = 3; i < n; i=i*2) { f(n) = O( log( log (n)) ) for (k = 2; k < n; k=k*3) {…} }(2 pts each) What is the average # of comparisons needed to find an element in the following data structure (assuming each element is equally likely to be targeted by find):f. A open addressing hash table of size 16 with 4 elements 1 2 4 8 16(1 pt each) For a data structure containing n elements, g. Deleting the (n-5)th element in a linked list is O( n )h. Deleting the (n-5)th element in a doubly-linked list (with tail) is O( 1
View Full Document
Unlocking...