Gain insights into key graph algorithms, including depth-first search, shortest paths, and flow networks. Explore their applications and foundational role in advanced computing disciplines.

This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engineer. 

You will begin with an introduction to the running-time analysis of algorithms and the representation and structure of graphs. You’ll cover the depth-first search algorithm and its many applications, like detecting cycles, topological sorting, and identifying cut-vertices and strongly connected components. You will then cover algorithms for finding shortest paths and minimum spanning trees. You’ll also learn about the Ford-Fulkerson algorithm and its use in finding a maximum flow and minimum cut in networks. Moreover, you will adapt it to find maximum matchings and minimum vertex covers in bipartite graphs. Finally, you will learn about the Gale-Shapley algorithm for finding stable matchings.

The material in this course serves as a basis for other advanced algorithms, like parallel and distributed algorithms, and has many diverse applications in other computing disciplines.

Mastering Graph Algorithms

We have talked at length about the big-O notation. We now want to go over how to convince ourselves that a particular function $f(n)$ is _not_ $O(g(n))$. 



# The difficulty 
  
Suppose our friend claims that $9^n\text{ is not }O(3^n)$. How can we be sure that our friend is right? 

It’s not enough to come up with two choices for the constants $c^\prime$ and $n^\prime$ (constants in the big-O notation) because we actually need to show that no such constants exist. How do we show nonexistence?

It so happens that there’s a useful proof technique that’s very effective when applied to situations just like these. 



# The technique 

The **proof by contradiction** technique is an indirect way to prove a point. 

Suppose we want to show that “X is true.” We start by assuming the opposite of what we want to show. So, our starting assumption, in this case, would be “X is false.” 

Then, we exercise our reason and make logical inferences until we arrive at a fact that contradicts another fact. Two contradictory facts indicate something went wrong. If our argument is valid, and every step logically follows from the previous steps, the only thing that could have possibly led to the contradiction is our starting assumption because that’s something we just made up. So, the only logical conclusion is that our starting assumption is false, implying for our above example that “X is true,” which is really what we wanted to show in the first place! 



# Example

Let’s apply this to the claim made by our friend.

> **Claim:** $9^n$ is not $O(3^n)$.

We begin by assuming the opposite.

> **Starting assumption:** $9^n$ is $O(3^n)$.

This implies by definition that, for some constants $c'$ and $n'$,
$$\begin{align*}
9^n \leq c^\prime 3^n \qquad \text{ for all }n \geq n'
\end{align*}$$
As $9^n = 3^{2n} = 3^n 3^{n}$, we can rewrite the above inequality as  

$$\begin{align*}
3^n3^n \leq c^\prime 3^n \qquad \text{ for all }n \geq n'
\end{align*}$$
Dividing both sides by $3^n$, we get
$$\begin{align*}
3^n \leq c^\prime \qquad \text{ for all }n \geq n'
\end{align*}$$

This tells us that $3^n$ is upper bounded by a constant for all $n \geq n^\prime$. But this contradicts what we know about $3^n$ that eventually, for larger values of $n$, $3^n$  becomes greater than any choice of constant $c'$. 
 
This contradiction establishes that the starting assumption is false. Therefore, $9^n$ is not $O(3^n)$.

Learn to establish when a big-O relation does not hold for two functions using the proof by contradiction technique.

Introduction

Review: Asymptotic Notation and Math Prerequisites

Working with Graphs

Depth-First Search and Applications

Prelude: Shortest Paths

Single-source Shortest Paths in Weighted Digraphs

All Pairs Shortest Paths

Minimum Spanning Tree

Flows

Matchings and Vertex Covers

Conclusion

Use Simulated Annealing for the Traveling Salesman Problem

Leveraging the Proof by Contradiction Technique