COMPSCI 170 Study Guide - Final Guide: Backtracking, Approximation Algorithm, Complete Graph
Document Summary
Write your answers in the space pro- vided. The exam has a total of 180 points. Since it is also connected, it must be a tree: modular exponentiation is known to take polynomial time. (modular exponentiation takes numbers a, b, c all in binary as input and returns ab (mod c) in binary as output). True: finding all solutions to the equation x2 = a (mod n ) is known to be solvable in polynomial time. We discussed that this is known to be equivalent to factoring: dijkstra"s algorithm will nd the correct shortest distances from a given starting node on a directed graph with negative edges provided there are no negative cycles. Then t (2n) = 22n = t (n)2, but t (n) is not polynomially bounded: suppose that the running time t (n) of an algorithm on inputs of size n satis es the recurrence t (n) =
