CSCI 532, Fall 2025

CSCI 532: Algorithms

Fall 2025

Date	Lecture Topic	Homework
21 Aug	Background/Skills Check
26 Aug 28 Aug	Minimum Spanning Trees (Graph Intro) Closest Pair (Divide and Conquer)	HW 1 (Due 16 Sep)
02 Sep 04 Sep	Longest Path in DAG (Dynamic Programming) Tree Algorithms (Dynamic Programming)
09 Sep 11 Sep	Flow Networks Flow Networks
16 Sep 18 Sep	Flow Networks Test 1
23 Sep 25 Sep	Linear Programming (Intro) Linear Programming (Simplex)	HW 2 (Due 21 Oct)
30 Sep 02 Oct	Linear Programming (Duality) Linear Programming (ILPs)
07 Oct 09 Oct	Randomized (Closest Pair) Randomized
14 Oct 16 Oct	Online Algorithms Online Algorithms
21 Oct 23 Oct	NP Completeness Test 2
28 Oct 30 Oct	Approximation Algorithms (APX) Approximation Algorithms (PTAS)	HW 3 (Due 18 Nov)
04 Nov 06 Nov	Approximation Algorithms (Randomized) Approximation Algorithms (Randomized Rounding)
11 Nov 13 Nov	No Class - Veteran's Day Approximation Algorithms (Inapproximability)
18 Nov 20 Nov	FPT Test 3
25 Nov 27 Nov	No Class - Thanksgiving No Class - Thanksgiving
02 Dec 04 Dec	Presentations Presentations
11 Dec	Presentations, 2:00 - 3:50 pm

Schedule subject to change. Refresh webpage (or hit F5) to view current page.

Lecture

Tuesday, Thursday 1:40 - 2:55 pm in NAH 153
Lectures will be videotaped and put on this website.

Instructor

Sean Yaw

E-mail: sean.yaw (at) montana.edu (email me whenever, I'll respond as soon as I get it)
Office: Barnard Hall 360
Office Hours: Tuesday, Thursday 12:00 - 1:30 pm and by appointment.

Textbook

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (3rd edition).

Course Objectives

MSU course description: Concrete time and space complexity; combinatorial algorithms; greedy algorithms; dynamic programming; probabilistic and randomized algorithms; branch-and-bound algorithms.

At the end of the course, my goal is for you to be able to:

Given a problem, understand it and develop a clear, efficient plan to solve it.
Understand a broad set of algorithmic tools and have an intuition for when to apply which tools, including:

Dynamic Programming.
Greedy Approaches.
Graph Representations.
Linear Programming.
Approximation Techniques.

Understand and be able to comment on the time and space complexity of an algorithm, including being able to characterize recursive relations.
Understand what NP-Complete problems are, have an intuition for the solvability of new problems, and have familiarity with techniques to deal with NP-Complete problems.

Grading

Homework - 20%
Test 1, 2, 3 - 20% each
Project - 20%

At the end of the semester, grades will be determined (after any curving takes place) based on your class average as follows:

93+: A
90+: A-
87+: B+
83+: B
80+: B-
77+: C+
73+: C
70+: C-
67+: D+
63+: D
60+: D-
0+: F

Late Policy

No late submissions will be accepted.

Collaboration Policy

You are encouraged to do homework assignments in groups of two people. You must indicate on the submission everyone that contributed. If someone did not substantially contribute to a submission, they cannot be included on it.
Exams are to be taken individually.
You may not copy or modify solutions that are not your own (e.g. from the Internet, from a classmate not listed as a contributor, from our AI overlords,...) for any graded material.

AI Policy

You may use AI tools to help you understand concepts, guide your problem-solving process, or improve your writing. However, you are expected to fully understand all of the work you submit. If you submit work that you cannot explain or demonstrate understanding of, then you are submitting work that is not yours. In such cases, grades may be adjusted retroactively to reflect this. You will not have access to AI on the in-class tests.