This class was created by Brainscape user Aiden Dawes. Visit their profile to learn more about the creator.
By:
Aiden Dawes
- decks
- flashcards
- learners
Decks in this class (38)
1.1-2 Proof by induction recap
How is induction like proof by pr...,
How does the induction hypothesis...,
How does strong induction differ
3
cards
1.3 Defining O-notation
Formal definition of,
Formal definition of,
Formal definition of
13
cards
1.4 Properties of O-notation
What is the rough hierarchy of fu...,
How to avoid comparing functions ...,
When to use formal definitions
7
cards
2.1 Greedy Algorithms
What is the interval scheduling p...,
What is the correct greedy algori...,
What are the properties of a gree...
4
cards
2.2 Interval correctness proof
Steps to prove correctness,
What is the mathematical definiti...,
How to prove that the mathematica...
10
cards
2.3 The Bridges of K¨onigsberg
What is a graph,
What is a walk,
What is a euler walk
9
cards
2.4 When does a graph have a euler walk
What is a path,
What is a connected graph,
What is a subgraph and an induced...
4
cards
3.1 Directed Euler Walks
What is a directed graph,
What is a strongly connected dire...,
What is a weakly connected direct...
8
cards
3.2 Hamilton Cycles
What is a cycle in a graph,
What is a hamilton cycle,
What is dirac s theorem special c...
4
cards
3.3 Shaking Hands
What is the handshake lemma,
What is the proof for the handsha...,
7
cards
3.4 Trees
What is a tree and a forest,
Prove this lemma,
Prove this lemma
9
cards
4.1 Graph representations
What is the space complexity of a...,
How to store a graph as an adjace...,
How to store a graph as an adjace...
8
cards
4.2 Depth first search
Which graph algorithm to use to f...,
What is the core idea behind dept...,
What is the psuedocode for dfs
7
cards
4.3 Breadth first search
What is breadth first search used...,
What is the distance between 2 ve...,
What is the idea behind bfs
6
cards
4.4 Dijkstra’s algorithm
What is the length of a walk in a...,
What is a weighted graph,
What are negative weights in graphs
8
cards
5.1 Matchings Definitions
What is a matching and a perfect ...,
What is a bipartition and a bipar...,
How does a bipartite graph relati...
3
cards
5.2 Finding maximum matchings
Why doesn t a greedy algorithm al...,
What is an augmenting path in a b...,
What is the switch function for a...
7
cards
5.3 Prims Algorithm
What is a minimum spanning tree o...,
What is a minimum steiner tree,
What is the core idea behind prim...
7
cards
5.4 Kruskal's algorithm
What is the core idea behind krus...,
What is the formal mathematical v...,
Why does kruskal s algorithm work
4
cards
6.1 Making Kruskal's fast
What is the psuedocode for kruska...
1
cards
6.2 The union-find data structure
What operations and runtimes does...,
What does makeunionfind operation...,
What does findset x operation do ...
9
cards
6.3 2-3-4 Trees I
What is a binary search tree and ...,
What is the core idea behind a 2 ...,
Describe how values are inserted ...
4
cards
6.4 2-3-4 Trees II
Describe how to delete a leaf fro...,
How to delete a non leaf from a 2...,
How to turn a 2 3 4 tree into a r...
3
cards
7.1 Linear Programming
What constitutes a linear program...,
Linear programming formal definition,
What are feasible and optimal sol...
7
cards
7.2 How to solve linear programs
How do linear program constraints...,
What is the geometric meaning of ...,
How does the simplex algorithm work
7
cards
7.3 Flow Networks
What is the definition of a flow ...,
What is the definition of a flow,
How is the in and out flow described
8
cards
7.4 The Ford-Fulkerson algorithm
What is the failed greedy approac...,
What is the residual graph of a f...,
What is an augmenting path in a f...
8
cards
8.1 Why the Ford-Fulkerson algorithm looks so familiar
How does a biparite matching redu...,
How to simulate rational weights ...,
Edmonds karp when to use it what ...
3
cards
8.2 Applications of Ford-Fulkerson
What is a circulation network,
How to reduce a circulation probl...,
What is a vertex flow network
5
cards
8.3 SAT and NP
What is a cook reduction,
How can reduction chains be built up,
What are cook reductions actually...
9
cards
8.4 NP-completeness and 3-SAT
What is a cnf formula with width ...,
2
cards
9.1 Independent sets and vertex covers
What is an independent set,
What is the decision problem for ...,
How to reduce 3 sat to finding a ...
5
cards
9.3 NP vs Co-NP
What is the complement of a decis...,
What is co np,
What is a karp reduction and how ...
7
cards
9.4 Dealing with NP-hard problems
Will quantum computers p np exter...,
What options do you have to solve...,
What are the benifits challenges ...
8
cards
10.1 Weighted Interval Scheduling
What is weighted interval scheduling,
What are the 3 steps of dynamic p...,
What is the idea behind construct...
4
cards
10.2 Dynamic Programming
What does the recurrence tree of ...,
What is memoization,
What is the memoised recursive ve...
4
cards
10.3 The Bellman-Ford Algorithm
What does excluding negative cycl...,
Why doesnt dijkstas algorithm wor...,
What is the dynamic programming i...
6
cards
10.4 The Real Bellman-Ford algorithm
How can we cache the edges for we...,
How do we cache the values for we...,
What is the final psuedocode for ...
4
cards
More about
Algorithms II
- Class purpose General learning
Learn faster with Brainscape on your web, iPhone, or Android device. Study Aiden Dawes's Algorithms II flashcards for their AISJ class now!
How studying works.
Brainscape's adaptive web mobile flashcards system will drill you on your weaknesses, using a pattern guaranteed to help you learn more in less time.
Add your own flashcards.
Either request "Edit" access from the author, or make a copy of the class to edit as your own. And you can always create a totally new class of your own too!
What's Brainscape anyway?
Brainscape is a digital flashcards platform where you can find, create, share, and study any subject on the planet.
We use an adaptive study algorithm that is proven to help you learn faster and remember longer....
Looking for something else?
Python Data Structures & Algorithms
- 13 decks
- 342 flashcards
- 127 learners
Decks:
Python Built In Data Structures, Python User Defined Data Structures, Python List Methods, And more!
