CMSC132, Practice Problems (Midterm #1)Problem 1 Files, Scanner, and Generics in JavaA. Files & Scannera. Files may be viewed as streams when opened using either the FileReader andFileInputStream classes. What is the difference between the two types of streams?b. What is the motivation for using the Scanner class to process text input?c. Write code to show how the scanner may be used to read in a series of alternatingnumbers (ints) and names (Strings) from a text file (starting with a number). class Scanner {Scanner ( … ) { … }boolean hasNext( ) { … }String next( ) { … }int nextInt( ) { … }String nextLine( ) { … } } myFileReader( ) { try { BufferedReader f = new BufferedReader( new FileReader( filename ));// insert code to read in numbers and names from file } catch (IOException e) { System.out.println(e.getMessage()); } }B. Genericsa. What is the motivation for using generic types?b. Classes in the Java Collection Framework support generic types in Java 1.5. Show how to modify the following code to declare a LinkedList class for Strings using generics, then add & get a String object from the list.// previously LinkedList myList = new LinkedList( );myList.add( new String(“test”) );String s = (String) myList.get(0);1Problem 2 Algorithmic Complexity C. Algorithmic complexitya. What is algorithmic complexity?b. List 2 reasons benchmarking is better than analyzing complexity c. What is the difference between best case, worst case, and average case?d. What is a recurrence relation?D. Big-O notation and complexitya. What does the Big-O notation represent?b. Why are O(2n+4) and O(n) considered equivalent?c. Why are O(n2) and O(n) not considered equivalent?d. What are some simple rules for calculating Big-O notation?e. Sort the following complexity categories from least to most complexi. Constant O(1)ii. Cubic O(n3)iii. Exponential O(2n)iv. Linear O(n)v. Logarithmic O(log(n))vi. Quadratic O(n2)f. How are the following complexity categories similar?O(n2), O(n4), O(n3), O(n12), O(n99)E. Calculating Big-O functionsWhat is the asymptotic complexity of the function f( ) below (using big-O notation) when the complexity of f( ), and g( ) are as shown?f(n) { g(n); h(n);}a. h(n) = n+1, g(n) = 2n f(n) = O( )b. h(n) = 3n, g(n) = 4n2f(n) = O( )c. h(n) = log(n), g(n) = 5nf(n) = O( )d. h(n) = 8n, g(n) = 2n f(n) = O( )2F. Finding critical regionsCalculate the asymptotic complexity of the code snippets below (using big-O notation) with respect to the problem size n: a. for (i = 1; i < n; i=i+2) { f(n) = O( )…}b. for (i = 1; i < n; i=i*2) { f(n) = O( )…}c. for (i = 0; i < n; i++) { f(n) = O( ) for (j = 1; j < n; j=j+2) {… }}d. for (i = 0; i < n-2; i++) { f(n) = O( ) for (j = 0; j < 100; j=j+2) { for (k = 1; k < 3*n; k++) { ... } }}e. for (i = 0; i < n; i=i*2) { f(n) = O( ) for (j = 1; j < n; j++) { ... }}f. 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 < n; j=j+1) { ... }}3Problem 3 Recursive AlgorithmsG. Recursiona. Describe the difference between an iterative and recursive algorithm?b. What are the 2 main parts of a recursive algorithm?c. Name 4 requirements for recursive algorithms to work correctly.d. Name 2 advantages & 2 disadvantages of recursive algorithmsH. Legality of recursive codeFor each of the following codes, describe what result is returned when foo(n) is invoked. Ifno result is returned, explain why.a. int foo (int n) { foo(n) =return foo(n-1);}b. int foo (int n) { foo(n) = if (n == 1) return 1; return foo(n-1);}c. int foo (int n) { foo(n) = if (n == 1) return 1; return 1+foo(n-1);}d. int foo (int n) { foo(n) = if (n == 1) return 1; return foo(n);}e. int foo (int n) { foo(n) = if (n == 1) return 1; return foo(n-1)+f(n-1);}I. Writing recursive code (you may use helper functions)a. Write a recursive function to search an unsorted array for a number kpublic static boolean findNum(int k, int[] array)b. Write a recursive function to calculate the sum of an array of intspublic static int sumArray(int[] array)c. Write a recursive function to determine whether an array of ints is sorted (ascending)public static boolean sortedArray(int[] array)4Problem 4 Linear Data StructuresJ. Taxonomy & propertiesa. Describe the main difference between linear and hierarchical data structuresb. Describe the main difference between a linked list and an arrayc. Describe the main difference between a queue and a stackd. Describe a circular linked listK. Given the following Java class definition for a singly linked listClass Node { int myValue; Node next;}Class LinkList { Node head; // first node in list Node find(int k) { … } void insertHead(Node n) { … } void insertTail(Node n) { … } void removeTail( ) { … }}Write the following code:a. find( k ) – Find a node with myValue = k in a linked listb. insertHead( n ) – Insert node n at the head of a linked listc. insertTail( n ) –Insert a node n at the tail of a linked listd. removeTail( ) – Delete the node at the tail of a linked liste. Which 2 methods in the LinkList class can be used to implement a queue?f. Which 2 methods in the LinkList class can be used to implement a stack?5Problem 5 Maps & HashingL. Sets & mapsa. What is the difference between a set and a map?b. What is the difference between a map and a hash table?c. How are maps useful?d. Given the following TreeMap API, show how to write code to construct a TreeMapstoring String objects for actor names with movie titles. The TreeMap should allowmovie names to be used to look up lead actor names (assuming each move has a singleleading actor)public class TreeMap { TreeMap( ) { … } Object get( Object key ) { … } Object put( Object key, Object value ) { … } Object remove( Object key ) { … }}TreeMap myDB = new TreeMap( );void addMovie( String leadActor, String movie ) {… // write code to add leading actor name for movie to TreeMap} String findLeadActor( String movie ) {… // write code to find String for leading actor name for movie }M. Hashinga. What is a hash function?b. What is a desirable property of hash functions?c. What is a perfect hash function?d. What is a collision?e.
View Full Document
Unlocking...