COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
reasoning mathematically about the algorithm
|
|
|
reasoning formally about the algorithm
|
|
|
by testing an implementation of the algorithm.
|
|
|
using multiple computers to run the algorithm.
|
Detailed explanation-1: -Formal reasoning. The only way to prove the correctness of an algorithm over all possible inputs is by reasoning formally or mathematically about it. One form of reasoning is a “proof by induction", a technique that’s also used by mathematicians to prove properties of numerical sequences.
Detailed explanation-2: -The proof consists of three steps: first prove that insert is correct, then prove that isort’ is correct, and finally prove that isort is correct. Each step relies on the result from the previous step.
Detailed explanation-3: -Mathematical induction is a very useful method for proving the correctness of recursive algorithms.
Detailed explanation-4: -In theoretical computer science, an algorithm is correct with respect to a specification if it behaves as specified. Best explored is functional correctness, which refers to the input-output behavior of the algorithm (i.e., for each input it produces an output satisfying the specification).