Lab 5: Tracking Variables

What is a Tracking Variable?

We have seen that one or more accumulation variables play an essential role in many loops for accumulating a result-so-far in the loop.

But many loops also require additional "helper variables" in order to perform the iteration correctly. These variables, known as tracking variables, keep track of important pieces of information from the past iterations performed so far. They might hold previous values in the sequence, or some accumulated information that is not itself the final result being accumulated, but is helpful for determining the final result.

Indeed, the fact that a loop might need one or more tracking variables is part of what makes loop design and implementation so challenging. It's often tricky to predict exactly what information needs to be stored in tracking variables in order for the loop to do its job. (This is why iteration tables are so important; they give the loop designer a concrete way to think about what tracking variables might be helpful for a particular iteration.

An Example: The isSorted Function

A good exanple of the need for a tracking variable is an isSorted function, which, given a list of numbers, returns True if the numbers are sorted in ascending order, and otherwise returns False. For example

>>> isSorted([3, 5, 8, 9, 12, 12 17])
True

>>> isSorted([3, 5, 9, 8, 12, 12, 17])
False

>>> isSorted([5])
True

>>> isSorted([])
True

Note that a list of numbers is sorted as long as there are no inversions, which are consecutive numbers in which the first is strictly greater than the second. Each inversion is a constructive proof that the list is not sorted. A list without any inversions is considered sorted, which is why isSorted returns true when called on a singleton list or an empty list.

Some psuedocode for the definition of the isSorted function is

We'll see later in the Index Loops section that we can use an index loop to find consecutive elements in the list. In general, it's preferable to write value loops rather than index loops (because index calculations can be error-prone). But a value loop will only have access to current number being visited in the list; how do we access the previous number (i.e., the number right before the current number)?

The answer is: we use a tracking variable to remember the value of the number from the previous iteration!

Below is a correct definition of isSorted based on this idea, where comments underscore the key notions: 

def isSorted(nums):
    if len(nums) < 2: # Take care of the small special cases first! 
        return True
    prev = nums[0] # Initialize prev tracking variable to first number in list 
    for n in nums[1:]: # Iterate over list starting with second number in list 
        if prev > n:     # If we find an inversion ...
            return False # ... return True immediately
        prev = n # The current num in this iteration becomes prev
                 # for the next iteration 
    return True # Return true if all numbers processed w/o finding an inversion

Table of Contents