Report Title

Algorithms
Algorithmsand
andcomplexity
complexity

A report submitted to the

,Department of Electrical and Computer science
College of science
University of Duhok

Student name: Hussein Shamdeen Younus

Moodle Email: abualirekani@gmail.com
Year: 2nd
Course: Second
Course code: SC2205
Instructor: Saman A. Barakat
Date: 1/7/2020

1
 University of Duhok Subject: Algorithms & Complexity
College of Science Date: 16 / 06 / 2020
Dept.: Computer Science Deadline: 1 / 07 / 2020
Class: 2nd year Questions: 5

Final Assignment
Full Name: Hussein Shamdeen Younus Mark

Answer the following questions: -

(10 Marks)
Q1) Writer the iteration steps to sort the following numbers using Merge sort algorithm.

1 1 2 3 1
9 6 5 4 2
3 5 0 7

9 6 1 13 5 25 4 30 17 2

9 6 1 13 5 25 4 30 17 2

9 6 1 13 5 25 4 30 17 2

4 25 17 2
6 9 13 5

5 13 2 17

1 5 13 2 17 30

1 5 6 9 13 2 4 17 25 30
2

1 2 4 5 6 9 13 17 25 30

#include<iostream>
2
using namespace std ;

void merge ( int arr [] , int l , int m , int r ) //m=1+(r-1)/2;

{ int I , j , k ;
int n1 = m - l + 1 ; //First subarrey is arr[l..m]"4"
int n2 = r - m ; // Second subarrey is arr[m + 1 ... r ]
int *L = new int [n1], *R= new int [n2];

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

L[i] = arr [ l + I ] ;

for ( j = 0 ; j < n 2 ; j++ )

R[j] =arr [m+1+j];
i=j=0;
k=l;

while (i < n1 && j < n2)

{
if ( L [i] < = R [ j ] )
{
arr [k] = L [i];
I ++;
}
else
{
arr [k] = R[j];
j++;
}
k++ ;
}
While ( i < n1 )
{
arr [k] = L [i];
i++ ;
k++ ;}
While (j<n2)
{arr [ k ] = R [ j ] ;
j++ ;
k++ ;
}}
void mergesort ( int arr [] , int l , int r )
3
{
if (l < r)
{
int m = l + (r - l)/2;
mergesort ( arr , l , m ) ;
mergesort ( arr, m + 1 , r ) ;
merge ( arr , l , m , r ) ;
}
}
void print ( int arr [] , int n )
{
for (int i =0; i < n ; i++ )
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main () {
int arr [] = { 9 , 6 , 1 , 13 , 5 , 25 , 4 , 30 , 17 , 2 } ;

int n = sizeof (arr) / sizeof ( arr [0]);

mergesort (arr, 0, n-1);

print ( arr , n);

system("pause");
}

4
 (10 Marks)
Q2) Writer a full program for Shell sort algorithm.
#include <iostream>
using namespace std;
/* function to sort arr using shellSort */
int shellSort(int arr[], int n)
{ // Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2)
{ // Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is
// gap sorted
for (int i = gap; i < n; i += 1) {
// add a[i] to the elements that have been gap sorted
// save a[i] in temp and make a hole at position i
int temp = arr[i];
// shift earlier gap-sorted elements up until the correct
// location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];

// put temp (the original a[i]) in its correct location

arr[j] = temp;
} }
return 0;
}
void printArray(int arr[], int n)
{ for (int i=0; i<n; i++)
cout << arr[i] << " ";
}
int main()
{ int arr[] = {12, 34, 54, 2, 3}, i;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Array before sorting: \n"<<endl;
printArray(arr, n);
cout<<endl;shellSort(arr, n);
cout << "\nArray after sorting: \n"<<endl;
printArray(arr, n);
cout<<endl;
system("pause");}
Output:
Array before sorting:
12 34 54 2 3
Array after sorting:
2 3 12 34 54

5
 (10 Marks)
Q3) Consider the following binary tree then answer the following questions: -
1- What is the pre order traversal? ----------- 1->2->4->8->5->9->3->6->10->7->11
2- What is the degree of the tree? ------------ 2
3- What is the height of node 2? ------------ 2
4- What are the descendants of node 3? --- 6 – 7 – 10 - 11
5- What are the ancestors of node 5? ------ 2 , 1

2 3

4 5 6 7

1 1
8 9
0 1

6
 (10 Marks)
Q4) Answer the following questions: -
1- What is a Full Binary Tree then give an example that contains the maximum number of nodes?
What is a Complete Binary Tree then give an example that contain the minimum number of nodes in a -2
?complete binary tree
?What is the Perfect Binary Tree then give an example -3

-:Solution
A full binary tree (sometimes proper binary tree) is a tree in which every node other than the leaves has 
.two children

The maximum number of nodes in a binary tree of height h is 2h+1-1, k>=0. (Ex: 24 –1 = 15) 

.The maximum number of nodes in a full binary tree of height h is 2h+1-1 

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, 
.and all nodes are as far left as possible

.The minimum number of nodes in a complete binary tree of height h is 2h 

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children 
.and all leaves are at the same level

7
 (10 Marks)
Q5) What is binary search tree then give an example: - in a binary search tree we have operations that us
to locate or print content of the tree (all nodes)
1-per-order traversal.
2- in-order traversal.
3- post-order traversal.

#include<iostream>
using namespace std;
int binarySearch ( int arr [ ] , int l , int h , int element )
{
while ( l <= h ) {
int m = ( l + h ) / 2 ; //both => m (2 l + r - 1) /
if ( arr [ m ] == element )
return m ;
if ( arr [ m ] > element )
h=m-1;
else
l=m+1;
}
return -1 ;
}
int main ( )
{
int arr [ ] = { 2 , 3 , 4 , 10 , 40 } ;
int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ;
int num ;
cout << " Enter an Integer : " ;
cin >> num ;
int result = binarySearch ( arr , 0 , n - 1 , num ) ;
if ( result == -1 )
cout << " The Number : ( " << num << " ) Was Not Found : " <<endl ;
else
cout << " The Number : ( " << arr [ result ] << " ) Was Found At Index : (" << result <<endl ;

system ( " pause ") ;

}

8
REFERENCES
[1] Reference 1 https://www.geeksforgeeks.org/shellsort/
[2] Reference 2 https://www.geeksforgeeks.org/binary-search-tree-data-structure/