Lectures, Tutorials, Course Outline, and Learning Objectives

Key to ASCII notation

• '{}' = ∅ = "empty set"
• '(-' = ∈ = "element of"
• '(_' = ⊆ = "subset of" (not strict)
• 'u' = ∪ = "union"
• 'n' = ∩ = "intersection"
• '~L' = L = "complement of L"
• '-]' = ∃ = "there exists"
• '\-/' = ∀ = "for all"
• '/\' = ∧ = "and"
• '\/' = ∨ = "or"
• '->' = → = "implies"
• '<->' = ↔ = "if and only if (iff)"
• '!' = ¬ = "not", e.g., 'a != b' = a ≠ b = "a is not equal to b", 'w !(- L' = w ∉ L = "w is not an element of L", etc.
• '\sum' = ∑ = summation sign
• '\prod' = ∏ = product sign
• '\Sigma' = Σ = capital greek letter Sigma, '\delta' = δ = lowercase greek letter delta, etc.
• '|_x_|' = ⌊x⌋ = floor(x)
• '|^x^|' = ⌈x⌉ = ceiling(x)
• '_' indicates a subscript, e.g., 'q_1' = q1
• '^' indicates a superscript, e.g., 'n^2' = n2
• curly braces '{}' surround longer subscripts/superscripts, e.g., '\sum_{0 <= i <= n} 2^{i/2}' = ∑0 ≤ i ≤ n 2i/2

Lecture notes

Every week, specific sections of the textbook will be posted as readings. You will be expected to read these sections to prepare for the following week's lectures.
At the end of each week, a short summary of the material covered during lectures will be posted. These files will mostly be in plain text, using the notation listed above for common mathematical symbols.

1. Sep 10–Sep 16: readings: Section 5.1 / Week 1 summary
2. Sep 17–Sep 23: readings: Section 4.4 / Week 2 summary
3. Sep 24–Sep 30: readings: Sections 6.1, 6.6 / Week 3 summary
4. Oct  1–Oct  7: readings: Section 6.5 / Week 4 summary
5. Oct  9–Oct 14: readings: Section 7.2 / Week 5 summary
6. Oct 15–Oct 21: readings: Sections 7.2, 7.3 / Week 6 summary
7. Oct 22–Oct 28: readings: Sections 7.1, 7.4 / Week 7 summary
8. Oct 29–Nov  4: readings: Section 8.2 / Week 8 summary
9. Nov  5–Nov 11: readings: Section 8.3 / Week 9 summary
10. Nov 14–Nov 20: readings: Section 8.3 / Week 10 summary
11. Nov 21–Nov 27: readings Section 9.2 / Week 11 summary
12. Nov 28–Dec  5: readings Sections 9.2, 9.1, 9.3 / Week 12 summary
See the Tests/Exam page for advice about studying for and writing the final exam.

Tutorial notes

Every week, a tutorial exercise will be posted below. This exercise will contain some number of problems that you should be able to solve easily given that week's lecture material. Think of the tutorial exercise as an "early warning system": if you have any difficulty solving it, then this is a strong indication that you need to review the lecture material and ask questions.

During tutorials, the TAs will go over the week's exercise and make sure that everyone understands how to solve them. This will be followed by a brief (10 minute) quiz at the end of each tutorial.

Tutorial exercises and their solutions will be posted here every week, following the tutorials. These files will mostly be in plain text, using the notation listed above for common mathematical symbols.

1. Sep 13: Tutorial 1 Exercise / Tutorial 1 Solution
2. Sep 20: Tutorial 2 Exercise / Tutorial 2 Solution
3. Sep 27: Tutorial 3 Exercise / Tutorial 3 Solution
4. Oct 4: Tutorial 4 Exercise / Tutorial 4 Solution
5. Oct 11: Tutorial 5 Exercise Tutorial 5 Solution
6. Oct 18: Tutorial 6 Exercise / Tutorial 6 Solution
7. Oct 25: Tutorial 7 Exercise / Tutorial 7 Solution
8. Nov 1: Tutorial 8 Exercise / Tutorial 8 Solution
9. Nov 8: Tutorial 9 Exercise / Tutorial 9 Solution
10. Nov 15: Tutorial 10 Exercise / Tutorial 10 Solution
11. Nov 22: Tutorial 11 Exercise / Tutorial 11 Solution
12. Nov 29: Tutorial 12 Exercise / Tutorial 12 Solution

Course outline

Lecture topics

The following topics will be covered in this course, in the order listed. For each topic, we have indicated the approximate number of weeks required to cover that topic.

• Greedy algorithms: 2 weeks.
• Dynamic programming: 2 weeks.
• Network flow: 2 weeks.
• Linear programming: 1 week.
• NP-completeness: 3 weeks.
• Approximation algorithms: 2 weeks.

Learning objectives

By the end of this course, students should

• be familiar with standard algorithm design techniques (greedy strategies, dynamic programming, network flow and linear programming, approximations):

• know the definitions of the various techniques,
• be able to recognize algorithms that employ these techniques,
• be able to write algorithms using these techniques,
• understand what it means for algorithms written using these techniques to be correct,
• be able to analyze the efficiency of algorithms written using these techniques;
• understand the importance of computational complexity:

• be familiar with the definitions of P and NP,
• be able to demonstrate membership in P or NP,
• be familiar with the definition of NP-completeness,
• be able to apply techniques for showing NP-completeness.