Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
49 Cards in this Set
- Front
- Back
|
Concatenation: abc |
Generates: "abc" |
|
|
Boolean OR: ab|ac |
Generates: "ab", "ac" |
|
|
Klenee Closure: ab* |
Generates: "a", "ab", "abbb", etc |
|
|
Optional: ab?c |
Generates: "ac", "abc" |
|
|
One or more: ab+ |
Generates: "ab", "abbb", etc |
|
|
Group using: (a|b)*c |
Generates: "ac", "bc" Generates: "c", "ac", "bc", "bac", "abaaabbabbabbac", etc |
|
|
Context-free grammar |
The left hand side of a production is a single non terminal
The right hand side of any production cannot be empty |
|
|
Dijkstra's Algorithm |
Make a table Choose a start node Settle it Choose lowest weight node Settle it Repeat
|
|
|
Kruskal's Algorithm |
Always the lowest edge until all visited
Choose lowest weight edge Repeat until all connected with no cycles
Result: Minimum spanning tree |
|
|
Prim's Algorithm |
Expands possibility of children
Choose any node Choose lowest edge from that node Add new node Choose lowest edge from both nodes Add new node Repeat
Result: Minimum spanning tree |
|
|
Tree edge |
Visit new node via edge |
|
|
Forward edge |
Node to descendant |
|
|
Backward edge |
Node to ancestor |
|
|
Cross edge |
Between to non-ancestor related subtrees |
|
|
DFS (Depht first search) |
Keep going until there's nothing more
Use a stack Add first node to stack Check child node (repeat) When no more children, go back Repeat removing from stack
Complexity: O(m)
|
|
|
BFS (Breadth first search) |
Find everything first, then move
Use a queue Add first node to queue Check all child nodes Remove from queue, and go to next Repeat
Complexity: O(m) |
|
|
Floyd's Warshall |
Shortest paths between all nodes
Create adjacency matrix Set unreachable nodes as infinite Go through each row and column reducing path lenghts
Complexity: O(n3) |
|
|
Reflexive Matrix |
Ones on diagonal a->a b->b c->c |
|
|
Symmetric |
Reflected over diagonal a->b b->a
sibling |
|
|
Antisymmetric |
Part symmetric a->b b->a b=a (must be equal) <= (less or equal) |
|
|
Transitive |
If I can get there in 2, then I can get there in 1 a b a
Create graph |
|
|
Equivalence |
Reflexive, Symmetric, Transitive |
|
|
Weak poset |
Reflexive, antisymmetric, transitive |
|
|
Strict poset |
Irreflexive, antisymmetric, transitive |
|
|
Maximal element |
Has relations on the bottom (it's only a parent) |
|
|
Minimal element |
Has relations at the top (it's only a children) |
|
|
Upper bounds |
The elements above the element a->e b->e d->e
upper bounds of e: {a, b, d} |
|
|
Lower bounds |
The elements below the element a->b a->c a->d
lower bounds of a: {b,c,d} |
|
|
Least upper bound |
b->c b->d a->b
The least upper bound of c & d is {b} (the smallest common parent of both elements)
|
|
|
Greatest lower bound |
b->d c->d a->b a->c
The greatest lower bound of b & c is {d} (the greatest common children of both elements) |
|
|
Function requirements |
Every element on domain has only one domain in the range |
|
|
Injective function |
Some elements on range are hit only once |
|
|
Surjective function |
All elements on range are hit at least once |
|
|
Bijective function |
All elements on range are hit exactly once |
|
|
2^|A|, A = {a,b,c} |
8 |
|
|
2^A, A = {a,b,c} |
{empty, {a}, {b}, {c}, {a,b} {b,c}, {a,c}, {a,b,c}} |
|
|
2^C, C = empty |
{empty} |
|
|
2^D, D = {empty} |
{empty, {empty}} |
|
|
|2^E|, E = {empty, {empty}} |
4 |
|
|
2^F, F = 10 |
1024 |
|
|
Union |
Sum & remove duplicates |
|
|
Intersection |
Keep only the ones present in both |
|
|
Subtraction |
Keep the ones that are on the left and not on the right |
|
|
Dijkstra's big o |
O((V + E)logE) |
|
|
Kruskal's big o |
O(ElogE), E = number of edges |
|
|
Prim's big o |
O(ElogE), E = number of edges |
|
|
Floyd-Warshall's big o |
O(V3), V = number of vertices |
|
|
DFS big o |
O(E + V) |
|
|
BFS big o |
O(E + V) |
