CSCI 532: Algorithms
Fall 2023
Date 
Lecture Topic 
Reading 
Homework 
24 Aug 
Background/Skills Check 
34 

29 Aug
31 Aug 
Dynamic Programming (Change Making)
Dynamic Programming (Matrix Multiplication) 
4.2, Notes
15.1, 15.2 
HW 1 (Due 07 Sep)

05 Sep
07 Sep 
Dynamic Programming (Sequence Alignment)
Greedy (MST) 
15.4
Notes, 23 
HW 2 (Due 18 Sep) 
12 Sep
14 Sep 
Greedy (Activity Selection)
Greedy (Lateness Scheduling) 
16.1
Notes 

19 Sep
21 Sep 
Exam 1
Flow Networks 
26 
HW 3 (Due 03 Oct) 
26 Sep
28 Sep 
Flow Networks
Flow Networks 


03 Oct
05 Oct 
Flow Networks
Linear Programming 
29 
HW 4 (Due 17 Oct)

10 Oct
12 Oct 
Linear Programming
Linear Programming 


17 Oct
19 Oct 
Linear Programming
Exam 2 


24 Oct
26 Oct 
NP Completeness
Approximation Algorithms (Vertex Cover) 
34
35.1 
HW 5 (Due 07 Nov)

31 Oct
02 Nov 
Approximation Algorithms (Set Cover)
Approximation Algorithms (Knapsack) 
35.3
Notes 

07 Nov
09 Nov 
Approximation Algorithms (TSP)
LP Relaxation 
35.2
35.4 
HW 6 (Due 14 Nov)
Presentations 
14 Nov
16 Nov 
Randomized Rounding (and Andras presentation)
Exam 3 


21 Nov
23 Nov 
No Class  Thanksgiving
No Class  Thanksgiving 


28 Nov
30 Nov 
Presentations (Garrett, Jasmine, Zach, Shahnaj, Deanta)
Presentations (Fatima, Angelo, Shama, Redempta, Nicholas) 

HW 7 (Due 11 Dec)

05 Dec
07 Dec 
Presentations (Jacob, Mojtaba, Turner, Sultan, Alex)
Presentations (Caleb, Felicia, Robert, Asibul, Arju) 


12 Dec 
Final Exam, 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 149
 Lectures will be videotaped and put on this website.
Instructor
Sean Yaw
 Email: 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 9:30  11:00 am 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; branchandbound 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 NPComplete problems are, have an intuition for the solvability of new problems, and have familiarity with techniques to deal with NPComplete problems.
Grading
 Homework (lowest dropped)  40%
 Exam 1, 2, and 3  30%
 Presentation  10%
 Final Exam  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,...) for any graded material. I know how to use the Google and I have a Chegg membership. If you find it, I will too!
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.