1. Consider the following algorithm, whi

Question

1. Consider the following algorithm, which takes as input n EN:
Initialize variables j = n and s = 0.
While j > 0, do the following:
Increment s by i
Decrement j by 1
Output the value of s.
Your task below is to prove (across several parts) that the above al-
gorithm computes the sum of the first n positive integers. Use the
following:
A
Pre-condition: ne N+ ján A
s=0
Post-condition: s= i
Loop invariant I: s= = {i=j+11
A MEN
(Let me remind you of a convention regarding summation notation: If
the lower limit is greater than the upper limit, then the sum is 0.)
(a) (2 points) Prove that the pre-condition implies I.
(b) (4 points) Prove that if I and the loop condition both hold right
before an iteration of the loop, then I holds right after the itera-
tion.

Kunduz · Accepted Answer

Giren conditions are:
DENT Ajan As=o (pre condition)
s.si
(post condition)
= {i=jt injen (loop conditions)
for prooving a,
belongs to natural numbers and given
that j = n .... it Natural numbers.
a
S:
for prooving by
if jao
jal »
j = 2 2 S=14243
S = 1+2
2 A
and these all belangs to W' as s is
increasing by j. .. I holds right after
iteration,

1. Consider the following algorithm, which takes as input n EN: Initialize variables j = n and s = 0. While j > 0, do the follow