10. Program to display a set of values { fij } as a rectangular mesh.

Description:

A polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling. The faces usually consist of triangles (triangle mesh), quadrilaterals, or other simple convex polygons, since this simplifies rendering, but may also be composed of more general concave polygons, or polygons with holes. The study of polygon meshes is a large sub-field of computer graphics and geometric modeling. Different representations of polygon meshes are used for different applications and goals. As polygonal meshes are extensively used in computer graphics, algorithms also exist for collision detection, and rigid-body dynamics of polygon meshes. The objective of this program is to develop a polygonal mesh using a set of values.

Program:

#include<stdio.h>

#include<GL/glut.h>

#define dx 15

#define dy 10

GLfloat x[100],y[100];

GLfloat x0=50, y0=50; //initial values for x,y

GLint i,j;

int maxx,maxy;

void display(void)

{

            glClearColor(1.0,1.0,1.0,1.0);

            glClear(GL_COLOR_BUFFER_BIT);

            glMatrixMode(GL_PROJECTION);

            glLoadIdentity();

            gluOrtho2D(0.0,499.0,0.0,499.0);

            glMatrixMode(GL_MODELVIEW);

            glLoadIdentity();

            for(i=0;i<=maxy;i++)

                        x[i]=x0+i*dx; //Compute x[i]

            for(j=0;j<=maxx;j++)

                        y[j]=y0+j*dy; //compute y[i]

            glColor3f(0.0,0.0,1.0);

            for(i=0;i<maxy;i++)

                        for(j=0;j<maxx;j++)

                        {

                                    glColor3f(0.0,0.0,1.0);

                                    glBegin(GL_LINE_LOOP);

                                    glVertex2f(x[i],y[j]);

                                    glVertex2f(x[i],y[j+1]);

                                    glVertex2f(x[i+1],y[j+1]);

                                    glVertex2f(x[i+1],y[j]);

                                    glEnd();

                        }

                        glFlush();

}

void main(int argc, char **argv)

{

            printf("Enter rows & Columns\n");

            scanf("%d%d",&maxx,&maxy);

            glutInit(&argc,argv);

            glutInitWindowPosition(10,10);

            glutInitWindowSize(500,500);

            glutCreateWindow("Rectangular Mesh");

            glutDisplayFunc(display);

            glutMainLoop();

}

Output 1:

sahyadrids1@sahyadrids1-Veriton-Series:~/cg_16$ ./mesh

Enter rows & Columns

10 11

Output 2:

sahyadrids1@sahyadrids1-Veriton-Series:~/cg_16$ ./mesh

Enter rows & Columns

25 20

PREFACE

        An algorithm is a sequence of unambiguous instructions for solving a computational problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.

Donald E. Knuth stated “Computer Science is the study of algorithms”. Programs will not exist without algorithms. They are the cornerstone of computer science.

Why to study this Course?

¢  Closely related to our lives

¢  Help to guide how others analyze and solve problems

¢  Help to develop the ability of analyzing and  solving problems via computers

¢  Very interesting if you can concentrate on this subject

Subject Prerequisite:

¢  Data Structure

¢  Discrete Mathematics

¢  C, C++, Java or other programming languages

¢  Advanced Mathematics

Algorithm: A brief History

¢  Muhammad ibn Musa al-Khwarizmi, one of the most influential mathematicians in 9th century in Baghdad, wrote a textbook in Arabic about adding, multiplying, dividing numbers, and extracting square roots and computing π.

¢  Many centuries later, decimal system was adopted in Europe, and the procedures in Al Khwarizmi’s book were named after him as “Algorithms”.

Expected Outcomes

¢  Student should be able to

—  Define algorithm formally and informally.

—  Explain the idea of different algorithms for the same problem

—  Describe the process of algorithm design and analysis

                                                                        Mehanaz Begum                                   

Lab program 1 - Sort a given set of elements using Quick sort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from the file or can be generated using the random number generator.

Description:

Quicksort is a very efficient sorting algorithm invented by C.A.R. Hoare. It has two phases:

• The partition phase and
• The sort phase.

As we will see, most of the work is done in the partition phase. The sort phase simply sorts the two smaller problems that are generated in the partition phase.

This makes Quicksort a good example of the divide and conquer strategy for solving problems. In quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions, ie we divide the problem into two smaller ones and conquer by solving the smaller ones. 

Algorithm

1.     Pick an element, called a pivot, from the array.

2.     Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

3.     Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Solution:

#include<stdio.h>

#include<time.h>

#include<stdlib.h>

