8)

Algorithm Min2 (All..)n ifi r else Algorithm Min1 (fo-1) //Input: An array A[O..n -1] of real numbers /Input: An array All....] of real numbers return A[O] return Al else temp Mini (Af0.n-2]) if temp s A[n -1] return temp tempi Min2 (A [1 1 (l + r)/2] ] ) temp2 Min2 (A [ 1(l + r)/21+1 r] ) if templ s temp2 else return templ return Aln - 1 return temp2 8. Traverse the graph given in the Figure 8 using Depth First Search (DFS) and construct the option corresponding depth first search tree specifying tree edges and back edges. Give the order in which the vertices were reached for the first time (pushed onto the traversal stack) and the order in which vertices become dead ends (popped off the stack). Start the traversal at vertex A and resolve the ties by vertex alphabetical order. 2 Figure 8 Consider the problem of counting, in a given text, the number of substrings that start with an A and end with a B. (For example, there are four such substrings in CABAAXBYA) (i) Design a brute-force algorithm for this problem and determine its efficiency class. i Design a more efficient algorithm for this nroblem 9. 2+1