# Lectures, Tutorials, Course Outline, and Learning Objectives

#### Key to ASCII notation

- '
`{}`' = ∅ = "empty set" - '
`(-`' = ∈ = "element of" - '
`(_`' = ⊆ = "subset of" (not strict) - '
`u`' = ∪ = "union" - '
`n`' = ∩ = "intersection" - '
`~L`' == "complement of`L``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`' =`q`_{1} - '
`^`' indicates a superscript,*e.g.*, '`n^2`' =`n`^{2} - curly braces '
`{}`' surround longer subscripts/superscripts,*e.g.*, '`\sum_{0 <= i <= n} 2^{i/2}`' = ∑_{0 ≤ i ≤ n}2^{i/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.

- Sep 10–Sep 16: readings: Section 5.1 / Week 1 summary
- Sep 17–Sep 23: readings: Section 4.4 / Week 2 summary
- Sep 24–Sep 30: readings: Sections 6.1, 6.6 / Week 3 summary
- Oct 1–Oct 7: readings: Section 6.5 / Week 4 summary
- Oct 9–Oct 14: readings: Section 7.2 / Week 5 summary
- Oct 15–Oct 21: readings: Sections 7.2, 7.3 / Week 6 summary
- Oct 22–Oct 28: readings: Sections 7.1, 7.4 / Week 7 summary
- Oct 29–Nov 4: readings: Section 8.2 / Week 8 summary
- Nov 5–Nov 11: readings: Section 8.3 / Week 9 summary
- Nov 14–Nov 20: readings: Section 8.3 / Week 10 summary
- Nov 21–Nov 27: readings Section 9.2 / Week 11 summary
- 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.

- Sep 13: Tutorial 1 Exercise / Tutorial 1 Solution
- Sep 20: Tutorial 2 Exercise / Tutorial 2 Solution
- Sep 27: Tutorial 3 Exercise / Tutorial 3 Solution
- Oct 4: Tutorial 4 Exercise / Tutorial 4 Solution
- Oct 11: Tutorial 5 Exercise Tutorial 5 Solution
- Oct 18: Tutorial 6 Exercise / Tutorial 6 Solution
- Oct 25: Tutorial 7 Exercise / Tutorial 7 Solution
- Nov 1: Tutorial 8 Exercise / Tutorial 8 Solution
- Nov 8: Tutorial 9 Exercise / Tutorial 9 Solution
- Nov 15: Tutorial 10 Exercise / Tutorial 10 Solution
- Nov 22: Tutorial 11 Exercise / Tutorial 11 Solution
- 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.

- be familiar with the definitions of