int partition(int a[],int low,int high)

{

             int i,j,key,temp,true=1;

             key=a[low];

            i=low+1;                                                                                                                                           

            j=high;

            while(true)

            {

                        while((key>=a[i])&&(i<high))

                                     i=i+1;

                        while(key<a[j])

                                     j=j-1;

                         if(i<j)

                        {

                                    temp=a[i];

                                    a[i]=a[j];

                                    a[j]=temp;

                         }

                        else

                                    true=0;

                        }

            temp=a[low];

             a[low]=a[j];

             a[j]=temp;

            return j;

}

void quicksort(int a[],int low,int high)

{

            int pos;

             if(low<high)

            {

                          pos=partition(a,low,high);

                         quicksort(a,low,pos-1);

                        quicksort(a,pos+1,high);

            }

}

void main()

{

            clock_t n1,n2,n3;

             double n4;

            int a[2000],n,i,low,high,choice,num;

            FILE *fp;

            char f_name[10];

            label:printf("\nEnter your choice :\nPress 1 to read numbers from file\n

            Press 2 to generate random numbers\nPress 3 to take the numbers from keyboard\n");

            scanf("%d",&choice);

            switch(choice)

            {

                         case 1: printf("Enter the filename:");

                                     scanf("%s",f_name);

                                     fp=fopen(f_name,"r");

                                     if(fp==NULL)

                                    {

                                                 printf("Error!! File not found");

                                                goto label;

                                    }

                                    i=0;

                                    while(fscanf(fp,"%d",&num)!=EOF)

                                    {

                                                 a[i]=num;

                                                 i++;

                                    }

                                    n=i;

                                    break;

                        case 2: printf("Enter the number of elements\n");

                                    scanf("%d",&n);

                                   

for(i=0;i<n;i++)

                                     {

                                                 a[i]=rand()%100;

                                    }

                                    break;

                        case 3: printf("Enter the number of elements\n");

                                    scanf("%d",&n);

                                    printf("Enter those elements \t");

                                    for(i=0;i<n;i++)

                                    {

                                                 scanf("%d",&a[i]);

                                    }

                                    break;

                         default:exit(0);

            }

            printf("\nThe unsorted array is:");

            for(i=0;i<n;i++)

            printf("\t%d",a[i]);

            n1=clock();

            for(i=0;i<10000;i++)

                        quicksort(a,0,n-1);

            n2=clock();

            n3=n2-n1;

            n4=n3/CLOCKS_PER_SEC;

            printf("\nThe sorted array is:\n");

            for(i=0;i<n;i++)

                        printf("\t%d",a[i]);

            printf("\nTime in microseconds is %f",n4*1000000/10000);

            printf("\nCPU time is %d",n3/10000);

}

OUTPUT 1 :

Enter your choice :

Press 1 to read numbers from file

Press 2 to generate random numbers

Press 3 to take the numbers from keyboard

1

Enter the filename:quick.txt

The unsorted array is:  23        45        65        23        12        343      54        43        0          0          0          0          0            0          0          0          0          1          1          11        1          2          2          2          2          2          2          2            33        3          3          3          3          3          3          4          4          4          4          4          4          44        4            4          4          4          4          4          5          55        5          5          5          5          5          5          5          5            5          5          5          6          6          66        6          6          6          6          6

The sorted array is:

            0          0          0          0          0          0          0          0          0          1          1          1          1          1          2            2          2          2          2          2          2          33        3          3          3          3          4          4          4          4            4          4          4          4          4          4          4          4          4          4          5          5          5          55        5            5          5          5          5          5          5          6          6          6          6          6          6          6          6          6            12        23        23        33        43        45        54        55        65        343

Time in microseconds is 0.000000

CPU time is 0

OUTPUT 2 :

Enter your choice :

Press 1 to read numbers from file

Press 2 to generate random numbers

Press 3 to take the numbers from keyboard

2

Enter the number of elements

20

The unsorted array is:

            83        86        77        15        93        35        86        92        49        21        62        27        90        59        63            26        40        26        72        36

The sorted array is:

            15        21        26        26        27        35        36        40        49        59        62        63        72        77        83            86        86        90        92        93

Time in microseconds is 0.000000

CPU time is 0

 OUTPUT 3 :

Enter your choice :

Press 1 to read numbers from file

Press 2 to generate random numbers

Press 3 to take the numbers from keyboard

3

Enter the number of elements

10

6 2 78 23 45 21 73 38 40 64

The unsorted array is: 

            6          2          78        23        45        21        73        38        40        64

The sorted array is:

            2          6          21        23        38        40        45        64        73        78

Time in microseconds is 0.000000

CPU time is 0

Lab program 2: Using OpenMP, implement a parallelized merge sort algorithm to sort a given set of elements and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

Description:

Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.

Algorithm

To sort A[p .. r]:

1. Divide Step

If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted. 

Solution:

#include<stdio.h>

#include<omp.h>

#include<stdlib.h>

void mergesort(int a[],int n);

void merge(int a[],int b[],int c[],int,int);

void main()

{

          int n,i,a[1000],choice,num;

          double  start_time,end_time;

          FILE *fp;

          char f_name[10];

          label:printf("\nEnter your choice :\nPress 1 to read numbers from file\nPress 2 to generate                            random numbers\nPress 3 to take numbers from keyboard \nPress 4 to exit");

         scanf("%d",&choice);

        

         switch(choice)

         {

             case 1:printf("Enter the filename:");

                        fflush(stdin);

                        gets(f_name);

                                fp=fopen(f_name,"r");

                        if(fp==NULL)

                       {

                            printf("Error!! File not found");

                            goto label;

                       }

                       i=0;

                       while(fscanf(fp,"%d",&num)!=EOF)

                       {

                               a[i]=num;

                               i++;

                       }

                       n=i;

                       break;

            case 2:printf("Enter the number of elements\n");

                       scanf("%d",&n);

           

                         for(i=0;i<n;i++)

                         {

                              a[i]=rand()%100;

                          }

                          break;

             case 3: printf("Enter the number of elements\n");

                          scanf("%d",&n);

                          printf("\nEnter %d elements:",n);

                          for(i=0;i<n;i++)

                                 scanf("%d",&a[i]);

                           break;

    

               default:exit(0);

          }

          printf("\nThe unsorted array is:");

          for(i=0;i<n;i++)

                printf("\t%d",a[i]);

          omp_set_num_threads(5);

          start_time=omp_get_wtime();

          mergesort(a,n);

          end_time=omp_get_wtime();

          printf("\n The sorted array is :");

          for(i=0;i<n;i++)

                printf("\t%d",a[i]);

           printf("\nTime taken=%.2f\n",end_time-start_time);

}

void mergesort(int a[],int n)

{

           int b[1000],c[1000],i,j=0;

           if(n>1)

          {

                   for(i=0;i<n/2;i++)

                         b[i]=a[i];

                  for(i=n/2;i<n;i++)

                  {

                    c[j]=a[i];

                     j++;

                  }

              #pragma omp parallel

              mergesort(b,n/2);

              #pragma omp parallel

              mergesort(c,j);

              #pragma omp parallel

              merge(b,c,a,n/2,j);

        }

}

void merge(int b[],int c[],int a[],int p,int q)

{

          int i=0,j=0,k=0,x;

          while((i<p)&&(j<q))

         {

                 if(b[i]<=c[j])

                        a[k++]=b[i++];

                 else

                        a[k++]=c[j++];

         }

         if(i==p)

        {

                 #pragma omp parallel for

                                    for(x=j;x<q;x++)

                       a[k++]=c[x];

        }

        else

       {

                #pragma omp parallel for

                           for(x=i;x<p;x++)

                       a[k++]=b[x];

       }

}

OUTPUT 1 :

Enter your choice :

Press 1 to read numbers from file

Press 2 to generate random numbers

Press 3 to take numbers from keyboard

Press 4 to exit

2

Enter the number of elements

100

The unsorted array is:  83        86        77        15        93        35        86        92        49        21        62        27        90            59        63        26        40        26        72        36        11        68        67        29        82        30        62        23            67        35        29        2          22        58        69        67        93        56        11        42        29        73        21            19        84        37        98        24        15        70        13        26        91        80        56        73        62        70            96        81        5          25        84        27        36        5          46        29        13        57        24        95        82            45        14        67        34        64        43        50        87        8          76        78        88        84        3          51            54        99        32        60        76        68        39        12        26        86        94        39

 The sorted array is :    2          3          5          5          8          11        11        12        13        13        14        15        15            19        21        21        22        23        24        24        25        26        26        26        26        27        27        29            29        29        29        30        32        34        35        35        36        36        37        39        39        40        42            43        45        46        49        50        51        54        56        56        57        58        59        60        62        62            62        63        64        67        67        67        67        68        68        69        70        70        72        73        73            76        76        77        78        80        81        82        82        83        84        84        84        86        86        86            87        88        90        91        92        93        93        94        95        96        98        99

Time taken=0.00