false

Study Guides
(247,960)

Canada
(121,197)

University of Waterloo
(5,717)

Computer Science
(334)

CS 341
(33)

Shallit
(1)

Quiz

Unlock Document

Computer Science

CS 341

Shallit

Fall

Description

Algorithm (steps followed to solve a problem) is effective, unambiguous, finite desccode, finite (halt) k polynomial time if there exists a k such that its worstcase time complexity T(n) is O(n ) OrderAsymptotic Notation f(n) is (g(n)) if there exist constants c > 0, c1> 0, n2uch th0 c g(n) f(n1 c g(n) for all2 n 0 f(n) is O(g(n)) if there exist constants c > 00n such that f(n) c g(n) for a0l n n f(n) is (g(n)) if there exist constants c > 0, 0 such that f(n) c g(n) for all 0n n if lim(n>inf) f(n)g(n) = c then c = 0, then f = o(g), c < , then f = (g), c = , then g = o(f) Strilings approximation: n! = n e sqrt(2 n) (1 + (1n)) Paradigms: 1. Reduce to known prob, 2. Preprocessing, 3. Invent or augment data structure, 4. Divide and Conquer, 5. Recursion, 6. Greedy Algorithm, 7. Dynamic Programming, 8. Exploit problem structure, 9. Probabilisticrandomized algo Master theorem: T(n) = aT(nb) + f(n) log(b,a) log(b,a) f(n) = O(n ) for > 0 (i.e c < log(b,a)), then T(n) = (n ) f(n) = (n log(b,(lg n)^(k)) (i.e c = log(b,a)), then T(n) = (n log(b,a)(lg n)^(k+1)) log(b,a) + f(n) = (n ) for > 0 (i.e c > log(b,a)), and if af(nb) < cf(n) for c < 1 and large n, then T(n) = (f(n)) Maxsubrange: O(n^3) brute, O(n^2) smarter, O(nlogn) divide and conquer, O(n) dynamic programming maxsofar := 0; maxsuffixsum := 0; for i := 1 to n do maxsuffixsum := max(0, maxsuffixsum + x[i]); maxsofar := max(maxsofar, maxsuffixsum); Unitcost model: each instruction costs 1 unit of time (good if numbers involved fit in one machine word) Logcost model: charge for an instruction is directly proportional to the number of bits handled by it e Discrete logarithm: prime p, a generator g, 1 a p1, find the exponent e such that g a (mod p) Convex Hull: Jarvis March big angle O(n^2), Graham Scan sort angles backtrack on right turn O(nlogn) n n2 n2 n2 Multiply: Pencil O(n^2), Karatsuba XY = (2 + 2 ) ac + 2 (ab) (dc) + (2 + 1) bd O(n^1.59) Matrix mult: div n conq O(n^2.8) x = (a+d)(e+h),1 = a(gh), x = (a+b2, x = d(fe),3 = (c+d)e, x 4(ca)(e+g), 5 6 x = (bd)(f+h); then r = x + x + x x , s = x + x , t = x + x , u = x + x + x x . 7 1 4 7 3 2 3 4 5 1 2 6 5 Abelian Square: naive O(n^3logn), rs idea O(kn^2) Greedy Algorithm: argument differ at some point, less optimal to do otherwise Matrix Mult Order: table (first) O(n^3), second O(n) m[i,j] = min(i k < j) m[i,k] + m[k+1,j] + p[i1]p[k]p[j] for i := 1 to n do m[i,i] := 0 for d := 1 to n1 do for i := 1 to nd do j := i+d; m[i,j] := infinity; for k := i to j1 do q := m[i,k] + m[k+1,j] + p[i1]*p[k]*p[j] if q < m[i,j] then m[i,j] := q; s[i,j] := k return(m,s) MATRIXMULT(M, s, i, j) if j > i then X := MATRIXMULT(M, s, i, s[i,j]); Y := MATRIXMULT(M, s, s[i,j]+1, j); return(X*Y); else return(M) i Dynamic Programming tips: 1. Figure out subproblems, 2. Write down the recursion for the subproblems, 3. Figure out the order in which to solve subproblems and fill the table, 4. Write iterative code for table, 5. Code to get answer from table Memoization disadvantages: recursion stack problems, complicated code, large storage, much harder to analyze runtime Dynamic programming disadvantages: hard to think about the subproblems, solving subproblems that you never use Longest common subsequence: O(mn) for table, O(m+n) for lcs Optimal change: O(nk) k is number of denominations thus not polynomial time Probabilistic analysis: E = s in S[s]*s i1 Find majority element: i 1p) p i = x = 1p O(n) Pseudo number generation: X n+1= a Xn c (mod m) Randomized Select: O(n) if p = r then return A[p]; q := RANDOMIZEDPARTITION(A,p,r); k := qp+1; if i = k then return A[q] else if i < k then return RANDOMIZEDSELECT(A,p,q1,i) else return RANDOMIZEDSELECT(A,q+1,r,ik); Induction: T(n) = (12) T(3n4) + (12) T(n1) + dn (12) (3cn4) + (c2) (n1) + dn <= cn suffices to take c = 8d. Deterministic Select: O(n) if n < 60 then sort(A); return ith smallest element; else m := floor(n5); M := array of medians of each group; x := SELECT(M,ceil(m2)); k := XPARTITION(A,x); if i = k then return x else if (i < k) then return SELECT(A[1..k1],i) else return SELECT(A[k+1..n],ik); T(n) T(floor(n5)) + T(7n10 + 3) + dn 9cn10 + 3c + dn <= cn if n 60, c 20d else c = max(20d, T(1), ..., T(59)59) Lower bounds: Adversary argument answers to maximize the size of the solution space Any algorithm that uses only yesno questions to decide from k alternatives, must use at least lg k questions (lg(n!) sort) Thrm: comparisonbased method for the max and min, must use at least (3n2)2 (even), or (3n2)32 comparisons ( odd) Proof: For n even., the algorithm must learn 2n2 units of information (lower bound n1 for minmax). The most it can learn in one question is 2 units; this can only happen at most n2 times. To learn the remaining n2 units of information, the algorithm must ask n2 questions. The total number of questions is therefore at least n2 + n2 = (32)n 2. Same for n odd. Second largest: n + ceil(lg n) 2, tournament, Median: n1 + (n1)2 = (32)(n1), (n1)2 noncrucial comparisons

More
Less
Related notes for CS 341

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.