Day 11 (August 12, 2013)  
Assignment to be done in class and as exercises.

Assignment 1: 
Write a program in C that takes as input a string S of 
n characters and generates all r-permutations of S (r <= n)
(i) with replacement and (ii) without replacement. 
Also print the number of permutations generated. 

Assignment 2: 
Write a program in C that takes as input an array 
S = {1,2,...,n} of length n and generates 
(i) all derangements of S 
(ii) all derangements of S where exactly k (k<=n) numbers 
go to the correct position. 

Assignment 3: 
Write a recursive program that solves the Tower of Hanoi 
problem for n disks and 3 pegs. 

As an additional exercise, think what would happen if the 
number of pegs increase from 3 to 4 and beyond.

Assignment 4: 
Write a program in C that allocates a 1D matrix M dynamically. 
Read some data into M and sort M. Now, perform the following: 
(i) given a value x, search whether x exists in M. 
[Hints: Use binary search.]
(ii) given an interval [a,b], report all values in M that lie 
within the interval [a,b].
(iii) given an interval [a,b], count (and not report) all values 
in M that lie within the interval [a,b]. 

In all the above cases, count the number of comparisons you are 
making. Can you solve (iii) faster than (ii) by storing the data 
intelligently? 


Assignment 5:  
Write a program in C that finds n! for a positive integer n. 
Note that n can be any arbitrary positive integer. 
[Hints: You can work with the linked list representation 
of a number.]

Assignment 6:
Write a program in C that represents a polynomial of a single variable 
in a linked list and stores only those entries that have non-zero 
co-efficient. With this representation of a polynomial, 
write functions that 
(i) adds two polynomials 
(ii) multiplies two polynomials
(iii) evaluates a polynomial at any real value
(iv) finds the derivative of a polynomial. 
   



------------------------------------------------------------------------
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: 
--------------------------------------------------------------------*/