CSCI 570 Homework 1 Due Date Sep 8 2024 at 11 59 P M 1 Arrange these functions under the Big O notation in increasing order of growth rate with g n following f n in your list if and only if f n O g n here log x is the natural logarithm1 of x with the base being the Euler s number e n n nlog n n log log n n log n 2log n log2 n log n 1 log n Taking logarithms of all we have n n log log nlog n log2 n 1 n log n 2 log n n 2 log n log log n log n log log log n 1 log n log n 1 log n 1 log n log 2log n log n log 2 log 2 log n log log2 n 2 log log n log n cid 112 log n log log n log log n 1 2 log log n cid 112 log n log log n log 2 log n log n log log log n log2 n log n n 2 Based on these for LARGE n using We can order all these functions as follows log n log log2 n log log n log n 1 log n log log n log nlog n log log n log 2log n n n Rubrics 10 points 3 points Missing process or explanation 1https en wikipedia org wiki Natural logarithm 1 point Each incorrect order maximum 7 points for completely incorrect order F4 F3 F2 3 Prove by induction that Fn 2 1 cid 80 n 2 The Fibonacci sequence F1 F2 F3 is defined as follows F1 F2 1 and Fn Fn 1 Fn 2 for n 3 For example F3 F2 F1 2 and i 1 Fi for n 1 Base case When n 1 1 Inductive hypothesis Assume that Fk 2 1 cid 80 k Fi 1 F1 1 1 2 F3 i 1 Induction step For n k 1 i 1 Fi for n k Fk 3 Fk 2 Fk 1 by definition Fk 1 1 Fi by inductive hyphothesis 1 cid 88 k cid 88 i 1 k 1 cid 88 i 1 1 Fi Rubrics 10 points 3 points Base case 2 points Inductive hypothesis 5 points Induction step 3 Given a connected graph G V E and a specific vertex u V Suppose we compute a DFS tree rooted at u and obtain a tree T that includes all nodes of G Suppose we then compute a BFS tree rooted at u and obtain the same tree T Prove by contradiction that G has the same structure as T that is G cannot contain any edges that do not belong to T Hint You can use the fact that if T is a BFS tree of G V E and x y E then in T the levels of x and y differ by at most 1 Suppose G doesn t have the same structure as T Then there exists an edge x y E such that x y T a By the fact that T is a DFS tree x is ancestor of y or y is ancestor of x Since x y T then the levels of x and y differ by at least 2 To prove this assume x is the ancestor of y and that x has a lower level say i Now consider the the moment when an edge incident to x is examined Since x y E but x y T there must be another edge x z E to be added to the DFS tree T first Then following the process of exploring the DFS tree node y will be added to T later Thus the level of y should be at least i 2 If y is the ancestor of x a similar argument applies b By the fact that T is a BFS tree we know that the levels of x and y differ by at most 1 We can prove this by contradiction Suppose the levels of x and y differ by more than 1 and without loss of generality assume x has a lower level say i Now consider the the moment when the edges incident to x are examined Since x y E y is one of the nodes discovered from x at this moment and thus belongs to level i 1 or a lower level This contradicts the assumption that their levels differ by more than 1 and y has a higher level which completes the proof Combining these two shows that x y is an edge in T which contradicts the assumption Rubrics 10 points 1 point Correct assumption for contradiction 4 points State a 4 points State b 1 point Correct conclusion by contradiction Full marks can also be obtained by using other correct methods 4 Given an unweighted undirected and connected graph G V E Con struct an algorithm to determine maximum of the shortest path distances between all pairs of nodes in G also called the diameter of the graph Also determine the time complexity of your algorithm and justify your answer Run BFS from each node as source node in G and determine the maxi mum layer reached while running BFS from that node In every iteration of BFS keep updating maximum layer reached keeping the maximum value Return the highest maximum layer reached would be the diam eter of the graph Worst case time complexity O V V E Since BFS from a single node takes O V E time and we perform BFS from O V nodes Rubrics 10 points 6 points Correct algorithm pseudocode can also receive full marks 2 points Correct corresponding time complexity 2 points Correct explanation for the time complexity Full marks can also be obtained by constructing other correct algorithm with the corresponding time complexity 5 Given an unweighted and undirected graph G V E and an edge e E Construct an algorithm to determine whether the graph G has a cycle containing that specific given edge e Also determine the time complexity of your algorithm and justify your answer Note To become eligible for full credits on this problem the running time of your algorithm should be bounded by O V E Let the two nodes forming the edge e be s and t Delete e from the graph G and run BFS or DFS starting from s If t can be reached on running BFS or DFS from s then there is a cycle in the graph containing edge e Time complexity O V E This is because BFS or DFS takes O V E time Rubrics 10 points 6 points Correct algorithm pseudocode can also receive full marks 2 points Correct time complexity must be bounded by O V E 2 points Correct explanation for the time complexity Full marks can also be obtained by constructing other correct algorithm with time complexity bounded by O V E 6 A directed graph G V E is singly connected if u v implies that G contains at most one simple path …