1. (a) A mathematical property P is an invariant for the code fragment Code, if the...

 

Transcribed Image Text:

1. (a) A mathematical property P is an invariant for the code fragment Code, if the Triple: {P} Code {P} is true. Which of the following instances are true and which are false? In each case give values for the variables to support your answer. Property P x+y is even Code x+x+1 Property P x+Y A[i+1] then 4 SORTED false 5 return SORTED 1. Complete the above algorithm by replacing ? in lines 1 and 2, so that it satisfies the specification. [8 marks] [2 marks] [2 marks] ii. What is the complexity of this algorithm in notation? iii. How many times is line 3 executed in the best case? iv. Modify the algorithm to improve its best case performance. Give an example array which will demonstrate the improvement. [13 marks] 1. (a) A mathematical property P is an invariant for the code fragment Code, if the Triple: {P} Code {P} is true. Which of the following instances are true and which are false? In each case give values for the variables to support your answer. Property P x+y is even Code x+x+1 Property P x+Y A[i+1] then 4 SORTED false 5 return SORTED 1. Complete the above algorithm by replacing ? in lines 1 and 2, so that it satisfies the specification. [8 marks] [2 marks] [2 marks] ii. What is the complexity of this algorithm in notation? iii. How many times is line 3 executed in the best case? iv. Modify the algorithm to improve its best case performance. Give an example array which will demonstrate the improvement. [13 marks]