CS341 Quiz: Algocheatsheet
Document Summary
Algorithm (steps followed to solve a problem) is effective, unambiguous, finite desc/code, finite (halt) polynomial time if there exists a k such that its worst-case time complexity t ( n ) is o ( n k ) = n n e -n sqrt(2 n) (1 + (1/n)) Maxsubrange: o(n^3) brute, o(n^2) smarter, o(nlogn) divide and conquer, o(n) dynamic programming maxsofar := 0; for i := 1 to n do maxsuffixsum := 0; maxsuffixsum := max(0, maxsuffixsum + x[i]); maxsofar := max(maxsofar, maxsuffixsum); Unit-cost model: each instruction costs 1 unit of time (good if numbers involved fit in one machine word) Log-cost model: charge for an instruction is directly proportional to the number of bits handled by it. Discrete logarithm: prime p , a generator g , 1 (cid:1226) a (cid:1226) p -1, find the exponent e such that g e (cid:1223) a (mod p )