Question 7 - 10 points Given an array A = [4, 0, 6, 7, 2, 5, 9, 3] and want to use quick sort to sort the array. Assume you always pick the last element at partition pivot. Show results after each step and final output.

Exercise 2. FAST FOURIER TRANSFORM. The objective is to compute all the coefficients of the product of two polynomials P and Q that are both of the generic form where the pj's and qij's are given coefficients. One step in this procedure requires the computation of P at the N2 points (wi,wi) for 0 ≤i, j≤N-1, where N is a power of two, and w = exp(2πi/N) is an N-th root of unity. Taking inspiration from Tukey's solution, show how this can be done efficiently, derive the recurrence for the RAM model complexity of your algorithm, and obtain the worst-case time in 0 () notation. Finally, without repeating the details, give the recurrence and its solution for the d-dimensional version of this problem (i.e., replace (z,y) by a d-dimensional vector).

Exercise 1. DIVIDE-AND-CONQUER: DESIGNING A COVID TESTING STRATEGY. A total of n vacationers are on a cruise ship but it is suspected that there is a COVID outbreak, and the number of COVID testing kits is severely limited. We need to identify the infected passengers as efficiently as possible. Each passenger has an unlimited amount of snot, all carefully collected and kept in separate jars. Snot of different passengers can be combined in one test. Design a strategy that insures that all k sick people can be found while using not more than O(1+ klog₂ (2n/k)) tests, where 0 ≤ k ≤n is not known beforehand.

Recursive Mania. Suppose an algorithm has worst-case time complexity given by the following recurrence relation: T(n) = T(n-1)+4n²-n+c₂ for n> 1 and T(1) = c₂. Solve the recurrence relation T(n) and give its order using Big-Oh notation, using iterative/repeated substitution. You must explain how you solved the recurrence relation. You might find one of the closed-form expressions listed in the "[Optional] Mathematics for Algorithm Analysis"

ADVERSARIAL 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 (as in the previous exercise). Describe how you would organize the oracle to obtain a lower bound by the method of adversaries. Your lower bound should be c'n for some explicit constant d (which is not necessarily the same constant as in the previous exercise).

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.

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.

Is the sequence < 23, 7, 14, 6, 13, 10, 1, 5, 17, 12 > a max-heap? If not, show all the steps to heapify the sequence. Show that the worst-case running time to heapify a sequence of size n is Ω (logn).

Let G = (V, E) be a connected graph. Suppose a depth-first search from a specific node u € V produces a tree T that includes all nodes of G. Additionally, let a breadth-first search from the same node u result in the same tree T. Prove that G cannot contain any edges that do not belong to T. Hint: proof by contradiction.

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++;