Question 820 points In the algorithm D-SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Explain why it works or does not work in linear time.

Using a loop invariant, show that the following code segment computes Sum = N³. Sum = 0; for (i = 0; i < N; i++) for (j = 0; j <N*N; j++) Sum++;

Describe a linear-time algorithm for computing a topological order of a DAG (b) A triangle in a graph G = (V, E) is a set of three distinct vertices u, v, w €V such that all three edges {u,v}, {u,w} and {v,w} exist in E. Show an algorithm that detects whether G has a triangle in time better than 0(³),where n = |V| is the number of vertices in the graph.[8 marks] (c) Define the ORTHOGONAL VECTORS problem (OV) and the Strong Exponential-Time Hypothesis (SETH), and state the connection between SETH and OV. (d) Illustrate the reduction from ORTHOGONAL VECTORS to graph diameter on the following input to OV: Set A contains vectors 1010, 1001, 0011, 0111, 1110 Set B contains vectors 1100, 1011, 0011, 1110, 1010 Draw the resulting graph and explain how the diameter of the resulting graph is connected to the status of the OV instance. Also state what implications this has for computing the diameter of a graph.

(10 pts.) Suppose you are given an array A[1...n] of integers which can be positive, negative or 0. Asub-array is a contiguous sequence of elements from A. In particular, for any two indexes i and j with 1 ≤ i ≤ j ≤ n, A[ij] is the sub-array that starts at index i and ends at j. The sum of the sub-array A[i] is the sum of all the numbers it contains: A[i] + A[i + 1] + ..... + A[j]. For example, ifA = [5, 1, -3, -2, 4, 0], the sum of A[03] is 1 and the sum of A[14] is 0. Given A, design a divide-and-conquer algorithm, running in O(n log n) time, to find the sub-array of minimum sum. For example, in the array A = [5, 1, -3, -2, 4, 0], the sub-array of minimum sum is A[2, 3] with sum -5. You will need to describe your algorithm (please refer to "Describing an Algorithm" on top for more instructions), prove the correctness of your algorithm, and analyze the running time of your algorithm.

1. Estimate the asymptotics of the following recurrence relations. You may use the master theorem. \text { (a) } T(n)=3 T(n / 3)+O(n) \text { (b) } T(n)=8 T(n / 2)+O\left(n^{2}\right) \text { (c) } T(n)=T(n / 3)+O(\sqrt{n}) \text { (d) } T(n)=2 T(n / 4)+O(\sqrt{n})

(a) Use the dynamic programming algorithm seen in the course to compute the edit distance between the strings "carrot" and "crow". Also provide the actual edits.[6 marks] (b) State the worst-case running time of the algorithm in Question 2a, for strings of size n and m.[4 marks] (c) Outline how the algorithm can be made to run faster for instances where the strings are similar, i.e., the edit distance is small.[6 marks] (d) Figure 1 shows a directed graph with an s-t flow of value 2 (thick edges). Allarcs have capacity 1. i. Construct the residual flow network. ii. Is the flow a max-flow? Justify your answer. (e) Describe a method for computing an s-t min-cut given an s-t max-flow, in a directed graph D.[6 marks]

4. The following equation describes the recurrence underlying our dynamic programming algorithm for Edit Distance for the case of operations COPY (cost 0), INSERT (cost 2), DELETE (cost 2) and REPLACE (cost 3). Here, as in the course, c[i,j] describes entry (i.j) of the dynamic programming table, 7₂ is character number i of the input string and y; is character number j of the output string, 1 <i<m and 1≤j≤n. ci-1.j-1] c[i,j] = min 3+ci-1.j-1] if i = 0 and j = 0 if i > 0, j>0 and z = 95 ifi>0 and j> 0 if i > 0 if j > 0 2+ci-1.j (2+ci.j-1] Describe a modification of the equation to incorporate the following operation:

2. (a) A company named RT&T has a network of n stations connected by m high-speed communication links. Each customer's phone is connected to one station in his or her area. The engineers of RT&T have developed a prototype video-phone system that allows two customers to see each other during a phone call. In order to have acceptable image quality, however, the number of links used to transmit video signals between the two parties cannot exceed 4. Suppose that RT&T's network is represented by a graph. Design an efficient algorithm that computes, for each station, the set of stations it can reach using no more than 4 links.

DECISION TREE LOWER BOUND. We are given 3n + 2 distinct numbers and are asked to find the (n+1)-st and (2n + 2)-nd smallest using a binary oracle. (i) Derive the decision tree lower bound for this problem (exactly-not in big oh notation). (ii) Show that as no, the lower bound is cn for some constant c (where means that the ratio of left and right-hand-side tends to one), and determine c.

Question 6 - 20 points Given an array A = [23, -10, 14, -20, 16, -8, 12, -2] and we want to find the sum of maximum subarray (1) Explain how the divide and conquer algorithm solve this problem. Show level by level results and final result. (2) Explain how the dynamic programming algorithm solve this problem. Show how you fill the memorization table and get the final result.