VIKING-CALC(A) 1: output= -4 2: for in-1; i > 0; i-i-4 do 3: 4: 5: 6:...

 

Transcribed Image Text:

VIKING-CALC(A) 1: output= -4 2: for in-1; i > 0; i-i-4 do 3: 4: 5: 6: 7: 8: return output key= A[i] test =A[i -2] condition = A[i - 3] if test x key output = output + test x condition == (key x condition) then D CL ▷ C2 DC3 ▷ CA ▷ C5 ▷ C6 D C7 D C8 Part a: Explain (in prose) what VIKING-CALC does. Part b: What is the return value of VIKING-CALC when A={3,2,4,2,1,1,3,2,1,2,2,6,3,2,3,4}. Part c: Under what conditions does line 7 get executed the fewest number of times? Under what conditions does line 7 get executed the most number of times? Part d: What is the total cost run-time, T(n), of VIKING-CALC? Parte : What is T(n) for VIKING-CALC when line 7 is executed the fewest number of times possible? Please provide your answer in the most simplified form possible. Part f: What is T(n) for VIKING-CALC when line 7 is executed the most number of times possible? Please provide your answer in the most simplified form possible. Part g: What is the worst case total cost run-time of VIKING-CALC in Big-O notation? Part h: What is the best case total cost run-time of VIKING-CALC in Big-O notation? VIKING-CALC(A) 1: output= -4 2: for in-1; i > 0; i-i-4 do 3: 4: 5: 6: 7: 8: return output key= A[i] test =A[i -2] condition = A[i - 3] if test x key output = output + test x condition == (key x condition) then D CL ▷ C2 DC3 ▷ CA ▷ C5 ▷ C6 D C7 D C8 Part a: Explain (in prose) what VIKING-CALC does. Part b: What is the return value of VIKING-CALC when A={3,2,4,2,1,1,3,2,1,2,2,6,3,2,3,4}. Part c: Under what conditions does line 7 get executed the fewest number of times? Under what conditions does line 7 get executed the most number of times? Part d: What is the total cost run-time, T(n), of VIKING-CALC? Parte : What is T(n) for VIKING-CALC when line 7 is executed the fewest number of times possible? Please provide your answer in the most simplified form possible. Part f: What is T(n) for VIKING-CALC when line 7 is executed the most number of times possible? Please provide your answer in the most simplified form possible. Part g: What is the worst case total cost run-time of VIKING-CALC in Big-O notation? Part h: What is the best case total cost run-time of VIKING-CALC in Big-O notation?

Answer rating: 100% (QA)

Part a Explanation of VIKINGCALC The given code VIKINGCALC is a pseudocode representation of an algorithm that processes an array A The algorithm iter... View the full answer