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

    2. 5 pts: Prove that for any three functions f(x)>1, g(x)>1 and s(x)>1
      s(x)=O(f(x)) and s(x)=O(g(x)) imply s(x) = O(f(x) * g(x)), but do not imply f(x) * g(x)=O(s(x)).

    3. 15 pts: consider h(x)=x2+3x+log2(x) and k(x)=x3+2x +log10(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 Binary Search
    1. 15 pts: You are given a large, sorted, array of N strings (stored as const char *) and
      bool operator<(const char *, const char *) const;
      that compares two strings in time O(K), where K is the maximal length of any string. Write a program that, given a new string S, effeciently finds the last position in the array which contains a string which is less than S. For this problem you should use C/C++ like syntax.

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

    3. 5 pts: If the function
      bool operator==(const char *, const char *) const;
      is also defined, is it necessary to change the above algorithm to additionally tell (without performing another binary search) whether the array contains a copy of string S? Explain.

  3. 25 pts Linear-time Operations with sorted ranges
      Imagine that you are working for the telephone company AZ&Z, which keeps records of all calls made through its telephone network.

      Each call is represented by an object of class Call. class Call overloads read-only boolean comparison operators ==, < > <= and >= (comparisons are done by the telephone number which initiated the call). To get the originating phone number, use method
      double getPhone#() const;
      (a 10-digit phone number can overflow int and unsigned).

      You are given three very large arrays of objects of class Call (sorted by initiating numbers), that represent all calls made over the weekend (named weekend), on weekdays after business hours (named evening) and 9am-5pm on weekdays (named business).

      To evaluate a new calling plan for AZ&Z, you need to count unique telephone numbers from which calls initiated over the weekend or on weekdays after business hours, but never initiated a call 9am-5pm on weekdays.

      Write a function that will print the total count of those unique telephone numbers. That function should take the three arrays as arguments and should return a similar array which contains the numbers specified. You may assume that each of the arrays use a record with the number 0000000000 as a marker for the last record. The array you return should also have such an end marker. You may further assume that the array you generate will have no more than N phone numbers (where N is a global).

      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. 
      1 5 9 2 10 6 8 3 7 4 
1 5 2 9 6 8 3 7 4 10 
1 2 5 6 8 3 7 4 9 10 
1 2 5 6 3 7 4 8 9 10 
1 2 5 3 6 4 7 8 9 10 
1 2 3 5 4 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10
    2. 15 pts; write a program that will do selection 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.
Extra credit: 15 pts
Consider struct ListNode { double value; ListNode * next; };
You are given two read-only pointers:
const ListNode * ptr1, * ptr2;
Each of them points to some element of a singly-linked circular list (pointers may actually point to the same list, but may also point to lists of different sizes).

You need to write a self-contained program (no calls to STL) to construct a new circular list containing each element of the first list and each element of the second list. The order of elements from the first list should be the same as in the first list, and the order of the elements from the second list should be reversed. The program must work in linear time and use only a linear amount of additional memory. All other details are up to you.