DFS Applications

Question: how do you learn the ideas from an algorithm? What kind of work shows that you understand it?

Connected Components

  1. Use BFS or DFS to determine if an undirected graph is connected. Inputs: number of vertices, adjacency list.

    1. Output v1: how many connected components are there?
    2. Output v2: a dictionary that takes in vertices and outputs the “component number” that contains the vertex. Number components consecutively starting from 1.
    3. Testing: include at least three test cases that demonstrate your code works.

Cut Vertices 1: Brute Force

An “articulation vertex” or “cut vertex” results in the number of components of the graph increasing when it is removed. Your goal here is to find a list of all of the cut vertices.

  1. Write a brute-force algorithm to find the cut vertices in a graph G. This means for each vertex $v$, check the number of connected components of the graph $G-{v}$, which is G with the vertex v and all edges to and from it removed.
  2. In terms of the number of vertices (V) and edges (E), how fast is the brute-force algorithm? Explain. Use big-O notation.

Cut Vertices 2: Good Way

  1. DFS modification: add in a dictionary that records the vertex with the earliest “in time” that you can reach from a node.

Problem Set Stops

Only the problems above are on the problem set.

Upcoming

  1. (Outline) Explain in words the idea for an efficient cut-vertex finder using the “earliest reachable ancestor” idea. Include a sentence or diagram explaining each of the situations, and why there are no more.
  2. Write an efficient algorithm to find all of the cut vertices in a graph.
  3. Test your algorithm on cases that contain all of the cases you have from the “Outline” step above.

Notes: Personal Software Process

Companies keep track of bugs to identify patterns in mistakes. They do a “root cause analysis” to figure out what happened, then they change the way they work to avoid those causes (as much as possible). One example: Google determined the io_uring kernel module was the source of too many exploits, so they disabled it on Android. If you keep track of your bugs, even informally, you will also learn when to be careful. You might even decide it’s worth the effort of writing tests!

How do you do this? Every time you find a bug, write down one or two lines in a text file. Identify the bug and what caused it.

For example, here are three entries for my binary_search.

  • binary_search: high was set to be length, should be length-1 I had no documentation so I did not know which “high” meant.
  • binary_search: had two different variables with similar names, low and c_low. Used the wrong one.
  • binary_search: another 10 min of debugging finds two more similar errors 2 errors found from careful testing

Programming: Formatting Using Black

Black is a “very opinionated” Python code formatter. It will make your code follow a lot of code style rules.

In the shell window:

  • Before: pip install black
  • Reformat: black main.py
Last modified October 2, 2023: DFS Applications: Problem Set 2. (f2f1501)