CSC 454/654 – Spring 2022 – 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 design.

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 10 – January 14

Reading: Perrin Number Information and Chapters 1–2
Tuesday: Class overview and syllabus review; intro to algorithms using Perrin numbers
Thursday: Review and discussion of formal notation, reasoning, and writing
Handout: Syllabus

Week 2: January 17 – January 21

Reading: Chapter 3 and Appendix A
Topics: Basics of algorithm analysis and asymptotic notation

Week 3: January 24 – January 28

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

Week 4: January 31 – February 4

Reading: Sections 4.3–4.5 (for Tuesday) and 7.1–7.4 (for Thursday)
Topics: Divide and Conquer, Recurrences, and Quicksort

Week 5: February 7 – February 11

Reading: Section 8.1
Topics: More on quicksort, Lower bound for comparison-based sorting, and exam review

Week 6: February 14 – February 18

Monday: Assignment 2 due at midnight
Tuesday: Mid-term Exam 1
Reading: Sections 15.1–15.3
Thurs: Dynamic programming, day 1

Week 7: February 21 – February 25

Reading: Section 15.4 and sample problems handout
Topic: Dynamic programming, week 2

Week 8: February 28 – March 4

Reading: Sections 16.1 – 16.3
Topic: Greedy algorithms

No class March 7 – March 11 (Spring Break)
Week 9: March 14 – March 18

Reading: Sections 22.1 – 22.4
Topic: Elementary graph algorithms

Week 10: March 21 – March 25

Tuesday: Minimum spanning tree algorithms (Chapter 23)
Thursday: Single-source shortest paths (Sections 24.1–24.3)

Week 11: March 28 – April 1

Tuesday: All-pairs shortest paths (Sections 25.1–25.2) and exam review
Thursday: Mid-term Exam 2

Week 12: April 4 – April 8

Reading: Sections 34.1 – 34.4
Topic: NP-completeness

Week 13: April 11 – April 15

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

Week 14: April 18 – April 22

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

Week 15: April 25 – April 27

Tuesday: Review/Problem solving day
No class Thursday (Reading Day)

Final Exam

Thursday, May 5, 12:00-3:00