- Find the closed form of the following recurrence relation. What is the asymptotic behavior of T in Big Oh notation?
T(0) = 1
T(1) = 2
T(k) = 2T(k-1) + 3T(k-2) + 1 - For the following algorithm, find a recurrence relation which describes the best-case runtime. What is the runtime complexity in Big Oh notation?
function foo(arr)
for i = 1 -> len(list) do (2 s)
for j = 1 -> len(list) do (2 s)
if arr[i] < arr[j] then (1 s)
swap(arr[i], arr[j]) (4 s)
end
end
end
end - Explain why the algorithm in question 2 above could be considered a "selection sort".
- Assume a single-linked list is composed of nodes with "next" pointers. Write C/C++ code to remove node "p":
void remove(node *p) {
...
} - What is the runtime complexity of remove(pos) for a dynamic array (e.g. std::vector)? Explain why.
- What data structure would you use to implement a queue? Why?
- What data structure would you use to implement a stack? Why?
- Say you are writing a program to keep track of attendance in a class. What data structure would you use to keep track of the students who attended for a given day? How much memory does your data structure need? What operations do you need and what are their runtime complexities?
- Use Bubble Sort on the following list of integers. Show each swap. How many swaps are required?
1 4 5 3 2 7
- Imagine a magic black box (an "oracle") which somehow computes the optimal quicksort pivot in constant time. Explain why this is impossible for muggle machines.
|
|
