Instructor:
Bahram Kouhestani
Goodwin Hall 235
Email: kouhesta AT cs dot queensu dot ca
Office hours: Wednesday 16:00-17:00
Classes:
Classes are in Goodwin 254 on Monday: 12:30 – 13:30, Wednesday: 11:30 – 12:30, Thursday: 13:30 – 14:30.
Text:
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 https://qcat.library.queensu.ca/vwebv/holdingsInfo?bibId=3365739
Grading:
Class participation 10%
Two homeworks each 15%
Two tests each 15%
Final 30%
Calendar:
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 www.academicintegrity.org). 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.
