Exam2 Algo-Combined

Question 1

Undirected Graph

Depth First Search

Purpose, Input, Output, Runtime

Answer 1

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

1. Prev[z] The parent index of vertex Z in the DFS visition
2. pre[z] the pre number of vertex z in the DFS visitation
3. post[z] the post number of the vertex z in the DFS visitation
4. (Optional) ccnum[z] the connected component number, if stored after SCC algorithm run on graph.

Runtime: O(n + m)

AKA:O(|V| + (|E|)

Question 2

Directed Graph

Depth First Search

Input, Output, Runtime

Answer 2

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

1. prev[z]: The parent index of vertex Z in the DFS visitation
2. pre[z]: the pre order number of vertex Z
3. post[z]: the post order number of vertex Z.

Runtime: O(n + m)

AKA: O(|V| + |E|)

Question 3

Topographial Sort Directed

Purpose, input, output, runtime.

Answer 3

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

1. 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.

Question 4

Find Directed Strongly Connected Components

Purpose, input, output, runtime

Answer 4

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

1. ccnum[z]: The connected component numer of vertex z for z in V.
2. topo[i] the SCC number for the ith SCC in topological order from left to right.
3. Ga = the SCC acyclic metagraph.

Runtime: O(n + m)

AKA: O(|V| + |E|)

Question 5

BFS_Explore

Purpose, Input, Output, Runtime, Note

Answer 5

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.

Question 6

dfs_explore

Purpose, input, output, runtime

Answer 6

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)

1. prev[z]
2. pre[z]
3. post[z]

Runtime: O(m) AKA O(E), only iterating over edges.

Question 7

Reverse Directed Graph

(Considered housekeeping not need to be black boxed)

Purpose, Input, output, runtime

Answer 7

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|)

Question 8

KruskalMST

Purpose, Input, Output, Runtime

+Note

Answer 8

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.

Question 9

Prim MST

Purpose, input, output, runtime, note

Answer 9

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.

Question 10

Dijkstra’s Single Source Shortest Path

Purpose, input, output, runtime, note

Answer 10

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))

Question 11

Directed Acyclic Graph Single Shorted Path

Purpose, Input, output, runtime, note

Answer 11

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.

Question 12

BellmanFord Single Source Shortest Path

Purpose, Input, Output, Runtime, Note

Answer 12

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.

Question 13

FloydWarshall All Point Shortest Path

Purpose, input, output, runtime, note

Answer 13

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(n³)

Can detect any negative cycles by checking distance from node to itself, if it is less than zero, there is a negative weight cycle.

Question 14

Ford-Fulkerson (max flow/min cut)

Purpose, Input, output, runtime

Answer 14

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.

Question 15

Edmonds-Karp (max flow/min-cut)

purpose, input, output, runtime, note

Answer 15

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(m²n)

Note: Same as F-F, but uses a BFS to find augmenting paths to give a runtime without the C.

Question 16

What is a Valid Flow?

What is a Maximum Flow?

Answer 16

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.

Question 17

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.

Answer 17

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.

Question 18

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.

Answer 18

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.

Question 19

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.

Answer 19

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.

Question 20

Using Fermats Little Theorem how can we avoid testing every number 1 to P

Answer 20

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/2^k as the probability flt returns yes when it is not prime.

Question 21

What theorem would you use to solve:

w^x - y^x divisible by N

if

1. N can be factored into two primes
2. GCD(w,N) = 1 and GCD(y,N) = 1

Answer 21

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 4¹⁵³⁶ - 9⁴⁸²⁴ 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

Z²⁴ = 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!!!

Question 22

What is the substitution rule for x and y

in modulo arithmetic in terms of x’ and y’

Answer 22

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)

Question 23

Can you prove that if a mod b has an inverse then b mod a must also have an inverse?

Answer 23

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.

Question 24

Euler’s Theorem

Answer 24

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

Question 25

Multiply Algorithm

Time O(n²)

Answer 25

Multiply(x,y):

if y == 0: return 0

z = multiply(x, floor(y/2))

if y is even:

return 2z

else

return x + 2z

Question 26

