CMPT 307 - D1 Algorithms
Spring 2016

 Announcements
  • Pre-exam Office Hours, Pavol: Monday April 11, 1 - 3pm, Harbour Centre room 3047

  • Pre-exam Office Hours, Pavol: Tuesday April 12, 10 - 12am, TASC1, room 9011

  • Pre-exam Office Hours, Ali: Wednesday April 13 and Thursday April 14, 3:30-4:30pm, ASB9838.2

  • Final Exam on April 17, 3:30 - 6:30, AQ3181

  • Exam viewing dates May 17 and June 16, 1:30 - 2:30pm, TASC1 room 9011

  • Exam topics - see "Reading" below


  • Note the practice problem at the end of the homework


 Course

Instructor

  • Pavol Hell
    E-mail: pavol AT sfu DOT ca
    Office Hours: TASC1 room 9011 on Tuesdays 1:00 to 2:00pm

Teaching Assistant

  • Ali Pazooki
    E-mail: 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.1-1,3,4
    Problem 3-1 a,b,c and 3-2 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 one-to-one (=injective) mapping of rationals to irrationals
    Prove that there is no one-to-one 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.1-2
    Exercise 4.4-9
    Exercise 4.5-1

  • #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 O-form 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.3-2.
    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

  • Practice problems for exam on Chapter 23
    Apply Kruskal's and Prim's algorithms to the graph in Figure 23.1 in which each weight w is replaced by 15-w


 References

Textbook:

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


 Marking
  • Homework assignments (skip the worst 2)                     15%

  • Midterms (better grade)                                                  35%

  • Final exam                                                                      50%

     Where to check grades: courses.cs.sfu.ca

     If you have any questions about your grades (assignments/exams), please follow these steps:

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

  2. Check with me if you disagree with TA's judgment

  3. No appeal will be accepted after 3 weeks