Starting from:
$30

$24

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

S1 [ S2 = S and S1
\ S2 = fg.PWrite aP
subsets S1 and S2
such that S1 = S2. Recall that S1 and S2 are a partition of S if and only if
method that solves the partition problem using backtracking.




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 de ne 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.













As usual, write a report describing your work.

More products