Programming Assignment Set
                  ---------------------------

Statutory Warning: 
------------------
Copying is a serious offence. The assignment in which copying is 
detected will be marked negative, i.e. a zero in that assignment 
and deduction from marks obtained rightfully in some other 
assignment. 

One who has allowed his/her program to be copied would be punished 
more severely than one who has copied. 


Programming Language: 
---------------------
You have to write the programs in C. Ensure that the programs 
compile with gcc. 


Deadlines:
----------
Clarification deadline date: May 09, 2015

Submission deadline date:  May 15, 2015


Naming conventions for program files. (xx is your roll number): 
---------------------------------------------------------------
For Problem 1: 
The name of the file for problem 1 should be  
``bs12xx-prob1.c''. 

For Problem 2: 
The name of the file for problem 2 should be  
``bs12xx-prob2.c''. 

For Problem 3: 
The name of the file for problem 3 should be  
``bs12xx-prob3.c''.

For Problem 4: 
The name of the file for problem 4 should be  
``bs12xx-prob4.c''. 
 
-----------------------------------------------------------------------

At the top of each of your program files, add the following. 
If you are writing multi-file programs, then each file should 
have it. 

/*------------------------------------------------------------------
Name: 
Roll Number:
Date of Submission:
Deadline date:  
Program description:
Acknowledgements: 
--------------------------------------------------------------------*/

Total Marks: 150

===============================================================
Problem 1: 

Write a C program that takes as input an array whose size is n 
and contains real numbers; and sorts them using the quick sort 
algorithm studied in the class. 

You will get extra credit if you allocate the array dynamically. 

Marks: 20+5 (for dynamic allocation)
=================================================================

Problem 2: 

Write a C program that takes as input an array whose size is n 
and contains real numbers; and implements the randomized 
selection algorithm studied in class. 

You will get extra credit if you allocate the array dynamically. 

Marks: 20+5 (for dynamic allocation)
==================================================================

Problem 3: 

Write a C program that takes as input a graph G=(V,E) with positive
weights on its edges and a source vertex s and a destination vertex 
t and finds the weight of the shortest path between s and t.

You need to think of data structures that stores the graph, maintains 
the partition of the vertices, and picks out the vertex with the 
minimum label from one partition. 

You will get extra credit if you allocate space for the graph 
dynamically. You will get extra credit if you can report the 
shortest path as well. 

Marks: 30+5+5 = 40
=====================================================================

Problem 4: 

Write a C program that takes as input a graph G=(V,E) with real weights 
on its edges. Find the weight of the minimum spanning tree of G. 

You will get extra credit if you allocate space for the graph 
dynamically. You will get extra credit if you can report the 
minimum spanning tree as well. 

Marks: 30+5+5 = 40
======================================================================

Problem 5:

Given a set P of n points in the plane and a positive integer k, find 
a k-clustering of P. A k-clustering of P is a partition of P into k 
non-empty groups such that the spacing between the clusters is maximized. 
The spacing between any two clusters is the minimum distance between 
any pair of points in different clusters. 

Marks: 20

======================================================================