**1. Prove that n is odd iff n2 is odd.**

Assume n is odd, then it can be written as k : n=2k+1, and n2=(2k+1)2 = 4k2+4k+1 is odd.

Assume n2 is odd, then assume that n is even. Since n is even, it can be written such that k : n = 2k. n2=4k2which is even. But that contradicts that n2is odd, then n must be odd.

2. Let A, B be sets. Prove that A-B = AB.

By definition, A-B = AB = AB.

3. Prove or disprove the following statement: “an undirected graph of n nodes and n edges contains a cycle.”

Assume n is odd, then it can be written as k : n=2k+1, and n2=(2k+1)2 = 4k2+4k+1 is odd.

Assume n2 is odd, then assume that n is even. Since n is even, it can be written such that k : n = 2k. n2=4k2which is even. But that contradicts that n2is odd, then n must be odd.

2. Let A, B be sets. Prove that A-B = AB.

By definition, A-B = AB = AB.

3. Prove or disprove the following statement: “an undirected graph of n nodes and n edges contains a cycle.”

**Look into generalizing the problem.**

4. If an algorithm A calls an algorithm B with a complexity of calls O(f(n)), and algorithm B has itself a complexity of O(g(n)), which is the overall combined complexity?

O(f(n)g(n))

5. If a C-language function functionA() has a complexity of O(f(n)) and functionB() has a complexity of O(g(n)), what is the complexity of functionA(functionB())?

O(f(n) + g(n))

6. What is the complexity, in Big-O notation, of variable assignments of the following code?

k = 1;

do {

j = n;

do {

j = j/2;

k++;

} while ( j < 1);

} while (k < n);

O(n + ln n) =O(n)

7. Consider an arbitrary binary tree where each node is programmed as a C-struct node { int key; struct node * left; struct node * right;} Write a recursive function sum() that when called on the tree’s root, ie. sum(root), it returns the sum of all keys in the leaves of the tree. You may use C-like pseudocode. What is your algorithm’s worst case complexity, in Big-O notation?

function sum(struct node * n) {

if (n==NULL) return 0;

else if (node->left == NULL && node->right == NULL) {

return node->key;

} else {

return sum(node->left) + sum(node->right);

}

}

4. If an algorithm A calls an algorithm B with a complexity of calls O(f(n)), and algorithm B has itself a complexity of O(g(n)), which is the overall combined complexity?

O(f(n)g(n))

5. If a C-language function functionA() has a complexity of O(f(n)) and functionB() has a complexity of O(g(n)), what is the complexity of functionA(functionB())?

O(f(n) + g(n))

6. What is the complexity, in Big-O notation, of variable assignments of the following code?

k = 1;

do {

j = n;

do {

j = j/2;

k++;

} while ( j < 1);

} while (k < n);

O(n + ln n) =O(n)

7. Consider an arbitrary binary tree where each node is programmed as a C-struct node { int key; struct node * left; struct node * right;} Write a recursive function sum() that when called on the tree’s root, ie. sum(root), it returns the sum of all keys in the leaves of the tree. You may use C-like pseudocode. What is your algorithm’s worst case complexity, in Big-O notation?

function sum(struct node * n) {

if (n==NULL) return 0;

else if (node->left == NULL && node->right == NULL) {

return node->key;

} else {

return sum(node->left) + sum(node->right);

}

}

## 0 comments:

## Post a Comment