Data Structures and Algorithms:

Computer Science Java.

Please show the steps how the answer is obtained and justify the reasoning.

1.A

1.B.

1.C

What is the cost function for the following algorithm? input: A[n], B[n] output: dot product of A and B sum = 0 for i = 0... n sum = sum + A[i] * B[i] return sum 2n + 6 6n + 2 6n^2 + 2n + 2 What is the cost function for the following algorithm? input: vals (n] output: median value of vals for i = 0 ... n / 2 for j = 0 Page 1 j] > vals (n - i - 1] t = vals[j] vals[j] vals [n - i - 1] = t i if = vals [n - i - 1] %3! return vals [n/2] 5n + 2 (9/4)n + 5 n^2 + 5n + 2 (9/4)n^2 + 5n + 2 What is the cost function for the following algorithm? input: S[n], T[k] // String of length n and token of length k output: location of T in S, or -1 for i = 0 ... n - k for i = 0 if S[i + j] != T[j] break if j == k %3D return Page 1 return -1 6kn - 6k^2 + 4n - 4k +1 6kn - 6n^2 + 4n 4k +1 6n^2 - 6k^2 + 4n - 4k +1 6n^2 + 4n +1