##### 🍐 我们总结了加拿大代写中——CS代写的经典案例，如果你有任何代写的需要，可以随时联络我们。CoursePear™ From @2009。

1. (10 marks) Consider the following recurrence.
Deadline: Tuesday, October 19, 2021 before 10:00 AM (to be delivered in BrightSpace)
T(n) = (5 n n n if 1  n  3, 2n+T 3 +T 4 +T 5 ifn>3.
(a) (2 marks) What is the solution to this recurrence? Your answer must be as precise as possible. You must write your answer using the big-O notation.
(b) (8 marks) Prove that your answer is correct. You must use a proof by induction. You cannot use the Master Theorem. You must justify every step of your proof.
2. (10 marks) Let G = (V,E) be an undirected graph and e 2 E be an edge of G. We denote by G {e} the graph obtained from G by deleting e. Here is an example.
e
G G{e}
An edge e = {a,b} 2 E is said to be critical if there is no path between a and b in
G{e}.
Design a deterministic algorithm to solve the following problem.

input: An undirected graph G = (V,E), stored using adjacency lists, together with an edge e = {a,b} 2 E.
output: CRITICAL if e is critical. Otherwise, return NOT.
Your algorithm must be deterministic. Your algorithm must take O(|V | + |E|) time. You must describe your algorithm in plain English (no pseudocode) and you must ex- plain why the running time of your algorithm is O(|V | + |E|).

CoursePear™提供各类学术服务，Essay代写Assignment代写Exam / Quiz助攻Dissertation / Thesis代写Problem Set代做等。