CSCI 382
Algorithms

Time

MWF 10:10am - 11:00am (A3)

Location

MC Reynolds 314

Instructor

Dr. Brent Yorgey
yorgey@hendrix.edu
(501) 450-1377
Office Hours

Overview

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 brute-force, 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.

Learning Goals

Upon completing this course, you will be able to:

Resources

Calendar

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 up-to-date.

Assignment submission form Excused absence request form Reflector report form
Unit Date Activity / Lecture Assignments & Resources
       
    stream = video     pdf = PDF     pogil = POGIL activity  
       
Introduction W Aug 23 Introduction to POGIL and CSCI 382 pogil HW 0 (Concept review) out
    Brute force algorithms pogil See the induction resources linked above!
  F 25 Reasons for POGIL pogil CSCI student survey due
    GCD analysis pogil I  
       
  M 28 GCD analysis II; proving algorithms correct stream pdf Grading contract due
Asymptotic Analysis W 30 Intro to asymptotic analysis pogil HW 0 due; HW 1 (GCD) out
  F Sep 1 Asymptotic analysis definitions and limit theorems stream pdf  
       
  M 4 No class; Labor Day  
  W 6 no class meeting (Dr. Yorgey travel) yt yt  
  F 8 no class meeting (Dr. Yorgey travel) HW 1 due; HW 2 (asymptotic) out
       
  M 11 Asymptotic Analysis Zoo stream pdf  
Graphs W 13 Graphs intro pogil  
  F 15 Graph proofs pogil HW 2 due; HW 3 (Graphs) out
       
  M 18 BFS stream pdf  
  W 20 BFS & bipartite graphs stream pdf  
  F 22 DAGs and topsort stream pdf HW 3 due; HW 4 (DAGs) out
      Topsort pseudocode & analysis
      check-graph.py
       
Greedy Algorithms M 25 Introduction to Dijkstra’s Algorithm pogil Grading contract evaluation due
  W 27 Dijkstra’s Algorithm stream pdf  
  F 29 Analysis of Dijkstra’s algorithm stream pdf HW 4 due
       
  M Oct 2 Minimum spanning trees pogil Exam 1 out
  W 4 Kruskal’s algorithm pogil  
  F 6 Union-find stream pdf  
       
  M 9 Exam 1 HW 5 (percolation) out
Divide & Conquer W 11 Introduction to Divide & Conquer pogil  
  F 13 No class; Fall Break  
       
  M 16 Divide & Conquer Arithmetic pogil  
  W 18 Master Theorem and Karatsuba’s Algorithm stream pdf  
  F 20 Divide & Conquer example: QuickSelect stream pdf HW 5 due; HW 6 (D&C) out
       
Dynamic Programming M 23 Intro to Dynamic Programming pogil  
  W 25 DP exemplar: high/low stress jobs stream pdf  
    High/low stress jobs writeup  
  F 27 2D dynamic programming (subset sum) pogil HW 6 due; HW 7 (DP) out
      High/low stress jobs writeup
      Subset sum writeup
       
  M 30 Floyd-Warshall stream pdf Grading contract evaluation due
Network flow W Nov 1 Intro to flow networks pogil  
  F 3 The Ford-Fulkerson algorithm stream pdf HW 7 due
       
  M 6 Max flow-min cut theorem stream pdf Exam 2 out
  W 8 MFMC theorem; applications of flow networks stream pdf  
Amortized Analysis F 10 Intro to amortized analysis pogil  
       
  M 13 Exam 2 HW 8 (flow) out
  W 15 Amortized analysis stream pdf  
  F 17 Amortized analysis examples pdf  
       
  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 INDEPENDENT-SET, SAT, and reducibility stream pdf final exam out
  W 29 P and NP stream pdf  
  F Dec 1 NP-completeness stream pdf HW 9 due
    Levin, “Universal Sequential Search Problems”  
    Cook, “The Complexity of Theorem-Proving Procedures”  
    Aloupis et al, “Classic Nintendo Games are (Computationally) Hard”  
       
  Th 7 Final exam 8:30-11:30  


