MWF 10:10am  11:00am (A3)
MC Reynolds 317 / MARS lab
Dr. Brent Yorgey
yorgey@hendrix.edu
(501) 4501377
Office Hours
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  POGIL Activity  Lecture  Assignments & Resources 
Introduction  W Aug 24  Introduction to POGIL and CSCI 382  HW 0 (Concept review) out  
Brute force algorithms  See the induction resources linked above!  
F 26  Reasons for POGIL  CSCI student survey  
GCD analysis I  
M 29  GCD analysis II  
W 31  Proving algorithms correct  HW 0 due; HW 1 (GCD) out  
Asymptotic Analysis  F Sep 2  Intro to asymptotic analysis  
M 5  No class; Labor Day  
W 7  Asymptotic analysis definitions and limit theorems  
F 9  Asymptotic analysis zoo  HW 1 due; HW 2 (asymptotic) out  
M 12  Three proofs  
Graphs  W 14  Graphs intro  
F 16  Graph proofs  HW 2 due; HW 3 (Graphs) out  
M 19  BFS  
W 21  BFS & bipartite graphs  
F 23  DAGs and topsort  HW 3 due; HW 4 (DAGs) out  
Topsort pseudocode & analysis  
checkgraph.py  
Greedy Algorithms  M 26  Introduction to Dijkstra’s Algorithm  
W 28  Dijkstra’s Algorithm  
F 30  Analysis of Dijkstra’s algorithm  HW 4 due  
M Oct 3  Minimum spanning trees  Exam 1 out  
W 5  Kruskal’s algorithm  
F 7  Implementing Kruskal  
Unionfind  
M 10  Exam 1; HW 5 (percolation) out  
Divide & Conquer  W 12  Introduction to Divide & Conquer  
F 14  No class; Fall Break  
M 17  Divide & Conquer Arithmetic  
W 19  Master Theorem and Karatsuba’s Algorithm  
F 21  Selection  HW 5 due; HW 6 (D&C) out  
Dynamic Programming  M 24  Intro to Dynamic Programming  
W 26  DP exemplar: high/low stress jobs  
F 28  2D dynamic programming (subset sum)  HW 6 due; HW 7 (DP) out  
High/low stress jobs writeup  
M 31  FloydWarshall  
Network flow  W Nov 2  Intro to flow networks  
F 4  The FordFulkerson algorithm  HW 7 due  
M 7  MaxFlow  Applications of flow networks: max bipartite matching, committee assignment  Exam 2 out  
W 9  Max flowmin cut theorem  
Amortized Analysis  F 11  Intro to amortized analysis  
M 14  Exam 2; HW 8 (flow) out  
W 16  Amortized Analysis of Arrays  
F 18  Binomial Heap  
Intractability  M 21  Intro to reductions  HW 8 due; HW 9 (amortized) out  
W 23  No class; Thanksgiving Break  
F 25  No class; Thanksgiving Break  
M 28  Reducibility  final exam out  
W 30  SAT and 3SAT  
F Dec 2  NPcompleteness  HW 9 due  
R 8  Final exam 8:3011:30 
#  HW  Assigned  Due 

Survey  W Aug 24  F Aug 26  
0  Concept review [tex]  W Aug 24  W Aug 31 
1  GCD and induction [tex]  W Aug 31  F Sep 9 
2  Asymptotic analysis [tex]  F Sep 9  F Sep 16 
3  Graphs [tex, graphF22.txt]  F Sep 16  F Sep 23 
4  DAG analysis [tex]  F Sep 23  F Sep 30 
topsort pseudocode & analysis [tex]  
graph data, checkgraph.py 
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 3  M Oct 10 
2  Midterm 2 [tex]  M Nov 7  M Nov 14 
3  Final exam [tex]  M Nov 28  R Dec 8 
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 revise 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, but you must spend n tokens to turn in a problem set up to n weeks late.
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).
From the day a graded problem set or midterm exam is returned to you, you have one week to submit a revised version, if you wish; submitting a revised version costs one token.
If you turn in a revised problem set or exam more than one week after it is returned to you, the same policy applies as for late submissions, with a cost of one token per week late (in addition to the token for resubmission).
It is not possible to revise the final exam.
Each student starts the semester with ten virtual tokens which they can spend however they wish. Tokens are nontransferable.
Conversely, additional tokens may be earned at any time:
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 revising it).
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 


You will receive credit for attendance and active participation in POGIL activites. Although attendance to lectures is not formally reflected in your grade, I expect you to attend and actively engage by responding and asking questions.
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.