Exam2 Algo-Combined Flashcards
RSA/Graph Theory
Undirected Graph
Depth First Search
Purpose, Input, Output, Runtime
Purpose: Perform a depth first search on an undirected graph G.
Input: Undirected Graph G = (V, E)
Output: 4 arrays: prev, pre, post each of length n
- Prev[z] The parent index of vertex Z in the DFS visition
- pre[z] the pre number of vertex z in the DFS visitation
- post[z] the post number of the vertex z in the DFS visitation
- (Optional) ccnum[z] the connected component number, if stored after SCC algorithm run on graph.
Runtime: O(n + m)
AKA:O(|V| + (|E|)
Directed Graph
Depth First Search
Input, Output, Runtime
Purpose: Perform a depth first search on a directed graph G
Input: Directed Graph G=(V, E)
Output: 3 arrays, prev, pre, post, each of length n
- prev[z]: The parent index of vertex Z in the DFS visitation
- pre[z]: the pre order number of vertex Z
- post[z]: the post order number of vertex Z.
Runtime: O(n + m)
AKA: O(|V| + |E|)
Topographial Sort Directed
Purpose, input, output, runtime.
Purpose: Sort the verticies of an input graph in topological order. (Following left to right on resulting list means all preconditions will be done in order)
Input: directed acyclic graph G = (V, E)
Output: array topo length n
- topo[i]: The vertex number of the i’th vertex in topological order from left to right (in descending post order)
Runtime: O(n + m) no need to do sort after DFS, we know post order numbers and their ranges.
AKA: O(|V| + |E|)
Sink: Node with smallest post order
Source: Node with highest post order.
Find Directed Strongly Connected Components
Purpose, input, output, runtime
Purpose: Find the strongly conencted components in a directed graph G.
Input: Directed Graph G=(V,E)
Output: Array ccnum of length n, array topo length t, where t is the number of SCCs, a directed acyclic metagraph Ga = Va, Ea
- ccnum[z]: The connected component numer of vertex z for z in V.
- topo[i] the SCC number for the ith SCC in topological order from left to right.
- Ga = the SCC acyclic metagraph.
Runtime: O(n + m)
AKA: O(|V| + |E|)
BFS_Explore
Purpose, Input, Output, Runtime, Note
Purpose: Explore a graph G (directed or undirected) from a given vertex s using the breath-frist strategy.
Input: a graph G = (V, E) (directed or undirected) and a “source” vertex s in V
Output: an array dist such that dist[u] = distantce (in terms of #edges crossed from vertex s to vertex u
Runtime: O(n + m). AKA: O(|V| + |E|)
note: dist[u] = +inf if the vertex u is not reachable from s, and BFS doesn’t account for edge weights, it can only find the shortest path from s to u in terms of edge count.
dfs_explore
Purpose, input, output, runtime
Purpose: Explore a graph G (directed or undirected) from a given vertex v
Input: G=(V, E), v in Vertexes
Output: (For reachable nodes, -1 for the rest)
- prev[z]
- pre[z]
- post[z]
Runtime: O(m) AKA O(E), only iterating over edges.
Reverse Directed Graph
(Considered housekeeping not need to be black boxed)
Purpose, Input, output, runtime
Purpose: Reverse a given directed graph G
input: A driected Graph G=(V,E)
output: A reversed graph Gr = (Vr, Er)
runtime: O(n + m) AKA O(|V| + |E|)
KruskalMST
Purpose, Input, Output, Runtime
+Note
Purpose: Finds the minimum spanning tree over an input undirected connected graph. (Sorts edges and selects edges not traversing graph)
Input: an undirected graph G = (V,E) and a weight function w such that w(u,v) = weight of edge.
Output: a set of edges X, which is the minimum spannign tree of G.
Runtime: O(m log n) AKA: O(E log (v))
Note:If the graph is not connected, we get a minimum spanning forest.
Prim MST
Purpose, input, output, runtime, note
Purpose: Finds the minimum spanning tree G over an input undirected connected graph.
Input: An undirected graph G=(V,E) and a weight function w such that w(u,v) = weight of edge.
Ouptut: an array prev where prev[n] is the parent vertex number of vertex v. prev[root] = null by def.
runtime: O(m log(n)) AKA: O(E log (V))
Note: PRIM expects a connected graph. This is similar to dikjstra’s only instead of using the weight of the full path in the priority tree, it uses the weight of the solitary edge to build up on the frontier.
Dijkstra’s Single Source Shortest Path
Purpose, input, output, runtime, note
Purpose: Finds the shortest path to all nodes from a source s in a weighted graph G (directed or undirected) with non-negative weights.
Input: A graph G=(V,E) directed or undirected, a source vertex and edge weights.
Output: dist[v] shortest distance from s to v, and prev[v] = prev of v in the shortest path from s to v.
Runtime: O((n + m) log(n))
Note: if the graph is connected, M dominates n+m and our time is O(mlog(n))
Directed Acyclic Graph Single Shorted Path
Purpose, Input, output, runtime, note
Purpose: Find the shortest path and its length from the given source vertex s to all vertices v in V, in a directed acyclic weighted graph G=(V,E)
“Same as depth first search, topological sorting”
Input: a DAG G=(V,E), a source vertex s in V, and weights
Output: dist[v] the shortest distance from s to v and prev[v] = the prev of v in the shortest path from s to v.
Runtime: O(n + m)
Note: If it is not possible to reach a vertex u from s, then dist[u] = inf, and negative edges are allowed in this algorithm.
BellmanFord Single Source Shortest Path
Purpose, Input, Output, Runtime, Note
Purpose: Find the shortest path to all nodes from a source s in a weight graph. With postiive or negative weights. (CAPABLE OF FINDING SHORTEST PATHS WITH NEGATIVE WEIGHTS)
Input: A graph G=(V,E), a source vertex s in v, and edge weights
Output: Dist[v] shortest distance from s to v, prev[v] previous vertex in shortest path from s to v.
Runtime: O(nm)
Note: Normally runs in V-1 cycles, however runnin gone more cycle can help detect negative weighted cycles. Also only cycles reachable from s can be detected.
FloydWarshall All Point Shortest Path
Purpose, input, output, runtime, note
Purpose: Finds the shortest path for all pairs, with positive or negative edge weights.
Input: A graph G(V,E) directed or undirected and edge weights.
Output: dist[s,t]: the shortest distance from s to t. (dist is an nxn array
Runtime O(n3)
Can detect any negative cycles by checking distance from node to itself, if it is less than zero, there is a negative weight cycle.
Ford-Fulkerson (max flow/min cut)
Purpose, Input, output, runtime
Purpose: Finds the maximum st-flow in a flow network
Input: Flow Network G=(V,E) with capacities and source sink s & t
Output: Flow fe for e in Edges
Runtime: O(mC) where C is the size of the maximium flow.
Edmonds-Karp (max flow/min-cut)
purpose, input, output, runtime, note
Purpose: Finds the maximium st-flow in a flow network (a directed graph G=(V,E) with capacities
Input: Flow network G=(V,E) with capacties, a source, and a sink
Ouput: Flow fe for edges
Runtime: O(m2n)
Note: Same as F-F, but uses a BFS to find augmenting paths to give a runtime without the C.
What is a Valid Flow?
What is a Maximum Flow?
A Valid flow in a flow network is a flow in g that satisfies all capacity constraints for the edges. (E.g. fe <= C(E)
A Maximum flow is a flow of maximum value.
Let G = (V,E) be a flow network with source s, sink t and integer capacities. Suppose that we are given a maximum flow in G.
Suppose that the capacity of a single edge (u, v) ∈ E is increased by 1. Give an O(V + E) time algorithm to update the maximum flow.
Compose the residual graph on the original flow. Add a positive 1 capacity on the edge that has been increased. Using BFS, search for an augmenting path; if the path exists, we can update the flow, otherwise, the flow is unchanged. We only need to do this once, as the augmenting path, if it exists, increases the flow by 1, which is the maximum increase possible.
Let G = (V,E) be a flow network with source s, sink t and integer capacities. Suppose that we are given a maximum flow in G.
Suppose that the capacity of a single edge (u, v) ∈ E is decreased by 1. Give an O(V + E) time algorithm to update the maximum flow.
Again, compose the residual graph on the original flow. If the decreased edge was not at capacity (that is, it still has positive residual capacity), then we can decrease the edge capacity by one without affecting the maximum flow. If not, then we add one to the negative capacity on the edge, and look for an augmenting path in reverse (going from t to s instead of from s to t) which includes the decreased edge.
Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow.
First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|)) and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting path would mean the solution is not a maximum flow.
Using Fermats Little Theorem how can we avoid testing every number 1 to P
for a single number
Prob that flt returns yes when N is prime is 1
Prob that flt returns yes when N is not prime is <= 1/2
So depending on the amount of certainty we pick k different a values, which gives us
1/2k as the probability flt returns yes when it is not prime.
What theorem would you use to solve:
wx - yx divisible by N
if
- N can be factored into two primes
- GCD(w,N) = 1 and GCD(y,N) = 1
Euler’s Theorem:
If N is the product of 2 prime numbers and GCD(a,n) = 1
Then A(p-1)(q-1) === 1 mod N
E.g. Is 41536 - 94824 divisible by 35
35 is product of 5 & 7 (two primes)
gcd(4,35) = 1
gcd(9,35) = 1
(p-1)(q-1) = (5-1) * (7-1) = 24
Z24 = 1 mod 35
1536/24 = 64 so 4(24*64) equals 1 mod 35
4824/24 = 201 so 9(24)(201) equals 1 mod 35
1 mod 35 = 1, 1 mod 35 = 1
1 -1 = 0, there is no left over so yes it is divisible!!!
What is the substitution rule for x and y
in modulo arithmetic in terms of x’ and y’
if
x = x’ (mod n) and y = y’ (mod n)
then
x + y === x’ + y’ (mod n)
and
xy === x’y’ (mod n)
10 * 15 (mod 4) =>
(10 (mod 4) * 15) (mod 4) -or-
(10 * 15 (mod 4)) (mod 4)-or-
(10 (mod 4) * 15 (mod4)) (mod 4)
Can you prove that if a mod b has an inverse then b mod a must also have an inverse?
Yes, a (mod b) only has an inverse if gcd (a,b) = 1
so the formula b (mod a) only has an inverse if gcd(b,a) = 1
gcd(a,b) and gcd(b,a) are the same formula.
Euler’s Theorem
For N = pq where p & q are prime,
For any Z where gcd(Z, N) = 1
Then Z(p-1)(q-1) is equivliant to 1 mod N
Multiply Algorithm
Time O(n2)
Multiply(x,y):
if y == 0: return 0
z = multiply(x, floor(y/2))
if y is even:
return 2z
else
return x + 2z
How can we use Fermats Little Theorem to prove a number is prime.
Fermat’s little theorem says:
If p is prime, then for every 1 <=a
a(p-1) === 1 (mod p)
So if we have a number P that we want to test for primality, then calculate
a(p-1) for every value a between 1 and p.
If they all equal 1 mod p, then it is prime.
(Note: There are some charmichael numbers like 561 which pass the test, but aren’t prime.
Euclid’s Rule
if x & y are positive integers x >= y,
then gcd(x,y) = gcd(x mod y, y)
How are keys created for RSA
- Pick two large prime numbers p and q
- calculate n = pq. (n is the modulus for pub and priv)
- Calculate totient of n .. (p-1)(q-1)
- Choose e (the public key exponent) so that the gcd(e, totient(n)) = 1. (can be small like 3, 5, 35)
- Calculate d to be the inverse of e mod totient(n)
- Use Extended-Euclid (e,n)
- The number that returns as the multiple (x) for e is the inverse.
- if it’s negative you need to mod it. (Basically add N to it until it is positive.)
- This number alone not (x * e) but the x is the inverse x Mod N.
Public Key = (n, e)
Private key = (d)
Note if you get a decryption key of 1, then your selection of e was not gcd 1 with totn.
ModExp Algorithm
Time O(n3)
ModExp(x, y, N):
if y = 0: return 1
Z = modexp(x, floor(y/2), N)
if y is even:
return z2 mod N
else
return x * z2 mod N
What is Euclid’s Algorithm for GCD
Time O(n3)
Euclid(a,b):
// a and b with a >= b >= 0
if b = 0: return a
return Euclid(b, a mod b)
b, a mod b =>
if x & y are positive
x >= y
then
gcd(x,y) is equal to
gcd(y, x mod y)
p is prime, q is prime:
N = pq
What is totient(N)
(p-1)(q-1)
Big O time for modulo
Addition
Multiplication
Division
Addition => O(n)
Multiplication => O(n2)
Division => O(n3)
What is multiplicative inverse for modulo numbers?
x is the multiplicative inverse of a (mod n)
if a*x (mod n) = 1
Sometimes one doesn’t exist. if gcd(a, N) > 1, it can never exist. E.g. a=2, N=6
When gcd(a, N) = 1 (we say a and N are relatively prime), the extended Euclid algorithm gives us integers x and y such that ax + N y = 1, which means that ax ≡ 1 (mod N). Thus x is a’s sought inverse.
Divide Algorithm
Time O(n2)
Divide(x,y):
if x = 0: return (q,r) = (0,0)
(q,r) = divide(floor(x/2), y)
q = 2 * q, r = 2 * r
if x is odd:
r = r + 1
if r >= y:
r= r - y
q = q + 1
return (q, r)
What is Eculid’s Extended Algorithm
(and what can you tell with it)
To check if a number d is the gcd of a and b. Then the extension says:
if d divides both a and b, and d = ax + by for some integers x and y then necessarily d = gcd (a,b)
extended-euclid(a,b):
input a,b with a>=b>=0
output: x, y, d such that d = gcd(a,b) and ax + by = d
if b = 0: return (1,0,a)
(x’, y’, d) = extended-Euclid(b, a mod b)
return (y’, x’ - floor(a/b)y’, d)
Euler’s Totient Function
For prime P, Totient(P) = P - 1;
When N = pq, Totient(N) = (p-1)(q-1)
How can you reduce 2345 (mod 31)
using the substitution rules and associativity, commutativity and distributivity
Taken together with the substitution rule, it is legal to reduce intermediate results modulo N at any stage. So simplifications can be made like:
2345 (mod 31) ==>
(25)69 (mod 31) ==>
3269 (mod 31) ==>
169 (mod 31) ==>
1 (mod 31)
What theorem would you use to solve
a mod N
if N is prime.
Fermats Little Theorem
(If N is prime, than for 1 <= a < n)
a(n-1) = 1 mod N
199 (mod 5)
19(5-1) => 194 = 1 mod 5
Divide exponent by N-1:
9/4 = 2 R 1
This means 198 = 1 mod 5
Substiution leaves
198 (mod 5) * 191 (mod 5) => 1 (mod 5) * 19 mod 5
1 * 4 = 4
How is RSA performed using:
N, e -> public key
d -> private key
Encrypt x:
y = xe mod N
Decrypt y:
x = yd mod N
Fermat’s Little Theorem
If p is prime, then for every 1 <=a < p
ap-1 = 1 (mod p)
e.g: is 2^2 = 1 mod 3
p = 3 and is prime
2^(3-1) = 2^2 = 1 mod 3
1 mod 3
How do you get a prime number?
Select a random n bit number
Run it through flt
if passes it is prime, otherwise try again
Probability of hitting a prime in n but numbers is 1/n so we expect this to only take n guesses at most.
What are the 3 main steps to Kruskal’s Algorithm
Time: O(mlogn)
m = edges
n = verticies
Input: Undireted graph G(v,e) with weights w(e)
- Sort E by increasing weight
- Set x to the empty set.
- For each edge in our sorted list of edges, if adding edge into x does not create a cycle, then add the edge.
- Return x
What are cut edges
Undirected G=(v,e)
Partition V = S union ~S
Cut(S,~S) = {(v,w) in E: v in S, w in ~s}
This says cut edges are the edges that
cross between S and ~S.
2 Takeaway’s from MST proof
1) I can take a tree, add in e* and that creates a cycle. I can then remove any edge from that cycle and get a new tree T’
2) A minimum weight edge across the cut is part of a mst.
What is topological order in an acyclic graph
The order based on decreasing post number.
Cut Property
In building a minimum spanning tree, if we connect two minimum spanning trees using the lightest edge between the two of them, the result is a new minimum spanning tree.
BFS
G = (V,E) - Directed or Undirected
vertex s in V
returns dist[u], prev[z]
O(n+m)
Dijkstra
G = (V,E) - Directed or Undirected; vertex s in V; w
returns dist[u], prev[z],
O((n+m) log n)
DFS
G = (V,E) directed or undirected
Output: prev, pre, post, ccnum
O(n+m)
Explore
G(V,E) Directed or undirected
visited[], O(m)
Kruskal’s
FInd MST defined bt Emst
G=(V,E) connected, undirected
O(m log n)
Prim’s
FInd MST defined by prev[]
G=(V,E) connected, undirected
O(m log n)
Bellman-Ford
Single source shorted path, allows negative edge weights.
O(nm)
Floyd-Warshall
All paths shorted path
O(n^3)
Ford Fulkerson
FInd max flow
Integers
O(mC)
Edmonds-Karp
Find Max Flow
O(nm^2)
What does V represent?
Set of vertices
What does E represent?
Set of edges
What does n = |V| represent?
Number of vertices
What does m = |E| represent?
Number of edges
What does s represent?
The source vertex
What does t represent?
The sink vertex
What is Breadth-first Search (BFS) algorithm used for?
To find unweighted Single Source Shortest Path (SSSP), the distance from s to u if s can reach u, otherwise it is infinity; Runtime is O(n+m)
What is Dijkstra’s algorithm used for?
To find weighted Single Source Shortest Path (SSSP), the distance from s to u if s can reach u, otherwise it is infinity; Understand that when weights are involved, the runtime increases to O((n+m) log n)
What is Depth-first Search (DFS) algorithm used for?
It behaves differently for directed and undirected graphs; In a directed graph, the pre/post numbers give information on how a graph COULD be explored; In an undirected graph, the pre/post numbers give information on how a graph WOULD be explored given a starting point; Runtime is O(n+m)
What is the Explore algorithm used for?
This is a subroutine of DFS and does most of the work in DFS, it runs on all edges and vertices that are reachable from the provided v, can be used with a visited array to will set to true for all nodes u that are reachable from v; Runtime is O(n+m) if run by itself
What is the Topological Sort algorithm used for?
This algorithm works by running DFS on the DAG (directed acyclic graph - it has no cycles) and using the post order number to sort the vertices from highest post number to lowest post number, when a DAG is ordered from source to sink, then all edges go from left to right; Runtime is O(n+m)
What is the Strongly Connected Components (SCC) algorithm used for?
It takes a directed graph and runs DFS twice, running once with pre/post order numbering on the reverse graph of G and sorting V in descending post order numbers, giving sink to source; It then runs again on G with V sorted, the output will have ccnum representing each SCC with highest = source, and lowest = sink, the ccnum can be used to gather up vertices that belong to each SCC; Runtime is O(n+m)
What is Kruskal’s Minimum Spanning Tree (MST) algorithm use for?
The algorithm sorts edges by weight of a connected and undirected graph, G = (V,E), and weights w, it grabs the lightest available edge that will not create a cycle when added to the MST, another way to look at this is to never add edges of vertices in the same component in the MST, this continues until all edges that will not create a cycle are added, this happens at exactly n-1 edges; Runtime is O(m log n)
What is a source vertex?
It has no incoming edges and has the highest post number
What is a sink vertex?
It has no outgoing edges and has the lowest post number
Vertices are strongly connected if?
There is a path from v -> w and w -> v
In Conjunctive Normal Form (CNF), AND is represented by?
^ looks like an A
In Conjunctive Normal Form (CNF), OR is represented by?
V looks like a V
What inputs are taken to a max-flow algorithm?
G(V,E), s, t, c where s a source vertex, t is a sink vertex, and c is capacities; This set of inputs is also known as a Flow Network
What are the steps involved in obtaining the max-flow of a graph?
Build a residual network of the graph that shows the capacities along edges; Check for any path in the residual network from s to t using DFS or BFS - if none is found, we’re done; If found, get the minimum capacity along the path; Augment the path by capacitive units along the path, forward edges are increased and backwards edges are decreased; Runtime is O(n+m)
Describe the Ford-Fulkerson algorithm.
Assumes all capacities are positive integers, runs in rounds by increasing the flow >= 1 per round so there are C rounds where C is the size of max flow; Runtime is O(mC)
Describe the Edmonds-Karp algorithm.
Very similar to Ford-Fulkerson except it uses BFS to determine the shortest path rather than “any path”; Runtime is O(nm^2)
Does an MST contain cycles?
No, they are acyclic graphs (no cycles)
What does the max flow - min-cut theorem state?
The size of the max flow equals the size of the minimum st-cut
