Design and analysis of Algorithms, 2nd Edition

Appendix E

EXAMPLES OF ALGORITHMS

E.1  Existence of a Triangle

Develop an algorithm which determines whether or nor there exists a triangle having sides corresponding to the given set of three numbers (all positive).

Algorithm E.1 | Triangle (a, b, c)

 

1	if(a + b) > c AND(a + c) > bAND(b + c) > a then
2	return 1;
3	else
4	return 0;
5	end

E.2  GCD—Recursive Implementation

Develop a recursive algorithm which finds the GCD of the two given numbers a and b.

Algorithm E.2 | gcdr (a, b)

 

1	if a = b then return a;
2	if a > b then return gcdr(a – b, b);
3	if b > a then return gcdr(a, b – a);

E.3  Knight’s Tour

Knight’s Tour: In the game of Chess, a Knight can move to any of the eight different positions from a given ...