23rd Feb, 2011

1. Modified Bubble-Sort							(35)
An inversion in an array of real numbers A is any pair (i,j) such that i<j and
A[i]>A[j].
For e.g. in the array A=[25,7,51,4], the inversions would be (0,1),(0,3),(1,3) and
(2,3). Write a C function which takes an array as a parameter and 
two indices i and j with i<j. 
Name the function as isInverted. Its signature would be
        void isInverted(int a[], int i, int j).
This function checks if these two indices correspond to an inversion pair in the array.
If no, then it simply returns and if yes, then swap the positions of the elements in
the array. 
For e.g., isInverted(A,1,3) will swap the postions of A[1] and A[3] in A as 7>3
while isInverted(A,0,2) will have no effect.
Use this function to implement the bubble-sort algorithm to make the given array
sorted in ascending order. Initialize the array in your program to 
arbitrary integer values in your program (no need to take user-input)

2. Stack								(40)
A stack is a last in, first out (lifo) data structure. It can store elements of any
type. A stack has an inherent notion of top and bottom. 
Elements can be read/added/removed only from the top if the stack. That is, not all
the elements can be accessed directly like in the case of arrays. 
A stack is characterised by two operations - push and pop. 
        a) push - this operation adds an item to the top of the stack
        b) pop - this operation removes an item from the top of the stack, and returns this
value to the caller
An integer stack can be implemented using a int-array. Write a C program which
implements a stack including the push and pop operations (functions).
Restrict your domain of elements in the stack to positive integers.
You may like to define a global integer array as your stack and a counter to keep
track of number of elements in the stack. Prototypes of push and pop
would then be void push(int numToPush) and int pop(). Create a stack of 10 elements
with the help of your push operation and then remove 7 elements out of it by
'popping'.
Extra Credit : 
Make the above program menu driven. eg . Display the following menu :
	1. push
	2. pop
	3. Exit 
Take input from user choosing the operation. Exit from program only if user chooses exit.


3. Totient Numbers							(25)
The totient number T(n) of a positive integer n is defined to be the number of
positive integers less than or equal to n that are coprime to n (i.e., having
no common factor other than 1).

For example, T(1) = 1 (special case); T(9) = 6 (as 1, 2, 4, 5, 7 and 8 are
coprime with 9).

Write a program that takes a positive integer as input and calculates its
totient number. Your program should implement the following two functions
(other than the main): 
	1. int coprime(int m, int n): returns 1 if m and n are co-prime, 0 otherwise
	2. int totient(int n): returns the totient number of n