Question

Write a PRAM algorithm that runs in \(\theta(\lg n)_{2}\) ) time for the problem of mergesorting. (Hint: Use \(n\) processors, and assign each processor to a key to determine the position of the key in the final list by binary searching.)

Short answer

The algorithm can be achieved by assigning each processor a key from the list, each processor counting the number of keys less or equal, and then putting its key in its final position in the sorted list concurrently. This results in a \(\theta(\lg n)_{2}\) time complexity, which is achieved due to binary search on `n` processors in a parallel environment.

Step-by-step solution

Understanding Merge Sort and Binary Search

Merge sort is a divide-and-conquer algorithm that splits the input array into two halves, recursively sorts them, and finally merges the two sorted halves. It has a time complexity of \(\theta(n\log n)\). Binary search is an algorithm used for finding the position of a specific value within a sorted array. It halves the part of the array where the value could be present until it's found or the interval size becomes zero. The time complexity of the binary search algorithm is \(\theta(\log n)\).

Designing Parallel Merge Sort Using PRAM model

In a parallel setting using PRAM model, the merge sort algorithm can be implemented by assigning each processor to a key. It will determine the position of the key in the final list using binary search. The steps of the algorithm can be defined as follows: \n 1. Assign each processor to a key from the list. \n 2. Let each processor compare its key to each other key in the list, having each processor keep a count of the number of keys less or equal to its assigned key. \n 3. After all processors are done comparing, each processor places its key into its final position in the sorted list according to the count value obtained. As each processor places its key concurrently, the total time is equivalent to one comparison.

Analyzing Time Complexity

The time complexity here is \(\theta(\lg n)_{2}\). This is because in binary search, each processor is trying to find the position of its corresponding key within the sorted array which is equivalent to a binary search operation taking \(\theta(\log n)\) time. Since we're operating in a parallel environment with `n` processors, the factor of `n` from the original \(n \log n\) merge sort time complexity is removed, resulting in \(\theta(\lg n)\) for the parallel merge sort algorithm.

Key concepts

PRAM Model

The PRAM (Parallel Random Access Machine) model is a theoretical framework used to design parallel algorithms. It allows us to analyze how algorithms can be broken down into steps that can be executed simultaneously. Think of it as having multiple processors working together to solve a problem, instead of just one. These processors can execute instructions without waiting for each other, thus speeding up computation.
In the PRAM model, tasks are divided among processors, each responsible for a part of the computation. This model assumes unlimited processors and shared memory, which simplifies programming but can be difficult to implement in reality.
There are different variations of PRAM, like EREW (Exclusive Read Exclusive Write) which limits access to memory locations, and CRCW (Concurrent Read Concurrent Write) which allows multiple processors to both read and write at the same time. The PRAM model is especially useful for designing algorithms for large scale problems such as Sorting or Searching.

Merge Sort

Merge Sort is a classic sorting algorithm that is based on the divide-and-conquer principle. The intuition behind it is simple: split an unsorted list into smaller parts, sort these parts and then merge them back together.
The process starts by dividing the list into two halves. Then, it recursively divides the halves until each part is reduced to a single element. Once the smallest elements are sorted, they are merged back together into larger sorted sublists until the entire list is reassembled in sorted order.
Merge Sort is efficient, with a time complexity of \( heta(n \log n)\). This efficiency comes from breaking down the problem into manageable pieces and working on them separately before combining the results. Since Merge Sort works independently of the data, it is especially useful and widely used in many computing systems.

Binary Search

Binary Search is a highly efficient algorithm for finding an item from a sorted list of items. The idea is to reduce the search problem into smaller problems by repeatedly dividing the array into halves.
To perform a binary search, start with the middle element of the array. If this element is the target, the search is complete. If the target is smaller, continue the search on the left half; if larger, on the right half. Repeat this process until you find the element or the subarray size becomes zero.
Binary Search has a time complexity of \( heta(\log n)\), which is significantly faster than linear search methods because it reduces the problem size by half with each step. This efficiency makes it a favorite choice for searching through large and sorted datasets quickly.

Time Complexity Analysis

Time complexity is a way to express how the runtime of an algorithm grows with the size of the input. It's crucial in understanding the efficiency of algorithms, particularly when dealing with large datasets.
In the context of Merge Sort and Binary Search, the time complexity analysis reveals the difference in efficiency. Merge Sort generally runs in \( heta(n \log n)\) time by sorting smaller subarrays and merging them back.
However, when adapted for parallel computing using the PRAM model, and combining Binary Search for position finding, the time complexity can improve to \( heta(\log n)\). This improvement occurs because each key is independently sorted using a processor and Binary Search, leading to dramatically reduced runtime by leveraging parallelism.
Understanding these complexities helps in choosing the right algorithm for a task based on the resources available and the size of the data.