MWF 10:10am  11:00am (A3)
MC Reynolds 314
Dr. Brent Yorgey
yorgey@hendrix.edu
(501) 4501377
Office Hours
Introduction to standard algorithms and algorithm design strategies, with an emphasis on constructing rigorous formal proofs of algorithm correctness and performance, as well as translating fluently between theory and practice. Strategies discussed include bruteforce, greedy algorithms, divide and conquer, dynamic programming, amortization, and problem reduction. The course includes an introduction to complexity theory and the complexity classes P and NP. Prerequisites: CSCI 151 and MATH 240.
Upon completing this course, you will be able to:
Below is a unified calendar for the semester showing the topic and mode for each class meeting, as well as assignment due dates. Some specifics may change as the semester progresses, but the calendar will be kept uptodate.
Unit  Date  Activity / Lecture  Assignments & Resources 
= video = PDF = POGIL activity  
Introduction  W Aug 23  Introduction to POGIL and CSCI 382  HW 0 (Concept review) out 
Brute force algorithms  See the induction resources linked above!  
F 25  Reasons for POGIL  CSCI student survey due  
GCD analysis I  
M 28  GCD analysis II; proving algorithms correct  Grading contract due  
Asymptotic Analysis  W 30  Intro to asymptotic analysis  HW 0 due; HW 1 (GCD) out 
F Sep 1  Asymptotic analysis definitions and limit theorems  
M 4  No class; Labor Day  
W 6  no class meeting (Dr. Yorgey travel)  
F 8  no class meeting (Dr. Yorgey travel)  HW 1 due; HW 2 (asymptotic) out  
M 11  Asymptotic Analysis Zoo  
Graphs  W 13  Graphs intro  
F 15  Graph proofs  HW 2 due; HW 3 (Graphs) out  
M 18  BFS  
W 20  BFS & bipartite graphs  
F 22  DAGs and topsort  HW 3 due; HW 4 (DAGs) out  
Topsort pseudocode & analysis  
checkgraph.py  
Greedy Algorithms  M 25  Introduction to Dijkstra’s Algorithm  Grading contract evaluation due 
W 27  Dijkstra’s Algorithm  
F 29  Analysis of Dijkstra’s algorithm  HW 4 due  
M Oct 2  Minimum spanning trees  Exam 1 out  
W 4  Kruskal’s algorithm  
F 6  Unionfind  
M 9  Exam 1  HW 5 (percolation) out  
Divide & Conquer  W 11  Introduction to Divide & Conquer  
F 13  No class; Fall Break  
M 16  Divide & Conquer Arithmetic  
W 18  Master Theorem and Karatsuba’s Algorithm  
F 20  Divide & Conquer example: QuickSelect  HW 5 due; HW 6 (D&C) out  
Dynamic Programming  M 23  Intro to Dynamic Programming  
W 25  DP exemplar: high/low stress jobs  
High/low stress jobs writeup  
F 27  2D dynamic programming (subset sum)  HW 6 due; HW 7 (DP) out  
High/low stress jobs writeup  
Subset sum writeup  
M 30  FloydWarshall  Grading contract evaluation due  
Network flow  W Nov 1  Intro to flow networks  
F 3  The FordFulkerson algorithm  HW 7 due  
M 6  Max flowmin cut theorem  Exam 2 out  
W 8  MFMC theorem; applications of flow networks  
Amortized Analysis  F 10  Intro to amortized analysis  
M 13  Exam 2  HW 8 (flow) out  
W 15  Amortized analysis  
F 17  Amortized analysis examples  
M 20  Binomial heaps  HW 8 due; HW 9 (amortized) out  
W 22  No class; Thanksgiving Break  
F 24  No class; Thanksgiving Break  
M 27  INDEPENDENTSET, SAT, and reducibility  final exam out  
W 29  P and NP  
F Dec 1  NPcompleteness  HW 9 due  
Levin, “Universal Sequential Search Problems”  
Cook, “The Complexity of TheoremProving Procedures”  
Aloupis et al, “Classic Nintendo Games are (Computationally) Hard”  
Th 7  Final exam 8:3011:30 
In this course, you determine your own final grade: you will prepare and submit for my approval a grading contract explaining your chosen final grade and what you will do to achieve it. You will then earn your chosen final grade by fulfilling the agreedupon contract.
This may be different than what you are used to. Professor Cathy Davidson of CUNY perfectly sums up the reasons for doing things this way:
The advantage of contract grading is that you, the student, decide how much work you wish to do this semester; if you complete that work on time and satisfactorily, you will receive the grade for which you contracted. This means planning ahead, thinking about all of your obligations and responsibilities this semester and also determining what grade you want or need in this course. The advantage of contract grading to the professor is no whining, no special pleading, on the student’s part. If you complete the work you contracted for, you get the grade. Done. I respect the student who only needs a C, who has other obligations that preclude doing all of the requirements to earn an A in the course, and who contracts for the C and carries out the contract perfectly.
There is no specific format required for a grading contract, but it must have the following components:
Your desired course grade. You may choose to contract for an A, B, or C (if you’re wondering about D’s and F’s, see below). Note that your grading contract should not explain the reasons for your choice. I will not judge you because of your choice, and you do not need to justify it: there are as many different valid reasons for choosing to work toward a particular final grade as there are students. If you do wish to explain to me the reasons for your choice—which you are in no way required to do—you may do so in an email, a personal conversation, etc., but it should not go in your contract.
A description of the work and requirements you will complete, in checklist format. It doesn’t have to be super detailed, but you do have to explicitly include everything. For example, you can’t just say “I will complete all the assignments listed in the syllabus”; you must actually list them. This is so that you and I both know that you are explicitly aware of the requirements, and to help you keep track of what you have completed and what you have yet to complete. You also have some choice in terms of which assignments you complete, so you must record your choice in the contract.
Note that at the beginning of the semester you may not have a very good idea about this. For example, if you need to complete eight modules, it’s not reasonable to insist that you know which specific modules you plan to complete. However, you can refine your contract over the course of the semester. You just have to put something to start; for example, a reasonable default would be to plan to complete the first eight modules assigned.
For example, a grading contract might look like this:
My desired course grade in Algorithms is a C. To achieve this grade, I will complete the following:
I also understand that I can have at most three unexcused absences. I will probably end up sleeping through my alarm once or twice but other than that I will be in class every day unless I am sick.
You must turn in an initial proposed grading contract by the start of class on Monday, August 28. After the initial submission, I may require some revisions before I approve your contract.
Two times during the semester (Monday, September 25 and Monday, October 30) you are required to reflect on your progress in the course and complete an evaluation of your work, comparing it against what you agreed to in your grading contract. Your evaluation should:
Contain a copy of your original grading contract, with items you have completed checked off.
Revise your grading contract with more specific details as appropriate, for example, regarding which modules you intend to complete.
Include a 12 paragraph reflection, which answers questions such as the following:
Your evaluation is also an opportunity to request an adjustment to your contract in either direction. If you find that you will be unable to meet the obligations of your contract, you may request to move to a lower grade and its requirements. Contrariwise, if you find that you’ve been performing above the obligations of your contract, you may request to fulfill the requirements for a higher grade.
Note, however, that you don’t have to wait for an evaluation to adjust your contract. If your life has really gone off the rails (or if, say, you are finding the class easier and more enjoyable than you thought!) just come and talk to me about adjusting your contract.
To “complete” an assignment means to complete it at or above the required criteria for receiving credit. For example, “complete a midterm exam” means not just taking the exam, but scoring sufficiently high on the problems so as to receive credit (possibly after retaking it).
[Adapted from Cathy Davidson.] You cannot intentionally contract for a grade of D (and certainly not for an F). However, I reserve the right to award a grade of D or F to anyone who fails to meet their contractual obligations in a systematic way. A “D” grade denotes some minimal fulfilling of the contract; an “F” denotes absence of enough satisfactory work, as contracted, to warrant passing of the course. Both a “D” and “F” denote a breakdown of the contractual relationship.
The core of your learning in this class will take place through weekly problem sets, typically due at 5pm on Fridays. The table below lists the assignments and their due dates, along with the expected amount of time to complete each assignment (based on average selfreported times from students in past iterations of the course).
#  HW  Completion time  Assigned  Due 

Survey  W Aug 23  F Aug 25  
0  Concept review [tex]  45 hrs  W Aug 23  W Aug 30 
1  GCD and induction [tex]  79 hrs  W Aug 30  F Sep 8 
2  Asymptotic analysis [tex]  5.57 hrs  F Sep 8  F Sep 15 
3  Graphs [tex, graphF23.txt]  68 hrs  F Sep 15  F Sep 22 
4  DAG analysis [tex]  6.58.5 hrs  F Sep 22  F Sep 29 
topsort pseudocode & analysis [tex]  
graph data, checkgraph.py  
5  Percolation [tex]  8.510 hrs  M Oct 9  F Oct 20 
Unionfind  
6  Divide & Conquer [tex]  810 hrs  F Oct 20  F Oct 27 
7  Dynamic Programming [tex]  79 hrs  F Oct 27  M Nov 6 
High/low stress jobs writeup  
Subset sum writeup  
8  Flow Networks [tex]  57 hrs  M Nov 13  M Nov 20 
9  Amortized analysis [tex]  57 hrs  M Nov 20  F Dec 1 
Discussion and collaboration on the problem sets is encouraged. However, solutions must be written up individually. Copying another student’s writeup, in whole or in part, or directly collaborating on a writeup, will be considered an academic integrity violation. Insightful discussion with others must be cited in your homework solutions. You will not lose credit for such citations.
Each solution on a problem set will be graded on a 04 scale.
To get credit for a problem set, the average score on the problems must be at least 3.25.
If you do not get credit for a problem set, you may revise it; see the resubmission policy below.
Homework assignments must be turned in electronically, in PDF format, via the submission form. You have several options:
Many of the assignments are gratefully based on materials from Brent Heeringa.
#  Exam  Out  Date 

1  Midterm 1 [tex]  M Oct 2  M Oct 9 
2  Midterm 2 [tex]  M Nov 6  M Nov 13 
3  Final exam  M Nov 27  Th Dec 7 
There will be two midterm exams and a cumulative final exam. Each exam will be distributed one week ahead of its administration date. Once you receive the exam, you may:
On the exam administration date, you will take the exam during class, with no external resources allowed. You will need to recreate your solutions using your learned understanding of what you prepared.
Exam problems will be graded in the same manner as homework problems. To receive credit for an exam, you must score an average of 3.0 or better on the exam problems.
If you do not receive credit for an exam, you may retake it; see the resubmission policy below.
However, if you score 2 or lower on an exam problem, Dr. Yorgey may also require you to complete an additional, similar problem. This additional problem must be completed under similar conditions as the original exam (that is, you may prepare a solution ahead of time using any resources you wish, but then you must write out your solution without referring to any resources, at an agreedupon time). To receive credit for the exam you must score an average of 3.0 or better on all the exam problems, including any newly assigned problems.
Weekly problem sets may be turned in late by spending a token.
Exams, on the other hand, must be taken on the scheduled day, unless you have made other arrangements with me (e.g. if you will be travelling for sports on the scheduled day).
Once a graded problem set is returned to you, you may submit a revised version, if you wish; submitting a revised version costs 1/2 token.
Midterm exams may be retaken, for 1 token, at a mutually agreed time. At Dr. Yorgey’s discretion, the retaken exam may include different (but similar) problems than the original exam. In such a case you will still be given the new problems in advance, just as with the original exam.
It is not possible to revise the final exam.
Each student starts the semester with three virtual tokens which they can spend however they wish. Tokens are nontransferable.
Conversely, additional tokens may be earned at any time:
Although you and I play different roles in the course, we both have your learning as a common goal. There are things I expect from you as a student in the course, but there are also things you can expect of me as the course instructor and facilitator.
If I am not fulfilling my responsibilities outlined below, you are welcome (and encouraged!) to discuss it with me.. I will also initiate a conversation if you are not fulfilling yours. However, none of us will meet all of the expectations perfectly—me included!—so it’s also important that we have grace and patience with one another.
What I expect from you  What you can expect from me  

Communication 


Preparation 


Engagement 


Attending class and being an active participant in the class community is one of the most important contributors to your learning. Attendance is especially important in this class since you will often engage in group learning activities.
Hendrix College is committed to high standards of honesty and fairness in academic pursuits. Such standards are central to the process of intellectual inquiry, the development of character, and the preservation of the integrity of the community. Please familiarize yourself with the statement of Academic Integrity.
You should also familiarize yourself with the Computer Sciencespecific Academic Integrity Policy.
If you have a documented disability or some other reason that you cannot meet the above expectations, and/or your learning would be best served by a modification to the usual course policies, I would be happy to work with you—please get in touch (via Teams or email)! The course policies are just a means to an end; I don’t care about the policies per se but I do care about you and your learning.
It is the policy of Hendrix College to accommodate students with disabilities, pursuant to federal and state law. Students should contact Julie Brown in the Office of Academic Success (505.2954; brownj@hendrix.edu) to begin the accommodation process. Any student seeking accommodation in relation to a recognized disability should inform the instructor at the beginning of the course.