1
Q
How do linear program constraints form a shape
A
2
Q
What is the geometric meaning of the objective function? And why is a solution always in the corner?
A
- (n-1)-d hyperplane
- Corner will always have the maximum c value
3
Q
How does the simplex algorithm work
A
Keep moving up until reach (local and global) maximum vertex
4
Q
Simplex algorithm runtime
A
Typically linear but potentially exponential
5
Q
What is a vertex cover
A
6
Q
How to express finding a vertex cover as an integer linear program
A
Binary value for each vertex
Constraints are the edges >= 1
7
Q
How and why to relax integer linear programs
A
Allow non-binary values, then round. Approx solution
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
