Assignment 4

Contents

Assignment 4#

Dave Friedman
CMPSC 465 Algorithms and Data Structures

1#

A ticket machine accepts a ticket of nonnegative integer value \(t\) and prints two tickets of nonnegative integer values \(t^2 \mod 400\) and \(t^2 + 1 \mod 400\) only one of which you may accept. For example, the ticket machine accepts a ticket \(103\) and prints two tickets \(209 = 103^2 \mod 400\) and \(210 = 103^2 + 1 \mod 400\).

If you start with a ticket \(1\) is it possible to obtain a ticket \(20\)?

In the terms of graphs, ticket values are represented by vertices. If \(t\) is a nonnegative integer modulo \(400\) then it is a value between \(0\) and \(399\). The exchange mechanism is represented by edges directed from the input value \(t\) to two output values \(t^2 \,\text{mod}\, 400\) and \(t^2 + 1 \,\text{mod}\, 400\). In the terms of graphs, we want to know whether vertex \(20\) is reachable from vertex \(1\).

\( \begin{aligned} V &= \{ 0, \dotsc, 399\} \\ |V| &= 400 \\ E &= \{ (t, t^2 \,\text{mod}\, 400) \} \cup \{ (t, (t^2 + 1) \,\text{mod}\, 400) \} \\ |E| &= 800 \\ \end {aligned} \)

\( \begin{aligned} t &\to t^2 \,\text{mod}\, 400, (t^2 + 1) \,\text{mod}\, 400 \\ 1 &\to 1, 2 \\ 2 &\to 4, 5 \\ 4 &\to 16, 17 \\ 5 &\to 25, 26 \\ 16 &\to 256, 257 \\ 17 &\to 289, 290 \\ \vdots \end {aligned} \)

2#

2A#

The visual representation of a reverse graph \(G_R\) of a directed graph \(G\) is just the same graph with the directed edges reversed.

\(G\)

A : B, C
B : C
C : B
D : E, F, K
E :
F : G
G : H
H : D
I : K
J : I
K : J

\(G_R\)

A :
B : A, C
C : A, B
D : H
E : D
F : D
G : F
H : G
I : J
J : K
K : D, I

TRAVERSE(G, v)
 1    visit(v)
 2    global pre[v] = clock
 3    global clock++
 4
 5    foreach (v, vx) in E
 6        if visited(v)
 7            continue
 8        TRAVERSE(G, vx)
 9
10    global post[v] = clock
11    global clock++

DFS_WITH_TIMING(G)
1    global clock = 1
2    foreach v in V
3        if visited(v)
4            continue
5        TRAVERSE(G, v)

3#

Consider a directed graph \(G = (V, E)\) and a particular vertex \(v \in V\) and edge \(e = (a, b) \in E\). Design an algorithm that runs in \(\Theta(|V| + |E|)\) time that can determine whether there is a cycle within \(G\) that contains both \(v\) and \(e\).

Contents