Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

GA > Exam 2 > Flashcards

Exam 2 Flashcards

1
Q

Tree edge

A

edge in DFS graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

DFS output is a tree/forest (T/F)

A

true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Types of edges not in DFS tree

A

back, forward, and cross edges: these edges are not in the DFS tree but are in the original graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

post-ordering of edge z->w

A

post(z) > post(w) except for back edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How do we know if G has a cycle?

A

G has a cycle if and only if its DFS tree has a back edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Post order number

A

When doing DFS, when we first visit a node, we give it a number (pre-order) and increase our counter, when we leave a node, we give it a number and increase our counter (post order)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How to do topological sorting (2 ways)

A
  1. Run DFS on a DAG
    - We know that for all z->w, post(z) > post(w) ==> order vertices by decreasing post order number
  2. Find a sink vertex, output it, delete it. Repeat. Will build ordering backwards
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is special about the first and last vertices in a topological sorting?

A

First vertex must be a source vertex and last must be a sink

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Source vertex and its post-order #

A

has no incoming edges, highest post-order #

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Sink vertex and its post-order #

A

has not outgoing edges, lowest post-order #

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

def: strongly connected

A

two vertices are strongly connected if there is a path from w to v and from v to w (in a directed graph)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

def: SCC

A

Maximal set of strongly connected vertices. only in directed graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

metavertex/metagraph

A

can replace SCCs with metavertices to create a metagraph. metagraph is always a DAG

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

SCC Algorithm general idea

A

find a sink SCC, output it, remove it, and repeat

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Why use sink SCC in algorithm?

A

Running explore on a vertex in sink will return all vertices in that SCC (and no others)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How do we find a vertex in a source SCC and how does this help with the SCC Algorithm?

A

Vertex with highest post number lies in a source SCC. If we reverse the graph, that vertex will be in a sink SCC

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

SCC Algorithm

A

SCC(G):
1. Construct a reverse graph
2. Run DFS on reverse G
3. Order vertices by decreasing post order number
4. Run undirected connected components algorithm on G (i.e. DFS)
Output = topological ordering of SCCs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

SCC runtime

A

O(m+n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

CNF formula

A

conjunctive normal form formula. AND of several clauses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

clause

A

OR of several literals

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

literals

A

x1, !x1, etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

SAT

A

input: CNF
output: T/F if it can be satisfied (and the assignments)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

K-SAT

A

each clause has size at most k. k>= 3 in NP-Complete

24
Q

How to simplify a 2-SAT

A
  1. Pick a unit clause (clause with 1 literal) and satisfy it
  2. Remove the unit clause and simplify all other clauses with that literal
  3. Repeat
    ==> End result is CNF where all clauses are of size 2
25
Q

How to convert a 2-SAT to a directed graph

A
  • 2n vertices for each literal
  • 2m edges for each “implication” of each clause:
    Implication example:
    (!x1 OR !x2) => x1=T, then x2=>F ==> x1->!x2
    => X2=T then x1=F ==> x2 ->!x1
26
Q

How do we know if a 2-SAT graph is satifiable?

A

For every x, x and !x must be in different SCCs

27
Q

2-SAT Runtime

A

O(m+n)

28
Q

What is an MST and what type of graph is it used on?

A

minimum sized, connected subgraph of minimum weight. Unconnected and weighted graph

29
Q

A tree with N vertices has how many edges?

A

N-1

30
Q

how many paths are between a pair of vertices on a tree?

A

1

31
Q

How do we know if a connected graph is a tree?

A

it has |E| = |V| - 1

32
Q

What is Kruskal’s Algorithm?

A

For finding an MST:

  1. Sort edges by increasing weight
  2. For each edge in sorted list, add the edge to the current tree if it doesn’t create a cycle
33
Q

Kruskal’s Algorithm runtime

A

|E| * log |V|

34
Q

What are the cut edges

A

The set of edges that connect two components

35
Q

What are the cut edges

A

The set of edges that connect two components

36
Q

Max-Flow Problem (input, goal, constraints, output)

A

Input: direct graph with capacity for each edge + source/sink vertices
Goal: Want to maximize the flow from s->t (flow out of s and into t)
Constraint: flow into a vertex must equal the flow out
Output: a flow for each edge

37
Q

Anti-parallel edge (max-flow)

A

if we have two parallel edges (i.e. v->w and w->v), we must create an anti-parallel edge:

  1. take on edge and split into 2 edges with an extra vertex in between
  2. New two edges have same weight as previous one edge
38
Q

How to create a residual network (max-flow)

A

Input: graph and flow set
Add forward edges: if f[e] < c[e], then add that edge with weight c[e] - f[e]
Add backwards edges: if there is an edge v->w and flow > 0, add an edge w->v with capacity f[e]

39
Q

Ford-Fulkerson Algorithm

A
  1. Set all flows = 0
  2. Create residual graph for current flow
  3. Check for a path s->t in residual graph
  4. If no path, output flows
  5. Let c(P) be the minimum capacity along the path in the residual network
  6. augment flows by c(P) (if e is a forward edge, increase flow by c(P), if e is a backward edge, decrease flow by c(P))
  7. Repeat steps 2-6 until no path
40
Q

Ford-Fulkerson runtime

A

C = size of max flow
M = length of s->t path
O(mC) time

41
Q

ST-Cut

A

Any cut of the graph that separates s into one half (L) and t into the other (R)

42
Q

Capacity(L, R)

A

capacity of all edges from L->R

43
Q

Min ST-Cut Problem

A

Want to find an st-cut with minimum capacity

44
Q

Max-Flow Min-Cut Theorem

A

size of the max-flow = minimum capacity of an st-cut

45
Q

Image segmentation problem

A

separate an image into objects

46
Q

Image segmentation formulation

A
  • Each pixel is a vertex in the graph
    • Edge between neighboring pixels
    • For each vertex there is a probability that it is in the foreground and a probability that it is in the background
    • For each edge, there is a separation penalty
47
Q

What is a demand for Max-Flow?

A

The demand for an edge is the minimum flow (so 0 <= demand <= flow <= capacity)

48
Q

what is a Feasible flow ?

A

a flow where every edge meets the demand

49
Q

Finding a feasible flow overarching idea

A

transform feasible flow problem into a max-flow problem

50
Q

How to create G’ for finding a feasible flow

A
  1. Add two extra vertices to G: s’ and t’
  2. C’(e) = c(e) - d(e) I.e. new capacities are the difference between the demand and old capacity
  3. Add new edges: from s’ to all vertices (except t’) and from all vertices (except s’) to t’
    ○ Capacity for all edges s’->v == the total incoming demand for v
    ○ Capacity for all edges v->t’ == the total outgoing demand for v
  4. Add an edge from t->s with capacity infinity
51
Q

What is a Saturated flow?

A

size(f’) == sum of all outgoing demand of s’ (and incoming demand of t’)

52
Q

How do we know if G has a feasible flow?

A

G has a feasible flow if and only if G’ has a saturated flow

53
Q

How do we know if G has a feasible flow?

A

G has a feasible flow if and only if G’ has a saturated flow

54
Q

Differences between Edmund-Karp and Ford-Fulkerson

A

E-K uses BFS only to find st-path

E-K does not require integer capacities

55
Q

E-K runtime

A

O(m^2*n)

GA (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions