CS 146 Practice Midterm

The practice midterm is below. Here are some facts about the actual
midterm: (a) The midterm will be in class Oct. 24. (b) It is closed 
book, closed notes. Nothing will be permitted on your desk except 
your pen (pencil) and test. (c) You should bring your student ID. 
(d) There will be more than one version of the test. Each version 
will be of comparable difficulty. (e) If your cell-phone or beeper 
goes off you will be excused from the test at that point and graded 
on what you have done till your excusal. (f) The test covers from
chapter 1 to the material on leftist heaps in Chapter 6. (g) To prepare for 
this test you should go over the practice midterm below, all homework
problems, and examples discussed in class. Then review your notes
and the readings from the book.

(1) Prove formally that:
    (a) N! is in O(2^{Nlog N})
    (b) N²+N is Theta(N²)
    (c) sum^N_i=1 (i+1)3ⁱ is O(N3^N) 
    (d) N is Omega(N^1/2)
    (e) log N is o(N)

(2) Estimate the runtimes of the following code fragments as a function of N:

    (a)  for( int i = 0; i < N; i++)
            for( int j = 0; j < N; j++)
                  System.out.println("Hello world");

    (b)  if( 5 > 3) System.out.println("hello");
         else
           for( int i = 0; i < N; i++)
              System.out.println("" + i);

    (c) for( int i = 0; i < N; i++)
              System.out.println("" + i);
        for( int j = 0; j < N; j++)
              System.out.println("" + j);

    (d) for(int j =0; j*j < N; j++)
             System.out.println("" + j);

    (e)  while (N > 0)
            N = N >>> 1;


(3) Suppose you have a singly linked-list A1->A2->...->A> and you are given
    a reference to A1 and a reference to some node Am where 1 < m < n.
    (a) Give an O(1) algorithm to remove Am+1 from the list
    (b) Give an O(1) algorithm to insert a node A' after Am.
    (c) Give an O(n) algorithm to find A(m-1)
    (d) Give an O(1) algorithm to remove the data associated with Am from the
         list.
    (e) Give an O(1) algorithm to produce a list with data items
         the same as the list:
         A1->...->A(m-1)->A'->Am->...->An
         where A' is some new node.  

(4) Show step by step how radix sort would sort the names 
    Ana, Art, Bea, Ted in increasing alphabetical order.

(5) Show step by step how to use a stack to evaluate the postfix expression:  
    4 2 7 * 5 - * 
    

(6) Show step by step how to use a queue to perform a level order traversal
    of the tree:
 
         (r)
       /  |  \
     (h) (i) (n)
     /   /
   (o)  (s)

(7) (a) Give the BST that results from performing the inserts 4 2 7 5 6. 
    (b) What does the BST look like after deleting the (4)?
    (c) redo (a) using AVL trees 
    (d) redo (b) using AVL trees.
    (e) Given the tree we got from (a) what would be the result of 
        a splay tree find operation on a search for 6?

(8) Define the following concepts:
    (a) B-tree of order M
    (b) primary clustering
    (c) rehashing
    (d) separate chaining
    (e) quadratic probing 

(9) (a) Give an O(N) algorithm that given an array of size N makes it into
        a heap.
    (b) Prove that it is O(N).

(10) Consider the following two leftist heaps:

      (3)            (4)
      /              / \
     (9)           (5) (6)

     Show how the merge algorithm from the book would merge them into
     one leftist heap.