Instructor
Teaching Assistant
 Ali Pazooki
Email: aptoroud AT gmail DOT com
Office Hours: ASB9838.2 on Mondays and Wednesdays from 3:30 to 4:20pm
Reading


See "Countable set" in Wikipedia.

Chapters 1  9, 12  13, 15  16, and 23 in the text, plus section 22.1.

Homework (please note that the problem and section numbers are from the Third Edition)


#1 for Thursday, January 21, COLLECTED AT EXACTLY 2:30pm
*** Please note that the homework will be solved at the beginning of the class, so no late homework can be accepted. ***
Prove that a subset of a countable set must be countable
Show that a union of two countable sets is countable
Prove that the rationals are countable
Prove that the reals are not countable
Prove that the irrationals are not countable
Exercises 3.11,3,4
Problem 31 a,b,c and 32 f (only big Oh, big Omega, and big Theta)

#2 for Thursday, January 28, COLLECTED AT EXACTLY 2:30pm
*** Please note that the homework will be solved at the beginning of the class, so no late homework can be accepted. ***
Find a onetoone (=injective) mapping of rationals to irrationals
Prove that there is no onetoone mapping of irrationals to rationals
Can you tile the plane with tiles whose sides are (top,right,bottom,left) (B,G,R,Y) or (G,G,B,G) or (R,Y,B,G)?
Can you tile the plane with just the tiles (G,G,B,G)?
Problem 1  1 for just lg n and n! and for 1 second and 1 century only
Problem 3  4 d,f
Prove that if f and g are O(h), then so is f+g
Exercise 3.12
Exercise 4.49
Exercise 4.51

#3 for Thursday, February 4, COLLECTED AT EXACTLY 2:30pm
*** YOU ARE REQUIRED TO SUBMIT TYPED SOLUTIONS ***
*** Please note that the homework will be solved at the beginning of the class, so no late homework can be accepted. ***
Design an algorithm to find the maximum and the minimum of an array on n numbers, with at most 3n/2 key comparisons
Prove that the sum 1^6 + 2^6 + ... + n^6 = Theta(n^7)
Prove that the sum 6^1 + 6^2 + ... + 6^n = Theta(6^n)
Exercises 4.2  3, 4, 6, 7
Exercise 4.4  4
Problem 4  1c

#4 for Thursday, February 25, COLLECTED AT EXACTLY 2:30pm
*** NOTE THE NEW DUE DATE ***
*** NOTE THE EXTRA PROBLEMS ADDED THIS WEEK ***
*** YOU ARE REQUIRED TO SUBMIT ONLINE ***
*** Please note that the homework will be solved at the beginning of the class, so no late homework can be accepted. ***
Exercise 4.4  8
Exercises 5.2  1, 2
Exercise 9.1  1
Exercises 9.3  8, 9
Problem 9  1ac
ADDED THIS WEEK:
Develop an Oform master formula for T(n) = T(an) + T(bn) + cn, depending on whether a+b < 1, =1, or >1
Exercises 9.3  1, 3, 5

#5 for Thursday, March 3, COLLECTED AT EXACTLY 2:30pm
*** YOU ARE REQUIRED TO SUBMIT ONLINE ***
*** Please note that the homework will be solved at the beginning of the class, so no late homework can be accepted. ***
Exercises 6.1  1, 2, 6
Exercises 6.5  4, 8, 9
Problem 6  2
Problem 9  1b
Exercises 8.1  1, 3
Exercise 8.2  4
Exercise 8.3  4

#6 for Tuesday, March 15
*** YOU ARE REQUIRED TO SUBMIT ONLINE PRIOR TO 2:30pm ***
*** NOTE THE UNUSUAL SUBMISSION DEADLINE ***
*** Note the ADDITIONAL QUESTIONS assigned this week ***
Exercises 12.1  1, 2
Exercises 12.2  1, 2, 3, 4, 5
Exercises 13.1  1, 2, 3, 5, 6

#7 for Thursday, March 24
*** YOU ARE REQUIRED TO SUBMIT ONLINE PRIOR TO 2:30pm ***
1. Solve Exercise 13.32.
2.The stagecoach problem has a source S, a sink T, and k levels L1, L2, ..., Lk of vertices
The source has a directed edge to each vertex on level L1, and the sink has a directed edge
from each vertex on level Lk
Otherwise there are just edges from vertices in any level to vertices on the next level
Each edge uv has a given length l(u,v), and the length of a path from S to T is the sum of the lengths of its edges
Give a dynamic programming algorithm to compute a shortest path from S to T computing the following parameter:
d(x,T) = the minimum length of a path from x to the sink T.
3. Extend your algorithm to actually output a shortest path itself (not just its length).
4. Solve Problem 15  4.
5. Prove that the sum 1 + 1/4 + 1/9 + ... 1/(n^2) is Theta(1) using integration.
6. Solve Exercise 15.4.1.
7. Complete the table started in class for the matrix chain product example

#8 for Tuesday, April 5
*** YOU ARE REQUIRED TO SUBMIT ONLINE PRIOR TO 2:30pm ***
Exercises 15.4  4, 5
Exercises 16.1  2, 3, 4, 5
Exercises 16.2  2, 3, 4, 5, 7
Complete the dynamic programming table for the knapsack problem from the class; state the solution cost and items

References

Textbook:

Introduction to Algorithms (Third Edition), by Cormen, Leiserson, Rivest, and Stein

Marking

Where to check grades: courses.cs.sfu.ca
If you have any questions about your grades (assignments/exams), please follow these steps:

(Within 2 weeks) Check with TAs because they do the marking

Check with me if you disagree with TA's judgment

No appeal will be accepted after 3 weeks

