Solved–Lab # 8 Algorithm Design Techniques– Solution

Description

1. (Randomized algorithms) Write a program to “discover” trigonometric identities. Your program should test all combinations of the trigonometric expressions shown below and use a randomized algorithm to

detect the equalities. For your equality testing, generate random numbers in the to range.

(a) sin(t)

(b) cos(t)

(c) tan(t)

(d) sec(t)

(e) sin(t)

(f) cos(t)

(g) tan(t)

(h) sin( t)

(i) cos( t)

(j) tan( t)

_(k) sin(t)

cos(t)

(l) 2 sin(t=2) cos(t=2)

(m) sin²(t)

(n) 1 cos²(t)

_(o) 1 cos(2t)

2

1. 16. ¹

cos(t)

2. (Backtracking) The partition problem consists of determining if there is a way to partition a set of integers

if S1 [S2 = S and S1 \S2 = fg. Write aP	P
S into two subsets S1 and S2 such that S1 =	S2. Recall that S1 and S2 are a partition of S if and only

function that solves the partition problem using backtracking. If a partition exists, your program should display it; otherwise it should indicate that no partition exists. For example, if S = f2; 4; 5; 9; 12g, your program should output the partition S₁ = f2; 5; 9g and S₂ = f4; 12g and if S = f2; 4; 5; 9; 13g your program should indicate that no partition exists.

Given the little time available, a demo will not be required, thus it is very important that your report accurately describes your work.

1