Mark the following statements as TRUE or FALSE. No need to provide any justification.
[ TRUE/FALSE ]
In a connected undirected graph, and using the same starting point, the depth of any
DFS tree is at least as much as the depth of any BFS tree.
[ TRUE/FALSE ]
Algorithm A has a running time of Ө() and algorithm B has a running time of Ө(n log n). From this we can conclude that A can never run faster than B on the same input set.
[ TRUE/FALSE ]
Let T be a complete binary tree with n nodes. Finding a path from the root of T to a
given vertex v ∈ T using breadth-first search takes O(log n) time.
[ TRUE/FALSE ]
Amortized cost of operations in a Fibonacci heap is at least as good as the worst case
cost of those same operations in a binomial heap.
[ TRUE/FALSE ]
Master’s Theorem can be used to calculate the running time of any recursive function.
[ TRUE/FALSE ]
Dijkstra’s shortest path algorithm can be used to find shortest path in graphs with any
edge weights.
[ TRUE/FALSE ]
Function f(n)= 5n24n + 6n43n is O(n43n) .
[ TRUE/FALSE ]
Stable Matching: Suppose Jack prefers Rose to others, and Rose prefers Jack to
others. The pair (Jack, Rose) exists in every stable matching.
[ TRUE/FALSE ]
A DFS tree is a spanning tree.
[ TRUE/FALSE ]
A binary max-heap can be built using an unsorted list of elements in O(n) time
Suppose that you want to get from vertex s to vertex t in a connected undirected graph G = (V; E) with positive edge costs, but you would like to stop by vertex u if it is possible to do so without increasing the length of your path by more than a
factor of α.
a- Describe an efficient algorithm in O( |E| log |V| ) time that would determine an optimal s-t path given your preference for stopping at u along the way if doing so is not prohibitively costly. (In other words, your algorithm should either return the shortest path from s to t, or the shortest path from s to t containing u, depending
on the situation.) If it helps, imagine that there are free burgers at u!
b- Show that your algorithm runs in O( |E| log |V| ).
Assume the coastline of the country Lyniera is an infinite straight line. There are islands off the coastline of Lyniera. In order to keep a close eye on these islands, the king of Lyniera decided to set up some radar bases along the coastline. Each radar base is a point on the coastline which can cover a circular area around itself with radius d. Let’s use the x-axis in a coordinate system as the coastline (horizontal axis), with the sea on the upper side of the x-axis. Each island is a point in the sea with coordinates (x, y). Design a greedy algorithm to find the minimum number of radar bases needed to cover all the islands and give their locations on the coastline. Prove the correctness of your algorithm. (Assume each island is within distance d of the coast.)
Solve the following recurrences using the Master Method. You do not need to justify your answers, but any justification that you provide will help when assigning partial credit.
i. T(n)=8T(n/2)+nlogn
ii. T(n)=4T(n/2)+n2(logn)2
iii. T(n)=2T(n/2)+ n3(logn)3
In the MERGE-SORT algorithm we merge two sorted lists into one sorted list in O(n)
time. Describe an O(n log k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. Be sure to explain why your algorithm runs in O(n log k)-time.
Indicate for each pair of expressions (A,B) in the table below, whether A is O, Ω, or
Ө of B (in other words, whether A=O(B), A= Ω(B), or A= Ө (B)). Assume that k and C are positive constants. You can mark each box with Yes or No. No justification needed.
(Note: log is base 2)
A B O Ω Θ
n^3+logn+n^2 Cn^3
n^2 Cn*2^log(n)
2^n*2^k n^(2k)
Design an algorithm which, given an undirected graph G = (V, E) and a particular edge e ∈ E determines whether G has a cycle containing e. The running time should be bounded by O(|V | + |E|). Explain why your algorithm runs in O(|V | + |E|) time.
Given the undirected graph shown below:
9 E
3
B 7
4 5 6 F
A 5 D 2
5 5
3 G
C 4
6
5 H
a- Use Prim’s algorithm to obtain an MST of this graph. Use A as your starting point. Show the final MST and indicate the order in which you selected the edges
b- Use Kruskal’s algorithm to obtain an MST. Show the final MST and indicate the order in which you selected the edges
c- Is the MST in this graph unique? If yes, explain why. If no, show edges that can
be part of an MST but don’t have to be part of every MST.