Question

Loop invariants:
Consider the following Python function that merges two sorted lists.
Here is a loop invariant for loop 1:
“the contents ofnewlistare in sorted order,newlistcontainsaelements oflistAandbelements oflistB”

def mergeSortedLists(listA, listB):

　newlist = [ ]

　a = 0

　b = 0

　# loop 1

　while a < len(listA) and b < len(listB):

　　if listA[a] < listB[b]:

　　　newlist.append(listA[a])

　　　a +=1

　　else:

　　　newlist.append(listB[b])

　　　b +=1

　if a < len(listA):

　　newlist.extend(listA[a:])

　if b < len(listB):

　　newlist.extend(listB[b:])

　return newlist

(a) Write down (in regular English) a pre-condition for the function. What important property needs to be true about the input in order for this function to work correctly?[1 marks]
(b) Write down (in regular English) a post-condition for the function. What do we want this function to return?[1 marks]
(c) Give an argument to show that the loop invariant is true before loop 1 is entered for the first time.[2 marks]
(d) Give an argument to show that, if the loop invariant is true upon entry to an arbitrary iteration of loop 1, it remains true after that iteration of the loop.[2 marks]
(e) Write down (in regular English) a post-condition for loop 1. What is established by the loop invariant and the loop exit condition upon exit from loop 1?[2 marks]
(f) Give an argument to show that your post-condition for loop 1, along with action of the code following the loop, infers your post-condition for the function.

Answer 1

a)  A pre-condition for the input should be that the list should contain numeric values only. If we use strings, the side effect will be because of the function extend as a string is an iterable, so if you extend a list with a string, you’ll append each character as you iterate over the string.

Example:

my_list = ['chegg','study']

my_list.extend('expert')

print my_list

So, the output will be ['chegg','study','e','x','p','e','r','t']

b)  We want this function to return the contents of the lists in sorted order. As we have performed the operations and our newlist is ready to be returned. We can return its contents as string by using str(newlist).

c) An argument to show that the loop invariant is true before loop 1 is entered for the first time.

listA = [1, 5, 6, 9]

listB = [3, 4, 7, 8, 10]

Here: a = 0 < len(listA) & b = 0 < len(listB), so it will enter the loop 1.

d) Same above example can be used for this scenario also:

listA = [1, 5, 6, 9]

listB = [3, 4, 7, 8, 10]

In 1st iteration:

a = 0 and b = 0, listA[a] = 1 and listB[b] = 3

As  listA[a] < listB[b], a will become 1 and newList = [ 1 ]

In 2nd iteration:

a = 1 and b = 0, which means a < len(listA) & b < len(listB) so it remains true after iteration of the loop.

e)  Loop exit condition is that if any one of the list is fully traversed, i.e. all the elements of any of the listA or listB are included in the new list then the while loop shall exit.

f)  In same example,

listA = [1, 5, 6, 9]

listB = [3, 4, 7, 8, 10]

After 8th iteration:

a = 4 and b = 3, which means a is not less than len(listA) as newList would have become [1, 3, 4, 5, 6, 7, 8, 9] containing all the elements of listA, so while loop will exit and the following code will start executing.

if b < len(listB):

newlist.extend(listB[b:])

After this code, newList will become [1, 3, 4, 5, 6, 7, 8, 9, 10]