1.  Runtime analysis

(a)  Given the following piece of code:

p u b l i c   s t a t i c   i n t   someFunction ( i n t   n )

{         i n t   i ,   j ,   sum  =  0 ;

f o r   ( i =0;   i  <  n ;   i +=2)    / ∗ l o o p   1  ∗/

sum  +=  i ∗ i ;

f o r   ( i =0;   i  <  n ;   i ++)    / ∗ l o o p   2  ∗/

f o r   ( j =1;  j  <  n ;   j=j ∗ 2 )     /∗ l o o p   3  ∗/

sum  +=  i ∗ j ;

r e t u r n  sum ;

}

What is the run time of:

i.  Loop 3

O(log n) (j is growing in multiples of 2, so after at most log n iteration it will reach n)

ii.  Loop 2 (including the runtime of loop 3).

Loop 2 runs loop 1 n times, so overall O(n log n)

iii.  Loop 1.

O(n) (notice that while the loop runs  times, the big-O expression is the simplest, no coefficients).

iv.  The whole function, explain briefly.

O(n log n)  .   First loop  1, followed by loop 2  (3 is nested within 2).   So the overall runtime is the sum of both.  Notice that the correct expression is O(n log n) and not O(n + n log n) because we use the simplest form, no coefficients or polynomials, and O(n log n) dominates O(n).

(b)  An algorithm takes 15 seconds to solve a problem of size 1000. If the algorithm is quadratic – i.e., runs as O(N2 ), how large a problem can be solved in 60 seconds?

i.  2000

ii. 4000

iii.  6000

iv.  none of the above

The answer is 2000.  A quadratic algorithm takes four times more when the input size is doubled.

2.  Java Data Structures (from Midterm F16):  For (a-c) below, determine what is the best data structure to use out of the ones we discussed in class: List, Set, Map. If more than one acceptable answer exists, use the most efficient one (with respect to runtime) that has the power you need. Also say what type you use:  LinkedList vs.  ArrayList, HashSet vs.  TreeSet or HashMap vs. TreeMap. Please provide an explanation.

(a) You are working on a banking program. Each day, the checks for one account are processed

and (assuming they don’t “bounce”) an appropriate Check object is added to the Account object, to wait for end-of-month processing to write the bank statement. The check objects have fields number (of type int), received (of type Date) and amount (of type Money) and must be kept in original order by time of arrival, and are only used once (in our simplified system) to write the statement, where they are reported in the same order.

List<Check>, Set<                               >, Map<                               ,                                 >

Both LinkedList and ArrayList are good.  Notice that a TreeSet that compares by date is not good because dates may have duplicates and a List is the simplest way to keep items in the order they were inserted.

(b) In the same banking scenario, each account has a unique id (an Integer) and one or more

owners identified by social security numbers (also ints).  Also bank account holders may have several accounts, each with a unique id.  Explain how you can use two Collections API classes working together to support looking up the bank accounts ids for given social security numbers.

List<                                    >, Set<                                    >, Map<Integer,Set<Integer>> HashMap and HashSet are best.

(c) You want to be able to display the courses a student took  (represented as Strings, like “CS310”) and their grades (represented as Characters between ’A’ and ’F’, assume there are no “A-” grades etc.), sorted by the grade. Explain briefly.

List<                                 >, Set<                                 >, Map<Character, Set<String>>

TreeMap of TreeSet are good.  Letter grades can have duplicates, so just a Map from a Character to a String won’t do.  Another option is to make a List<Set<String>> with 5 entries, from A to F (no E, of course).

3.  Hash tables

(a) You created a hash table using separate chaining and forgot to rehash.  You then realized

that you inserted n log n elements into the hash table whose array size is n.  What would be the average lookup time for your hash table now? Explain briefly.

Assuming a good hashing function, the average lookup time is the average number of ele- ments per chain, which is O(log n).

(b) We implement a hash table of integers, using an array of size 7.   The hashing function

for an integer x is h(x) = x%7.  We use linear probing to resolve collisions.  The elements are inserted in the following order:  1,15,14,3,10,5,25.  We do not rehash.  Draw the final configuration of the table and determine how many collisions each element will cause. For your convenience you may use the following table and illustration of the hash table.