Grader Use Only 1 2 3 4 5 6 7 8 Total CMSC132 Summer 2006 Midterm 2 Key First 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 1 12 12 12 12 10 14 14 14 100 NOTE Remember the punt rule while grading Problem 1 Hashing 12 pts 2 1 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 size 4 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 return distinct 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 Java programming language TM Problem 2 Networking 12 pts 1 2 pts Which of the following applications can use UDP Circle those that apply a Video Streaming b Online banking 3 c ftp client Answer a 2 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 number 3 1 pt TCP is unreliable True False Answer false 4 1 pt UDP has low overhead True False Answer true 5 2 pts What is a DNS server Answer Maps domain names to IP addresses 6 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 bogus 7 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 bigO 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 sort 4 3 2 pts What causes quicksort to have a cuadratic O n2 performance Briefly explain Answer A bad partitioning function 4 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 sort 5 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 explain Answer Algorithm where the relative order of equal keys is unchanged Problem 4 Algorithmic Complexity 12 pts 1 2 pts What array operation has an asymptotic complexity of O 1 Answer Array indexing 2 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 5 O log n Answer O log n O nlog n O n3 4 O n3 O nlog n O 3n O 3n 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 608 Answer a z 0 9 2 3 pts What is the output of the following code fragment 6 Pattern p Pattern compile site Matcher m p matcher BCsite12 done DDsiteDD while m find System out println m group 2 Answer 12 DD 3 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 c Problem 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 zero is provided Feel free to add an auxiliary method Non recursive solutions will receive no credit 7 One possible solution public static String reverse int a if a null a length 0 return return reverseAux a 0 private static String reverseAux int b int index if index b length 1 return String valueOf b index else return reverseAux b index 1 b index …
View Full Document
Unlocking...