CSCI 382
Algorithms

Time

MWF 9:10am - 10:00am (A2)

Location

CSCI 382 Algorithms in Microsoft Teams

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. 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
         
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 (proof and analysis)    
  F Oct 2   Union-find 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    
Dynamic Programming W 14 Intro to Dynamic Programming    
  F 16   DP exemplar: high/low stress jobs HW 6 due; HW 7 (DP) out
         
  M 19 2D dynamic programming (subset sum)    
  W 21   More DP examples (matrix chain mult)  
  F 23   Floyd-Warshall HW 7 due; HW 8 (DP II) out
         
Network flow M 26 Intro to flow networks    
  W 28   The Ford-Fulkerson algorithm  
  F 39   Applications of flow networks HW 8 due; Exam 2 out
         
  M Nov 2   Max flow-min 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 3-SAT    
  F 20   NP-completenes HW 10 due; final exam out
         
  M 23   CIRCUIT-SAT and NP-hard video games  
         
  T Dec 8 Final exam due; oral exam slots 8:30-11:30    

Weekly problem sets

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


# 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] F Sep 18 F Sep 25

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.

Exams

There will be two midterm exams and a cumulative final exam. Each exam will have two parts, a take-home portion and an oral portion.

Grading scale

Grading for this course will work on a cumulative, points-based system.

The total points available will thus be at least 850.

Final grades will be assigned as follows:


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

Algorithms will meet synchronously every Monday, Wednesday, and Friday from 9:10-10: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!

Piazza

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.

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.