contents    up   

CSCI 0190 · Fall 2026

Finding Paul🔗

    1 What is This Assignment’s Purpose?

    2 Theme Song

    3 Problem Setup

    4 Assignment

    5 Testing

    6 Built-Ins

    7 Starter

1 What is This Assignment’s Purpose?🔗

In this assignment, you will get some practice working with matrix representations of graph concepts.

You will also work with two different representations for the same data, and hence different algorithms for them. To confirm that despite these differences they implement the same behavior, you will use PBT to cross-validate.

Finally, you will also be set up for subsequent work on program proofs.

2 Theme Song🔗

Paul Revere by Noah Kahan

3 Problem Setup🔗

Read the essay Using Metadata to Find Paul Revere.

4 Assignment🔗

Consume a table where the rows are people and the columns are organizations. You will produces two matrices.

The key idea in the essay is that the person-organization membership matrix, multiplied by its own transpose, give a person-person matrix, whose each entry counts shared organization memberships. (And dually, for shared people.)

Write two functions: p-by-p produces the person-by-person matrix, while o-by-o produces the organization-by-organization matrix. Because these are matrices, not tables, we will use a convention to assume that that rows and columns name the entities in the same order.

(While the centrality measures are very interesting, they require much more math than this course expects, so it would unfair to expect it of everyone.)

You will implement this in the following ways:

  1. Implement it using matrices:

    1. Implement the basic matrix operations yourself using a list-of-lists.

    2. Use Pyret’s matrices library. Compare the performance with your version!

  2. Compute this count directly by using filter and length.

Arguably, we can think of the latter as close to the definition of the operation, and the former as an alternate implementation in terms of matrices. (Though for people sufficiently at home in linear algebra, it may feel the other way around!)

Use these operations, with the full dataset from the paper, to make sure you get everything working right.

5 Testing🔗

When given two implementations of the same concept, we should confirm that they are in harmony. Do that by setting up:

  1. A PBT harness to check the two matrix implementations against each other.

  2. A PBT harness to check a given matrix implementation aginst the list implememtation.

For the latter, you will want to use the faster matrix implementation. But the latter combined with the former should help confirm that you could have used the slower one too and it would have produced the same answers (except over much more time!).

6 Built-Ins🔗

You should use the matrices library for the parts of the assignment that call for it. You can also use it to set up testing against other implementations.

You will also find the timing library useful for measuring relative performance.

7 Starter🔗

Starter (opens in a new tab)

    contents    up