EECS 380: Early Midterm - due 7:30 pm

This exam is for students who cannot attend the regular exam.
You should not take the midterm twice.

1. 25 pts Complexity
   1. 5 pts: Give the formal definitions of big-O and big-theta.

   2. 10 pts: Prove or disprove that for any three functions f(x), g(x), and s(x):
      s(x)=O(f(x)) and s(x)=O(g(x)) imply s(x) = O((max(f(x), g(x))), but do not imply max(f(x), g(x))=O(s(x)).

   3. 10 pts: consider h(x)=x²+1^x+log₂(x) and k(x)=x³+2^x +log₂₀(x),
      prove or disprove these two statements:
      h(x)=O(k(x)), k(x)=O(h(x)).
      You may use known facts about big-O relationships between elementary functions (polynomials, logs, exponentials). You need to state any relations you use, and otherwise provide a rigorous and self-contained proof.

2. 25 pts Search
   1. 15 pts: You are given two sorted integer arrays, a and b. There are N elements in a and M elements in b where M is always less than the square root of N. (Typical values might be N=1000000, M=100)

      Write a function int search(int a[], int b[], int M, int N) which has a return value of the number of elements which are found in both a and b. It should do this as effecently as possible.

   2. 5 pts: Give the tightest possible big-O complexity estimate for your program in terms of N then explain your answer. You should refer back to the known complexity results for binary search.

   3. 5 pts: If M were much closer to N (M=0.1*N) would you use the same algorithm as above? Justify your answer. If you have a different algorithm, provide its tightest possible big-O complexity.

       

       

3. 25 pts Sorted lists
   Your employer, the legal firm Dewey, Cheetham and Howe, has just gotten a new list of potential clients. They have asked you to add those people to their current client information and update existing entries. You are to write a function which takes two sorted, NULL terminated linked lists are arguments. You are to return a pointer to a sorted, NULL terminated, linked list which is a merge of the two lists. You must not change either of the two linked lists passed in. Each entry of the linked list consists of the following structure:

        struct Client
        {
            char f_name[40];  //first name
            char l_name[40];  //last name
   	 double money;     // how much money do they have?
        }
        

   An entry is considered a duplicate if and only if the first and last names match exactly. In the case of a duplicate entry you are to use the newer list's value for the money field in your list. Your function should be of the following form:

        Client * merge(Client * oldlist, Client * newlist)
        

   The code you write for this part should be able to be compiled under g++.
   That is, we want exact C++ syntax.
   You cannot use STL for this question

4. 25 pts: Algorithms for sorting
   1. 10 pts: Examine the following sequence of ranges that gradually become sorted, mention all sorting algorithms (out of selection sort, bubble sort, insertion sort, shaker sort, quick sort and merge sort) that are consistent with this sequence.

      0 2 4 6 8 1 9 7 5 3 
      0 2 4 6 8 1 9 7 5 3 
      0 1 4 6 8 2 9 7 5 3 
      0 1 2 6 8 4 9 7 5 3 
      0 1 2 3 8 4 9 7 5 6 
      0 1 2 3 4 8 9 7 5 6 
      0 1 2 3 4 5 9 7 8 6 
      0 1 2 3 4 5 6 7 8 9 
      0 1 2 3 4 5 6 7 8 9 
      0 1 2 3 4 5 6 7 8 9 
      

   2. 15 pts; write a program that will do insertion sort and prove its worst-case and best-case big-theta complexity (w/o referring to Chapter 6 in Sedgewick). Show best-case and worst-case inputs.