Series of Exrcises 2: Tutorial & Lab Session

LICENSE 2 IN COMPUTER SCIENCE 2020/2021
A lgorithmique et S tructures de Données 3

SERIES of EXRCISES 2
Tutorial & Lab session: Computational complexity, sorting algorithms
101010101010101010101010101010101010101010101010101010101010101010101010101010101010
EXERCISE 1: (TUTO)
f)
Give the complexity class in Big O notation for each of int sum = 0;
the following code fragments, It is asked to do an exact for (int i = 1; i <= N; i++) {
for (int j = 1; j <= 100; j++) {
calculation such as O (2N3 + 4N + 14) before deducing sum++;}}
the answer. ‫أحسب التعقيد الخوارزمي مع التبرير‬ for (int k = 1; k <= 10000; k++) {
a) sum++;}
int sum = 0; cout << sum << endl;
for (int i = 1; i <= N + 2; i++) { h)
sum++; int sum = 0;
} for (int i = 0; i < N * 2; i++) {
for (int j = 1; j <= N * 2; j++) { for (int j = 0; j < 100; j++) {
sum += 5;} for (int k = 0; k < j*j*j; k++) {
cout << sum << endl; sum++;}}}
b) cout << sum << endl;
int sum = 0; i)
for (int i = 1; i <= N - 5; i++) { int sum = 0;
for (int j = 1; j <= N - 5; j += 2) { for (int i = 0; i < N * 2; i++) {
sum++;}} for (int j = 0; j < i/2; j++) {
cout << sum << endl; for (int k = 0; k < N*N; k++) {
c) sum++;}}}
int sum = N; cout << sum << endl;
for (int i = 0; i < 1000000; i++) { j)
for (int j = 1; j <= i; j++) { int count = 0;
sum += N;} for (int i = N; i > 0; i /= 2)
for (int j = 1; j <= i; j++) { for (int j = 0; j < i; j++)
sum += N;} count++;
for (int j = 1; j <= i; j++) {
sum += N;}}
cout << sum << endl; EXERCISE 2: (TUTO)
d)
The same question of the previous exercise for the
int sum = 0;
for (int i = 1; i <= N - 2; i++) { following recursive calls. ‫نفس السؤال السابق لحاالت التراجع اآلتية‬
for (int j = 1; j <= i + 4; j++) { a)
sum++;} int function1(int n)
sum++;} {
if (n <= 0)
for (int i = 1; i <= 100; i++) { return 1;
sum++;} else
cout << sum << endl; return 1 + function1(n-1);}
e) b)
int sum = 0; int function2(int n)
for (int i = 1; i <= N; i++) { { if (n <= 0)
for (int j = 1; j <= N * N; j++) { return 1;
sum++; else
} return 1 + function2(n-5);}
for (int j = 1; j <= 100; j++) { c)
sum++; int function3(int n)
} { if (n <= 0)
for (int j = 1; j <= N; j++) { return 1;
sum++;} else
sum++;} return 1 + function3(n/5);}
cout << sum << endl;
Raouf O. Lakehal Ayat

d) void insertion_sort(int *arr,int size)
int function4(int n) { int current;
{ for(int i=0; i<n; i++)
{ function4(n-1);} for (int i=1;i<size;i++)
} {current=arr[i];int j=i;
e) while(arr[j-1]>current && j>0)
int function5(int n)
{ for (int i = 0; i < n; i += 2) { {arr[j]=arr[j-1];j--;}
// operation } arr[j]=current;
if (n <= 0) }
return 1;
else }
return 1 + function5(n-5);} main()
f)
{ int size= ;int arr[100];
void function6(int a, int b, int c)
{ if (a <= 0) for(int i=0;i<size;i++)
{cout<<"func6:"<<b<<c<<endl;} arr[i] = rand()%1000;
else
//bubble_sort(arr,size);
{ function6(a-1, b+1, c);
Function6(a-1, b, c+1); //selection_sort(arr,size);
} } //insertion_sort(arr,size);
EXERCISE 1: (LAB) cout<<"\n sorting algorithm: "<<endl;
for(int i=0;i<size;i++) cout<<arr[i]<<" ";
Write on your IDE the recursive functions of exercise 2
}
then:
- Write a main function which calls these functions rand () is a function of <cstdlib> to generate a random
- Compile each function several times by modifying number, with rand()%1000 the bounds are [0.1000].
the value of the parameters and note the difference in 1. For the same parameter, call each function
execution time by referring to the time displayed on separately and note the execution time by referring to
the console. ‫أكتب دوال التمرين السابق حيث يتم استدعاؤها في دالة‬ the time displayed on the console.
‫رئيسية ثم يتم تجريب قيم مختلفة ومالحظة الفروقات في وقت التنفيذ‬
2. Change the parameter several times and make your
EXERCISE 2: (LAB)
conclusions.
You have to type on your IDE the 3 quadratic time
3. Use the quicksort function below and compare the
sorting algorithms seen in the course:
runtime results with the previous sorts.
‫أكتب الدوال التالية الخاصة بخوارزميات الفرز البسيطة مع الدالة الرئيسية ونفذ كل‬
‫استدع هذه املرة دالة الفرز السريع التالية في دالة رئيسية وقارن زمن التنفيذ مع ما سبق‬
‫دالة بشكل منفرد عدة مرات وبإعدادات مختلفة مع تسجيل وقت التنفيذ لكل واحدة‬
.‫منها ثم تتم مقارنة النتائج بين دالة وأخرى‬
void bubble_sort(int *arr,int size)
{ int temp;
for(int i=size-1; i>0 ; i--)
for( int j=1;j<=i;j++)
{if(arr[j-1]>arr[j])
{ temp=arr[j-1];arr[j-1]=arr[j];
arr[j]=temp;}
}
}
void selection_sort(int *arr,int size)
{ int temp,i,min; HOME WORK :
for(i=0; i<size; i++) 1. Write a C++ function that displays the tringle of stars
{min=i; for(int j=i+1;j<size;j++) below on console:
if(arr[j]<arr[min]) min=j; *
***
if(min!=i) *****
{temp=arr[i];arr[i]=arr[min];arr[min]=temp; *******
} *********
***********
}
2. Rewrite your solution by using recursion.
}
3. Calculate big O complexity for each.
Raouf O. Lakehal Ayat

Series of Exrcises 2: Tutorial & Lab Session

Uploaded by

Copyright:

Available Formats

Series of Exrcises 2: Tutorial & Lab Session

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Series of Exrcises 2: Tutorial & Lab Session

Uploaded by

Copyright:

Available Formats

LICENSE 2 IN COMPUTER SCIENCE 2020/2021

A lgorithmique et S tructures de Données 3

Raouf O. Lakehal Ayat

Raouf O. Lakehal Ayat

You might also like