c++ problem

[aamir55]

i have to write this as follow
but when i run my programm it shows lot of errors
so someone can tell me what is the problem and how to solve it
and how to do extra coding as asked me in below
so i m new in c++
see the attachment also



Goal
We have discussed two algorithms for computing the 2-d maxima of a set of points in the x-y plane. One is the brute force algorithm which runs in O(n2) time and the other is sweep line which runs in O(n log n) time. Your task is code the sweepline algorithms in C++, run the two algorithms on input of xy points of varying size, determine the actual CPU time used and compare the times obtained.

Files Provided
• 2DMaxima.dev
This is the Dev-Cpp project file. It has appropriate settings in the project options that are needed to access the cpu timing routines. Load the project in Dev-Cpp and open the "Project Option" dialog. You will see an entry "C:\WINDOWS\system32\ibmts.lib" in the "General" tab in "Linker Options" and "C:\WINDOWS\system32" in "Files/Directories" tab "Include Directories".
• 2dm.cpp
This is only C++ source file in the project. The source does not make use of any C++ classes. It is actually a C source file. It uses the "printf" routine for printing of data instead of cout. You can get information on "printf" on the web or in any good book on C or C++.
The file contains most of the code already written for the assignment. Here is what the code does:
1. Setup global variable and arrays which are used by various functions. This avoids the need to pass parameters around.
2. The main routine picks up the value of n from the command line.
3. The routine generates a random set of "n" xy data points by calling a random number generator.
4. The main routine starts the CPU timer and calls the brute force routine to compute the maximal set for the given xy data points. Upon return, the main routine stops the timer and gets the actual CPU time used in seconds and microseconds. These two are then printed.
5. The main routine repeats the same for the sweep line algorithm.
The body of the sweep line function is empty. Your task is to write the sweep line routine using the algorithm discussed in the lecture. The sweep line algorithm sorts the xy data and then uses a stack to determine the maximal set. The stack ADT is available from data structures. Use the array implementation of the stack. In case the internal array is too small, increase the maximum size. You will need to add code for some suitable O(n log n) sorting algorithm. We have discussed merge sort and quick sort in the data structures course.
• ibmtsinst.exe
This file contains the installer for the CPU timing routines. The files in the package are installed in the directory "C:\WINDOWS\System32". Please install these on your machine by double clicking on the .exe file. The two files needed by the project are "ibmts.h" and "ibmts.lib".

Tasks to perform
Once you have the sweep line function working properly, run the program for various values of n. Fill up the following table from your timing analysis:
N Brute Force Sweep Line Ratio:
brute/sweepline
seconds microseconds seconds microseconds
50
250
500
1000
2000
5000
10,000
25,000
50,000

What to turn in
Turn in your DevCpp project: the .dev file and all .cpp and .h files. We will build the .exe and run it to see if it works correctly. Write a one page report that has the table or runtimes filled out with the CPU times you have obtained.

To run at command prompt
C:\> 2DMaxima.exe [input Size]

[Peter_APIIT]

What is your problem ?

[Odiee]

There is no problem, This is a sceleton project file all of the algorithms are written and there is accctually one function like this:

void sweepLine( int n )
{
  // ** STUDENT will add the code
}

One would think that a person with 109 posts would know the policy of homeworks here. But don't loose hope, read this:
http://www.codeguru.com/forum/showthread.php?t=366302

[Peter_APIIT]

Student nowadays lack of trying and debugging skills.

[aamir55]

kindly tell me how to remove those errors??

[aamir55]

i m getting errors in both .ccp and .h file when i debug
so i need to correct them
after that i will write sweep line function

[TheCPUWizard]

kindly tell me how to remove those errors??

Just follow the instructions given in Reply #3....

[aamir55]

hi
i have writen a stak class as follow

#include <iostream.h>

/* The Stack class */

class  Stack 
{
    public:
        int pop(){ return A[current--];}    	// The pop function    
        void push(int x){A[++current] = x;} // The push function
        int top(){ return A[current];}      	// The top function
        int notEmpty(){return ( current == -1 );} // Will return true when stack is empty
        

     private:
       
       int   current; 				// Index of the array
       int A[];
};

and i have written sweep line function as

void sweepLine( int n )
{
  // ** STUDENT will add the code
Stack s;
int i;
int y;

for(i=1;i<n;i++)
{
y=P[i];
while(s.notEmpty()&& s.top()<=y)
{
s.pop();
s.push(P[i]);
}
}
}

but it is giving errors

Pseudo code of sweep line algorithm as follow

Plan-Sweep(int n,P[i...n]
sort P in increasing order by x;
stack s;
for i<-1 to n
do
while(s.notEmpty()& s.top().y<=p[i].y)
do s.pop();
s.push(P[i]);
output the contents of stack s;

any body can help me

thanks

[TheCPUWizard]

1) Please start a new thread for a new problem.
2) You should always post (minimal yet) complete code.
3) You should always post the EXACT compiler errors
4) It is beneficial to highlight the exact line where the error is being flagged.

Posting the code in a zip file takes significantly more time for every single person who wants to help. This is nefficient (and somewhat rude) compared to the one person (who is asking for the help) spending a few extra minutes on the post to make it easier to provide assistance.

[aamir55]

i have done it no error is comming
but i want to modify it as follow
on the consol, i have to take a number lets say n and we have to enter its value
this value should be less than 100000
after taking input from user ,it can show computational time for brute force and sweep line algorithm in seconds and microseconds
after this, it can compute ratio=brute force computational time/sweep line computational time
i have written whole code as follow

// program to compute 2d-maxima for a set of xy points. The xy data points
// are generated using a random number generator. The command to run the program
// at DOS prompt is:
//
//   - compute 2d-maxima for 500 xy points 
//     .\2dmaxima 500
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include "ibmts.h" //#include <ibmts.h>
#include <time.h>
#include "Stack.h"

