## CSCI 382Algorithms

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

• Explain, implement, and apply standard algorithmic solutions to common problems.
• Appropriately select and apply standard algorithmic problem-solving and proof techniques such as greedy algorithms, divide & conquer, dynamic programming, network flow, and amortization.
• Use Big-O notation and standard tools such as recurrence relations and the Master Theorem to analyze the asymptotic time and space complexity of computational processes.
• Explain basic definitions and results in complexity theory; prove NP-hardness results by polynomial reduction.
• Construct and reason about appropriate formal mathematical models of a given computational problem.
• Write coherent, logically sound proofs of algorithm correctness and asymptotic complexity, using standard tools such as induction and invariants.
• Move fluently between theory and practice by writing programs to implement theoretical results, and using theory to analyze existing programs.

## 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 check-graph.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 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 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 Floyd-Warshall   (no class meeting) HW 7 due; HW 8 (DP II) out Network flow M 26 Intro to flow networks W 28 The Ford-Fulkerson algorithm F 30 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

# 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, check-graph.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:

• You can write your solutions by hand and scan them using a free scanner app such as Genius Scan.
• Alternatively, you can type your solutions. I strongly encourage you to use LaTeX; the easiest way to get started is by using a free account on overleaf.com. If you use some other software to type your solutions (e.g. Word or Pages), just be sure to export to a PDF before submitting.

Each homework question will be graded on a 5 point scale, as follows:

• 5: The solution is clear and correct. This solution would easily find a home in a research paper.
• 4: The solution contains a few mistakes, but they are mostly arithmetic or of little significance to the overall argument.
• 3: The solution hits on the main points, but has at least one logical gap.
• 2: The solution contains several logical mistakes, but parts of it are salvageable.
• 1: The solution is just plain wrong.
• 0: No attempt is made at solving the problem.

Many of the assignments are gratefully based on materials from Brent Heeringa.

## Exams

# 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 take-home portion and an oral portion.

• The take-home portion will be similar to a weekly problem set (with some important differences):
• You will be given one week to complete the midterm exams, and at least a week and a half to complete the final exam.
• Like a weekly problem set, you may use any resources in preparing your solutions to the exam—including your notes, textbook, online resources, and each other.
• However, unlike a weekly problem set, I will only answer clarification questions about the exam; I will not offer hints or assistance.
• As with a weekly problem set, each student must turn in their own individual writeup of their exam solutions.
• The oral portion will take place in the week after turning in the exam.
• Either individually or in pairs, students will sign up for a half-hour meeting with me.
• During the meeting, I will ask you to explain one or two of the problems from the written exam, to check your understanding.
• I will also ask you to solve one or two problems you have not seen before.

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

• There will be at least 200 points available on weekly homework assignments in total (usually 5 points per problem).
• You will earn 10 points for attendance and engagement in each POGIL activity (for a total of about 200 points).
• Two midterm exams will be worth 125 points each.
• The final exam will be worth 200 points.
• There may be other occasional opportunities to earn extra points.

The total points available will thus be at least 850.

Final grades will be assigned as follows:

• 680+ points (80%) = A
• 595+ points (70%) = B
• 510+ points (60%) = C
• 425+ points (50%) = D
• less than 425 points = F

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