17BCI0035_VL2017185002397_DA.  Indiana University, Bloomington AST 05

DIGITAL ASSIGNMENT-1
NAME: VASUDHA GROVER
REGISTRATION NO: 17BCI0035
SLOT: G1
COURSE: DATA STRUCTURES AND ALGORITHMS
Q1. For any 3 algorithms, explain proof of correctness.
A1. Example 1: Linear Search
Algorithm:
i=1;
while (a[i]!=x && i<=n)
i+=1;
if(a[i]==x)
return i;
else
return 0;
Proof of Correctness by Loop Invariants
Loop Invariant (I): 1<= I <= n ^ a[i]==x
Initialization: Before the first iteration, i=1. This implies that all the values
before a[1] are not the target values, proving that the loop invariant holds prior
to the loop’s first iteration.
Maintenance: For any i, the loop repeats all the elements before a[i] is not the
target value. Therefore, from a[1] to a[i-1], the invarian