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

47 views2 pages

For unlimited access to Class Notes, a Class+ subscription is required.

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
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class