CpE-300: Design and Analysis of Algorithms

Programming Assignment 1

A selection problem is a problem to find the kth order static element from a set of n distinct numbers.

Input: a set A of n distinct numbers (unsorted) and an integer k.

Output: the element x which is larger than k-1 other elements in A.

Read Sections 9.2 & 9.3 from the text book ( Introduction to algorithms by Cormen, Leiserson, Rivest, Stein 2^nd or 3^rd edition).

The presented selection algorithm depend on divide-and-conquer algorithm and the expected running time O(n).The important part in this algorithm is choosing the pivot for partitioning (randomly or median-of-medians). make sure that you make two Classes or more if you need to

Implement the selection algorithm ( using both method of selecting the pivot) using an object oriented programming language.

Your code should be readable and well designed with a strategy pattern. ( read about a strategy pattern). it is important you have to read it

Run your code multiple times with different size of Array A, display your results in x-y plane where:

X is the Size of the array

Y is the execution time

Requirements:

Reading sections 9.2 & 9.3 from text book

Reading about the strategy pattern

Submission:

each student should submit a soft-copy (upload in OCS) and a hard-copy (in class) including the following:

Readable, well designed program code (add comment for clarification)

Your Statistics ( ArraySize-execution time ) table and graph

Compare your results with the expected selection algorithm running time