(1) In one short sentence explain what the purpose of the algorithm is. Be as sp

Question

(1) In one short sentence explain what the purpose of the algorithm is. Be as specific as possible by referring to program variables (e.g., P and S, and use simple math notation such as sets, sequences, etc.).

(2) Provide a proof of correctness by loop invariant. Be sure to clearly state the invariant.

4. Consider the following algorithm, where P and S are arrays of characters (i.e., strings), and answer the questions below. The -- notation represents logical negation (i.e., flip the proceeding variable value from true to false, or visa versa). Require: PlO,..,m-1], S1,..,n], for 1 1: f- false 2: =0 3: while (i n-m) AND do m Sn 5: f-true 6: for j 0;(j

Explanation / Answer

Important consition:- given two strings are NON-NULL.

1. The purpose of the given algorithm is find difference in length of given two strings. Function is returning a value (1 + difference in length of non-null strings).

2. Loop Invariant (i <= n-m) and (j < m AND f) is true throughout the algorithm, stages:-

        Initial stage:- Since i = 0 < n-m; TRUE

                             also j = 0 < m AND TRUE is logically 1

        Intermediate stage:- since outer loop is CONTROLLER loop, it is true at all intermediate stages also.

         Termination stage;- When value of 'i' will exceed the difference in length of two strings, loop will terminate.

The given function retuens a value (1 + difference in length of two strings).

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.