Lab 10

Overview

The goal of this lab is to use graphs determine whether a given series of statements about time intervals are logically consistent with each other. Each of these statements tell you something about the relationship between arbitrary intervals, but do not contain any information about the start and end times of intervals.

Concretely, all of the statements are of two forms:

1. X ends before Y starts.
2. X and Y overlap.

You should assume that every interval has nonzero length.

Defining logical consistency

A series of statements are logically consistent if it is possible to create a set of start and end times to assign to each interval such that all statements are simultaneously true.

Step 1: Develop intuitions about inconsistent statements

Explain why the following set of statements are inconsistent.

• A overlaps with B
• B ends before C starts
• C overlaps with D
• D ends before A starts

Step 2: Develop intuitions about consistent statements

Come up with start and end times for intervals A, B, C, D, E and F such that the following statements are simultaneously true.

• A overlaps with B
• B overlaps with C
• A ends before C starts
• C ends before D starts
• D overlaps with E
• E ends before F starts

Step 3: Representing the statements

How can you use graphs to represent the two types of statements? Here are some questions that might help:

• How many vertices would you need per statement?
• What are the different relationships between vertices that you need to represent? How can you represent these with edges?

Step 4: Algorithm design

Design an efficient algorithm that takes a collection of statements as described above and tries to assign consistent start and end times to each interval. As output, your algorithm should either return a (start, end) pair for every interval to demonstrate consistency, or it should report that no consistent time assignment is possible.

In your writeup include:

1. Description of your algorithm
2. An analysis of time and space complexity of this algorithm to determine the consistency of n different statements.

Step 5: Submit the writeup

• Create one markdown file per group with all of the required details outlined in the previous section. (You can use https://demo.hedgedoc.org/new if that worked for you last time)

• Each group member should submit the same markdown file to Moodle. In the submission comment add a link to the hedgedoc file and also indicate who you worked with.