Cs6515 Exam 2 Questions And Answers

x mod N = {Ans: x = qN + r}Sink Vertex {Ans: - No outgoing edges = lowest post order # in DAG}SCC Algorithm Idea {Ans: - Find sink SCC, output it, remove it, and repeat - Why Sink? - Since it's a sink SCC, then you only visit the other nodes in that sink SCC when you run explore}What is the time to check whether or not a flow is a max flow {Ans: - O(n + m) 1. Build the residual graph takes O(n + m) time 2. Checking if there's a path from s to t using DFS, which takes linear time.}Max-flow = Min st-cut {Ans: Size of Max-flow = min capacity of a st-cut}Time to multiply or divide 2 n-bit numbers {Ans: O(n^2)}RSA Protocol {Ans: 1. Bob picks 2 n-bit random primes p & q 2. Bob chooses e relatively prime to (p-1)(q-1) 3. Bob publishes his public key (p*q, e) 4. Bob computes his private key: d ::: e^-1 mod (p-1)(q-1) 1. Alice looks up Bob's public key (pq, e) 2. Alice computes y:::m^e MOD N 1. Bob receives y 2. Bob decrypted: computes y^d MOD N :::