Given a graph-G that has |V| vertices and |E| edges, that is:

• Connected.
• Directed.
• Weighted

What is the worst case time complexity to determine if there is an edge between vertex-u and vertex-v (incoming or outgoing), if G is implemented using adjacency matrix?

Recall the algorithm for shortest paths in an unweighted graph. We provide it below, as given in the course notes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function BFS(G = (V, E), s)
   dist[1..n] = ∞
   pred[1..n] = null
   queue = Queue()
   queue.push(s)
   dist[s] = 0
   while queue is not empty do
      u = queue.pop()
      for each vertex v adjacent to u do
         if dist[v] = ∞ then
            dist[v] = dist[u] + 1
            pred[v] = u
            queue.push(v)

Analyse this algorithm and provide:

• Its worst-case time complexity,
• Its auxiliary space complexity (excluding the input).

Assume the graph G is stored as an adjacency matrix. Make no assumption on the edge density of the graph.

Select one worst-case time complexity and one auxiliary space complexity from the list below. Two correct answers and zero incorrect answers are required to pass this question.

Pierre's microwave has keys to input reheating time, with possible positive times described by the set K. For instance, we could have K=\{1,10,60\}.

Pierre is wondering what the minimum number of keys to press to input the time t. Each key can be pressed multiple times.

For example, the minimum number of keys to press for a time t=25 is 7: pressing 10 twice and pressing 1 five times.

In order to solve this problem, we decompose the problem into subproblems defined as 

minPresses[t]= {the minimum number of key presses required to input a time t using keys from K}.

Give a recurrence relation for minPresses by giving all cases in the expression

minPresses[t] = \begin{cases} \text{first case}\\ \dots\\ \text{last case},

\end{cases}

(Recall that a recurrence relation needs at least one base case and one general case.)

Solve, in big-θ, the following recurrence relation

T(n) = 4 * T(n/4), where n >= 4
T(n) = c, where n = 1
for a constant c.

Given the following pseudocode, derive the recurrence relation that represents its time complexity. 

def fibonacci(n):
    if (n==0 or n==1):
        return n 
    return fibonacci(n - 1) + fibonacci(n - 2)

Let b and c represent constant values. What is the base case and recurrence step?