1
Q
What is the space complexity of an adjacency matrix. And time complexity of an adjacency + neighbourhood query
A
1
Q
How to store a graph as an adjacency matrix
A
i, j = row, column
2
Q
How to store a graph as an adjacency list
A
3
Q
What is the space complexity of an adjacency list. And time complexity of an adjanceny + neighbourhood query
A
4
Q
Compare adjacency matrices to adjacency lists
A
5
Q
How does Google page rank use adjacency lists
A
6
Q
What are 2 examples of multi-graphs
A
Knowing we won’t cover these may help on the exam
7
Q
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
