CMSC132 Summer 2006Midterm #2 KeyFirst 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 100 points. - The short answer questions are not essay questions. Strive to answer them in 1 or 2 sentences. Longer answers are not necessary and are discouraged.- WRITE NEATLY. If we cannot understand your answer, we will not grade it (i.e., 0 credit).- PUNT RULE:. For any question, you may write PUNT, and you will get ¼ of the points for the question (rounded down). If you feel totally lost on a question, you are encouraged to punt rather than waste time writing down a bunch of vaguely related verbiage in hopes of getting some partial credit.1Grader Use Only:#1 (12)#2 (12)#3 (12)#4 (12)#5 (10)#6 (14)#7 (14)#8 (14)Total (100)NOTE: Remember the punt rule while grading.Problem 1 Hashing (12 pts)21. (2 pts) What are the properties of a good hash function? Notice we are not asking about the properties of the Java hashCode method.Answer: It distributes values nicely. It is not expensive to compute.2. (2 pts) What is bucket hashing (chaining)? Briefly explain.Answer: Approach where the hash table contains list of objects.3. (2 pts) In the context of hashing, what is the load factor? Briefly explain.Answer: Entries/table size4. (2 pts) When defining a hashCode for a class, could two objects have the same hash code? Briefly explain.Answer: Yes as this does not contradicts the java constract for the hashCode. 5. (2 pts) Say objects a and b are equal according to the Java equals method. What should be true about their hash codes, so that the java contract regarding hashing is satisfied? Briefly explain.Answer: Their hash codes must be the same.6. (2 pts) Is the hashing java contract satisfied if you don’t overwrite the equals and the hashCode methods for a class? Briefly explain. Answer: Yes because by default equals compare the addresses of objects and hashCode returns an integer that corresponds to the internal address of the object.As much as is reasonably practical, the hashCode method defined by class Object does returndistinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)Problem 2 Networking (12 pts)1. (2 pts) Which of the following applications can use UDP? Circle those that apply.a. Video Streamingb. Online banking3c. ftp clientAnswer: a2. (2 pts) What other piece of information we need in addition to the IP address in order to identify a process in a computer?Answer: port number3. (1 pt) TCP is unreliable. True/FalseAnswer: false4. (1 pt) UDP has low overhead. True/False.Answer: true5. (2 pts) What is a DNS server? Answer: Maps domain names to IP addresses6. (2 pts) Identify the protocol, and the domain name in the following URL:ftp://www.notreally.bogus/dist/p1.pdf Answer: Protocol: ftp Domain Name: www.notreally.bogus7. (2 pts) Say a server has obtained a socket to communicate with a client (e.g., clientRequestSocket = serverSocket.accept()). What should the server do next in order to send and receive information from the client? You do not need to write code, just indicate what the server should do.Answer: Obtain input and output streams associated with the socket.Problem 3 Sorting (12 pts)1. (2 pts) What is the proven lower bound for comparison-based sorting? Write you answer using big- O notation.Answer: O(nlog(n))2. (2 pts) Name two linear sorting algorithms discussed in class.Answer: Any two of counting sort, bucket (bin) sort, radix sort43. (2 pts) What causes quicksort to have a cuadratic (O(n2)) performance? Briefly explain.Answer: A bad partitioning function4. (2 pts) What two sorting algorithms have an average case and worst case complexity that corresponds to O(nlog(n))?Answer: Heap sort and merge sort5. (2 pts) Name two sorting algorithms that are stable? Answer: Any two of bubble, selection, merge, counting, bucket, or radix sort 6. (2 pts) What is an in-place sorting algorithm? Briefly explainAnswer: Algorithm where the relative order of equal keys is unchangedProblem 4 Algorithmic Complexity (12 pts)1. (2 pts) What array operation has an asymptotic complexity of O(1)?Answer: Array indexing2. (2 pts) What is the critical section of an algorithm? Briefly explain.Answer: Section of an algorithm that dominates overall execution time.3. (2 pts) Sort the following complexity categories from least to most complex.5O(log(n)) O(n3) O(nlog(n)) O(3n)Answer: O(log(n)) O(nlog(n)) O(n3) O(3n)4. (6 pts) Calculate the asymptotic complexity of the code snippets below (using big-O notation) with respect to the problem size n: a. f(n) = O( n2)int a=1, b;while (a <= n/2) {b = 1;while (b <= 2*n) {System.out.println(a * b);b++;}a++;}b. f(n) = O( n )for (int i=0; i<=n/2; i += n/2) {for (int k=0; k<n/2; k++) {System.out.println(i + k);}}c. f(n) = O( nlog(n) )for (int k=0; k<n-1; k++) {for (int m=1; m<n; m*=2)System.out.println(k*m);}Problem 5 Regular Expressions (10 pts)1. (4 pts) Write a Java regular expression for the language that includes strings of digits that are preceded by zero or more characters except lowercase letters. Examples of strings in the language are:A557 %608Answer: [^a-z]*[0-9]+2. (3 pts) What is the output of the following code fragment?6Pattern p = Pattern.compile("(..)site(..)");Matcher m = p.matcher("BCsite12 done DDsiteDD");while (m.find()) System.out.println(m.group(2));Answer:12DD3. (3 pts) What is the language defined by the following Java regular expression?a+(b|c)Answer: 1 ore more a’s followed by a b or cProblem 6 Recursion (14 pts)The static method reverse has the following prototype:public static String reverse(int[] a)The method returns a string with the elements of the integer array in reverse order. For example, the method call reverse(new int[]{10, 20, 30}) will generate the string 30 20 10. An empty space should appear between elements. The method should return the empty string (“”) if an array of size zerois
View Full Document
Unlocking...