Class Notes (1,100,000)
CA (630,000)
UW (20,000)
CS (1,000)
CS341 (20)
Lecture

# Assignment #1 This is the first assignment from winter 2010 term

Department
Computer Science
Course Code
CS341
Professor
Forbes Burkowski

This preview shows half of the first page. to view the full 2 pages of the document. CS 341, Winter 2010
Timothy Chan
Assignment 1 (due Jan 28 Thursday noon)
structions.
1. [4 marks] Give a complete proof from the deﬁnition of ω(not using limits) that
n3.41 2010n1.28 + 1 ω(n3).
2. [12 marks] For each pair of functions f(n) and g(n), ﬁll in the correct asymptotic notation
among Θ, o, and ωin the statement f(n)Ã(g(n)). Formal proofs are not necessary, but
provide brief justiﬁcations for all of your answers. (The default base in logarithms is 2.)
(a) f(n) = (2n)341 + (n+ 350)2010 vs. f(n) = (n+ 341)350 + (3n)2010
(b) f(n) = n1.52nvs. g(n) = n1001.99n
(c) f(n) = nlog nvs. g(n) = nlog n
log log n
(d) f(n) = (log n)log log nvs. g(n) = n0.01
3. [10 marks] Analyze the following pseudocode and give a tight (Θ) bound on the running
time as a function of n. Carefully show your work. (Here, “. . . ” refers to some constant-time
operations that do not change the values of i,j,k,`, and n.)
(a) [5 marks]
1. for i= 1 to ndo {
2. for j= 1 to i+ 3 do
3. for k= 1 to n+ 3 do
4. . . .
5. for j=ito ndo
6. for k=ito ndo
7. for `= 1 to ndo
8. . . .
9. }
1