// Homework 3. Please turn in your homework to the TA at the beginning of the discussion section. Note that all 
// C++ code that you use as part of your solution must be real C++ code (that is, we must be able to compile it).
// Do *not* express your solution in pseudo code.


Problem 1)

Suppose we have numbers from 0 to 15 stored in an STL vector, in a random order. Let's suppose we
want to look for the place (index) within that vector where some given value (for example, 12) is located. One easy
way of accomplishing this is by writing a for loop that tests each element of the vector, comparing
it to 12. When we find it, we simply print the index where it is. 

However, we might want to speed-up the search process and look for that value in parallel.
One possible way of achieving this is by creating several processes using fork(). Each process
can then search for the value in just a smaller portion of the vector, and all processes do so in parallel. 
For this problem, we want each process to be assigned with just *one* element of the vector. The task of each process 
will be to check if that one element is equal to the value that we are looking for. In order to accomplish this, we will 
need to repeatedly split the original range of the vector into 2 parts, assigning each part to a new process until a 
process is given a range containing just one element to examine. When this happens, it can then compare that one element 
to the element we are looking for.

The way that we're going to do this is by binary search: initially, the parent process starts with the task of searching 
for a given element in the whole vector. Since that's too difficult, we're going to call fork; the 1st resulting process will
have the task of searching over the first half of the vector and the second process will look in the second half. 
Now, each of these processes still has a complicated task (remember, we are assuming that each process is
only capable of testing whether one specific element in the vector is equal to the one we are looking for).
Therefore, each of these processes will in turn call fork again, creating new processes that will examine 
the respective first and second halves of the vector. We keep doing this until the range to be examined by each process
contains just one element. When that happens, we can compare it to the element we're looking for.

Note how this is just like a recursive binary search: each process first checks if the range of the vector that it has to 
examine contains more than one element. If it does, it calls fork and assigns each half of its vector to a new process. 
If, on the other hand, the range that it has to examine contains only one element, then it can directly compare it to the 
one we are looking for. If we have found the element, then we print its index within the array.


Construct your solution using the following code. The value to be looked for is passed by parameter when you call your program 
and should be a number from 0 to 15. The vector where the random data is stored is called "data". The parts of the program
where your code should be placed are marked with "(...)".


#include <iostream>
#include <string>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>   // Declaration for exit()
#include <vector>
#include <algorithm>

using namespace std;

ptrdiff_t myrandom (ptrdiff_t i) { return rand()%i; }
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;


int main(int argc, char *argv[])
{
 	srand ( unsigned ( time (NULL) ) );
	
	int N=16;

	if (argc != 2) {
		cout << "Use: " << argv[0] << "<number between 0 and " << N-1 << ">" << endl;
		exit(1);
	}

	int looking_for = atoi(argv[1]);

	if ((looking_for < 0) || (looking_for > N-1)) {
                cout << "Use: " << argv[0] << "<number between 0 and " << N-1 << ">" << endl;
                exit(1);
        }

	cout << "Generating random data..." << endl;
	vector<int> data;
	for(int i=0; i<N; i++)
		data.push_back(i);

	random_shuffle(data.begin(), data.end(), p_myrandom) ;
	
	cout << "Random data is" << endl;
	for(int i=0; i<N; i++) {
		cout << "At position " << i << ":\t" << data[i] << endl; 
	}

	cout << endl << "Looking for " << looking_for << endl << endl;
	
	// Initially the element we're looking for can be anywhere between "first" and "last". 
	// "first" and "last" are the variables describing what range of the vector the current process has to examine
	int first = 0;
	int last  = N-1 ;

	while( (first-last+1) != 1 ) {     // if the range this process has to examine contains more than one element..
              (...) // then we fork and give half of the current range to each of the new processes
	}

	// when the "while" loop exits, that means the current process has to examine a range of the vector that
	// contains just one element
	if ( (...) == looking_for)
		cout << "Data found in position " << (...) << endl;

	return 0;

}
 



Problem 2) In a short answer, explain why a one-processor system can
support multiple programs or threads. Explain what a context switch is.




Problem 3) Consider the parallel Fibonacci example from lecture, which
forked child processes to print out the Fibonacci numbers from 0,...,N.
Implement this instead by creating (N+1) new threads (one thread for the
calculation of each Fibonacci number). Put the results into a shared
global map. Each thread must lock/unlock the map when using it, and the
Fibonacci number calculation cannot rely on the results from other
threads.
The results must print out in order, F(0),...,F(N).
The Fibonacci numbers are defined as: F(0)=0. F(1)=1. F(n)=F(n-1)+F(n-2)
Try N=20 or so to start with. Skeleton code is below.
Compile with "g++ -Wall -pedantic -o hw3_p4 hw3_p4.cc -lpthread".
Google "pthread_create" etc to find function descriptions.


#include <iostream>
#include <map>
#include <pthread.h>
using namespace std;

#define FIB_NMAX (20)

map<int,long> fib_results;
// any other required global variable:  e.g. a mutex variable
  
long fib(int n)
{
  if (n==0) { return 0; }
  if (n==1) { return 1; }
  return (fib(n-1) + fib(n-2));
}

void *fib_thread(void *i)
{
  int n = (int)((long)i); // not the cleanest, but works...

  // calculate fib(n), put results into shared global map, entry fib_results[n]
  // lock the minimum critical section with pthread_mutex_lock()/unlock()

  return NULL;
}

int main()
{
  // init mutex, create threads, join threads, print results in order
  // use pthread_mutex_init(), pthread_create(), pthread_join()
  //
  // You can use NULL for the attributes in pthread_mutex_init()
  // and pthread_create(). If you have int n, you can recast it
  // and pass ((void *)n) as the thread function argument to pthread_create().
  //
  // You can ignore the return value in the second argument of pthread_join(),
  // by declaring "void *r", using &r as the second argument of pthread_join(),
  // and never bothering to check it (fib_thread() always returns NULL).
}