Programming 1, 2020-21
Week 8: Exercises

1. Cycle

Write a function cycle that takes a list of length N representing a permutation of the integers 0, …, N – 1. The function should return True if the permutation is a single cycle. For example:

• cycle([2, 3, 1, 0]) is True because the permutation

  0 -> 2
  1 -> 3
  2 -> 1
  3 -> 0

  is a cycle (0 -> 2 -> 1 -> 3 -> 0).

• cycle([2, 3, 0, 1]) is False because the permutation

  0 -> 2
  1 -> 3
  2 -> 0
  3 -> 1

  is not a cycle (0 -> 2 -> 0, 1 -> 3 -> 1).

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

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

4. Duplicate Values

1. Write a function that takes a list of integers and returns True if there are any duplicate values in the list. Use sorting to accomplish this task. Do not modify the original list.

2. Write a function with the same behavior, using a set to accomplish the task.

3. Which implementation do you think will be faster on a large list in the best case? In the worst case?

4. As an experiment, generate a list of 1,000,000 integers in the range from 1 to 1,000,000,000, then call both of the above functions on your list. How does the exection time compare?

5. Modify the experiment so that all the integers your generated list are unique. Now run both functions on your list. How does the execution time compare?

5. Vector Class

Write a class Vector that represents a vector in n-dimensional space.

• Provide an initializer that takes a list of numbers, yielding a vector with those components.

• The '+' operator should add two vectors.

• The '*' operator should multiply a scalar times a vector, yielding a new vector.

• The '*' operator should compute the dot product of two vectors, yielding a scalar.

• Provide a method v.length() that computes the length of a vector.

• Provide a method v.angle(w) that computes the angle between two vectors in radians.

• A vector should have a string representation such as "[3.25 5.02 -6.12]", with two digits after the decimal point in each component.

6. Grep

The well-known utility 'grep' prints all lines in a file that contain a given string:

$ grep world ulysses
Gleams that untravell'd world whose margin fades 
'T is not too late to seek a newer world.
$

If you include the '-i' option, it matches lines without regard to case:

$ grep -i achilles ulysses
And see the great Achilles, whom we knew.

Write 'grep' in Python:

$ python3 grep.py -i achilles ulysses
And see the great Achilles, whom we knew.

7. Functions and Classes

Write a program that reads a Python source file and reports the names of all functions and classes defined in the file. Do not count methods as functions.