CSCI 382
Algorithms

Time

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

Location

MC Reynolds 317 / MARS lab

Instructor

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

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.

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
        check-graph.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  
      Union-find  
         
  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 Floyd-Warshall    
Network flow W Nov 2 Intro to flow networks    
  F 4   The Ford-Fulkerson algorithm HW 7 due
         
  M 7 Max-Flow Applications of flow networks: max bipartite matching, committee assignment Exam 2 out
  W 9   Max flow-min 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 3-SAT    
  F Dec 2   NP-completeness HW 9 due
         
  R 8 Final exam 8:30-11:30    

Weekly problem sets

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


# 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, graph-F22.txt] F Sep 16 F Sep 23
4 DAG analysis [tex] F Sep 23 F Sep 30
  topsort pseudocode & analysis [tex]    
  graph data, check-graph.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.

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

Submission policies

Late submissions

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

Resubmission

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.

Tokens

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

Conversely, additional tokens may be earned at any time:

Final grade specification

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


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.
  • Let me know via email or Teams message if you will need to miss class for some reason.
  • 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 online 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

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.

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.