CSCI 432, Spring 2025

CSCI 432: Advanced Algorithm Topics

Spring 2025

Date	Lecture Topic	Reading	Homework
14 Jan 16 Jan	Intro/Running Time Recurrence Relations	3 4.5
21 Jan 23 Jan	Dynamic Programming Dynamic Programming	15 15	HW 1 (Due 28 Jan)
28 Jan 30 Jan	Dynamic Programming Dynamic Programming	15 15	HW 2 (Due 04 Feb)
04 Feb 06 Feb	Greedy Greedy	16 16	HW 3 (Due 11 Feb)
11 Feb 13 Feb	Review Test 1
18 Feb 20 Feb	Flow Networks Flow Networks	26 26	HW 4 (Due 25 Feb)
25 Feb 27 Feb	Flow Networks Flow Networks	26 26	HW 5 (Due 04 Mar)
04 Mar 06 Mar	Linear Programming Linear Programming	29 29	HW 6 (Due 11 Mar)
11 Mar 13 Mar	Linear Programming Linear Programming	29 29	HW 7 (Due 25 Mar)
18 Mar 20 Mar	No Class - Spring Break No Class - Spring Break
25 Mar 27 Mar	Review Test 2
01 Apr 03 Apr	Approximation Algorithms Approximation Algorithms	35 35	HW 8 (Due 08 Apr)
08 Apr 10 Apr	Approximation Algorithms Approximation Algorithms	35 35	HW 9 (Due 15 Apr)
15 Apr 17 Apr	Approximation Algorithms Approximation Algorithms	35 35	HW 10 (Due 22 Apr)
22 Apr 24 Apr	Randomization Randomization	5, 35 5, 35	HW 11 (Due 29 Apr)
29 Apr 01 May	Review Test 3
08 May	Final Exam, 12:00 - 1:50 pm

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

Lecture

Tuesday, Thursday 12:15 - 1:30 pm in Romney 315
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 10:00 - 12:00 pm, Thursday 11:00 - 12:00 pm and by appointment.

Grader

Sultan Yarylgassimov

E-mail: sultanyaril (at) gmail.com
Office Hours: Wednesday 2:00 - 4:00 pm in Barnard Hall 259

Textbook

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

Course Prerequisites

CSCI 246: Discrete Structures.
CSCI 232: Data Structures and Algorithms.
CSCI 338: CS Theory. Strongly recommended.

Course Objectives

MSU course description: A rigorous examination of advanced algorithms and data structures. Topics include average case analysis, probabilistic algorithms, advanced graph problems and theory, distributed and parallel programming.

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

Given a problem, understand it and develop a clear, efficeint 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 and Algorithms.
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 (lowest dropped) - 60%
Tests 1, 2, and 3 - 30% (10% each)
Final Exam - 10%

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

If you submit a homework assignment late, but within 12 hours of being due, the maximum credit you can receive is 50%. After 12 hours, you receive 0.

Collaboration Policy

You may do homework assignments in groups of up to three 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.
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, AI overlords...) for any graded material.

Failure to abide by these rules will result in everyone involved being reported to the Dean of Students and could result in failing the course.