CSCI 532: Algorithms

Spring 2021

Date Lecture Topic Reading Homework
12 Jan
14 Jan
Background Skills Check
Divide and Conquer (Closest Pair)
3-4
33.4
HW 1 (Due 25 Jan)
Solution
19 Jan
21 Jan
Dynamic Programming (Change Making)
Dynamic Programming (Matrix Multiplication)
4.2, Notes
15.1, 15.2
 
 
26 Jan
28 Jan
Dynamic Programming (Sequence Alignment)
Greedy (MST)
15.4
Notes, 23
HW 2 (Due 08 Feb)
Solution
02 Feb
04 Feb
Greedy (Activity Selection)
Greedy (Lateness Scheduling)
16.1
Notes
 
 
09 Feb
11 Feb
Quiz 1 Solution
Flow Networks
 
26
HW 3 (Due 22 Feb)
Solution
16 Feb
18 Feb
Flow Networks
Flow Networks
 
 
 
 
23 Feb
25 Feb
Linear Programming
Linear Programming
29
 
HW 4 (Due 08 Mar)
 
02 Mar
04 Mar
Linear Programming
Linear Programming
 
 
 
 
09 Mar
11 Mar
Linear Programming
Quiz 2
 
 
 
 
16 Mar
18 Mar
No Class
No Class
 
 
 
 
23 Mar
25 Mar
NP Completeness
Approximation Algorithms (Vertex Cover)
34
35.1
HW 5 (Due 05 Apr)
 
30 Mar
01 Apr
Approximation Algorithms (Set Cover)
Approximation Algorithms (Knapsack)
35.3
Notes
 
 
06 Apr
08 Apr
Approximation Algorithms (TSP)
LP Relaxation / Randomized Rounding
35.2
35.4
HW 6 (Due 14 Apr)
 
13 Apr
15 Apr
Other (FPT? Randomization?)
Quiz 3

 
 
 
20 Apr
22 Apr
Presentations
Presentations
 
 
 
 
27 Apr
29 Apr
Presentations
Presentations
 
 
 
 
Schedule subject to change. Refresh webpage (or hit F5) to view current page.

Lecture

Instructor

Sean Yaw

Textbook

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:

  1. Given a problem, understand it and develop a clear, efficient plan to solve it.
  2. Understand a broad set of algorithmic tools and have an intuition for when to apply which tools, including:
  3. Understand and be able to comment on the time and space complexity of an algorithm, including being able to characterize recursive relations.
  4. 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

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

Late Policy

No late submissions will be accepted.

Collaboration Policy

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.

Sickness Accommodations

Masks

Per MSU: "Face coverings are required in all indoor spaces and all enclosed or partially enclosed outdoor spaces. MSU requires all students to wear face masks or cloth face coverings in classrooms, laboratories and other similar spaces where in-person instruction occurs. MSU requires the wearing of masks in physical classrooms to help mitigate the transmission of SARS-CoV-2, which causes COVID-19. The MSU community views the adoption of these practices as a mark of good citizenship and respectful care of fellow classmates, faculty, and staff. The complete details about MSU’s mask requirement can be found at https://www.montana.edu/health/coronavirus/index.html."