COP 3530 Section 1                           EXAM 1                     October 4, 2001

 

Kraynek                                                                                 Name:_______________

 

5 pts.

1. What is the big-O growth rate of the solution to the following recurrence?

 

            f(1) = a

            f(n) = f(n/2) + bn

 

5 pts.

2. Which function grows faster, n1/2 or (log(n))2 ?

 

 

 

 

 

10 pts.

3. What is the big-0 running time in terms of n of the following segment?

 

            int x = 0;

            for(int i = 0; i < n; i++ )

                        for( int j = i; j < n; j++ )

                                    x = x+ 1;

 

 

15 pts.

4. What is the output of the following segment?

                        String out = "";

                        LinkedList L = new LinkedList();

                        ListIterator itr = L.listIterator();

                        itr.add(new Integer(1));

                        itr.add(new Integer(2));

                        itr.add(new Integer(3));

                        itr.add(new Integer(4));

                        itr.add(new Integer(5));

                        itr = L.listIterator();

                        out += L + "\n";

                        itr.next();

                        itr.next();

                        itr.next();

                        itr.add(new Integer(37));

                        out += L + "\n";

                        itr.previous();

                        out += itr.previous() + "\n";

                        itr.remove();

                        itr.next();

                        itr.next();

                        itr.set(new Integer(37));

                        out += L + "\n";

                        JOptionPane.showMessageDialog(null,out);

 

15 pts.

5. Write a recursive method

 

int numOfZeroes(ArrayList A, int right);

 

that returns the number of 0’s in the ArrayList A of Integer objects from index 0 to index right.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15 pts.

6. Suppose that A is an ArrayList whose elements are LinkedLists of Integers. Write a method

 

            void incrementAll(ArrayList A);

 

that adds 1 to every Integer value in A.

20 pts.

7. Write a method

 

            Map getTeams(BufferedReader in );

 

that read lines from a file as in Assignment Two and returns a Map with years (Strings) as keys and Sets of names (Strings) as values. If aYear is mapped into the Set S then S contains the names of all of the teams that participated in the NCAA tournament that year.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15 pts.

8. Suppose T is a TreeSet of Comparable objects. Show how to construct from T a TreeSet T1 of the same objects but the iterator for T1 will return the objects in the opposite order as the iterator for T.