1
Q
What is the interval scheduling problem
A
2
Q
What is the correct greedy algorithm to the interval scheduling problem (idea and psuedo-code)
A
- Greedy: Always pick the element with first finish time
3
Q
What are the properties of a greedy algorithm
A
4
Q
What are some incorrect greedy algorithms to the interval scheduling problem (ideas)
A
- Choosing the first starting interval
- Choosing the shortest intervals
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
