Week 6: Exercises

1. List Running Time

Suppose that a is a list, with len(a) = N. How long will each of these operations take asymptotically, as a function of N, in the best/worst case?

  1. a[len(a) / 2] += 100

  2. del a[0]

  3. del a[-1]

  4. 100 in a

  5. a.append(100)

  6. a += [100, 101]

  7. a = a + [100, 101]

  8. sum(a[:1_000_000])

  9. sum(a[1_000_000:])

  10. a.insert(0.9 * len(a), 100)

  11. a.sort()

2. Printing with Commas

Write a program that reads an integer, and writes it out with embedded commas. Do not use string interpolation or the format() method.

Input:

28470562348756298345

Output:

28,470,562,348,756,298,345

3. Column with Largest Number

Write a program that reads a square matrix of integers. The program should print the largest value in the matrix and the column number that contains it.

Input:

2 8 3
9 6 7
0 3 -1

Output:

Column 1 contains 9.

4. Symmetric Matrix

A matrix M is symmetric if Mij = Mji for all i and j. For example, here is a symmetric matrix:

1 2 3
2 5 4
3 4 6

Write a function that takes a square matrix M represented as a list of lists, and returns True if the matrix is symmetric.

5. Largest Row or Column Sum

Write a program that reads a square matrix of integers. The program should print the largest sum of any row or column in the matrix.

Input:

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

Output:

32

6. Matrix Sum

Write a function that computes the sum of two matrices A and B, represented as lists of lists. Assert that the matrices have the same dimensions.

7. Matrix Product

Write a function that computes the product of two matrices A and B, represented as lists of lists. Assert that the matrices have dimensions that are compatible for multiplication.