Each vertex keeps track of three states: visited, in progress, done. We also keep track of when we going to enter it and when we are also be done

# initialize vertex.state = UNVISITED across graph

def dfs(vertex, currentTime):
    vertex.startTime = currentTime
    currentTime++

    vertex.state = IN_PROGRESS

    for v in vertex.neightbors:
        if v.state == UNVISITED: # to prevent loops
            currentTime = dfs(v, currentTime)
            currentTime += 1
    w.finishTime = currentTime
    w.state == DONE

    return currentTime

This explores all connected component starting from each vertex, so presumably you have to repeatedly by iterating through all verticies.

undirected graph

constituents

• vertices’s \(V\), a set of values of node
• edges \(E\), a set of unordered sets of verticies

requirements

We write:

\begin{equation} G = \qty(V, E) \end{equation}

We say:

• degree of vertex is the number of edges coming out
• connected verticies are neighbors

additional information

directed graph

constituents

• vertices’s \(V\), a set of values of node
• edges \(E\), a set of directed edges

requirements

We write:

\begin{equation} G = \qty(V, E) \end{equation}

Start with an initial sample \(\tau\)

At each distribution…

1. sample \(\tau ’ \sim g\qty(\cdot | \tau)\) (for instance, \(\tau’ \sim \mathcal{N}\qty(\cdot | \tau, \sigma^{2})\))
2. accept the sample with probability given by \(\frac{\bar{p} \qty(\tau’) g\qty(\tau | \tau’)}{\bar{p}\qty(\tau) g\qty(\tau’ | \tau)}\), otherwise keep \(\tau\) (this is also called the Metropolis-Hastings criteria)

intuition

The kernel is often chosen to be symmetric, so:

\begin{equation} g\qty(\tau | \tau’) = g\qty(\tau’ | \tau) \end{equation}

we want to sample from areas of high density more often. Consider:

Abstraction and Idealization

• abstraction: omit details of real world situation
• idealization: change aspects of real world situation

risks of inclusion and exclusion

• inclusion: you will have lots of information collected about you, privacy concerns, etc.
• exclusion: you will have less voice heard, you needs may not be measured / accounted for, actions may be taken to make you more legible

perpetuating cycle

1. broad simplification
2. failed solution translation to be incorporated
3. downstream injusticet'

incommesurability

lacking a common measure of value (what is “more than” / “less than” / “better than”) etc.

Key Sequence

Notation

New Concepts

• graph
• depth first search

Important Results / Claims

• solving topological sort with depth first search

Questions

Interesting Factoids