ESc101 Laboratory Assignment 
	              Wednesday of Week of 20/09/04


The Assignment consists of THREE programs. USE OF ARRAYS IS NOT ALLOWED.

NOTE: Use objects of StringBuffer Class. (String Class represents fixed-length, 
immutable character sequences. In contrast, StringBuffer Class represents growable 
and writable character sequences.) 

1) Write a program which encodes or decodes a given word (ignoring the case). 
The encoding scheme is as follows : 
Suppose the word is "case" then it is coded to "c Mc(a) Ma(s) Ms(e)"
where Ma, Mb, ..., Mz are maps from alphabets to alphabets given by
Ma(a) = b, Ma(b) = c,..., Ma(y) = z, Ma(z) = a (each letter shifts circularly by one)
Mb(a) = c, Mb(b) = d,..., Mb(y) = a, Mb(z) = b (each letter shifts circularly by two)
so on. Thus "case" is coded as "cdtx". The decoding is its converse.

2) You are given 2 sorted words. Merge the two words such that the resultant 
string should also be sorted. For example on merging "aefrt" and "bhrsu"
we get "abefhrrsu".

3) Given two integers x, y find their greatest common divisor (gcd(x,y)) = z.
Note that z can be expressed as linear combination of x, y.
i.e. ax + by = z ,    Find a, b.

Procedure for finding GCD

Suppose x < y

1. Given two numbers, subtract maximum possible multiple of smaller number 
   from larger one.
   (find p*y such that value of p is maximum possible and (x - p*y)  >= 0)

2. Continue this process with now remaining two number.  (y and (x - p*y) )

3. Do this iteratively till you get one of the numbers as 0.  The other 
   number is GCD.

Now you have to express this GCD as liner combination of original numbers.

Refer to previous iterative process.
1. Express GCD as linear combination of two number in the last iteration.
2. Now iteratively go on substituting the current numbers with linear 
   combination of numbers in previous iteration.
3. Continue till you express GCD as linear combination of original numbers.

Example:   x= 21   y= 35

Iteraion 1:    21    (35 -  (1*21))
               21     14

Iteration2:    (21 - (1*14))     14
                7               14

Iteration3:     7    (14- (2*7))
                7     0

GCD = 7


(a*21)  +   (b*35)  = 7


7 = 7 - 0
  = 7 - (14 - (2*7))
  = (3*7) - 14
  = (3*(21- (1*14)) - 14
  = (3*21)- (4*14)
  = (3*21)-(4*(35-(1*21)))
  = (7*21) - (4*35)

So a = 7,  b = -4