AP Computer Science Principles · Unit 4 lecture · Part 7 of 11 · 7 min

4.2 Analyzing failuresFind the weak spot

Mr. Thompkins
Network questions on the exam are little logic puzzles. They come in four flavors, and once you know the method for each, they're some of the most reliable points on the test. Pencil out.
Question it asksHow to answer it
How many paths from X to Y?List them by first step, then second. No device twice in one path.
Can X still reach Y if this fails?Cross out the failed link (or every link of a failed device), then look for any path.
Minimum failures to cut X from Y?Try every single failure. If each has a detour, try pairs. Stop at the first size that works.
Is there a single point of failure?Look for one link or device that every path must cross.
The four kinds of network question, and the method for each.

Here's a network where a careless look gets the wrong answer. Every device has at least two connections, so it looks safe. And it is safe against any single broken connection. But look at device M in the middle.

HJKMNOQ
Two halves joined in the middle. Connections: H-J, H-K, J-K, J-M, K-M, M-N, M-O, N-Q, O-Q.

Every path from the left half (H, J, K) to the right half (N, O, Q) passes through M. So if device M fails, it takes J-M, K-M, M-N and M-O with it, and the halves are split. M is a single point of failure, even though no single connection is. That difference between a failed connection and a failed device is exactly what the exam likes to test.

XXXXHJKMNOQM is down
Device M fails, and all four of its connections go with it. H can still reach J and K, but nothing on the left can reach N, O or Q.
?Wait, what's a "select two" question?
In Section I, 8 of the 70 questions ask you to choose two answers out of four, and you need both right to earn the point. The best method is to judge each statement true or false on its own first, then pick the two trues.
Pause and think
In this network, how many connections would have to fail to cut H off from Q? Try a single failure first, then think about which pairs would do it.
I thought about it. Show me
Two. No single connection does it: each one has a detour. Pairs that work include H-J with H-K (isolating H), J-M with K-M, or M-N with M-O. Python checked all 36 possible pairs; six of them cut H off from Q.
A select-two network question
In the network shown, which TWO statements are true? I. If connection J-M fails, H can still communicate with Q. II. If device M fails, H can still communicate with Q. III. There are exactly two paths from N to O. IV. Connection N-Q is a single point of failure.
  1. Statement I: cross out J-M. H-K-M-N-Q still works. True.
    Why?
    One path is all you need to show "can still communicate".
  2. Statement II: cross out M and all four of its connections. Nothing joins the left half to the right half. False.
  3. Statement III: from N, you can go to M then O (N-M-O), or to Q then O (N-Q-O). Any other route would have to come back through M or Q, repeating a device. Exactly two. True.
  4. Statement IV: cross out N-Q. Q still connects through O-Q, and everyone else is still connected. False.
    Why?
    A single point of failure has to break something on its own. N-Q doesn't.

Answer: I and III. The lesson of II: a network can survive any single broken connection and still have one device it cannot lose.

Stuck? Get a hint
  1. Take the statements one at a time and decide true or false for each.
  2. For II, remember that a failed device takes every one of its connections with it.
  3. For III, list the ways out of N: toward M or toward Q.
Check yourself
In the same network, which single failure would stop J from communicating with N?
  1. AConnection J-K
  2. BConnection M-N
  3. CDevice M
  4. DDevice K
Show the answer

C. Device M is on every path from the left half to the right half. Without connection M-N, J can still go J-M-O-Q-N. Without J-K or device K, J still reaches N through J-M-N. Treating a device like a single connection is the trap.

Check yourself
A network has these connections: A-B, B-C, C-D, D-A, and C-E. Which statement is true?
  1. ANo single failure can stop any device from communicating with any other
  2. BIf connection C-E fails, E can no longer communicate with A
  3. CThere is only one path from A to C
  4. DIf connection A-B fails, A can no longer communicate with C
Show the answer

B. E's only connection is C-E, so losing it cuts E off. A, B, C and D form a loop: A reaches C through B or through D, so the third and fourth choices are false, and the first is false because C-E (and device C) are single points of failure.

Exam tip from Mr. T

When a network is given as a list of connections, draw it before you read the choices. Then, for each statement, physically cross out what failed. Most wrong answers come from imagining a path through something that's already broken.

  • Count paths by first step, then second, with no device repeated.
  • Minimum failures: test singles, then pairs. The first size that works is the answer.
  • A device can be a single point of failure even when no single connection is.
  • Select two: judge each statement on its own, then pick the pair.