NJIBARA UNIVERSITY
CollegeofEngineering and Technology
Department of InformationTechnology
DATA STRACTURE AND ALGORITHIM GROUP ASSIGNMENT
Group ......1
Students Name. Id
[Link]...........................1500630
[Link]....................................1501190
3.G/meskelAyelign..........................1500829
[Link]..........................1500659
[Link]............................1500915
[Link] ..........................1500573
Submitted To Agerie.B
Submissiondat:20/08/2017
Injibara, Ethiopia
1. Given an array of integers, write a C++ program to find the second largest element using linear
search
#include <iostream>
using namespace std;
int main() {
int arr[] = {10, 45, 67, 89, 34, 89, 23};
int n = sizeof(arr) / sizeof(arr[0]);
int first = INT_MIN, second = INT_MIN;
for (int i = 0; i < n; i++) {
if (arr[i] > first) {
second = first;
first = arr[i];
} else if (arr[i] > second && arr[i] != first) {
second = arr[i];
if (second == INT_MIN)
cout << "No second largest element." << endl;
else
cout << "Second largest element is " << second << endl;
return 0;
}
2. Suppose you have an array with 10,000 elements. What is the maximum number of iterations
required to perform a binary search in this array?
The maximum number of iterations in a binary search is:
[log2(10000)] + 1 = [13.28] + 1 = 14
Answer: 14 iterations
3. What happens if the array is not sorted in a binary search algorithm? How can you modify the
algorithm to handle such a situation?
If the array is not sorted, binary search will not work correctly, as it relies on the sorted order to
eliminate half of the search space each time.
Modification: Sort the array first using an efficient sorting algorithm (e.g., quicksort or mergesort),
and then perform binary search.
4. Consider an array with n elements. Suppose you want to find the kth largest element in the array
using a binary search algorithm. How would you modify the algorithm to achieve this?
To find the kth largest element:
1. Sort the array in descending order.
2. Return the element at index k-1 (0-based indexing).
Alternatively, use a min-heap of size k to keep track of the k largest elements in O(n log k) time.
Binary search can be adapted if the array is sorted and you apply binary search on value range, but
that’s more advanced.
def find_kth_largest(arr, k):
Finds the kth largest element in an unsorted array using Quickselect.
n = len(arr)
if k < 1 or k > n:
return None
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] >= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickselect(arr, low, high, k):
if low <= high:
pivot_index = partition(arr, low, high)
if pivot_index == k - 1:
return arr[pivot_index]
elif pivot_index > k - 1:
return quickselect(arr, low, pivot_index - 1, k)
else:
return quickselect(arr, pivot_index + 1, high, k)
return None
return quickselect(arr, 0, n - 1, k)
5. Implement a simple sorting algorithm such as bubble sort or selection sort in a programming
language of your choice. Test the algorithm on various input sizes and report the running times.
does the running time scale with input size? Are there any input sizes where the algorithm performs
particularly well or particularly poorly?
1. Bubble Sort Implementation:
The bubble_sort(arr) function implements the algorithm. It iterates through the list multiple times,
comparing adjacent elements and swapping them if they are in the wrong order.
2. Input Sizes:
The input_sizes list specifies the different array sizes to test on.
3. Time Measurement:
For each input size, a random list of numbers is generated, and the bubble_sort function is called.
The [Link]() function is used to record the start and end times of the sorting process.
4. Results Storage:
The execution time is stored in the results dictionary, keyed by the input size.
5. Output:
The code prints the running time for each input size, allowing you to observe how the algorithm's
performance changes with increasing input size.
Running Time Analysis:
Bubble Sort has a time complexity of O(n^2) in the worst and average cases. This means that the
time it takes to sort the array increases quadratically with the input size (n). In the best case (when
the array is already sorted), it's O(n). The code's output should demonstrate this:
As the input size increases, the running time will increase significantly.
You'll likely observe a much larger increase in running time when moving from, for example, 100 to
1000 elements, than when moving from 10 to 100 elements.
Input Sizes where Bubble Sort Performs Well or Poorly:
Small input sizes:
Bubble Sort can be reasonably fast for small lists (e.g., 10, 100 elements). Its simplicity makes it easy
to implement and understand.
Nearly sorted input:
If the input list is already mostly sorted, Bubble Sort will perform relatively well because it will need
fewer swaps and passes.
Large input sizes:
As the input size increases, the quadratic time complexity of Bubble Sort becomes a significant
drawback. For very large lists, other sorting algorithms (like Merge Sort or Quick Sort) are much
more efficient.
Worst-case input:
The worst-case scenario for Bubble Sort is when the input is reverse sorted (e.g., 10, 9, 8, ..., 1). In
this case, it will perform the maximum number of comparisons and swaps, resulting in the longest
running time.