All questions of Searching & Sorting for Computer Science Engineering (CSE) Exam

Sorting 1 GB of data with only 100 MB of available main memory

To sort 1 GB of data with only 100 MB of available main memory, we need to choose a sorting technique that can efficiently handle external sorting, where data is too large to fit entirely in main memory. Among the given options, merge sort is the most appropriate choice. Here's why:

Merge Sort
Merge sort is a divide and conquer algorithm that is well-suited for external sorting. It works by splitting the input into smaller chunks, sorting them individually, and then merging them back together.

Advantages of Merge Sort for External Sorting:
1. Efficient use of memory: Merge sort is designed to minimize the amount of memory required for sorting. It can handle large datasets by dividing them into smaller chunks that can fit into memory.
2. Stable sorting: Merge sort is a stable sorting algorithm, meaning that it preserves the relative order of elements with equal values. This is important when sorting data that is already partially sorted or contains duplicate values.
3. Good worst-case time complexity: Merge sort has a worst-case time complexity of O(n log n), which is efficient for large datasets. This makes it suitable for sorting 1 GB of data.
4. Easy to implement: Merge sort has a simple and intuitive algorithmic structure, making it easier to implement and debug.

How Merge Sort Works for External Sorting:
1. Divide: The input data is divided into smaller chunks that can fit into memory (e.g., 100 MB in this case).
2. Sort: Each chunk is sorted individually using an in-memory sorting algorithm like quick sort or insertion sort.
3. Merge: The sorted chunks are merged back together using a merge operation that compares and combines the elements in a sorted manner. This can be done efficiently even if the chunks are too large to fit in memory at once, by reading and writing data from/to external storage (e.g., hard disk).

Conclusion
Considering the constraints of limited available memory and the need for efficient external sorting, merge sort is the most appropriate technique among the given options. It provides efficient memory utilization, stability, good worst-case time complexity, and ease of implementation.

Merge sort data can be sorted using external sorting which usses merge sort..

Explanation:

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Best Case Scenario:

The Best case scenario for Bubble Sort occurs when the elements are already sorted in ascending order. In this case, the algorithm will only need to make a single pass through the list to identify that it is already sorted and no swaps are needed. Therefore, the time complexity of this scenario is O(n).

Worst Case Scenario:

The Worst case scenario for Bubble Sort occurs when the elements are sorted in descending order. In this case, the algorithm will need to make n-1 passes through the list and perform n-1 swaps in each pass. Therefore, the time complexity for this scenario is O(n*n).

Average Case Scenario:

In the average case scenario, the time complexity of Bubble Sort is O(n*n).

Conclusion:

In conclusion, the best case scenario for Bubble Sort occurs when the elements are already sorted in ascending order. In this scenario, the time complexity of Bubble Sort is O(n). However, in the worst-case scenario, Bubble Sort takes O(n*n) time to sort the list.

Want to find the sum of all the even numbers in the array L.

To do this, you can iterate through each element in the array and check if it is even. If it is even, add it to a running total. Here is the code to achieve this:

```python
L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
sum_even = 0

for num in L:
if num % 2 == 0:
sum_even += num

print(sum_even)
```

Output:
```
56
```

In this code, we initialize a variable `sum_even` to 0 to keep track of the sum of even numbers. Then, we iterate through each element `num` in the array `L`. Inside the loop, we use the modulo operator `%` to check if `num` is divisible by 2 (i.e., even). If it is, we add it to `sum_even`. Finally, we print `sum_even`, which gives us the sum of all even numbers in the array.

Understanding Sequential Search
Sequential search, also known as linear search, involves checking each element in a list one by one until the desired item is found. The average number of key comparisons for a successful search can be derived from basic principles of probability and counting.
Calculating Average Comparisons
- In a list of 'n' items, when searching for an item, there are 'n' possible positions where the item could be located.
- For a successful search, the item could be at any position in the list (1st, 2nd, ... nth).
- The average position of the item can be computed by considering the contributions from all positions:
Average Position Formula
- The average position (where the item is found) is given by the sum of all positions divided by the number of items:
(1 + 2 + 3 + ... + n) / n
- The sum of the first 'n' integers is n(n + 1)/2. Thus, the average position becomes:
n(n + 1)/(2n) = (n + 1)/2.
Conclusion
- Therefore, the average number of key comparisons required for a successful search in a sequential search is indeed (n + 1)/2.
- This result leads us to select option 'C' as the correct answer.
Key Takeaway
- Average comparisons for a successful search in sequential search: (n + 1)/2.
- This understanding helps in estimating the efficiency of search algorithms in data structures.

Explanation:

To find the minimum number of comparisons for a particular record among 32 sorted records through binary search, we need to determine the maximum number of comparisons required.

Binary Search:
Binary search is a divide and conquer algorithm that works by repeatedly dividing the search interval in half. It starts by comparing the target value with the middle element of the sorted array. If the target value matches the middle element, the search is successful. If the target value is less than the middle element, the search continues on the lower half of the array. If the target value is greater than the middle element, the search continues on the upper half of the array. This process continues until the target value is found or the search interval is empty.

Maximum Number of Comparisons:
In binary search, the search interval is halved at each step. The maximum number of comparisons required to find a particular record can be determined by finding the height of the binary search tree.

- In the first comparison, we compare the target value with the middle element of the array.
- If the target value is less than the middle element, we divide the search interval into two halves. The next comparison will be made with the middle element of one of the halves.
- Each subsequent comparison divides the search interval into half until the target value is found or the search interval is empty.

Height of Binary Search Tree:
The height of a binary search tree with n nodes is given by h = log2(n+1) - 1.

