Week 4: Exercises

1. Building a List

In the lecture, we considered these two programs:

(1)

n = int(input('Enter n: '))
a = []
for i in range(n):
    a.append(i)

(2)

n = int(input('Enter n: '))
a = []
for i in range(n):
    a = a + [i]

We found that program 1 runs in O(N), and program 2 runs in O(N2), an important difference.

Now consider this third program:

(3)

n = int(input('Enter n: '))
a = []
for i in range(n):
    a += [i]

Do you think it will run in O(N), or O(N2)? Perform an experiment to find out which is the case.

(Recall that on lists += is a synonym for Python's extend() method.)

2. Word Length Histogram

Write a program that prints a histogram of the lengths of all words found in all input lines. For example, if the input is

there is a big green tree
in the park
on a sunny day

the program's output might look like this:

1: **
2: ***
3: ***
4: **
5: ***

You may assume that all words found in the input will be at most 30 characters long.

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. Identity Matrix

The identity matrix of size N x N contains ones along its main diagonal, and zeroes everywhere else. For example, here is the identity matrix of size 4 x 4:

1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

Write a function identity_matrix(n) that returns the identity matrix of size n x n, represented as a list of lists.

6. 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

7. Matrix Sum

Write a function that takes two matrices, and returns the sum of the matrices. Assume that the matrices have the same dimensions.

8. Matrix Product

Write a function that takes two matrices, and returns the product of the matrices. Assume that the matrices have dimensions that are compatible for multiplication.