1. Sort Example
    1. Output 
      
First fill with random values
        Element Key   Value
             0   38   5.61538
             1  437   3.62245
             2  365   5.58824
             3  112       353
             4  142   7.39474
             5  421   5.17442
             6  497   2.33766
             7  391   22.1429
             8  457   3.93902
             9  240    2.8481
            10  446   2.19512
            11   87   10.7105
            12  111   2.05263

Now sort the array
In bubble sort
        Element Key   Value
             0   38   5.61538
             1   87   10.7105
             2  111   2.05263
             3  112       353
             4  142   7.39474
             5  240    2.8481
             6  365   5.58824
             7  391   22.1429
             8  421   5.17442
             9  437   3.62245
            10  446   2.19512
            11  457   3.93902
            12  497   2.33766

Insert some new values in the array
        Element Key   Value
             0   38   5.61538
             1   87   10.7105
             2  111   2.05263
             3  112       353
             4  142   7.39474
             5  240    2.8481
             6  365   5.58824
             7  391   22.1429
             8  421   5.17442
             9  437   3.62245
            10  446   2.19512
            11  457   3.93902
            12  497   2.33766
            13   34    3.1457
            14   23     1.123

Find some values in the array
        Find 34   Using Linear search 3.1457
        Find 600   Using Linear search  Not found

Put the new values in sequence
In Exchange Sort
        Element Key   Value
             0   23     1.123
             1   34    3.1457
             2   38   5.61538
             3   87   10.7105
             4  111   2.05263
             5  112       353
             6  142   7.39474
             7  240    2.8481
             8  365   5.58824
             9  391   22.1429
            10  421   5.17442
            11  437   3.62245
            12  446   2.19512
            13  457   3.93902
            14  497   2.33766

Find some values in the array
        Find 34   using Binary search 3.1457
        Find 600   using Binary search  Not found
Press any key to continue . . .

    2. Header File 
      #ifndef SORTIT
#define SORTIT

struct Element {
       int   key;
       float value;
};

class Array {
      private :
              int     size;
              Element Table[100];
              bool    sorted;
              void    Bubble();
              void    Exchange();
              int     Linear(int);
              int     Binary(int);
              
      public:
             Array();               // Constructor
             void Sort();
             bool Find(int, float&);
             void Put(int, float);
             void Show();
};
#endif

    3. Main 
      #include <cstdlib>
#include <iostream>
#include "sort.h"

using namespace std;

