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)
Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html first for general in-
structions.
1. [4 marks] Give a complete proof from the definition of ω(not using limits) that
n3.41 2010n1.28 + 1 ω(n3).
2. [12 marks] For each pair of functions f(n) and g(n), fill in the correct asymptotic notation
among Θ, o, and ωin the statement f(n)Ã(g(n)). Formal proofs are not necessary, but
provide brief justifications 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
You're Reading a Preview

Unlock to view full version