false

Class Notes
(834,408)

Canada
(508,508)

University of Toronto St. George
(43,985)

Computer Science
(754)

CSC165H1
(167)

Nathalie Fournier
(31)

Lecture

Unlock Document

Computer Science

CSC165H1

Nathalie Fournier

Fall

Description

CSC165H1F Tutorial # 7 | Sample Solutions Fall 2011
1. Write a detailed, structured proof that
8f : N ! R ;8g : N ! R ;g 2 O(f) ) g 2 O(f ) 2
(where f and g are de▯ned in the obvious way: 8n 2 N;f (n) = f(n) ▯ f(n), and similarly for g).
(I show only the ▯nished proof here, not its development.)
+ +
Assume f : N ! R and g : N ! R .
Assume g 2 O(f).
+
Then 9c 2 R ;9B 2 N;8n 2 N;n > B ) g(n) 6 c ▯ f(n). # de▯nition of O
Let c 0 R + and B 20N be such that 8n 2 N;n > B ) g(n0 6 c ▯ f(n).0
2 2
# Show that g 2 O(f ):
Let c = c . Then c 2 R . + # because c 2 R +
1 0 1 0
Let B 1 B . 0hen B 2 N.1 # because B 20N
Assume n 2 N and n > B = B .
1 0
Then g(n) 6 c 0 f(n) (because n > B ),0
so g (n) = g(n) ▯ g(n) 6 (c ▯ f(n)) ▯ (c ▯ f(n)) = c ▯ f(n) ▯ f(n) = c ▯ f (n).
0 0 0 1
Hence, 8n 2 N;n > B ) 1 (n) 6 c ▯ f (1). 2
+ 2 2
Then 9c 2 R ;9B 2 N;8n 2 N;n > B ) g (n) 6 c ▯ f (n).
Thus, g 2 O(f ).2 # by de▯nition of O
2 2
Therefore, g 2 O(f) ) g 2 O(f ).
Then, 8f : N ! R ;8g : N ! R ;g 2 O(f) ) g 2 O(f ). 2
2. Prove that T (n) 2 ▯(n ), where BFT is the algorithm below.
BFT
BFT(E;n):
1. i n ▯ 1
2. while i > 0:
3. P[i] ▯1
4. Q[i] ▯1
5. i i ▯ 1
6. P[0] n
7. Q[0] 0
8. t 0
9. h 0
10. while h 6 t:
11. i 0
12. while i < n:
13. if E[Q[h]][i] 6= 0 and P[i] < 0:
14. P[i] Q[h]
15. t t + 1
16. Q[t] i
17. i i + 1
18. h h + 1
(Although this is not directly relevant to the question, this algorithm carries out a breadth-▯rst traversal of
the graph on n vertices whose adjacency matrix is stored in E.)
2 2 2
We show that T BFT (n) 2 ▯(n ) by proving T BFT (n) 2 O(n ) and T BFT (n) 2
(n ).
Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 4 CSC165H1F Tutorial # 7 | Sample Solutions Fall 2011
TBFT (n) 2 O(n ) :
+
Let c = 16 and B = 1. Then, c 2 R and B 2 N.
Assume n 2 N, n > B = 1, and E is an arbitrary input of size n.
One of the tricky features of this algorithm is that the main loop depends on the values of h
and t, but the algorithm does not explicitly bound either value. To prove an upper bound on
T BFT(n), we start by proving a bound on the value of t. Namely, we show that at any point
during the execution of the algorithm, t 6 n.
From lines 1{9, when the main loop (lines 10{18) begins execution, h = t = 0, P[0] = n,
Q[0] = 0, and P[i] = Q[i] = ▯1 for i = 1;2;:::;n ▯ 1.
Note that the value of t is changed only on line 15, and this line is executed only when
P[i] < 0 (among other conditions).
Moreover, each time t is incremented, the value of Q[t] is set to a natural number (on
line 16), so that at any point during the execution of the algorithm, Q[0:::t] 2 N and
Q[t + 1:::n ▯ 1] = ▯1. Since h 6 t (from line 10), this means that Q[h] > 0 is always
true inside the main loop.
Hence, on line 14, the assignment P[i] = Q[h] guarantees that P[i] > 0 from that
point on. This means that the value of t can increase at most once for each value of
i = 0;1;:::;n ▯ 1 (it increases only when P[i] < 0, at which point P[i] is set to a
natural number), i.e., t 6 n.
From the algorithm,
▯ line 1 takes 1 step;
▯ lines 2{5 take 4 steps for one iteration, and are executed exactly n ▯ 1 times (once for
each value of i = n ▯ 1;n ▯ 2;:::;1), plus 1 more step for the last execution of line 2, for
a total of 4(n ▯ 1) + 1 = 4n ▯ 3 steps;
▯ lines 6{9 take 4 steps;
▯ lines 12{17 take at most 6 steps for one iteration (if the condition of the if statement
is true at every iteration), and are executed exactly n times (once for each value of i =
0;1;:::;n ▯ 1), plus 1 more step for the last execution of line 12, for a total of at most
6n + 1 steps;
▯ lines 10{18 take at most 6n + 1 + 3 = 6n + 4 steps for one iteration, and are executed at
2
most n times (since t 6 n, as shown above), for a total of at most 6n + 4n steps;
▯ so in total, the algorithm takes at most 1 + 4n ▯ 3 + 4 + 6n + 4n = 6n + 8n + 2 steps.
Since n > 1, this means that the number of steps executed by the algorithm on input (E;n)
is 6 6n + 8n + 2 6 6n + 8n + 2n = 16n . 2
Since (E;n) was arbitrary, 8n 2 N;n > 1 ) T BFT (n) 6 16n .
2
Therefore, TBFT (n) 2 O(n ).
TBFT (n) 2
(n ):
+
Let c = 1 and B = 1. Then, c 2 R and B 2 N.
Assume n 2 N and n > B = 1.
Consider an input (E;n) such that E[i][j] = 1 for all indices 0 6 i < n;0 6 j < n.
The ▯rst time that lines 12{17 are executed, the condition of the if statement will be true for
all values of i = 0;1;:::;n ▯ 1 so at the end of the loop, t will have value at least n (since
t starts at 0 and gets incremented n times). Since lines 12{17 always get executed exactly n
times (once for each value of i = 0;1;:::;n ▯ 1), they take at least n steps.
This means that lines 10{18 will get executed for every value of h = 0;1;:::;n ▯ 1 (at least),
2
and take at least n steps at each iteration, for a total of at least n steps.
So the number of steps on input (E;n) is > n . 2
2
Hence, 8n 2 N;n > 1 ) T BFT (n) > n .
Therefore, TBFT (n) 2
(n 2).
Dept. of Computer Science, University of Toronto, St. George Campus Page 2 of 4 CSC165H1F Tutorial # 7 | Sample Solutions Fall 2011
3. Find a tight bound on the worst-case running time of the following algorithm. (This example was started
during lecture, but it was not ▯nished.)
# Precondition: L is a list that contains n

More
Less
Related notes for CSC165H1

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.