Recitation 5: Loop Invariants and Sets

Your instructor will guide you through these questions.

Part 1: Loop Invariants

Find the loop invariant of:

Before creating the formal loop invariants, think about what the functions do. How might you use that as you construct the invariants?

• the max(list) function.

# a_list is some list with at least one element
max = float('-inf')
for a in a_list:
    max = a > max ? a : max

• insertion sort.

for i in range(1, len(array)):
    temp = array[i]
    position = i
    while position > 0 and array[position-1] > temp:
        array[position] = array[position-1]
        position-=1
    array[position]=temp

• bubble sort.

for passes in range(len(array)-1, 0, -1):
    for i in range(passes):
        if array[i]>array[i+1]:
            array[i],array[i+1] = array[i+1],array[i]

Part 2: Sets

Sets

True or False:

• For every set A, A ⊆ A
• For every set A, A ⊂ A
• {1, 2, 3}={2, 3, 1}
• ∅ ⊂ A for all A

Let A = {a, b, c, d} What is P(A)?

Set of sets

A = {{1, 2, 3},{1, 2},∅,{1}}

• Is 1 ∈ A? Why or why not?
• Is {1, 2}∈A? Why or why not?
• Is {∅} ∈ A? Why or why not?
• What is P(A)?