Algorithms PDF

# علوم الحاسب ## الفرقة الثانية ### Session 2 ## هياكل البيانات ### Data Structures Computer Science Department ## Q.1. What is an algorithm, give some examples for problems can solved by algorithms? A sequence of instructions for solving a problem, for obtaining a required output for any input i...

# علوم الحاسب ## الفرقة الثانية ### Session 2 ## هياكل البيانات ### Data Structures Computer Science Department ## Q.1. What is an algorithm, give some examples for problems can solved by algorithms? A sequence of instructions for solving a problem, for obtaining a required output for any input in a finite amount of time. Input → Sequence of computation → Output ### Examples - Sorting. - Searching. ## Q.2. What are the criteria used to measure the performance of an algorithm? ### 1) Time complexity: - Time complexity: is a function of the running time of the algorithm. - Time efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input size. - Basic operation: the operation that contributes the most towards the running time of the algorithm. | Problem | Input size measure | Basic operation | |:---|:---|:---| | Searching for key in a list of n items | Number of list's items, i.e. n | Key comparison | | Multiplication of two matrices | Matrix dimensions or total number of elements | Multiplication of two numbers | Running time $T(n) = C_0 + C_1(n)$ **where:** * Input size = n * Execution time for basic operation or cost = $C_0$ * Number of times basic operation is executed = $C_1(n)$ - Worst case: $C_{worst}(n)$ - maximum over inputs of size n. - Best case: $C_{best}(n)$ - minimum over inputs of size n. - Average case: $C_{avg}(n)$ - "average" over inputs of size n. Using asymptotic notations, we can give time complexity as -fastest possiblell, -slowest possiblell or -average timell. Various notations: Ω, Θ, Ο Basic asymptotic efficiency classes: | Complexity | Class | |:---|:---| | 1 | constant | | $log n$ | logarithmic | | $N$ | linear | | $n log n$ | n-log-n | | $n^2$ | quadratic | | $n^3$ | cubic | | $2^n$ | exponential | | $n!$ | factorial | $O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)$ ### Space complexity Space complexity is a function of the space required by it to run to completion. ## Q.3. Write linear search algorithm and its C++ implementation. ### Algorithm for Linear search Linear_Search (A[ ], N, val, pos) - Step 1: Set pos = -1 and k = 0 - Step 2: Repeat while k < N - Begin - Step 3: if A[k] = val - Set pos = k - print pos - Goto step 5 - End while - Step 4: print - Value is not present|| - Step 5: Exit ### C++ Linear search implementation: ```c++ #include <iostream> #include <conio.h> using namespace std; int main() { int array[100], search, c, n; cout << "Enter number of elements in array\n"; cin >> n; cout << "Enter integer(s)\n"; for (c = 0; c < n; c++) cin >> array[c]; cout << "Enter a number to search\n"; cin >> search; for (c = 0; c < n; c++) { if (array[c] == search) { cout << search << " is present at location " << c + 1; break; } } if (c == n) cout << search << " isn't present in the array.\n"; _getch(); } ``` ## Q.4. What is binary search, write C++ implementation. **If searching for 23 in the 10-element array:** 2 5 8 12 16 23 38 56 72 91 **L** **H** 23 > 16, take 2nd half 2 5 8 12 16 23 38 56 72 91 **L** **H** 23 < 56, take 1st half 2 5 8 12 16 23 38 56 72 91 **L** **H** **Found 23, Return 5** - Binary search run-time complexity of $O(log n)$. - Binary search algorithm works on the principle of divide and conquer. - Binary search looks for a particular item by comparing the middle most item of the collection. - Before applying binary searching, the list of items should be sorted. ```c++ #include <iostream> #include <conio.h> using namespace std; int main() { int c, first, last, middle, n, search, array[100]; cout << "Enter number of elements\n"; cin >> n; cout << "Enter numbers \n"; for (c = 0; c < n; c++) cin >> array[c]; cout << "Enter value to find: \n"; cin >> search; first = 0; last = n - 1; middle = (first + last) / 2; while (first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) { cout << search << " found at location" << middle + 1 << endl; break; } else last = middle - 1; middle = (first + last) / 2; } if (first > last) cout << "Not found!" << search << " isn't present in the list.\n"; _getch(); } ``` ## Q.5. Write bubble sort algorithm and its implementation. - "Bubble" the largest value to the end using pair-wise comparisons and swapping. - Move from the front to the end. | Index | Iteration 1 | Iteration 2 | Iteration 3 | Iteration 4 | Iteration 5 | Iteration 6 | |:---|:---|:---|:---|:---|:---|:---| | 0 | 18 | 18 | 18 | 18 | 18 | 18 | | 1 | 32 | 32 | -11 | -11 | -11 | -11 | | 2 | -11 | -11 | 32 | 6 | 6 | 6 | | 3 | 6 | 6 | 6 | 32 | 32 | 32 | | 4 | 68 | 68 | 68 | 68 | 68 | 2 | | 5 | 2 | 2 | 2 | 2 | 2 | -34 | | 6 | -34 | -34 | -34 | -34 | -34 | 68 | ### ALGORITHM: Bubble_Sort (A[],N) - Step 1: Start - Step 2: Take an array of n elements - Step 3: for i=0,.............n-2 - Step 4: for j=i+1,.......n-1 - Step 5: if arr[j]>arr[j+1] then - Interchange arr[j] and arr[j+1] - End of if - Step 6: Print the sorted array arr - Step 7: Stop ### Implementation in C++ ```c++ #include <iostream> #include <conio.h> using namespace std; int main() { int array[100]; int i, j, num, temp; cout << "Enter the value of num \n"; cin >> num; cout << "Enter the elements one by one \n"; for (i = 0; i < num; i++) { cin >> array[i]; } /* Bubble sorting begins */ for (i = 0; i < num; i++) { for (j = 0; j < (num - i - 1); j++) { if (array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } cout << "Sorted array is...\n"; for (i = 0; i < num; i++) { cout << array[i] << "\n"; } _getch(); } ``` ## Q.6. Write selection sort algorithm and its implementation. | Iteration | Array | Output | |:---|:---|:---| | 1 | 29 72 98 13 87 66 52 51 36 | 13 is smallest | | 2 | 13 72 98 29 87 66 52 51 36 | 29 is smallest | | 3 | 13 29 98 72 87 66 52 51 36 | 36 is smallest | | 4 | 13 29 36 72 87 66 52 51 98 | 51 is smallest | | 5 | 13 29 36 51 87 66 52 72 98 | 52 is smallest | | 6 | 13 29 36 51 52 66 87 72 98 | 66 is smallest | | 7 | 13 29 36 51 52 66 87 72 98 | 72 is smallest | | 8 | 13 29 36 51 52 66 72 87 98 | 87 is smallest | | 9 | 13 29 36 51 52 66 72 87 98 | sorting completed | ### C++ implementation ```C++ void selectionSort(int arr[], int size) { int i,j; for (i = 0; i < size; i++) { for (j = i; j < size; j++) { if (arr[i] > arr[j]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } ``` ## Q.7. Write insertion sort algorithm and its implementation. | Iteration | Array | |:---|:---| | 1 | 9 7 6 15 17 5 10 11 | | 2 | 7 9 6 15 17 5 10 11 | | 3 | 6 7 9 15 17 5 10 11 | | 4 | 6 7 9 15 17 5 10 11 | | 5 | 5 6 7 9 15 17 10 11 | | 6 | 5 6 7 9 10 15 17 11 | | 7 | 5 6 7 9 10 11 15 17 | ### C++ implementation ```C++ void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } ```