CSC 454/654 – Spring 2021 – Schedule

The following gives a schedule of topics covered, readings assigned, and assignment handouts/due dates. Each topic includes several required readings that students should read before the topic is discussed in class – always look ahead a few days to see what readings you should be doing. Note that some topics, particularly weeks 1, 2, and 9, should be mostly review from earlier classes (CSC 250 and CSC 330), so we will go through these very quickly focusing primarily how this material fits in the context of general algorithm study.

The schedule in this class is flexible, and past dates will be updated to reflect what was actually covered. Future dates are always tentative and subject to change.

Week 1: January 19 – January 22

Reading: Perrin Number Information and Chapters 1–2
Tuesday: Class overview and syllabus review; introduction to the study of algorithms
Thursday: Basics of algorithm analysis
Handout: Syllabus

Week 2: January 25 – January 29

Reading: Chapter 3
Topics: Asymptotic notation and summations

Week 3: February 1 – February 5

Reading: (For Thursday) Sections 4.1–4.2
Tuesday: Common functions and relative growth rates
Thursday: Divide-and-conquer basics and Strassen’s algorithm

Week 4: February 8 – February 12

Reading: Sections 4.3–4.5 and 7.1–7.4
Tuesday: Recurrences
Thursday: Quicksort

Week 5: February 15 – February 19

Reading: Section 8.1, Sections 15.1 – 15.2
Tuesday: Lower bound for comparison-based sorting
Thursday: Dynamic programming, day 1

Week 6: February 22 – February 26

Reading: Sections 15.3 and 15.5
Topic: Dynamic programming, continued

Week 7: March 1 – March 5

Reading: Sections 16.1 – 16.3
Topic: Greedy algorithms

Week 8: March 8 – March 12

Tuesday, March 9: Midterm Exam
Thursday: Basic graph algorithms, day 1 (Sections 22.1 – 22.2)

Week 9: March 15 – March 19

Tuesday: Basic graph algorithms, day 2 (Chapter 22.3 – 22.4)
Thursday: Minimum spanning tree algorithms (Chapter 23)

Week 10: March 22 – March 26

Tuesday: Single-source Shortest Paths (Sections 24.1–24.3)
Thursday: All-pairs shortest paths (Sections 25.1–25.2)

Week 11: March 29 – April 2

Reading: Sections 34.1 – 34.4
Topic: NP-completeness

Week 12: April 5 – April 9

Reading: Sections 34.5
Topic: NP-completeness – practice and common errors

Week 13: April 12 – April 16

Reading: Sections 35.1 – 35.3
Topic: Coping with NP-completeness – approximation algorithms

Week 14: April 19 – April 23

Tuesday: Class-choice topic
Thursday: Review/Problem solving day

Final Exam

Tuesday, May 4, 12:00-3:00