Algorithms II (Fall 2015)


Bahram Kouhestani

Goodwin Hall 235

Email: kouhesta AT cs dot queensu dot ca

Office hours: Wednesday 16:00-17:00


Classes are in Goodwin 254 on  Monday: 12:30 – 13:30, Wednesday: 11:30 – 12:30, Thursday: 13:30 – 14:30.


1) Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, third edition.

2) Computational Geometry: Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.
An electronic version is available from the Queen’s Library


Class participation 10%

Two homeworks each 15%

Two  tests each 15%

Final 30%


Week 1:
1. Mon, Sep 14: Review of Dynamic Programming
2. Wed, Sep 16: Knapsack problem using DP
3. Thu, Sep 17: Problem set

Week 2:
4. Mon, Sep 21: Model of computation
5. Wed, Sep 23: Computational complexity
6. Thu, Sep 24: Recap, Linear time sorting

Week 3:
7. Mon, Sep 28: Linear time sorting
8. Wed, Sep 39: Problem set + recap
9. Thu, Oct 1: Test 1

Week 4:
10. Mon, Oct 5: Quick sort, randomized sort
11. Wed, Oct 7: Median and order statistics
12. Thu, Oct 8: Problems set

Week 5:
13. Mon, Oct 12: Thanksgiving: (No Class)
14. Wed, Oct 14: Amortized analysis
15. Thu, Oct 15:  problem set     (Homework 1 due)

Week 6:
16. Mon, Oct 19: Hashing
17. Wed, Oct 21: Universal hashing
18. Thu, Oct 22: Problem set

Week 7:
19. Mon, Oct 26: Approximation algorithms (vertex cover)
20. Wed, Oct 28: Approximation algorithms
21. Thu, Oct 29: Problem set

Week 8:
22. Mon, Nov 2: Introduction to CG, convex hull
23. Wed, Nov 4: Problem set + recap
24. Thu, Nov 5: Test 2

Week 9:
25. Mon, Nov 9: Convex hull
26. Wed, Nov 11: Guarding + art gallery
27. Thu, Nov 12: Problem set

Week 10:
28. Mon, Nov 16: Triangulation
29. Wed, Nov 18: More triangulation
30. Thu, Nov 19: Problem set

Week 11:
31. Mon, Nov 23: Doubly Connected Edge List
32. Wed, Nov 25: Minimum Weight Triangulation
33. Thu, Nov 26: Problem set (Homework 2 due)

Week 12:
34. Mon, Nov 30: Reviewing (weeks 1-4)
35. Wed, Dec 2: Reviewing (weeks 5-8)
36. Thu, Dec 3: Reviewing (weeks 9-11)

Academic Integrity

Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the “freedom of inquiry and exchange of ideas” essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 ), on the Arts and Science website (see Academic Integrity ), and from the instructor of this course. Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen’s. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.

Disability Accommodations

Queen’s University is committed to achieving full accessibility for persons with disabilities. Part of this commitment includes arranging academic accommodations for students with disabilities to ensure they have an equitable opportunity to participate in all of their academic activities. If you are a student with a disability and think you may need accommodations, you are strongly encouraged to contact the Disability Services Office (DSO) and register as early as possible. For more information, including important deadlines, please visit the DSO website at: HCDS

Accommodation Requests

Please let me know if you require any special accommodations.