Week 4: Exercises

1. Input Words

Write a program that counts the number of words on all input lines. (For this exercise and other exercises on this page, consider a word to be any sequence of printable characters.)

2. Longest Word

Write a program that prints the longest word found on any input line.

3. 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.)

4. 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: ***

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

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

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

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

9. Matrix Sum

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

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

11. Largest product in a series

Solve Project Euler's problem 8:

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Read the input number as a series of lines from standard input.

12. Special Pythagorean triplet

Solve Project Euler's problem 9:

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.