Background Competency Test Answers

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.”

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