**Problem 1(40%):** Calculate the time T(N) that each of the
following recursive functions takes to execute. That is, find
the recursive function T(N), for example: T(N) = 3* T(N/2). You
do **not** need to solve the recursive equation.

int foo(int N) { if (N == 0) return 1; else return N * foo(N-1); } int bar(int N) { if (N == 1) return 1; for (int i = 1; i < N; i++){ bar(N-1); } } int bazo(int N) { if (N < 1) return 1; for (int i = 1; i < N*N; i++){ for (j = 1; j < i; j++) { bazo(N/2); } } } int hard(int N) { if (N < 1) return 1; return (N*hard(N/2))/hard(N-1); }

**Problem 2(10%):** Calculate the time T(N) that the
following function takes. This time, however, you need to solve
the resulting equation.

int easy(int N) { if (N < 1) return 1; for (int i =1; i < 5; i++) easy(N/3); for (int i =1; i < N*N; i++) something(); // takes O(1) time }

**Problem 3(50%):** For this part you will implement a binary
search function and an insertion sort.

A binary search looks for a particular value in a vector. The
function assumes that the vector is sorted. Therefore, it looks
for the value by checking if the value is bigger or smaller than
the middle value in the vector. If its bigger then it
**recursively** examines the second half of the vector.,
otherwise it examines the first half. Figure 5.12 of the
textbook shows a binary search. This is the function you must
implement. However, **the function you implement must be
recursive**. It must also obey the function declaration
(i.e. signature) I give below.

For the second part you are to implement an insertion sort
function. The book implements an insertion sort in Figure
8.3. However, the insertion sort you will implement will have
the same signature as the STL sort (this is the *right* way
of extending the STL), which I give below. Your insertion sort
will need to use iterators. Also, you will notice that you
cannot store a tmp value, as the book does. You must get around
this using the built-in (in the standard library) swap()
function. You will have to really understand how insertion works
in order to use swap() instead of a tmp value.

#include<iostream> #include<vector> #include<algorithm> using namespace std; //Like figure 8.3, but using iterators. //You cannot simply copy figure 8.3. It will not work because // you cannot declare a tmp variable like they do (why? templates). //However, you can get around this by using the standard library // swap(x,y) function and changing the algorithm slightly. //You can assume that the Iter is a random access iterator. // that is you can ++, --, add and subtract ints to it. template <class Iter> void myInsertionSort(Iter begin, Iter end){ //implement this } // bool myBinarySearch(vector<int> & v, int e){ //implement this } void print(int e){ cout << e << ' '; } int main() { vector<int> v; v.push_back(2); v.push_back(9); v.push_back(4); v.push_back(5); v.push_back(7); v.push_back(3); v.push_back(8); v.push_back(1); v.push_back(10); for_each(v.begin(), v.end(), print); cout << endl; //You might want to replace this with sort() and implement the //myBinarySearch() first since its easier. myInsertionSort(v.begin(),v.end()); for_each(v.begin(), v.end(), print); cout << endl; for (int i = 3; i< 12; i++){ if (myBinarySearch(v, i)) cout << i << " is in " << endl; else cout << i << " is not in" << endl; } return 0; }

Jose M. Vidal Last modified: Tue Sep 14 16:58:14 EDT 1999