## Course Description

An introduction to the design, analysis, and implementation of algorithms to solve common computational problems. Basic algorithm design techniques such as the greedy strategy, divide-and-conquer, and dynamic programming, as well as network flows, intractability, and NP-completeness will be discussed.

See the course outline for more information.

## Course Details

### Lecture Time/Place

Monday, 12:30pm–1:20pm; Wednesday, 11:30am–12:20pm; Thursday, 1:30pm–2:20pm

All lectures are held in Mulroney Hall, room 3022.

**Special Note for Winter 2024.** On Monday, April 8, the Friday schedule of classes and labs will be offered.

### Textbook

J. Kleinberg and É. Tardos, *Algorithm Design*. Pearson Addison-Wesley, 2005.

The textbook is available for sale at the campus bookstore. Course notes will also be provided for each lecture.

### Marking Scheme

- Four assignments (12.5% each, total 50%)
- Midterm examination (25%)
- Final examination (25%)

You must write the final examination in order to pass the course, even if the weighted sum of your assignment and midterm examination grades is at least 50%.

## News

- Feb. 29: The third assignment has been posted. It is due by Mar. 14 at 1:30pm.
- Feb. 26: Lecture notes for the seventh week have been posted.
- Feb. 14: Due to the delayed opening of the university today, office hours this morning are cancelled.
- Feb. 12: The midterm will be written this week during the Feb. 15 lecture. See the review document and the Exams section below for more details. A practice midterm is also available.
- Feb. 7: As mentioned in lecture today, the lecture on Thursday will be cancelled due to the instructor being away.
- Feb. 5: Lecture notes for the fifth week have been posted.
- Feb. 4: Due to forecasted inclement weather, office hours and the lecture will be cancelled tomorrow. The deadline for Assignment 2 has been moved to Monday, Feb. 12.
- Jan. 29: Lecture notes for the fourth week have been posted.
- Jan. 28: Due to forecasted inclement weather, office hours and the lecture will be cancelled tomorrow.
- Jan. 25: The second assignment has been posted. It is due by Feb. 8 at 1:30pm.
- Jan. 22: Lecture notes for the third week have been posted.
- Jan. 15: Lecture notes for the second week have been posted.
- Jan. 11: The first assignment has been posted. It is due by Jan. 25 at 1:30pm.
- Jan. 8: Lecture notes for the first week have been posted.
- Jan. 8: Welcome to the course! Please see our Moodle page for details about the course this term.

## Lectures

Week |
Notes |
Readings |

1 | Introduction: stable matching, representative problems | Kleinberg & Tardos, 1.1–1.2 |

2 | Algorithm analysis | Kleinberg & Tardos, 2.1–2.2, 2.4 |

— | Review of graphs (optional reading) | Kleinberg & Tardos, Ch. 3 |

3 | Greedy algorithms: coin changing, scheduling, partitioning | Kleinberg & Tardos, 4.1–4.2 |

4 | Greedy algorithms (cont’d): Dijkstra, MSTs (Prim, Kruskal, Borůvka) | Kleinberg & Tardos, 4.4–4.6 |

5 | Divide and conquer: mergesort, quicksort, median/selection | Kleinberg & Tardos, 5.1–5.2, 5.4 |

6 | Mid-course review, midterm examination | — |

— | Winter study break | — |

7 | Divide and conquer (cont’d): master theorem, integer and matrix multiplication | Kleinberg & Tardos, 5.5 |

**Credit.** Lecture slide sources courtesy of Kevin Wayne.

## Assignments

- Assignment 1, due Jan. 25
- Assignment 2, due
~~Feb. 8~~Feb. 12 - Assignment 3, due Mar. 14
- Assignment 4, due Apr. 4

Assignments are due at the beginning of class on the due date. Late assignments will be accepted up to the beginning of the first class following the due date. Late assignments are subject to a penalty of 10% deducted from the earned mark.

## Exams

### Midterm

Date: Feb. 15, 2024

Time: 1:30pm–2:20pm

Place: Mulroney Hall, room 3022

Content: All material from Weeks 1 to 5

## Personnel

### Instructor

Taylor J. Smith

Email: tjsmith [at] stfx [dot] ca

Office: Annex, Room 9A

Office hours: Monday/Wednesday/Friday, 9:30am–10:30am