# ES242. Data Structures and Algorithms I. Exam 01

## ES242. Data Structures and Algorithms I.

##### Exam 01

Issued: 16 Feb, 2023

::: Problem 4. A Bit of a Graph

The bit strings of length four are given by:

`0000`

, `0001`

, `0010`

, `0011`

, `0100`

, `0101`

, `0110`

, `0111`

, `1000`

, `1001`

, `1010`

, `1011`

, `1100`

, `1101`

, `1110`

, `1111`

.

Consider a graph where we have:

- a vertex for every bit string of length
*four*, and let us say that the bit string associated with a vertex u is denoted by b_u; and - an edge from u to v if the corresponding bit strings are such that the last three bits of b_u is the same as the first three bits of b_v.

For example, we will have an edge from the vertex representing `0010`

to the vertex representing `0101`

. We will also have an edge from the vertex representing `0010`

to the vertex representing `0100`

.

:::