Lab 10 - List operations and algorithms¶

Part 1: List methods¶

Lists and strings are very similar. In both cases we can access individual elements using an index, and we can get a substring or sublist using slices. We can concatenate two lists together using the + operator.

The biggest difference is that, unlike strings, lists are mutable. You can use an index to assign a new value to an element of a list, you can add new elements to a list, and you can use the del keyword to remove an element.

You can find a summary of the most common list methods here http://interactivepython.org/runestone/static/thinkcspy/Lists/ListMethods.html

In addition to the methods, there are some keywords and operators that work with lists. We have seen del and + above. You can use the in keyword to determine whether an element occurs in a list.

And you can use the * operator to create a list of multiple copies of a given list. For example, here is an easy way to create a list containing 10 zeros:

However, the method you’ll use the most is append. As an example, recall that in class we saw how to read a bunch of numbers entered at the console and store them as a list. (That list could then be sorted to determine the median value, among other things.)

Part 2: Pencil and paper are a programmer’s best friend¶

When we are programming simple things, we can often get away with just writing some code and tinkering with it until it works. When writing loops involving lists and strings, what we are doing can be complex enough that we have to be a bit more careful to figure out exactly what we want our code to do, and think of ways to check.

We have seen some problem-solving strategies already:

• Write down concrete examples and do them by hand.
• Identify a related, simpler problem and solve it first.
• As you write code, think of ways to verify that it is correct, such as using codelens or printing out partial results.

Programmers use pseudocode to describe the basic steps of an algorithm, without getting into the details of variable names or correct Python syntax. What is pseudocode? Imagine you are explaining to your baby sister how to perform the steps of your solution. You should be able to explain the steps in a simple and direct enough way that your little sister can carry them out from your instructions, without understanding the problem you are trying to solve.

As an example, let’s work through solving the following problem: Is one list a sublist of another list? This is like a substring, but for lists. For example, using a list of integers, we might have:

haystack = [3, 2, 4, 3, 1, 2, 3]
needle = [3, 1, 2]

We would say that needle is a sublist of haystack, because there is a way to line them up so every element of needle is equal to the corresponding element of haystack

[3, 2, 4, 3, 1, 2, 3]
         [3, 1, 2]

On the other hand, what if

haystack = [3, 2, 4, 1, 3, 2, 3]
needle = [3, 2, 1]

We can try all possible ways to line them up by shifting the needle over to the right:

[3, 2, 4, 1, 3, 2, 3]
[3, 2, 1]

[3, 2, 4, 1, 3, 2, 3]
   [3, 2, 1]

[3, 2, 4, 1, 3, 2, 3]
      [3, 2, 1]

[3, 2, 4, 1, 3, 2, 3]
         [3, 2, 1]

[3, 2, 4, 1, 3, 2, 3]
            [3, 2, 1]

But no matter what, we can’t find a way to line them up so that all the corresponding elements match. So in this case needle is not a sublist of haystack.

This is looking complicated! Let’s try a simpler problem. What if we only had to check the first case? That is, we only worry about lining the two lists up at the beginning.

[3, 2, 4, 1, 3, 2, 3]
[3, 2, 1]

What do we have to do?

Check whether needle[0] is equal to haystack[0], ok, keep going.

Check whether needle[1] is equal to haystack[1], ok, keep going.

Check whether needle[2] is equal to haystack[2], nope, so the answer is no.

Describe this in pseudocode as

for each index in needle
    if the two elements at that index are different
        answer is False

And if we make it all the way through this loop, the answer must be true. Notice this is a search problem. We are “searching” for a pair of elements that don’t match.

What would be different if they are lined up some other way? Say we shift needle over by 4:

[3, 2, 4, 1, 3, 2, 3]
            [3, 2, 1]

Check whether needle[0] is equal to haystack[4], ok, keep going.

Check whether needle[1] is equal to haystack[5], ok, keep going.

Check whether needle[2] is equal to haystack[6], nope, so the answer is no.

Again in pseudocode,

for each index in needle
    if the needle[index] is different from haystack[index + shift]
        answer is False

Looks like we just have to add a amount to the haystack’s index to account for the amount shifted. Let’s try writing a real Python function that does just this much.

What’s needed to complete the algorithm? We just have to perform the steps above for each possible shift amount. If we find a shift amout for which everything matches, then we know the function returns True. If we don’t find one, the function returns False. (Another search problem!)

for each possible shift amount
    if everything matches using that shift (*)
        return True
return False

(()())()

())()(()

(((()))

            (  (  )  (  )  )  (  )
lefts:      1  2  2  3  3  3  4  4
rights:     0  0  1  1  2  3  3  4

[5, 4, 4, 2, 3, 4, 4, 4, 2, 2, 3, 4]

5            4            4           2           ...
count 1      count 1      count 2     count 1
max 1        max 1        max 2       max 2