CSCI 532: Algorithms
Fall 2023
| Date |
Lecture Topic |
Reading |
Homework |
| 24 Aug |
Background/Skills Check |
3-4 |
|
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
- 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 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; 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 (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.