### Programming Assignments

Note that demonstrations of working programs must be given on the scheduled day of your practicals immediately following the deadline. The programs may be mailed to the TA (discuss it with your class TA) by the deadline (if the demo is not already given).

If delayed by upto 1 week, it will be graded out of 50% of the marks and beyond that there will be no credit.

DO NOT TRY TO COPY PROGRAMS. You will be given negative credit and reported to the academic disciplinary committee.

### Programming Assignment 1

1. Exercises 3,5,6,8, 9 of Ocaml handout

2. Find out the value of max_int without using the the constant max_int

### Programming Assignment 2 (Due Sept 12)

2. Consider a game of NIM that is played between two players P1 and P2. The game begins with n tokens and players P1 and P2. A player can draw one or two tokens from the pile. Their turns alternate and the number of tokens in the pile is known at all times. The player who draws the last token loses. Starting from n tokens, we say that there is a winning strategy for player P1 if P1 starts and irrespective of whatever tokens player P2 draws, P1 can win (i.e. force P2 to pick the last token).
For example, if n =3, P1 can pick 2 so that P2 must pick the last token.
Write an ocaml program that given n returns 1 if there is a winning strategy for P1 and 0 otherwise.

3. Towers of Hanoi: Move a stack of n disks arranged in increasing sizes from top to bottom from peg A to peg B one by one such that at no intermediate step a larger disk should reside on a smaller disk. You can use an intermediate peg C for this purpose. Your program should list all the disk moves.

4. Write an program to convert an integer (in decimal) to base k (> 1) representation.

Hint: You may want to use the observation that the least significant digit in base k representation is the number modulo k.

5. Write a function unique : int list-> bool which takes an integer list M as input (with possibly repeated elements) and it returns true if all elements are unique and false otherwise.
How many operations does your program take for a list of n elements ?

### Programming Assignment 3 (Due Oct 3)

1. Write programs to manipulate "LARGE" integers (positive or negative) of arbitrary size. These integers could be greater than MAX_INT or smaller than MIN_INT. Choose an appropriate way of representing these numbers. Then write functions for (i) addition/subtraction
(ii) multiplication
(iii) division, i.e., quotient and remainder
(iv) Square root n : find an integer a such that a2 <= n < (a +1)2
(v) Extended GCD -- Extended GCD of two numbers u and v expresses u and v as a.u + b.v = d, where d = GCD(u,v)). Write recurrences to compute "a" and "b".
(vi) Check if a number is prime or not : We shall use the following algorithm (called Fermat's algorithm) for checking if a number p is prime or not. Pick any number a randomly between 1 and (p-1). Compute a(p-1) and take its remainder modulo p. If it is not 1, then the number p is not prime. Unfortunately the converse of this statement is not true. So it may happen that for all values of a between 1 and (p-1), the value of a(p-1)= 1 modulo p, and yet a is not a prime number. But the set of such numbers is very sparse. So we shall assume that the number p does not fall into this class. So here is the final algorithm :

Repeat T times

pick a between 1 and p-1 randomly.
check if a(p-1) = 1 mod p
If not, p is not prime
Output p is prime. Here T is a parameter you take as an input.

2. Write an Ocaml function to sort a list using Mergesort - you may want to use the function defined in the previous assignment to do the pivoting. Further, you should have an appropriate "comparison" function that will be part of the input and using which you should be able to sort any arbitrary (totally ordered) set.