# Fall 2023 - CMPT 307 D100

## Overview

• #### Course Times + Location:

Sep 6 – Dec 5, 2023: Mon, Wed, Fri, 9:30–10:20 a.m.
Burnaby

Oct 10, 2023: Tue, 9:30–10:20 a.m.
Burnaby

• #### Exam Times + Location:

Dec 9, 2023
Sat, 3:30–6:30 p.m.
Burnaby

• #### Instructor:

bbart@sfu.ca
1 778 782-4685
• #### Prerequisites:

CMPT 225, (MACM 201 or CMPT 210), (MATH 150 or MATH 151), and (MATH 232 or MATH 240), all with a minimum grade of C-. MATH 154 or MATH 157 with a grade of at least B+ may be substituted for MATH 150 or MATH 151.

## Description

#### CALENDAR DESCRIPTION:

Design and analysis of efficient data structures and algorithms. General techniques for building and analyzing algorithms (greedy, divide & conquer, dynamic programming, network flows). Introduction to NP-completeness.

#### COURSE DETAILS:

The objective of this course is to introduce concepts and problem-solving techniques that are used in the design and analysis of efficient algorithms. This is done by studying various algorithms and data structures.

## Topics

• The following topics may be included:
• Motivating example: the stable matching problem
• Greedy (graph) algorithms, BFS, DFS, Dijkstra's Kruskal's and Prim's
• Simple data structures: priority queues (with heaps) and union-find
• Divide and conquer algorithms ant their anaysis: solving recursions
• Dynamic programing algorithms and their analysis
• Flow algorithms and matching
• Randomized algorithms
• NP-completeness

#### NOTES:

The course has a final examination (worth 40% of the total grade).
There will be four homework assignments which won't be collected and graded. Instead, there will be four 50-min quizzes in class (worth 15% each).

## Materials

#### MATERIALS + SUPPLIES:

Reference Material:

Introduction to Algorithms (3rd Edition)
, T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, MIT Press, 2009, 9780262033848

Algorithm Design
J. Kleinberg, É. Tardos
2006
ISBN: 9780321295354

Your personalized Course Material list, including digital and physical textbooks, are available through the SFU Bookstore website by simply entering your Computing ID at: shop.sfu.ca/course-materials/my-personalized-course-materials.