EECE 352: PS4

Due: Tuesday, 21 September 1999

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