1
Posted April 2, 2011 by Bandish Patel in IGNOU Assignments
 
 

IGNOU MCA Assigment(MCS-031-january)


Course Code              : MCS-031

Course Title              : Design and Analysis of Algorithms

Assignment Number  : MCA(3)/031/Assign/2011

Maximum Marks              : 100

Weightage                              : 25%

Last Dates for Submission:15th April, 2011 (For January Session)

15th October, 2011 (For July Session)

 

There are four questions in this assignment, which carries 80 marks. Rest 20 marks are for viva-voce. Answer all the questions. You may use illustrations and diagrams to enhance the explanations. Please go through the guidelines regarding assignments given in the MCA Programme Guide for the format of presentation.  The examples, whenever asked to be given, should be different from those that are discussed in the course material.

 

Question 1:

 

(a)  What is Randomized Quicksort? Analyse the expected running time of

Randomized Quicksort, with the help of a suitable example.                      (5 Marks)

Ans :

 

In Randomized quick sort a random element is choose as a pivot element.

In very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot.

 

Consider a zero-sum game between player A, whose strategies are deterministic algorithms, and player B, who’s strategies are inputs for A’s algorithms. The cost of a strategy profile is the running time of A’s chosen algorithm on B’s chosen input. Therefore, player A tries to minimize the cost, and player B tries to maximize it. In the world of pure strategies, for every algorithm that A chooses, B may choose the most costly input – this is the worst case scenario, and can be found using standard complexity analysis.

But in the real world, inputs are normally not selected by an ‘evil opponent’ – rather, they come from some distribution over inputs. Since this is the case, if we allow the algorithms to also be drawn from some distribution, we may look at the game as one that allows mixed strategies. That is, each player chooses a distribution over it’s strategies.

Analysis

 

Incorporating mixed strategies into the game allows us to use von Neumann’s minimax theorem:

 

where R is a distribution over the algorithms, D is a distribution over inputs, A is a single deterministic algorithm, and T(A, D) is the average running time of algorithm a on input D. More specifically:

 

If we limit the set of algorithms to a specific family (for instance, all deterministic choices for pivots in the quick sort algorithm), choosing an algorithm A from R is equivalent to running a randomized algorithm (for instance, running quick sort and randomly choosing the pivots at each step).

This gives us an insight on Yao’s principle, which states that the expected cost of any randomized algorithm for solving a given problem, on the worst case input for that algorithm, can be no better than the expected cost, for a worst-case random probability distribution on the inputs, of the deterministic algorithm that performs best against that distribution.

 

Algorithm:

void RandQuickSort(int Array[], int l, int r) {

 

int piv=l+(rand()%(r-1+1);

swap(Array[1],Array[piv]);

int i = l+1;

int j = r;

 

void RandQuickSort(int Array[], int l, int r) {

 

int piv=l+(rand()%(r-1+1);

swap(Array[1],Array[piv]);

int i = l+1;

int j = r;

 

while (1) {

while(Array[i] <= Array[1] && i<r) ++i;

while (Array[j] <= Array[l] && j>l) –-j;

if (i >=j) {

swap(Array[j],Array[l]);

return j;

}

else Swap(Array[i],Array[j]);

}

 

http://www.filesonic.com/file/………./MCS-031-Jan11-Assign.pdf


Bandish Patel