JNTU B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (November/December - 2020 - R15)

The Merge Sort algorithm is a classic application of the Divide and Conquer paradigm. It works by recursively splitting an array into two halves until each sub-array contains a single element, then merging these sub-arrays in sorted order.

The process follows three distinct phases:

• Divide: The algorithm finds the midpoint of the current array and splits it into two equal halves. This step repeats until the base case is reached (a sub-array of size 1).
• Conquer: The sub-arrays are sorted recursively. Since a single-element array is inherently sorted, the base case requires no further action.
• Combine (Merge): The sorted sub-arrays are merged back together. During this step, the algorithm compares elements from both sub-arrays and places the smaller element into a temporary array, ensuring the resulting merged array is sorted.

Consider the example array: [38, 27, 43, 3].

1. Divide: Split into [38, 27] and [43, 3]. Split further into [38], [27], [43], and [3].
2. Merge: Compare 38 and 27 to form [27, 38]. Compare 43 and 3 to form [3, 43].
3. Final Merge: Compare the sorted sub-arrays [27, 38] and [3, 43]. Compare 27 and 3 (take 3), compare 27 and 43 (take 27), compare 38 and 43 (take 38), and finally take 43. The result is [3, 27, 38, 43].

Merge Sort has a time complexity of O(n log n) in all cases (best, average, and worst), making it highly efficient for large datasets, though it requires O(n) auxiliary space for the merging process.

The Job Sequencing with Deadlines problem involves a set of n jobs, where each job i has a deadline d_i and a profit p_i. Each job takes one unit of time to complete, and only one job can be processed at a time. The goal is to maximize the total profit by scheduling jobs such that each job completes on or before its deadline.

The Greedy approach is used to solve this problem by prioritizing jobs with the highest profit. The algorithm follows these steps:

1. Sort all given jobs in non-increasing order of their profit values.
2. Initialize a schedule array (or time slot array) of size equal to the maximum deadline among all jobs, initially marked as empty.
3. Iterate through the sorted jobs. For each job, attempt to schedule it in the latest possible free time slot that is less than or equal to its deadline.
4. If a slot is available, assign the job to that slot and add its profit to the total. If no slot is available before the deadline, discard the job.

This strategy works because it makes a locally optimal choice at each step by picking the most profitable job available, which leads to a globally optimal solution for this specific problem structure. The time complexity of this approach is O(n log n) due to sorting, and the space complexity is O(n) to store the schedule.