Linear Search is one of those algorithms that is easy to conceive of, but why are...

 

Transcribed Image Text:

Linear Search is one of those algorithms that is easy to conceive of, but why are you convinced that it works? // Post: . . int Linear Search(int arr [], int len, int target) { for (int i = 0; i < len; i++) { // Assert: if (arr[i] target) return i; } return -1; } The Problems: (a) [5 marks] Complete the post condition. (b) [5 marks] Complete the assertion. You will have the correct assertion if you answer yes to the following two questions: Does the assertion describe what you know is true after you've run the ith loop? Does the assertion relate to your postcondition? (c) [10 marks] Prove the algorithm is correct using a proof by induction. Linear Search is one of those algorithms that is easy to conceive of, but why are you convinced that it works? // Post: . . int Linear Search(int arr [], int len, int target) { for (int i = 0; i < len; i++) { // Assert: if (arr[i] target) return i; } return -1; } The Problems: (a) [5 marks] Complete the post condition. (b) [5 marks] Complete the assertion. You will have the correct assertion if you answer yes to the following two questions: Does the assertion describe what you know is true after you've run the ith loop? Does the assertion relate to your postcondition? (c) [10 marks] Prove the algorithm is correct using a proof by induction.