CSCI 532: Algorithms

Spring 2020

Date Lecture Topic Reading Homework
14 Jan
16 Jan
Background
Divide and Conquer (Closest Pair)
3-4
33.4
HW 1 (Due 27 Jan)
Solution
21 Jan
23 Jan
Dynamic Programming (Change Making)
Dynamic Programming (Matrix Multiplication)
4.2, Notes
15.1, 15.2
 
 
28 Jan
30 Jan
Dynamic Programming (Sequence Alignment)
Greedy (MST & Change Making)
15.4
Notes, 23
HW 2 (Due 10 Feb)
Solution
04 Feb
06 Feb
Greedy (Activity Selection)
Greedy (Lateness Scheduling)
16.1
Notes
 
 
11 Feb
13 Feb
Quiz 1
Flow Networks
 
26
HW 3 (Due 24 Feb)
Solution
18 Feb
20 Feb
Flow Networks
Flow Networks
 
 
 
 
25 Feb
27 Feb
Linear Programming
Linear Programming
29
 
HW 4 (Due 09 Mar)
Solution
03 Mar
05 Mar
Linear Programming
Linear Programming
 
 
 
 
10 Mar
12 Mar
Quiz 2
Linear Programming
 
 
 
HW 5 (Due 30 Mar)
17 Mar
19 Mar
Spring Break - No Class
Spring Break - No Class
 
 
 
 
24 Mar
26 Mar
NP Completeness
NCUR - No Class
34
 
 
 
31 Mar
02 Apr
Approximation Algorithms (Vertex Cover)
Approximation Algorithms (Set Cover)
35.1
35.3
HW 6 (Due 13 Apr)
Solution
07 Apr
09 Apr
Approximation Algorithms (Knapsack)
Approximation Algorithms (TSP)
Notes
35.2
 
 
14 Apr
16 Apr
LP Relaxation / Randomized Rounding
Quiz 3
35.4
 
 
 
21 Apr
23 Apr
Presentations
Presentations
 
 
HW 7 (Due 04 May)
 
28 Apr
30 Apr
Presentations
Presentations
 
 
 
 
07 May FINAL EXAM, Posted 8:00 am (5/7), due 8:00 am (5/8)    
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.