Question) For each of the following problems: design an exhaustive search or opt

Question

Question) For each of the following problems: design an exhaustive search or optimization algorithm that solves the problem; describe your algorithm with clear pseudocode; and prove the time efficiency class of your algorithm.

When writing your pseudocode, you can assume that your audience is familiar with the candidate generation

algorithms in this chapter, so you can make statements like “for each subset X of S” without explaining the

details of how to generate subsets.

a)The Pythagorean triple problem is:

input: two positive integers a, b with a < b

output: a Pythagorean triple (x, y, z) such that x, y and z are positive integers, a x y z b, and

x2 +y2=z2 or None if no such triple exists.

Explanation / Answer

int a=0, b=0,c =0
int s = 1000;
int m = 0, k = 0, n = 0, d = 0;
bool found = false;

int mlimit = (int) Math.Sqrt(s / 2);
for (m = 2; m <= mlimit; m++) {
    if ((s / 2) % m == 0) { // m found
        if (m % 2 == 0) { // ensure that we find an odd number for k
            k = m + 1;
        } else {
            k = m + 2;
        }
        while (k < 2 * m && k <= s / (2 * m)) {
            if (s / (2 * m) % k == 0 && gcd(k, m) == 1) {
                d = s / 2 / (k * m);
                n = k - m;
                a = d*(m * m - n * n);
                b = 2 * d * n * m;
                c = d * (m * m + n * n);
                found = true;
                break;
            }
            k += 2;
        }
    }
    if (found) {
        break;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.