int main(int argc, char *argv[])
{
    Array x; 
    float a,b;
    int i;
    int ikey;
    srand(0);

    cout << endl << "First fill with random values "<<endl;
    for(i=0;i<13;i++) {
        ikey=rand()%500;
        a=rand()%500;
        b=rand()%100+1;
        x.Put(ikey,a/b);
    }
    x.Show();

    cout << endl << "Now sort the array " << endl;
    x.Sort();
    x.Show();    

    cout << endl << "Insert some new values in the array" << endl;
    x.Put(34,3.1457);
    x.Put(23,1.123);  
    x.Show();   

    cout << endl << "Find some values in the array" <<endl;
    cout << "\tFind 34   ";
    if( x.Find(34,a)) cout << a << endl;
    else cout << " Not found " << endl;
    cout << "\tFind 600   ";
    if( x.Find(600,a)) cout << a << endl;
    else cout << " Not found " << endl;    

    cout << endl << "Put the new values in sequence" << endl;
    x.Sort();
    x.Show();    

    cout << endl << "Find some values in the array" <<endl;  
    cout << "\tFind 34   ";
    if( x.Find(34,a)) cout << a << endl;
    else cout << " Not found " << endl;
    cout << "\tFind 600   ";
    if( x.Find(600,a)) cout << a << endl;
    else cout << " Not found " << endl;

    system("PAUSE");
    return EXIT_SUCCESS;

    4. Implementation 
      #include <iostream>
#include <iomanip>
#include "sort.h"
#include <cstdlib>

using namespace std;

Array::Array() // Constructor
{
     size=0;
     sorted=false;
}
void Array::Put(int key, float value)
{
     if(size < 100) {
             Table[size].key=key;
             Table[size].value=value;
             size++;
             sorted=false;
     }
}
void Array::Sort()
{
     static int count=0;
     if(count) Exchange();
     else Bubble();
     sorted=true;
     count++;
}

void Array::Show()
{
     int i;
     cout << "\tElement Key   Value" <<endl;
     for(i=0;i<size;i++) 
         cout << "\t" << setw(6) << i
              << setw(5) << Table[i].key
              << setw(10) << Table[i].value << endl;
} 
bool Array::Find(int key, float& value)
{
     bool found=false;
     int  subscript;
     if( sorted) subscript=Binary(key);
     else subscript=Linear(key);
     if(subscript >= 0) {
                  found=true;
                  value=Table[subscript].value;
     }
     return found;
}

// Private Functions

int Array::Linear(int key)
{
    int found=-1;
    int i;
    cout << "Using Linear search ";
    for (i=0;i<size;i++)
        if(key == Table[i].key) return i;
    return(-1);
} 
int Array::Binary(int key)
{
    int lo,hi,mid;
    lo=-1;
    hi=size;
    cout << "using Binary search ";
    while(1) {
             if(lo+1==hi) return (-1);
             mid=(lo+hi)/2;
             if(Table[mid].key > key) hi=mid;
             else if(Table[mid].key < key) lo=mid;
             else return mid;
    }
    return (-1);
}   
void Array::Bubble()
{
     Element temp;
     cout << "In bubble sort"<< endl;
     int  a,b;
     for(a=0;a<size-1;a++)
        for(b=a+1;b<size;b++)
           if(Table[a].key > Table[b].key) {
                  temp=Table[a];
                  Table[a]=Table[b];
                  Table[b]=temp;
           }                 
}
void Array::Exchange()
{
     Element temp;
     bool pass;
     int  a;
     cout << "In Exchange Sort " << endl;
     pass=true;
     while(pass) {
          pass=false;
          for(a=0;a<size-1;a++)
              if(Table[a].key > Table[a+1].key) {
                  temp=Table[a];
                  Table[a]=Table[a+1];
                  Table[a+1]=temp;
                  pass=true;
              }
     }
}

  2. Eight Queens Problem.
    8 . . . . . . . .
    7 . . . . . . . .
    6 . . . . . . . .
    5 . . . . . . . .
    4 . . . . . . . .
    3 . . . . . . . .
    2 . . . . . . . .
    1 . . . . . . . .
    ABCD EFGH 
    /*
  8 Queens
*/
#include 
#include 

int safe( int, int[]);
void print(int[],int);

using namespace std;

void main()
{
	int board[9];			// use 1..8
	int thisqueen, count, i;
  
	for(i=0;i<9;i++) board[i]=0;	// clear the board
	 
	board[1]=1;						// set queen 1 in row 1
	thisqueen=2;					// start with queen 2
	count=0;

	while(1) {
		count++;					// time thru this loop.
		if(safe(thisqueen,board)) {  // Can I put this queen on the board?
			thisqueen++;             // go to next queen;
			if(thisqueen > 8) {      // past 8 we have a solution
				print(board,count);  // print it.
				break;               // out of loop
			}
		} else {				 	// Not safe!
			if(board[thisqueen] < 9) {  // Can I move this queen?
				board[thisqueen]++;     // yes
			} else {					// no BACKTRACK!
				board[thisqueen]=0;     // set this queen back at start
				thisqueen--;            // reurn to prior queen
				board[thisqueen]++;
			} 
		} // end of safe check;
	} // end of loop
}

int safe(int here, int board[9])
{
/*
    Is the queen on here safe?
*/
	const int TRUE=1;
	const int FALSE=0;
	int till, value;

	value=TRUE;			// assume safe

	if(board[here] ==0 || board[here] > 8) value=FALSE;  // bad values

	for(till=1;till< here && value == TRUE; till++) {
		if(board[till] == board[here] ||				//same row
			here-till == abs(board[here]-board[till]))  // same daigonal
			value=FALSE;
	}
	return value;
}

void print(int board[9], int count)
{
	char row[]=" ABCDEFGH";
	static int solution=1;

	int i;

	cout << "Solution :" << solution;
	cout << " Iterations : " << count << " ";
	for(i=1;i<9; i++) {
		cout << row[i] << board[i] << " ";
	}
	cout << endl;
	solution++;
}

Solution :1 Iterations : 1092 A1 B5 C8 D6 E3 F7 G2 H4
Press any key to continue

    8 . . Q . . . . .
    7 . . . . . Q . .
    6 . . . Q . . . .
    5 . Q . . . . . .
    4 . . . . . . . Q
    3 . . . . Q . . .
    2 . . . . . . Q .
    1 Q . . . . . . .
    ABCD EFGH

  3. When you invest money over several years, how you do know how much you have earned on you investment? For example you invest the following amounts. 
     Year   Amount
  1     $1,000
  2     $2,000
  3     $3,000
  4     $4,000
    In year 5 you receive $12,000, you invested $10,000, so you earned $2,000 or 20% on your investment. Not quite there is a time value to money a dollar today is worth more than a dollar a year from now. If the current interest is 6% a dollar a year from now is worth only 94.3 cents. Or this can be stated as $1.00/(1 + interest rate).

    In order to figure how much we made on out investment we need to treat cash outflows as negative numbers and inflows as positive numbers and solve the following equation for i. 

    x0/(1+i)0 + x1/(1+i)1i + x2/(1+i)2 + x3/(1+i)3 - x4/(1+i)4=0



    When we find an i where the inflows equal the outflows we know the return on our investment. One way is to use a binary search for the i value. Write a program to calculate the irr for this set of cash flows.
    1. Header 
      #ifndef _IRR
#define _IRR

class flow {
      private:
              float list[100];
              int    count;
       public:
              flow();    //constructor
        void  push(float);
        float irr();
};   

#endif

    2. Main 
      #include <cstdlib>
#include <iostream>
#include <iomanip>
#include "irr.h"

using namespace std;

int main(int argc, char *argv[])
{
  float value;
  flow  x;
  
  cout << "when entering values enter" << endl;
  cout << "cash outflows as negative numbers" << endl;
  cout << "cash inflows as positive numbers" << endl;
  do {
      cout << "Enter a flow value :";
      cin >> value;
      x.push(value);
   } while(!cin.eof());
   cout << setiosflags( ios:: showpoint | ios::fixed); 
   cout << endl << "The rate of return on this investment was " 
        << setprecision(2) << x.irr() << " percent" << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

    3. Implementation 
      #include <cmath>
#include "irr.h"

using namespace std;

flow::flow()
{
     count=0;
}
void flow::push(float value)
{
     list[count]=value;
     count++;
}
float flow::irr()
{
  float high,low, result, sum;
  int limit;  
  count--;       
  high=1;
  limit=0;
  low=0;
  do {
      if(++limit >20) break;
      sum=0;
      result=(high+low)/2;
      for(int j=0;j<count;j++)
           sum+= list[j] / pow((1+result),(float)j);
      if( sum < 0.0 ) high=result;
      if( sum > 0.0 ) low=result;;
  } while (fabs(sum) > 0.00001);
  result*=100.0;
  return result;
}

    4. Execution When I run this program for the values in the problem I get: 
      when entering values enter
cash outflows as negative numbers
cash inflows as positive numbers
Enter a flow value :-1000
Enter a flow value :-2000
Enter a flow value :-3000
Enter a flow value :-4000
Enter a flow value :12000
Enter a flow value :^Z

The rate of return on this investment was 9.32 percent
Press any key to continue . . .
      Not as good as 20% but still good. If I reverse the order of cash outflows my return is less. Why? 
      when entering values enter
cash outflows as negative numbers
cash inflows as positive numbers
Enter a flow value :-4000
Enter a flow value :-3000
Enter a flow value :-2000
Enter a flow value :-1000
Enter a flow value :12000
Enter a flow value :^Z

The rate of return on this investment was 6.20 percent
Press any key to continue . . .