Lecture Overview

Introduction to Algorithms.

• Examples of algorithms: making change for a given amount of money, the shortest path problem.
• When studying algorithms, we are interested in
  • Figuring out how to solve a problem without having to deal with the details of how it is implemented in python; instead we describe the solution informally using English and/or what is called pseudocode.
  • Proof of correctness: a proof that the algorithm works correctly on every possible input. Also, we are interested in proofs of properties of the algorithms, such as that the algorithm to make change always uses the fewest number of coins.
  • Common algorithm techniques: many problems share similarities and so we would like a bag of tricks to use when presented with a new problem. For example, solving a Rubik's cube is similar to the shortest path problem, where "cities" are positions of the Rubik's cube and "roads" are the possible rotations that transition one position of the cube to another.
  • Estimate of the speed: Many times we have multiple algorithms to solve a problem and would like a rough estimate of the speed of each. For example, the coin changing problem can be solved by generating a list of all possible ways of making change, sorting the list by the number of coins, and picking the way of making change that uses the smallest number of coins. This algorithm happens to be slower than the greedy algorithm.

Selection Sort

Here is selection sort as an example of the above points. Selection sort has the following pseudocode (Note that python and pseudocode are very similar and this isn't an accident; pseudocode is old and when the python developers were designing the language they used pseudocode as an inspiration.)

1
2
3
4
5
6
7
8
9
10
11
12

for i in 0 to L.length - 1
    # Find the smallest element among positions i to L.length-1
    min_idx = i
    for j in i+1 to L.length - 1
        if L[j] < L[min_idx]
           min_idx = j
       endif
    endfor

   # move the smallest found into position i
   swap L[i] with L[min_idx]
endfor

Informal Proof of Correctness

Selection sort works by progressively making the slice L[0...i] of the list the i-th smallest elements in sorted order (recall that list slicing is up to but not including the top index) until the entire list is sorted. So say L[0...i] is the i-smallest elements in sorted order and we want to extend this to L[0..(i+1)]. What we need to do is search all the elements from i to the end of the list and find the smallest among them. Whatever element is found to be the smallest is moved into position. The body of the loop over i carries out this task: it first finds the smallest element (lines 3-8) and then swaps the smallest found into position (line 11). To find the smallest element, we loop over j, comparing the smallest found so far with the element at index j.

An informal argument of the above type is what we do 99% of the time. The above paragraph argued that the algorithm always produces a sorted list no matter the input and while it didn't mention every detail it was (hopefully) enough convince you. We are lazy and only want to explain enough so that we are convinced the algorithm works. This is dangerous because maybe there is an error somewhere in a detail we didn't mention, but we don't notice this because we ignored some details. For newbies to these types of proof, it is very hard to know when a detail should be left out or if it needs to be explained. One detail which was omitted is why the loop over j can start at i+1 instead of i.

Formal Proof of Correctness

For comparison, here is a more formal proof of correctness. It mentions more details and so you can be more certain there is no error that you have overlooked, but it is more work to both write and read. The proof of correctness works via loop invariants, which are statements which are true throughout every iteration of the loop.

• I claim the following is always true: between lines 4 and 5, L[min_idx] is the smallest element from among L[i...j] (remember this slice does not include j). This statement is called a loop invariant.
  • To prove this loop invariant, we prove two things.
  • Initialization: the loop invariant is true at the beginning of the loop. The beginning of the loop is when j = i+1 and min_idx = i, so the loop invariant states that L[i] is the smallest element from among L[i..(i+1)] = L[i] which is true.
  • Maintenance: the body of the loop (including the increment of the loop index j) preserves the invariant. We know that between lines 4 and 5, L[min_idx] is the smallest from among L[i..j]. The body of the loop checks if L[j] is smaller than L[min_idx] and if so sets min_idx to j, so between lines 7 and 8 we know that L[min_idx] is the smallest from among L[i..(j+1)]. When j is incremented when the loop rolls around, the loop invariant will still be true between lines 4 and 5.
  • We therefore get to conclude that the invariant is true after the loop is over, which happens when j=len(L). In this case, substituting j=len(L) into the loop invariant, we know that on line 9 L[min_idx] is the smallest from among L[i..len(L)].
• I claim the following is true: between lines 1 and 2, the entries L[0..i] are the i-th smallest elements of L in sorted order.
  • Again to prove this loop invariant, we check initialization and maintenance.
  • Initialization: at init, i = 0 so the invariant states that L[0..0] are the 0-th smallest elements in sorted order. This is true since the list slice is empty (recall it is up to but not including the top index).
  • Maintenance: By the previous argument, we know that at line 9 L[min_idx] is the smallest from among L[i..]. By swapping it into position L[i], we now know that between lines 11 and 12, L[0..(i+1)] are the (i+1)-th smallest elements in sorted order. When the loop rolls around, the loop invariant will therefore be maintained.
  • We therefore get to conclude the invariant is true after the loop is over which happens when i=len(L). By substituting i=len(L) into the loop invariant, we know that L[0..len(L)] is the len(L)-th smallest elements in sorted order, i.e. the list L is sorted.

Speed

I show how we estimate the speed of this algorithm next time.

Exercises

• Design an algorithm for determining the day of the week of any date since January 1, 1900. For example, November 16, 2015 is a Monday and January 1, 1900 is also a Monday. Give the psuedocode (not python) for the algorithm and a brief description of why it works (it doesn't need to be as detailed as my argument for selection sort above). Remember that in pseudocode you don't need to explain every detail, for example you don't need to say how a day of the week is stored. You can just say things like "the weekday 3 days after Sunday".

• Design an algorithm that, given a list of integers, finds the two smallest elements in the list without sorting the entire list. Give the pseudocode and a brief argument for why it works (it doesn't need to be as detailed as my argument above). Hint: the answer is similar to selection sort above, but of course does not sort the entire list.