Grading

Grading contracts

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 agreed-upon 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.

Required components of a grading contract

There is no specific format required for a grading contract, but it must have the following components:

Example grading contract

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.

Grading contract submission

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.

Contract evaluation and adjustment

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:

  1. Contain a copy of your original grading contract, with items you have completed checked off.

  2. Revise your grading contract with more specific details as appropriate, for example, regarding which modules you intend to complete.

  3. Include a 1-2 paragraph reflection, which answers questions such as the following:

    • What have you done well?
    • What have you learned?
    • What could you do to improve your learning?
    • What could I (the instructor) do to improve your learning?
    • Are there ways in which you have not lived up to the requirements of your contract, and if so, what steps are you taking, or will you take, to rectify that?

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).

A, B, and C grades

D and F grades

[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.


Weekly problem sets

Assignment submission form algorithms-hw.sty (LaTeX style)


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 self-reported 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] 4-5 hrs W Aug 23 W Aug 30
1 GCD and induction [tex] 7-9 hrs W Aug 30 F Sep 8
2 Asymptotic analysis [tex] 5.5-7 hrs F Sep 8 F Sep 15
3 Graphs [tex, graph-F23.txt] 6-8 hrs F Sep 15 F Sep 22
4 DAG analysis [tex] 6.5-8.5 hrs F Sep 22 F Sep 29
  topsort pseudocode & analysis [tex]      
  graph data, check-graph.py      
5 Percolation [tex] 8.5-10 hrs M Oct 9 F Oct 20
  Union-find      
6 Divide & Conquer [tex] 8-10 hrs F Oct 20 F Oct 27
7 Dynamic Programming [tex] 7-9 hrs F Oct 27 M Nov 6
  High/low stress jobs writeup      
  Subset sum writeup      
8 Flow Networks [tex] 5-7 hrs M Nov 13 M Nov 20
9 Amortized analysis [tex] 5-7 hrs M Nov 20 F Dec 1

Academic integrity

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.

HW grading

Each solution on a problem set will be graded on a 0-4 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.

HW submission

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.

Exams

# 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 grading

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.

Exam revision

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 agreed-upon 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.

Tokens and submission policies

Late submissions

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).

Revision

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.

Tokens

Each student starts the semester with three virtual tokens which they can spend however they wish. Tokens are non-transferable.

Conversely, additional tokens may be earned at any time:

Expectations

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
  • Check your email and Teams for occasional course announcements.
  • Fill out the form requesting an excused absence as soon as you know you will need to miss class.
  • Let me know as soon as possible if you feel you are struggling, would like extra help, or have something going on that will affect your engagement in the course or your ability to fulfill your responsibilities.
  • Clearly communicate expectations, assignment details and dates, and grading standards.
  • Return grades and feedback on submitted work within 7 days of submission.
  • Provide a way for you to view your current grades in the course.
  • Respond to emails within 24 hours.
Preparation
  • Come prepared to fully engage in class meetings, with distractions minimized, to the best of your ability.
  • Spend time outside of class actively practicing unfamiliar or shaky concepts or skills (not just reading over notes).
  • Have a concrete plan for how we will spend each class meeting, prepared to lead you through the plan.
  • Complete all homework and exam questions myself, to help ensure they are reasonable and don't hold any unintended surprises.
Engagement
  • Actively engage in lectures by taking notes and asking questions.
  • Actively engage in POGIL activities by working with your teammates, fulfilling your assigned role, and working hard towards completing the assigned activity.
  • Start early on homework assignments and exam preparation, work hard, work together, and get help when you need it.
  • Abide by the College's Academic Integrity Policy and the Computer Science-specific Academic Integrity Policy.
  • Make myself available to meet outside of class, and give you my full attention during a meeting.
  • Be committed to your learning, open to feedback and willing to respond in substantive ways to your suggestions or concerns.

Attendance

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.

Academic Integrity

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 Science-specific Academic Integrity Policy.

Disabilities

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.