3. (Dasgupta et a. question 2.23(a) An array A1.. has a majority element if more
ID: 3585049 • Letter: 3
Question
3. (Dasgupta et a. question 2.23(a) An array A1.. has a majority element if more than half of its entries are the same. Given an array, the problem is to design an algorithm to find such an element if one exists. Note that the elements of A are not necessarily orderable, but a pair can be tested for equality in constant time. Design and write a divide-and-conquer algorithm that solves this problem in O(n logn) time 4. (adapted from Dasgupta et al, question 2.27 (a) and (b)) The square of a matrix A is its product with itself, so A2 = AA. ) Show that 5 nmutipliationsa2*2 matris (b) explain two reasons why we cannot generalize this to a (o5) algorithm for squaring a matrix of size n.Explanation / Answer
3.
A divide and conquer approach for solving the given problem can be explained as follows.
First, split the given array, A in two subsets, say A1 and A2, and so on. In this, we need to show that T(n) is O(n log n).
If A has a majority element, say m, then it must also be a majority element of A1 or A2 or both. At the same time, we can also say that: (If m is <= half in each, it is <= half in the total).
If both parts have the same majority element, it is automatically the majority element for A. Now, we need to check that if one of the parts has a majority element, count the number of repetitions of that element in both parts (in O(n) time) to see if it is a majority element.
If both parts have a majority, then it is needed to count each of the two candidates. This will again take O(n) time. This splitting can be done recursively. The base case is when n = 1.
A recurrence relation is T(n) = 2T(n/2) + O(n), so T(n) is O(n log n) by the Master Theorem
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.