CMSI 2130: Final Exam

Problem	You got	Out of
1		10
2		10
3		10
4		10
5		10
6		10
7		10
8		10
9		10
10		10
TOTAL		100

Let $f(n)=n^3$ and $g(n)=n^2(\log_2{n})^{12}$. Is $f$ in $O(g)$, $\Omega(g)$, or $\Theta(g)$? At what value of $n$ does one function overtake the other one for good?
So you’re reading this fancy paper on algorithms and you see a small snippet of code. It’s a recursive algorithm, with a small enough number of recursive calls that you can count them on two hands. The paper says that complexity of the algorithm is “obviously $\Theta(n^{2.58496250072})$.” Explain the structure of the algorithm and how this “obvious” value was obtained.
One of the freshman tried to do RSA. The student chose $p=87$, $q=73$, and correctly computed $N=6351$. However, the student forgot to compute $(p-1)(q-1)$ and instead picked $e=5$ and computed $d$ as the modular inverse of $e$ and $N$. What value of $d$ arose from this mistake? Show the value that results from encrypting then decrypting the message $200$, e.g. compute $200^e \bmod N$ then decrypt the result. If this works, explain why we have to compute $(p-1)(q-1)$ in “regular” RSA. If not, why don’t you get the original message back?
Consider the undirected, weighted graph with vertices $\{A, B, C, D, E, F\}$ and edges $(A,B,5)$, $(B,D,6)$, $(B,C,1)$, $(A,C,3)$, $(F,E,2)$, $(D,E,2)$, $(E,C,8)$, $(A,E,1)$, and $(C,D,1)$. Again, please note the graph is undirected.
1. Draw the graph.
2. Which edges are bridges?
3. Which nodes are articulation points?
4. Enumerate the nodes in depth-first order, starting at $A$, always choosing the node that comes first in alphabetical order whenever you have a choice.
5. Enumerate the nodes in breadth-first order, starting at $A$, always choosing the node that comes first in alphabetical order whenever you have a choice.
For the graph in the previous problem:
1. What order are edges added to a MST, using Kruskal’s algorithm?
2. What order are nodes added to a MST, using Prim’s algorithm? Always using alphabetical order whenever you have an arbitrary choice to make.
3. What is the shortest path from $B$ to $F$?
4. Is there a Hamilton Cycle? If so, name one. If not, why not?
5. Is there a Hamilton Path? If so, name one. If not, why not?
6. Is there an Euler Trail? If so, name one. If not, why not?
One of the freshman ran Dijkstra’s single-source shortest path algorithm starting from $A$ on the directed graph with edges $(A,B,7)$, $(A,E,4)$, $(A,F,5)$, $(F,C,-15)$, $(E,B,1)$, $(C,D,4)$, and $(E,D,2)$. Did the student get the right answer? What would happen if the edge from $A$ to $F$ were reweighted to 8?

Fill out the bottom-up dynamic programming table for the 0-1 knapsack problem given a 15kg sack and the following items:

Item A, 2 kg, value = $7.
Item B, 3 kg, value = $10.
Item C, 5 kg, value = $18.
Item D, 6 kg, value = $20.

Process them in alphabetical order.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
A
A,B
A,B,C
A,B,C,D

Show the development of the search tree for the top-down version in the last problem. Mark the points in the search tree where you would use a pre-computed result.

What graph algorithm is this? Why does it work?

def mystery(g):
    def helper(n, s):
        if len(s) == g.order:
            return True
        for m in n.adjacent_nodes():
            if m not in s:
                helper(m, s.union({m}))
        return False
    for n in g.nodes:
        if helper(n, {n}):
            return True
    return False

An algorithm with complexity function $T(n) = n^4$ can process a 16-element list on our PC in 256 seconds.
1. How much time is needed to process a 32-element list?
2. If we ran the algorithm on a machine that was 1024 times faster than our PC, how large of a list could we process in one day? (Note 1 day = 86400 seconds)
3. If we needed a computer that could process 100 elements in a minute, how much faster than our original PC does this computer need to be?