I encountered the following question:

  1. Provide a definition of the semantic correctness of algorithm $A$ with respect to pre-condition $\alpha$ and post-condition $\beta$. A well-presented precise and complete definition is expected.

  2. Explain the difference between the total correctness and the partial correctness.

Can someone explain both of these to me or point me in the direction with good material on this topic? I somewhat understand the second question in the sense that partial correctness does not require/make the algorithm terminate and total correctness = partial correctness + termination, but that's it.

  • 3
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX). Give proper attribution to the source where you encountered this! $\endgroup$ – D.W. Nov 25 '19 at 4:25
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Nov 25 '19 at 4:25
  • $\begingroup$ Please ask only one question per post. If you have two questions, ask them separately in two different posts. Thank you! $\endgroup$ – D.W. Nov 25 '19 at 4:25

The correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification, in this case, starting from the pre-condition $\alpha$ if the algorithm executes and land in states described by $\beta$ where the pre-condition is as weakest as possible and post-condition is as strongest as possible. The algorithm is said to be correct. Proof of Correctness can be proved using invariants. Refer this for more information about Hoare logic and program correctness.

A distinction is made between partial correctness, which requires that if an answer is returned it will be correct, and total correctness, which additionally requires that the algorithm terminates. Refer this for more info.

Hope this helps!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.