Advanced Algorithms

Course Description

Advanced Algorithms pushes past the general-purpose techniques of CSC202 into specialized methods: approximation algorithms, randomized algorithms, and a deeper treatment of computational hardness. The course is proof-heavy and assumes real comfort with the CSC201/CSC202 sequence.

Learning Outcomes

Design and analyze approximation algorithms for hard optimization problems.
Apply randomized algorithmic techniques and analyze their expected behavior.
Reason formally about reductions between computational problems.
Read and critique an algorithms research paper.

Weekly Topics

Examines advanced complexity review from a practical angle, using a case drawn from real systems to motivate the concepts.

Builds directly on the previous week to extend approximation algorithms i, with an emphasis on where the earlier techniques stop working.

Combines a short lecture on approximation algorithms ii with an in-class exercise students carry into the week's assignment.

Focuses on common mistakes and misconceptions around randomized algorithms i, using student work from the previous assignment as material.

Introduces randomized algorithms ii and immediately puts it to use in a small design or implementation task.

Situates amortized analysis within the broader arc of the course, showing how it connects to what comes next.

Uses a guest dataset or scenario to explore mid-semester review in a setting closer to professional practice.

Introduces advanced graph algorithms through short lectures and worked examples, building the vocabulary the rest of the course relies on.

Works through linear programming basics in a lab-driven session, with guided exercises students complete and discuss in small groups.

Covers reductions & hardness in depth, connecting the underlying theory to a concrete example the class builds together.

Examines reading group: research papers from a practical angle, using a case drawn from real systems to motivate the concepts.

Builds directly on the previous week to extend independent problem set, with an emphasis on where the earlier techniques stop working.

Combines a short lecture on revision with an in-class exercise students carry into the week's assignment.

Assessment

Assignments — 25%

Practical Work — 15%

Mid-Semester — 20%

Final Examination — 40%

Prerequisite Map

Related Courses

Core200 Level

CSC201

Data Structures & Algorithms

Data Structures & Algorithms is where students stop asking only "does this work?" and start asking "how well does this work, and why?" The course covers the core data structures used throughout the rest of the curriculum — stacks, queues, trees, hash tables, graphs — alongside the analytical tools to reason about their time and space costs. Every structure is motivated by a problem it solves better than the alternatives.

Kenji Watanabe 4 cr

Core200 Level

CSC202

Algorithms Analysis & Design

Algorithms Analysis & Design moves from the data-structure-centered view of CSC201 into general strategies for designing efficient algorithms: divide and conquer, greedy methods, dynamic programming, and the tools to argue about correctness and lower bounds.

Hannah Lindqvist 4 cr