CS 6515 Graph Algorithms
Components of a complete solution
(a) Describe your algorithm
NO PSEUDOCODE - use words
What changes you may need for the in-
put
What black box you will feed your input to
What changes you may need for the out-
put
Repeat with more black boxes as needed
(b) Justify why your algorithm is correct
Explain how your problem is solved by
the black boxes used
What are the components of a graph
Explain how changing the inputs and/or
theory solution?
outputs gets what you want
(c) Analyze the runtime
Must be presented in Big O notation
Can explain/analyze in words
Can use known black box runtime with-
out explanation. Must include run time
analysis for any pre/post processing, as
well as any modifications to the black box
(if permitted by the problem)
Again, if we give you a run time, you
must meet that for full credit. If we do not
specify a run time, faster (and correct) in
Big O notation are worth more credit.
Rules
NO PSEUDOCODE - YOU WILL LOSE
A LOT OF POINTS
Only black boxes of known algorithms
What are the rules for writing a graph are allowed
theory solution? One or more graph black box must be
used to solve problems in this section
Do not make changes to black boxes
unless explicitly allowed. This is very rare
and may not happen during the semester
1/9
, CS 6515 Graph Algorithms
We consider all Graphs to be provided as
G=(V,E)
V is an array of vertices
E is an adjacency list
When a graph is provided as input, you
are also given n=#V# and m=#E#
Size of Max-flow = min capacity of a
Max-flow = Min st-cut
st-cut
A variation of Ford-Fulkerson Algorithm
that uses BFS instead of DFS to ensure
the algorithm terminates even if loops
exist.
It takes longer though, running at
O(|V|*|E|^2) time and using O(|E|+|V|)
space.
Edmonds-Karp Algorithm inputs:
outputs:
runtime:
Input: Graph G unweighted
Output:
1. prev[z] - parent index of vertex z
2. pre[z] - pre number of vertex z
DFS Algorithm
3. post[z] - post number of vertex z
4. ccnum[z] - connected component
number of z
Runtime: O(m+n)
Tree Edge
Back Edge
Types of Edges from DFS
Forward
Cross
2/9
Components of a complete solution
(a) Describe your algorithm
NO PSEUDOCODE - use words
What changes you may need for the in-
put
What black box you will feed your input to
What changes you may need for the out-
put
Repeat with more black boxes as needed
(b) Justify why your algorithm is correct
Explain how your problem is solved by
the black boxes used
What are the components of a graph
Explain how changing the inputs and/or
theory solution?
outputs gets what you want
(c) Analyze the runtime
Must be presented in Big O notation
Can explain/analyze in words
Can use known black box runtime with-
out explanation. Must include run time
analysis for any pre/post processing, as
well as any modifications to the black box
(if permitted by the problem)
Again, if we give you a run time, you
must meet that for full credit. If we do not
specify a run time, faster (and correct) in
Big O notation are worth more credit.
Rules
NO PSEUDOCODE - YOU WILL LOSE
A LOT OF POINTS
Only black boxes of known algorithms
What are the rules for writing a graph are allowed
theory solution? One or more graph black box must be
used to solve problems in this section
Do not make changes to black boxes
unless explicitly allowed. This is very rare
and may not happen during the semester
1/9
, CS 6515 Graph Algorithms
We consider all Graphs to be provided as
G=(V,E)
V is an array of vertices
E is an adjacency list
When a graph is provided as input, you
are also given n=#V# and m=#E#
Size of Max-flow = min capacity of a
Max-flow = Min st-cut
st-cut
A variation of Ford-Fulkerson Algorithm
that uses BFS instead of DFS to ensure
the algorithm terminates even if loops
exist.
It takes longer though, running at
O(|V|*|E|^2) time and using O(|E|+|V|)
space.
Edmonds-Karp Algorithm inputs:
outputs:
runtime:
Input: Graph G unweighted
Output:
1. prev[z] - parent index of vertex z
2. pre[z] - pre number of vertex z
DFS Algorithm
3. post[z] - post number of vertex z
4. ccnum[z] - connected component
number of z
Runtime: O(m+n)
Tree Edge
Back Edge
Types of Edges from DFS
Forward
Cross
2/9
