Recitation 14

Recitation notes for the week of December 4, 2017.

Announcements

Most TAs will be having up to two extra office hours during finals week (including one or two review sessions). Come see us!

Bellman-Ford

The Goal

Find the minimum distances to a terminal $t$ in a directed graph $G=(V,E)$ with negative edge costs $c_e$, $e\in E$ (but no negative cycles).

Overview of Bellman-Ford

The algorithm fills in an $n\times n$ matrix $M$ that is defined recursively as follows: \[M[u][i]=\min\{M[u][i-1],\min_{(u,w)\in G}\{c_{(u,w)}+M[w][i-1]\}\}.\] Ultimately the algorithm will output $M[s][n-1]$ for every $s\in V$.

Note

$n-1$ is the maximum number of edges that given graph (with no negative cycles) in a path that Bellman-Ford to consider.

Note to TAs

Talk about why is true and what would happen if there was a negative cycle.

Run of Bellman-Ford

Run Bellman-Ford on example from textbook:

The final matrix $M$ should look like :

012345
$t$000000
$a$$\infty$-3-3-4-6-6
$b$$\infty$$\infty$0-2-2-2
$c$$\infty$33333
$d$$\infty$43320
$e$$\infty$20000

Chapter 6, Exercise 1

The Problem

Graph $G$ is an undirected graph with $n$ nodes (and each node has a weight). Graph $G=(V,E)$ is also a path meaning that each graph G that we can have as input will be of the form:

An independent set is a subset $S\subset V$ such that no two nodes in $S$ are joined by an edge. E.g. in the above example: \[\{a,c,e\}\] \[\{a,d\}\] \[\{b,d\}\] and so on.

The goal is to find an independent set with the maximum possible weight.

Note to TAs

Go over the following two algorithms and why they do not work.

                                    start with S as {}
                                    
                                    while G is not empty:
                                        pick a node of max weight
                                        add v to S
                                        delete v and its neighbors from G
                                    return S
                                


                                    let S1 be set of all vi where i is odd
                                    let S2 be set of all vi where i is even

                                    determine which of S1 or S2 has greater total weight and return it

The final solution

Built on relationship \[\text{OPT}(j) = \max\{\text{OPT}(j-1), \text{OPT}(j-2) + w_j\}.\]

Note to TAs

See if students can come up with solution before giving it out.

Example

Consider the following input instance:

\[\text{OPT}(v_0) = 1\] \[\text{OPT}(v_1) = 8\] \[\text{OPT}(v_2) = \max\{\text{OPT}(v_0) + 6, \text{OPT}(v_2)\} = 8\] \[\text{OPT}(v_3) = \max\{\text{OPT}(v_1) + 3, \text{OPT}(v_2)\} = 11\] \[\text{OPT}(v_4) = \max\{\text{OPT}(v_2) + 6, \text{OPT}(v_3,)\} = 14\]

If there is extra time

Take any questions on sample final.

Further Reading