How can we use Fermats Little Theorem to prove a number is prime.

Answer 26

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.

Question 27

Euclid’s Rule

Answer 27

if x & y are positive integers x >= y,

then gcd(x,y) = gcd(x mod y, y)

Question 28

How are keys created for RSA

Answer 28

1. Pick two large prime numbers p and q
2. calculate n = pq. (n is the modulus for pub and priv)
3. Calculate totient of n .. (p-1)(q-1)
4. Choose e (the public key exponent) so that the gcd(e, totient(n)) = 1. (can be small like 3, 5, 35)
5. Calculate d to be the inverse of e mod totient(n)
   
   1. Use Extended-Euclid (e,n)
   2. The number that returns as the multiple (x) for e is the inverse.
   3. if it’s negative you need to mod it. (Basically add N to it until it is positive.)
   4. 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.

Question 29

ModExp Algorithm

Time O(n³)

Answer 29

ModExp(x, y, N):

if y = 0: return 1

Z = modexp(x, floor(y/2), N)

if y is even:

return z² mod N

else

return x * z² mod N

Question 30

What is Euclid’s Algorithm for GCD

Time O(n³)

Answer 30

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 =>

Question 31

if x & y are positive

x >= y

then

gcd(x,y) is equal to

Answer 31

gcd(y, x mod y)

Question 32

p is prime, q is prime:

N = pq

What is totient(N)

Answer 32

(p-1)(q-1)

Question 33

Big O time for modulo

Addition

Multiplication

Division

Answer 33

Addition => O(n)

Multiplication => O(n²)

Division => O(n³)

Question 34

What is multiplicative inverse for modulo numbers?

Answer 34

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.

Question 35

Divide Algorithm

Time O(n²)

Answer 35

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)

Question 36

What is Eculid’s Extended Algorithm

(and what can you tell with it)

Answer 36

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)

Question 37

Euler’s Totient Function

Answer 37

For prime P, Totient(P) = P - 1;

When N = pq, Totient(N) = (p-1)(q-1)

Question 38

How can you reduce 2³⁴⁵ (mod 31)

using the substitution rules and associativity, commutativity and distributivity

Answer 38

Taken together with the substitution rule, it is legal to reduce intermediate results modulo N at any stage. So simplifications can be made like:

2³⁴⁵ (mod 31) ==>

(2⁵)⁶⁹ (mod 31) ==>

32⁶⁹ (mod 31) ==>

1⁶⁹ (mod 31) ==>

1 (mod 31)

Question 39

What theorem would you use to solve

a mod N

if N is prime.

Answer 39

Fermats Little Theorem

(If N is prime, than for 1 <= a < n)

a^(n-1) = 1 mod N

19⁹ (mod 5)

19^{(5-1) =>} 19⁴ = 1 mod 5

Divide exponent by N-1:

9/4 = 2 R 1

This means 19⁸ = 1 mod 5

Substiution leaves

19⁸ (mod 5) * 19¹ (mod 5) => 1 (mod 5) * 19 mod 5

1 * 4 = 4

Question 40

How is RSA performed using:

N, e -> public key

d -> private key

Answer 40

Encrypt x:

y = x^e mod N

Decrypt y:

x = y^d mod N

Question 41

Fermat’s Little Theorem

Answer 41

If p is prime, then for every 1 <=a < p

a^p-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

Question 42

How do you get a prime number?

Answer 42

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.

Question 43

What are the 3 main steps to Kruskal’s Algorithm

Time: O(mlogn)

m = edges

n = verticies

Answer 43

Input: Undireted graph G(v,e) with weights w(e)

1. Sort E by increasing weight
2. Set x to the empty set.
3. For each edge in our sorted list of edges, if adding edge into x does not create a cycle, then add the edge.
4. Return x

Question 44

What are cut edges

Undirected G=(v,e)

Partition V = S union ~S

Answer 44

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.

Question 45

2 Takeaway’s from MST proof

Answer 45

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.

Question 46

What is topological order in an acyclic graph

Answer 46

The order based on decreasing post number.

Question 47

Cut Property

Answer 47

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.