3.10. ExercisesΒΆ

  1. What is the result of each of the following:

    1. ‘Python’[1]
    2. “Strings are sequences of characters.”[5]
    3. len(“wonderful”)
    4. ‘Mystery’[:4]
    5. ‘p’ in ‘Pineapple’
    6. ‘apple’ in ‘Pineapple’
    7. ‘pear’ not in ‘Pineapple’
    8. ‘apple’ > ‘pineapple’
    9. ‘pineapple’ < ‘Peach’
    1. ‘Python’[1] = ‘y’
    2. ‘Strings are sequences of characters.’[5] = ‘g’
    3. len(‘wonderful’) = 9
    4. ‘Mystery’[:4] = ‘Myst’
    5. ‘p’ in ‘Pineapple’ = True
    6. ‘apple’ in ‘Pineapple’ = True
    7. ‘pear’ not in ‘Pineapple’ = True
    8. ‘apple’ > ‘pineapple’ = False
    9. ‘pineapple’ < ‘Peach’ = False
  1. Draw a reference diagram for a and b before and after the third line of the following python code is executed:

    a = [1, 2, 3]
    b = a[:]
    b[0] = 5
    
    Your diagram should show two variables referring to two different lists. a refers to the original list with 1,2, and 3. b refers to a list with 5,2, and 3 since the zero-eth element was replaced with 5.
    Show Comments
  1. Draw a reference diagram for a and b before and after the third line of the following python code is executed:

    a = [1, 2, 3]
    b = 2*a
    c = 3*b
    c[0] = 5
    
  1. Question: Determine the complexity of the following task: Sum up all the negative numbers in a list.
  1. Question: Determine the complexity of the following task: Count how many words in a list have length 5.

    Answer:

    To complete this task, we must

    1. visit each of the words in the list: \(n\) operations, each \(O(1)\).
    2. For each word, check if the word is longer than 5: \(n\) operations, each \(O(1)\).
    3. For each word larger than 5, add 1 to the count. Suppose there are \(m\) long words: \(m < n\) operations, each \(O(1)\).

    Thus the total complexity is \(n*O(1) + n*O(1) + m*O(1) < n*(3*O(1)) = O(n*1) = O(n)\)

  1. Determine the complexity of the following task: Add up all of the entries of an \(n\times n\) matrix
Next Section - 4. Expression-Oriented Sequence Transformations