Operating Systems Background Competency Test

In my Operating Systems class, we took a Background Competency Test written by my teacher to test our abilities and knowledge on proofs, big-O notation and programming.

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?

For the answers, see our next post!