Wednesday, January 30, 2013

HPC Contest IIT Kanpur: Analysis

IIT Kanpur saw its first high performance computing contest last weekend.

Contest duration : 24 hours
Number of Problems : 3
Maximum number of compute processors available : 6

Winners:
1st - Team TafriBAAZ - Sumit Kumar ,Suyash Garg, Niraj Kant Sinha
2nd - Team JONAM - Manoj Chandrasekaran

The problems were designed to test some of the basic concepts of Parallel Computing.

Problem A: Vector addition
Concept: Data Redistribution

Add 2 vectors of N dimensions for T test cases and print the resulting vector.

Sample Input:
2
4
1 1 2 3
2 3 4 1
5
1 2 3 4 5
5 4 3 2 1

Sample Output:
3 4 6 4
6 6 6 6 6

The solution code is Here.

Problem B: Mersenne Prime

Concept: Parallel Search

There are some prime numbers p for which 2p-1 is also prime. We define 2p-1 as a Mersenne prime number and p as the Mersenne prime exponent. For eg. lets take p = 2 then 2p-1 = 3 is also prime, we call 3 as a Mersenne prime number and 2 is a Mersenne prime exponent. In the given sequence of integers find the first occurrence of a Mersenne prime number or a Mersenne prime exponent.

Input
The first line contains an integer T (1<=T<=102), the number of test cases. The second line contains an integer, n (1<=n<=106). It is followed by one line containing a sequence of n space-separated integers (all integers are less than 2*107).

Output
For each, test case output a single line containing the first occurrence of a lucky prime number or a lucky prime exponent in the sequence. Separate test cases with a new line.


Sample Input
2
3
14 586 1279
3
8191 3 19

Sample Output
1279
8191

Explanation
In the first case 1279 is a Mersenne prime exponent.
In the second case 8191 is a Mersenne prime.


To get the solution code of more generic prime search problem click Here.


Problem C: Median
Concept: Parallel Selection

The median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest to highest value and picking the middle one. If there is an even number of observations, the median is the mean of the two middle values.
For example:
1,2,3,4,5 : The median is 3.
1,5,9,2,8,4: The median is 4.5.


Visit this link for the solution algorithm and try implementing it as it will not be difficult if you can understand the solutions provided above.


Endnote: This contest was just a primer to the 1st International High Performance Computing Contest which will be organised in Techkriti'13.
Click here and follow our G+ page to get latest updates.

1 comment:

  1. Nice ! That's a lovely post. Congratulations
    I have nominated your blog for the Libester Blog award friend, kinldy take a look at the link below :
    http://thankgodforlife.blogspot.in/2013/02/liebster-awards-thanks-jahid-neo.html

    ReplyDelete

Comment will be sent for moderation.