For 32 sorted records, the height of the binary search tree would be:
h = log2(32+1) - 1
= log2(33) - 1
= 5 - 1
= 4

Minimum Number of Comparisons:
The minimum number of comparisons required to find a particular record is equal to the height of the binary search tree. In this case, the height is 4.

Therefore, the minimum number of comparisons for a particular record among 32 sorted records through binary search method will be 4, which corresponds to option 'B'.

Explanation:

- QuickSort is an efficient sorting algorithm with average case complexity of O(nLogn). However, its worst case complexity is O(n^2) when the pivot selected is either the smallest or largest element in the array, resulting in unbalanced partitions.
- To improve the efficiency of QuickSort, we can use a better pivot selection strategy. One such strategy is to choose the median element as the pivot, which ensures that the partitions are roughly equal in size and reduces the chances of worst case scenario.
- If we have an O(n) time algorithm to find the median element of an unsorted array, we can use it to select the pivot in QuickSort. This will result in a modified version of QuickSort with improved worst case complexity.
- The worst case scenario for this modified QuickSort will occur when the median element is selected as the pivot and it still results in unbalanced partitions. This can happen if the array is already sorted or has many duplicate elements, such that the median element is either the smallest or largest element in the array.
- In this worst case scenario, the time taken by the median finding algorithm will be O(n), and the time taken by QuickSort will be O(n^2), resulting in a worst case time complexity of O(n^2).
- However, this worst case scenario is unlikely to occur in practice, and the average case complexity of the modified QuickSort will still be O(nLogn).
- Therefore, the correct answer is option B, O(nLogn).

Insertion sort runs in Θ(n + f(n)) time, where f(n) denotes the number of inversion initially present in the array being sorted.

For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced. 

-Merge Sort works better than quick sort if data is accessed from slow sequential memory. 

Space Complexity of Binary Search Algorithm

Explanation:

- The space complexity of an algorithm is the amount of memory space required by the algorithm to execute and store the data values.

Binary Search Algorithm:

- In the given binary search algorithm, the only extra space used is for the variables `low`, `high`, `mid`, and `data`.

Variables:
- low, high, mid: These variables are used to keep track of the indices in the array during the search process. They each take up constant space.
- data: This variable stores the value that is being searched for in the array. It also takes up constant space.

Space Complexity:
- Since the space used by the algorithm is constant regardless of the size of the input array, the space complexity of the binary search algorithm is O(1) (constant space complexity).

Hash Table with Random Probing
In random probing, we use a pseudo-random function to determine the next position to probe if a collision occurs during insertion. In this case, the pseudo-random function is i = (i + 5) % 7.

Inserting Keys
Let's insert the keys one by one according to the given order: 15, 11, 25, 16, 9, 8, 12.
- Insert 15: H(15) = 1. Key 15 is inserted at position 1.
- Insert 11: H(11) = 4. Key 11 is inserted at position 4.
- Insert 25: H(25) = 4. Since position 4 is already occupied by key 11, we use random probing i = (4 + 5) % 7 = 2. Key 25 is inserted at position 2.
- Insert 16: H(16) = 2. Key 16 is inserted at position 2.
- Insert 9: H(9) = 2. Since position 2 is already occupied by key 16, we use random probing i = (2 + 5) % 7 = 0. Key 9 is inserted at position 0.
- Insert 8: H(8) = 1. Since position 1 is already occupied by key 15, we use random probing i = (1 + 5) % 7 = 6. Key 8 is inserted at position 6.
- Insert 12: H(12) = 5. Key 12 is inserted at position 5.

Position of Key 25
After inserting all keys, the final positions are: 0, 1, 2, 4, 5, 6. Key 25 is at position 2, as determined by random probing. Therefore, the correct answer is option 'D' - 2.

Worst case time complexity of the modified QuickSort:

Explanation:
In the modified QuickSort algorithm, we first find the median of the unsorted array using the O(n) time algorithm. Then we use this median as the pivot for partitioning the array in the QuickSort algorithm.

Step 1: Finding the Median
Finding the median of an unsorted array takes O(n) time. This is because we can use the O(n) time algorithm to find the median in linear time. So, the first step of finding the median has a time complexity of O(n).

Step 2: Partitioning the Array
In the QuickSort algorithm, we partition the array around the pivot element. In the worst case scenario, if the pivot is always chosen as the median, the array will be evenly split into two halves. This means that each partitioning step will divide the array into two subarrays of roughly equal size. The worst case time complexity for partitioning is O(n) because we need to compare each element with the pivot and move them to the left or right subarray accordingly.

Step 3: Recursion
After partitioning the array, we recursively apply the QuickSort algorithm on the two subarrays. Since each partitioning step divides the array into two roughly equal halves, the size of the subarrays will be halved at each recursive call.

Time Complexity Analysis:
Let's denote the length of the array as n.

- In the first step, finding the median takes O(n) time.
- In the second step, partitioning the array around the median pivot takes O(n) time.
- In the third step, we recursively apply the QuickSort algorithm on two subarrays of size n/2.

The recurrence relation for the worst case time complexity of the modified QuickSort algorithm can be written as:
T(n) = T(n/2) + O(n)

Using the Master Theorem, we can solve this recurrence relation. In this case, the recurrence relation falls under Case 2 of the Master Theorem, which states that if the partitioning step divides the problem into two subproblems of size n/2, and the time complexity of the partitioning step is O(n), then the time complexity of the algorithm is O(n log n).

Therefore, the worst case time complexity of the modified QuickSort algorithm is O(n log n), which corresponds to option (d).

The worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n is O(log n).