CS341 Quiz: Algocheatsheet

158 views2 pages

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 )

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers

Related Documents