Is O(2^n) equal to O(3^n)? Why?
No. O(f(n)) = O(g(n)) if and only if f(n)/g(n) is bounded between two positive real numbers for all sufficiently large values of n; but as n increases, the ratio 2^n / 3^n tends to zero.
What is the expected run-time of quicksort? What is the worst-case run-time?
The expected run-time of quicksort (for random inputs) is O(n log n). The worst-case run-time of quicksort is O(n^2).
What is the difference between a binary tree (that should be binary search tree) and a B-tree? When and why does this difference matter?
Internal nodes in a binary tree have at most two children, while internal nodes in a B-tree can have many children (depending on the block size). This is useful when the tree data is stored in a manner which exhibits large read latencies (e.g., on disk) since the higher fan-out means that the height of a B-tree is less than the height of a corresponding binary tree.
Name the heap operations used by heapsort and the asymptotic running time of each.
There are two operations: Heapify, which takes n elements and builds a heap out of them in O(n) time; and pop-max, which deletes the largest element from the heap and returns it in O(log n) time.
Describe an algorithm that determines if a graph is bipartite.
Attempt to 2-colour the graph as follows:
- Pick an uncoloured vertex; if there are none remaining, return success.
- Colour that vertex red.
- Perform a graph traversal (depth-first search and breadth-first search both work) starting from the vertex we picked. Every time we reach a vertex, colour it green if all its coloured neighbours are red, or red if all of its coloured neighbours are green; if it has both red and green neighbours, return failure.
- Go to step 1.
The graph is bipartite if and only if the 2-colouring algorithm did not fail.