// we will handle a maximum of MAXPOINTS xy data points
#define MAXPOINTS 100000
int x[MAXPOINTS], y[MAXPOINTS];
int P[MAXPOINTS];
// the 2d maximal points will be placed in the following two arrays by the 
// algorithm used.
int xm[MAXPOINTS], ym[MAXPOINTS];
// the actual count of xy points that form the maximal set.
int numberOfMaximalPoints; 

// Example from the notes
int xn[] = {2,4, 4,5,7,7, 9,11,12,13,14,15};
int yn[] = {5,11,4,1,7,13,10,5,12, 3,10, 7};
int notesN = 12;
//int RAND_MAX;
// The main driver
int main(int argc, char *argv[])
{
   void genXY(int);
   void sweepLine(int);
   void bruteForce(int);
   bool useSweepline = true;
   bool doNotesExample = false;
   unsigned int t1sec, t1usec, t2sec, t2usec, elapsedsec, elapsedusec,B_elapsedsec,S_elapsedsec,ratio;

   // parse the command line for number of data points to handle and
   // which algorithm to use: brute force or sweepline.
   int n = 25; // default number of x,y points
   if( argc > 1 )
   {
     n = atoi( argv[1] );
     printf("n specified as %s, converted to int %d.\n", argv[1], n);
   }
   if( n <= 0 ) n = 25;
   
   // the command line 
   //    .\2dMaxima 100 notes
   // will cause the program to the xy data used in the example in the lecture
   if( argc > 2 ) doNotesExample = true;

   if( !doNotesExample )
   {
     // generate the xy data points
     printf("Generating %d points.\n", n );
     genXY( n );
   }
   else
   {
     for(int i=0; i < n; i++ )
     {
       x[i] = xn[i]; y[i] = yn[i];
     }
     n = notesN;
     printf("Using xy data from example in the notes; n=%d points.\n", n );
   }
          
   //** BRUTE FORCE
   printf("Computing maximal set of points using brute-force.\n" );
   ibmts_calcTimeStamp(&t1sec, &t1usec ); // start time
     bruteForce( n );
   ibmts_calcTimeStamp(&t2sec, &t2usec ); // end time
   
   elapsedsec=t2sec-t1sec;
    B_elapsedsec=elapsedsec;
   elapsedusec=t2usec-t1usec; 
  
   printf("bruteforce: %d data points, %d points in maximal set.\n",
            n, numberOfMaximalPoints );
   printf("  elapsed time: %u seconds, %u microseconds\n", 
              elapsedsec, elapsedusec );

   if( doNotesExample )
   {
     printf("bruteforce: points in maximal set:\n\tx[i]\ty[i]\n");
     for(int j = 0; j < numberOfMaximalPoints; j++ )
       printf("\t%d\t%d\n", xm[j], ym[j] );
   }   

   // ** SWEEPLINE
   printf("Computing maximal set of points using sweepline.\n" );
   ibmts_calcTimeStamp(&t1sec, &t1usec ); // start time
     sweepLine( n );
   ibmts_calcTimeStamp(&t2sec, &t2usec ); // end time
sweepLine( n );
   if( doNotesExample )
   {
     printf("sweepline: points in maximal set:\n\tx[i]\ty[i]\n");
     for(int j = 0; j < numberOfMaximalPoints; j++ )
       printf("\t%d\t%d\n", xm[j], ym[j] );
   }   

   elapsedsec=t2sec-t1sec;
    S_elapsedsec=elapsedsec;
   elapsedusec=t2usec-t1usec; 
  
   printf("sweepline: %d data points, %d points in maximal set.\n",
            n, numberOfMaximalPoints );
   printf("  elapsed time: %u seconds, %u microseconds\n", 
              elapsedsec, elapsedusec );

   ratio=B_elapsedsec/ S_elapsedsec;
   printf("Ratio:%d ",ratio);
   system("PAUSE");
   return 0;
}

// The function genXY will generate 'n' xy data points and store them in
// the global x and y array. 'n' must be less than MAXPOINTS
void genXY(int n )
{
  int genRandom(int, int );

  if( n >= MAXPOINTS ) n = MAXPOINTS;
  
  // Seed the random number generator. The signature of 'srand' is
  //        srand(unsigned int seed)
  // A different seed will produce different set of random numbers.
  //
  srand(time(NULL));
   printf("generating %d x,y points.\n", n );
  
  // both x an y will be in the range 0-100.
   for(int i=0; i < n; i++ ) {
      x[i] = genRandom(0,150);
      y[i] = genRandom(0,150);
   } 
}

int genRandom(int low, int high )
{
    return (int)(low + (double)rand () * (high - low + 1) / RAND_MAX);
}

void sweepLine( int n )
{
  // ** STUDENT will add the code
Stack s;
int i;
int y;

for(i=1;i<n;i++)
{
y=P[i];
while(s.notEmpty()&& s.top()<=y)
{
s.pop();
s.push(P[i]);
}
}
}

void bruteForce( int n )
{
   int i, j;
   int k = 0;
   bool maximal;
   for(i=0; i < n; i++ )
   {
     maximal = true;
     for( j = 0; j < n; j++ )
     {
       if( i != j )
         if( x[i] <= x[j] && y[i] <= y[j] )
         {
           maximal = false;
           break;
         }
     }
     if( maximal )
     {
       xm[k] = x[i];  // we have a maximal point.
       ym[k] = y[i];
       k = k+1;
     }
   }
   numberOfMaximalPoints = k; // count of maximal points
}

i did some technique for computing ratio but when the program it gives error and terminates.
thanks