MWF 9:10am  10:00am (A2)
CSCI 382 Algorithms in Microsoft Teams
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. All classes (both POGIL activities and lectures) will take place in a Microsoft Teams meeting, in the CSCI 382 Algorithms team.
Unit  Date  POGIL Activity  Lecture  Assignments & Resources 
Introduction  F Aug 21  Introduction to POGIL and CSCI 382  HW 0 (Concept review) out  
Brute force algorithms  See the induction resources linked above!  
M 24  Reasons for POGIL  
GCD analysis I  
W 26  GCD analysis II  
F 28  Proving algorithms correct  HW 0 due; HW 1 (GCD) out  
Asymptotic Analysis  M 31  Intro to asymptotic analysis  
W Sep 2  Asymptotic analysis definitions  
F 4  Asymptotic analysis: limit theorems  HW 1 due; HW 2 (asymptotic) out  
M 7  Three proofs  
Graphs  W 9  Graphs intro  
F 11  BFS  HW 2 due; HW 3 (Graphs) out  
M 14  BFS applications and directed graphs  
W 16  Bipartite graphs  
F 18  DAGs and topsort  HW 3 due; HW 4 (DAGs) out  
Topsort pseudocode & analysis  
checkgraph.py  
Greedy Algorithms  M 21  Introduction to Dijkstra’s Algorithm  
W 23  Dijkstra’s Algorithm  
F 25  Analysis of Dijkstra’s algorithm  HW 4 due; Exam 1 out  
M 28  Minimum spanning trees  
W 30  Kruskal’s algorithm [key]  
F Oct 2  Implementing Kruskal  
Unionfind  Exam 1 due; HW 5 (percolation) out  
Divide & Conquer  M 5  Introduction to Divide & Conquer  
W 7  Divide & Conquer Arithmetic  
F 9  Master Theorem and Karatsuba’s Algorithm  HW 5 due; HW 6 (D&C) out  
M 12  Quickselect  Quickselect pseudocode & analysis  
Dynamic Programming  W 14  Intro to Dynamic Programming  
F 16  DP exemplar: high/low stress jobs  High/low stress jobs writeup  
HW 6 due; HW 7 (DP) out  
M 19  2D dynamic programming (subset sum)  Subset sum writeup  
W 21  More DP examples (matrix chain mult)  
F 23  FloydWarshall (no class meeting)  HW 7 due; HW 8 (DP II) out  
Network flow  M 26  Intro to flow networks  
W 28  The FordFulkerson algorithm  
F 30  Applications of flow networks  HW 8 due; Exam 2 out  
M Nov 2  Max flowmin cut theorem  
Amortized Analysis  W 4  Intro to amortized analysis  
F 6  The accounting method  Exam 2 due; HW 9 (flow) out  
M 9  Amortized analysis examples  
W 11  Binomial heaps  
Intractability  F 13  Intro to reductions  HW 9 due; HW 10 (amortized) out  
M 16  Reductions  
W 18  SAT and 3SAT  
F 20  NPcompletenes  HW 10 due; final exam out  
M 23  CIRCUITSAT and NPhard video games  
T Dec 8  Final exam due; oral exam slots 8:3011:30 
#  HW  Assigned  Due 

0  Concept review [tex]  F Aug 21  F Aug 28 
1  GCD and induction [tex]  F Aug 28  F Sep 4 
2  Asymptotic analysis [tex]  F Sep 4  F Sep 11 
3  Graphs [tex, graph.txt]  F Sep 11  F Sep 18 
4  DAG analysis [tex, graph data, topsort pseudocode & analysis, checkgraph.py]  F Sep 18  F Sep 25 
5  Percolation [tex]  F Oct 2  F Oct 9 
6  Divide & Conquer [tex]  F Oct 9  F Oct 16 
7  Dynamic Programming I [tex]  F Oct 16  F Oct 23 
8  Dynamic Programming II [tex]  F Oct 23  F Oct 30 
The weekly problem sets, typically due Friday at 5:00pm, will collectively be worth about 25% of your grade.
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 points for such citations.
Each student has four late days to spend throughout the semester as they wish. Simply inform me any time prior to the due date for an assignment that you wish to use a late day; you may then turn in the assignment up to 24 hours late with no penalty. Multiple late days may be used on the same assignment. There are no partial late days; turning in an assignment 2 hours late or 20 hours late will both use 1 late day.
Homework assignments must be turned in electronically, in PDF format, via the submission form. You have two options:
Each homework question will be graded on a 5 point scale, as follows:
Many of the assignments are gratefully based on materials from Brent Heeringa.
#  Exam  Assigned  Due 

1  Midterm 1 [tex]  F Sep 25  F Oct 2 
2  Midterm 2  F Oct 30  F Nov 6 
3  Final exam  F Nov 20  T Dec 8 
There will be two midterm exams and a cumulative final exam. Each exam will have two parts, a takehome portion and an oral portion.
Grading for this course will work on a cumulative, pointsbased system.
The total points available will thus be at least 850.
Final grades will be assigned as follows:
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 call me out, perhaps via the anonymous feedback form. 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 


Algorithms will meet synchronously every Monday, Wednesday, and Friday from 9:1010:00am in Microsoft Teams. If you wish to request approval to participate in class asynchronously, you must apply to the Provost’s office.
You will receive points 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.
The default mode of attendance should be with your microphone muted and video on. I recognize that you may have good reasons (either technical or personal) for turning off your video, and I will not ask questions. However, if you are able, I highly encourage you to keep your video on for the most part, since it contributes substantially to everyone’s sense of engagement and connection (not least of all my own!).
With all that said, it’s easy for connection issues to occasionally prevent you from attending despite your best intentions. If this happens just let me know!
This semester we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates and from me. Rather than emailing questions to me, or sending messages in Teams, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.
You should have received a signup link in your email. If you didn’t, or you can’t find it, you can also use this class signup link.
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.