Lab # 8 Algorithm Design Techniques Solution



1. The partition problem consists of determining if there is a way to partition a set of integers S into two subsets S1 and S2 such that P S1 = P S2. Recall that S1 and S2 are a partition of S if and only if

S1 S2 = S and S1 S2 = {}. Write a method that solves the partition problem using backtracking.

2. Write a randomized algorithm to check probabilistically whether two trigonometric expressions are iden- tities. Your expression can be written as java methods. For example, to check whether tan(θ) = sin(θ)/cos(θ) you can define methods:

public static double f(double theta){

return Math.sin(theta)/Math.cos(theta);


public static double g(double theta){

return Math.tan(theta);


And then implement a method that tests the equality using a large number of random values in the π to π range. Try your method on as many of the identities in the following image as you can. Try it also on expressions that are not identities to make sure those are correctly detected.