Let's see how you do:

**1. Prove that n is odd iff n^2 is odd.**

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

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

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?

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())?

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);

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?

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

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

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?

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())?

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);

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?

**For the answers, see our next post!**

## 0 comments:

## Post a Comment