1. We talked in lecture about the idea that it is very useful to study an algorithm to try to find an "invariant" for th

[answerhappygod]

1 We Talked In Lecture About The Idea That It Is Very Useful To Study An Algorithm To Try To Find An Invariant For Th 1 (290.37 KiB) Viewed 135 times

1. We talked in lecture about the idea that it is very useful to study an algorithm to try to find an "invariant" for the algorithm, which is informally defined as some property that is true for each iteration of the algorithm or at some key point in the processing of the algorithm. It is especially valuable to find invariants for algorithms we are in the middle of designing. And the invariants we are the most interested in right now are the ones that point to an understanding of why the algorithm always returns a correct answer. This problem invites you to demonstrate your ability to translate your understanding of algorithms into a good candidate for an invariant for each of several relatively simple algorithms. For each of the following algorithms discussed in lecture, give a precise and concise description of an invariant for the algorithm that would support an argument about the correctness of the algorithm: Example: Selection Sort Solution: One very good invariant for SelectionSort would be: "After iteration I, the first I entries of the array are sorted, and they contain the first I entries of the final result of the fully sorted array." (a) InsertionSort (b) BubbleSort (c) Interval Task Partitioning