CSCE4110 Final Flashcards
Advantages of adjacency list
works well for sparse graphs
space is theta(V + E)
disadvantage of adjacency list
searching for edges slower than adjacency matrix
advantages of adjacency matrix
works well for dense graph
edge lookup is theta(1)
disadvantage of adjacency matrix
requires more space than adjacency list
Examples of a BFS algorithm
Prims and dijkstras
Goal for a BFS algorithm
find smallest number of edges to each reachable vertex
time complexity for BFS
O(V+E)
Explain BFS briefly
Pick a starting vertex
Visit all nodes connected to starting vertex (start alphabetically)
Mark visited node
Add visited node to Queue
Explain DFS briefly
Pick a starting vertex
Visit next connected node (alphabetically)
Mark visited node
Add node to top of stack
Time complexity of DFS
O(V+E)
Are MST always unique
NO
How are Prim’s and Kruskal’s algorithms greedy?
Adds smallest weighted edge each step as long as it maintains tree property
Time complexity of Kruskals and Prims algorithm
O(E lg V)
How is single-source shortest paths exhibit optimal substructure?
If we have a path p(xy) and patch a new path in between it would be impossible
Can shortest paths be computed with negative weight edges?
Yes
Can shortest paths be computed with negative edge cycle?
No
Can a shortest path have a cycle?
No
Initialize single source
3 steps
Set distance: infinity
Set predecessors: NULL
Set s.d: 0
Running time of initializing single source
theta(V)
Running time for bellman ford
theta(VE)
Running time for Dijkstras
O(E lg V)
All pair shortest path input and output
a matrix
Max Flow equilibrium
inflow = outflow at every vertex
Max flow termination
all paths from s to t are blocked by either full forward edge or empty backward edge
applications for maxflow
data mining and baseball elimination
Rounding errors can increase over series of computations
numerical stability
What is a hamiltonian cycle
a simple cycle in a graph G=(V,E) that contains each vertex in V
Hamiltonian cycles are generally not solvable in
polynomial time
You can check hamiltonian cycles in
polynomial time
what are P problems
problems that are solvable in polynomial time
what are NP problems
problems that are verifiable in polynomial time
if there exists a polynomial-time computable function
the problem is polynomial time reducible
what is an approximation ratio
δ if and
only if for every instance of the problem, A, gives a solution which is at most δ times the optimal value for
that instance
δ is always at least
1
Why do we use approximation algorithms
used to find approximate solutions to optimization problems
traverse traveling sales man graph in
preorder (dot to the left)
applications for linear programming
data mining, and supply-chain management
what is a slack variable
variable that is added to an inequality constraint to transform it to an equality
Feasible solution properties
Set n – m nonbasic variables to 0, solve for remaining m variables.
Solve m equations in m unknowns.
Where are feasible solutions located on the graph
On the line
Decision problems are simply
any problem
whose answer is one bit: “yes” or “no”
T/F: The superscripts in an output matrix for an all-pairs shortest paths algorithm refer to the dimensions of the matrix.
True
