CSCI 382: Algorithms (Fall 2019)

Documents

Assignments

The weekly problem sets, typically due Friday at 1:10pm, 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 may be turned in either electronically (via the submission form) or on physical paper (use the envelope hanging outside my office). If you submit electronically, I strongly encourage you to use LaTeX; the easiest way to get started is by using a free account on overleaf.com. I will provide a LaTeX version of each problem set which you can use as a starting template for writing up your solutions. You will also need this LaTeX style file.

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.

Assignment	Resources	Due
Info sheet	Online info sheet form	Fri, 8/30
HW 0 (background)	PDF, TeX	Tues, 9/3 @1pm
HW 1 (GCD, induction)	PDF, TeX	Fri, 9/6 @1pm
HW 2 (Asymptotic analysis)	PDF, TeX	Fri, 9/13 @1pm
HW 3 (Graphs)	PDF, TeX, graph.txt	Fri, 9/20 @1pm
HW 4 (DAG analysis)	PDF, graphs.tar.gz, check-graph.py	Fri, 9/27 @1pm
HW 5 (Percolation)	PDF, union-find notes	Fri, 10/11 @1pm
HW 6 (Divide & Conquer)	PDF, TeX, QuickSelect (D&C exemplar)	Fri, 10/25 @1pm
HW 7 (1D Dynamic Programming)	PDF, TeX, exemplar (hi/lo stress jobs)	Fri, 10/25 @1pm
HW 8 (2D Dynamic Programming)	PDF, TeX, neruda.tar, 2D dynamic programming exemplar (subset sum)	Fri, 11/1 @1pm
HW 9 (Flow Networks)	PDF, TeX, flow network exemplar	Fri, 11/8 @1pm
HW 10 (Amortized Analysis)	PDF, TeX	Mon, 11/25 @1pm
HW 11 (Reductions and NP-completeness)	PDF, TeX	Fri, 12/6 @1pm
Optional EC HW (Graph coloring via SAT - 30 pts)	PDF	Mon, 12/16 @5pm

Activities/Lectures

	Introduction to Algorithms
W 28 Aug	Introduction to POGIL and CSCI 382; Brute force algorithms	MARS
F 30 Aug	Reasons for POGIL; GCD analysis	MARS
M 2 Sep	No class (Labor Day); optional induction review session	MARS
W 4 Sep	Proving algorithms correct (Euclidean algorithm)	317
F 6 Sep	Asymptotic Analysis I (Big-O, Ω, Θ)	MARS
M 9 Sep	Asymptotic Analysis II (limit theorems)	MARS
	Graphs
W 11 Sep	Graphs intro/review	MARS
F 13 Sep	BFS (definitions, properties, asymptotics)	317
M 16 Sep	Applications of BFS	MARS
W 18 Sep	Bipartite graphs	317
F 20 Sep	DAGs and topsort (topsort pseudocode and analysis)	317
	Greedy Algorithms
M 23 Sep	Intro to Dijkstra’s algorithm	MARS
W 25 Sep	Dijkstra’s algorithm	317
F 27 Sep	Analysis of Dijkstra’s algorithm	317
M 30 Sep	Minimum Spanning Trees	MARS
W 2 Oct	Kruskal’s Algorithm and Union-Find	317
F 4 Oct	Exam 1	317
	Divide & Conquer Algorithms
M 7 Oct	Introduction to Divide & Conquer	MARS
W 9 Oct	Divide & Conquer Arithmetic	MARS
F 11 Oct	Master Theorem and Karatsuba’s Algorithm	317
M 14 Oct	Quickselect	317
	Dynamic Programming
W 16 Oct	Introduction to Dynamic Programming	MARS
F 18 Oct	Fall break
M 21 Oct	DP exemplar: high/low stress jobs	317
W 23 Oct	2D dynamic programming	MARS
F 25 Oct	More subset sum	MARS
	Network flow
M 28 Oct	Intro to flow networks	MARS
W 30 Oct	The Ford-Fulkerson algorithm	317
F 1 Nov	Applications of flow networks	317
M 4 Nov	Max flow/min cut	317
	Amortized analysis
W 6 Nov	Intro to amortized analysis	MARS
F 8 Nov	The accounting method	317
M 11 Nov	Amortized analysis examples	317
W 13 Nov	Binomial heaps	317
F 15 Nov	Exam 2	317
	Intractability
M 18 Nov	Intro to reductions	MARS
W 20 Nov	Reductions	317
F 22 Nov	SAT and 3-SAT	317
M 25 Nov	NP-completeness	317
27-29 Nov	Thanksgiving
M 2 Dec	CIRCUIT-SAT is NP-complete	317
M 4 Dec	NP-hard video games	317
	Linear-time sorting
F 6 Dec	Comparison sorting and bucket sort	MARS
M 9 Dec	Radix sort	317

Exams

There will be two midterm exams and a cumulative final exam. For each exam, you will be given the exam questions at least one week in advance (probably longer for the final exam). You may use any resources in preparing your solutions to the exam—including your notes, textbook, online resources, and each other—with the only exception that I will not answer specific questions about the exam. On the day of the in-class exam, you must come with no notes and write out your solutions on a clean copy of the exam.

Fri 4 Oct	Midterm 1 (125 points)
Fri 15 Nov	Midterm 2 (D&C, DP, flow networks; 125 points)
Fri 13 Dec (2-5pm)	Final exam (cumulative; 200 points)

Community

I welcome the chance to engage with you outside of class. Here are the best ways to get in touch with me:

Send an email Make an appointment Submit (anonymous) feedback

My office is MC Reynolds 310. Make an appointment or just drop by whenever my door is open!

Learning teams

You will work with the same team on POGIL activities at least up through the first exam; we may switch after that. If every member of your team gets at least 90 points on the first exam (out of 125), every member of your team will get an extra 10 points.

Rader, Jack F, Ivy, Levi
Brandon, Jordan, Tate
Andrew, Jack M, Zach, Andrei

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. 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 for occasional course announcements. Let me know via email 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 class with a notebook and something to write with. Come prepared to not be on your phone or computer during class, to avoid distracting others or yourself. Spend time outside of class actively practicing unfamiliar or shaky concepts or skills (not just reading over notes).	Come to class with a concrete plan for how we will spend our time, 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 lecture classes by listening, 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.

Grading

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

Final grades will be assigned as follows:

650+ points = A
570+ points = B
490+ points = C
410+ points = D
less than 410 points = F

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 come talk to me or send me an 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.