Questions: Checkpoint 4 — Contest 4 Practice

A directed graph has vertices {A, B, C, D, E} and edges {AB, AE, BC, CA, CD, DA, DE, EB}. The edge AB goes from A to B.

How many different cycles does the graph contain? A cycle must follow the direction of the edges and visits no vertex twice, except that it ends where it started. Each cycle is counted once, whichever vertex it is written from: ABCA, BCAB and CABC are the same cycle.

A directed graph has this adjacency matrix, where the entry in row i and column j is 1 when there is an edge from i to j:

How many paths of length 3 go from C to E? A path follows the direction of the edges and may repeat vertices and edges, as the entries of M³ count them.

Find all ordered triples (A,B,C) that make this circuit TRUE.

INPUTS A B C
p = XOR(A, B)
q = NOT(C)
r = NAND(p, q)
out = AND(r, B)

Write the expression of this circuit, and simplify it as a sum of products with the fewest terms and then the fewest letters.

INPUTS A B C
p = NOR(A, B)
q = AND(A, C)
r = OR(p, q)
out = XNOR(r, C)

This program is written in ACSL pseudocode. Remember ACSL's substring rules: S[:n] is the first n characters, S[n:] is the last n characters, and S[a:b] is positions a through b, both included. Positions start at 0, and a FOR loop includes its end value.

S = "WATERMELON"
T = S[:1]
FOR j = 1 TO 3
   T = T + S[j:j + 1] + S[j:]
NEXT j
OUTPUT T, len(T)

What exactly is output?

This program is in Python, so Python's slicing rules apply. % is the remainder.

A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
S = "ZEBRA"
T = ""
for j in range(len(S)):
    k = 0
    while A[k] != S[j]:
        k = k + 1
    T = T + A[(k + j) % 26]
print(T, T[1:4])

What exactly does the program print?

ACC starts at 0, and every DC line sets its location before the program runs. After this program runs, what number is in the location Z?

X     DC    -23
Y     DC    4
Z     DC    0
      LOAD  X
      DIV   Y
      STORE Z
      MULT  Y
      SUB   X
      MULT  =-1
      ADD   Z
      STORE Z
      END

The input numbers are 7, 15, 3, 10, 22 and −1, in that order. What does this program print?

C     DC    0
LOOP  READ  N
      LOAD  N
      BL    DONE
      SUB   =10
      BG    BIG
      LOAD  C
      ADD   N
      STORE C
      BU    LOOP
BIG   PRINT N
      BU    LOOP
DONE  PRINT C
      END

The vertices of a directed graph are capital letters, and the edge AB goes from A to B. A route is a list of vertices written together, such as ABCA. Using the words of Unit 12, every route is exactly one of these kinds:

• NOT A PATH: somewhere in the route, a vertex is not joined to the next one by an edge going that way.
• CYCLE: a path that ends at the vertex where it started, with no other vertex appearing twice. In a directed graph a cycle may have just two vertices: ABA is a cycle when AB and BA are both edges.
• SIMPLE PATH: a path in which no vertex appears twice.
• PATH: any other path, which visits some vertex more than once.

The first line of input holds the vertex letters, in alphabetical order, run together (such as ABCDE). The second line holds the edges, separated by single spaces, each written as two letters. The third line holds R, the number of routes. Each of the next R lines holds one route.

Print one line for each route, in order: its kind, written exactly as above.

Constraints

• There are between 2 and 26 vertices: different capital letters, in alphabetical order. They need not start at A.
• There are between 1 and 200 edges, and every edge joins two vertices of the first line.
• No edge joins a vertex to itself, and no edge appears twice. AB and BA may both appear: they are two different edges.
• 1 <= R <= 400, and every route has between 2 and 30 letters, each a vertex of the first line.

Sample Input

ABCDE
AB BC CA CD DB DE EA
6
ABCA
DEAB
ABCDBC
ACDE
ABCABCA
CDEABC

Sample Output

CYCLE
SIMPLE PATH
PATH
NOT A PATH
PATH
CYCLE

ABCDBC follows the edges but visits B and C twice, so it is a path but not a simple path. ACDE fails at its first step: the edge between A and C is CA, which goes the other way. ABCABCA ends where it started, but it goes round the triangle twice, so it is a path, not a cycle.