1
Q
What is a directed graph
A
2
Q
What is a strongly connected directed graph
A
3
Q
What is a weakly connected directed graph
A
Means there is an undirected path between any 2 elements
4
Q
What is a strong / weak component
A
5
Q
What is the relationship between the connectedness of a directed graph and it having a euler walk
A
6
Q
What is the in and out neighbourhood of a directed graph
A
The vertices point to it and from it respectively
7
Q
What is the in and out degree of a vertex in a directed graph
A
8
Q
What are the 2 cases for a euler walk in a directed graph (in relation to in and out degrees)
A
Algorithms II
flashcards
Decks in class (39)
# Cards
-
1.1-2 Proof by induction recap3
-
1.3 Defining O-notation13
-
1.4 Properties of O-notation7
-
2.1 Greedy Algorithms4
-
2.2 Interval correctness proof10
-
2.3 The Bridges of K¨onigsberg9
-
2.4 When does a graph have a euler walk4
-
3.1 Directed Euler Walks8
-
3.2 Hamilton Cycles4
-
3.3 Shaking Hands7
-
3.4 Trees9
-
4.1 Graph representations8
-
4.2 Depth first search7
-
4.3 Breadth first search6
-
4.4 Dijkstra’s algorithm8
-
5.1 Matchings Definitions3
-
5.2 Finding maximum matchings7
-
5.3 Prims Algorithm7
-
5.4 Kruskal's algorithm4
-
6.1 Making Kruskal's fast1
-
6.2 The union-find data structure9
-
6.3 2-3-4 Trees I4
-
6.4 2-3-4 Trees II3
-
7.1 Linear Programming7
-
7.2 How to solve linear programs7
-
7.3 Flow Networks8
-
7.4 The Ford-Fulkerson algorithm8
-
8.1 Why the Ford-Fulkerson algorithm looks so familiar3
-
8.2 Applications of Ford-Fulkerson5
-
8.3 SAT and NP9
-
8.4 NP-completeness and 3-SAT2
-
9.1 Independent sets and vertex covers5
-
9.3 NP vs Co-NP7
-
9.4 Dealing with NP-hard problems8
-
10.1 Weighted Interval Scheduling4
-
10.2 Dynamic Programming4
-
10.3 The Bellman-Ford Algorithm6
-
10.4 The Real Bellman-Ford algorithm4
-
Untitled Deck1
