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
- Exercises 3,5,6,8, 9 of Ocaml handout
- Find out the value of max_int without using the the constant max_int
Programming Assignment 2 (Due Sept 12)
-
Write your own function myadd that detects overflow (using exception)
when you add two integers.
-
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.
- 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.
- 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.
-
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)
- 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.
- 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.