CPSC 413 Design and Analysis of Algorithms Fall 2010

  • Here is the course info sheet.
  • The class meets Tuesday/Thursday, 9.30-10.45 in ST 141.
  • My office is in ICT 627; office hours are Monday 11.00-12.00, Tuesday 11.00-12.00 or by appointment (gscruttw (at) ucalgary.ca).
  • Tutorials:
    • M 11:00 EDC 154
    • M 15:00 ST 063
    • T 14:00 EDC 276
  • The joint tutorial is on Thursday at 18:00 in SA 106. The joint tutorial will be for quizzes (every second week, starting Sep. 23), a midterm review (Oct. 28), and a final review (Dec. 9).
  • Your final mark is given by: Quizzes 30%, Assignments 20%, Midterm 20%, Final Exam 30%, with the following grade given for each component: 90+: A/A+, 85-90: A-, 80-85: B+, 75-80: B, 70-75: B-, 65-70: C+, 60-65: C, 50-60: C-, 40-50: D, <40: F.
  • The quizzes, midterm, and final are all closed book.
Exercise sheets will be distributed every week. These are not to be handed in. In the individual tutorial sessions, the TAs will go over these questions.
  1. Exercise Sheet 1 (Sep. 16th) Additional reading: 2.2 and 2.4.
  2. Exercise Sheet 2 (Sep. 23rd) Additional reading: 4.1.
  3. Exercise Sheet 3 (Sep. 30th) Additional reading: 4.2 and 4.3.
  4. Exercise Sheet 4 (Oct. 7th) Additional reading: 2.5, 4.4, and 4.5.
  5. Exercise Sheet 5 (Oct. 14th) (Updated! There is no greedy algorithm for question 1). Additional reading: 4.8, 5.1, 5.2
  6. Exercise Sheet 6 (Oct. 21st) Additional reading: 5.3, 5.4, 5.5.
  7. Exercise Sheet 7 (Review Questions) (Oct. 28th)
  8. Exercise Sheet 8 (Nov. 4th) Additional reading: 6.1 and 6.2
  9. Exercise Sheet 9 (Nov. 10th) Additional reading: 6.4
  10. Exercise Sheet 10 (Nov. 18th) Additional reading: 6.3, 6.6, 6.8
  11. Exercise Sheet 11 (Nov. 25th) Additional reading: 8.1 and 8.3
  12. Exercise Sheet 12 (Dec. 2nd) Additional reading: 8.2 and 8.4
  13. Extra practice questions (will be covered in the final Thursday review session).
There are six five quizzes. Quizzes will be written in the joint tutorial. You will be able to drop your quiz with the lowest mark.
  1. Sep. 23: Asympototic analysis
  2. Oct. 7: Greedy algorithms (solutions)
  3. Oct. 21: More greedy algorithms (solutions)
  4. Nov 4: Divide and conquer algorithms
  5. Nov 18: Dynamic programming (solutions)
  6. Dec 2: NP problems
There are two assignments. The assignment due dates are: updated: Nov 1st, 4pm, and December 9, 4pm. There are dropboxes for the assignments in the 2nd floor of the math and science's building.
  1. Asymptotic analysis, greedy algorithms, divide and conquer algorithms Update! Question 5 was formulated incorrectly. It is no longer required for assignment 1. As a result, the due date has also been pushed back to Nov 1st at 4pm. Solutions.
  2. Dynamic programming and NP problems. Note: in question 4, the districts must be of equal size; assume that the number of precincts is even. Solutions
The midterm was held on November 2nd. Here are the solutions. The final exam has been scheduled for Dec. 15th, 3:30-6:30pm, in ICT 121.

Last modified: December 2nd, 2010.

I think there is a world market for maybe five computers - Thomas Watson, chairman of IBM, 1943