COS 216: Algorithms

Spring 2022

Basic Information

• Instructor: Jed Yang,
• Office hours: Tuesday and Friday 13:30–14:30; or by appointment (instructions)
• Lectures: Mod C (MWF 11:10–12:00) in Zoom
• Course website: https://www.mathcs.bethel.edu/yang/cos216.22s/

Calendar

Schedule to be updated throughout the term; topics and exam dates are tentative and subject to change.

Week	Monday	Wednesday	Friday
1	1. 01/31 M 1. introduction 1.1 stable matching - NRMP hw02: Getting started hw03: textbook exercises 1.1, 1.2 hw05: 1.5	2. 02/02 W 2. fundamentals 2.{1,2,4} algorithm analysis review hw04: 2.1, 2.3 As always, show work to justify your answers.	3. 02/04 F 2.3 data structures review hw06: 2.6 Remember to do hw05, posted on Day 1.
2	4. 02/07 M 2.5 priority queues review - heap visualization hw07: kattis	5. 02/09 W 3. graphs 3.1 graphs review (no new homework assigned)	6. 02/11 F 3.{2,3} graph traversal hw08: 3.10
3	7. 02/14 M 3.4 bipartite graphs hw09: 3.2	8. 02/16 W 3.5 directed graphs hw10: 3.11	9. 02/18 F 3.6 topological order hw11: 3.12 hw12: none, study for exam
4	10. 02/21 M 4. greedy algorithms 4.1 greedy stays ahead hw13: 4.3 truck packing	11. 02/23 W 4.2 greedy: exchange argument hw14: 4.6 triathlon	12. 02/25 F exam1 (topics and logistics)
5	13. 02/28 M 4.4 shortest paths hw15: 4.18 Canada trip	14. 03/02 W 4.4 shortest paths hw16: bigtruck	15. 03/04 F 4.5 minimum spanning trees hw17: 4.10 update MST You may assume all edge weights are distinct.
6	16. 03/07 M 4.6 union-find hw18: virtualfriends	17. 03/09 W 5. divide and conquer 5.1 mergesort hw19: 5.1 median	18. 03/11 F 5.2 master theorem hw20: airconditioned
7	(Spring break)	(Spring break)	(Spring break)
8	19. 03/21 M 5.3 counting inversions hw21: 5.2 significant inversion hw22: none, study for exam	20. 03/23 W 5.5 integer multiplication hw23: 5.3 bank cards hw24: 5.5 hidden surface	21. 03/25 F quicksort - textbook - visualization (no new homework assigned)
9	22. 03/28 M exam2 (topics)	23. 03/30 W 6. dynamic programming 6.1 weighted interval scheduling hw25: 6.1 independent set	24. 04/01 F 6.2 memoization/iteration hw26: 6.3 ordered graph
10	25. 04/04 M 6.4 subset sum hw27: 6.20 average grade hw28: buttonbashing	26. 04/06 W 6.6 sequence alignment hw29: 6.4 consulting hw30: 6.24 gerrymandering hw31: narrowartgallery hw32: none, study for exam	27. 04/08 F 6.8 shortest paths (no new homework assigned)
11	28. 04/11 M 8. complexity theory (no new homework assigned)	29. 04/13 W 8.1 polynomial-time reductions hw33: 8.22 black box	(Good Friday)
12	(Easter Monday)	30. 04/20 W 8.3 NP via verifiers (no new homework assigned)	31. 04/22 F 8.4 NP-completeness hw34: 8.1 yes/no/open
13	32. 04/25 M exam3 (topics)	33. 04/27 W 8.4 Cook–Levin theorem hw35: 8.2. Hint: construct a Karp reduction from IndependentSet	34. 04/29 F 8.2 boolean satisfiability hw36: 8.6 monotone SAT
14	35. 05/02 M 8.{2,7} graph problems hw37: 8.20 clustering	36. 05/04 W 8.8 numerical problems hw38: 8.17 zero-weight cycles	37. 05/06 F 8.5 sequencing problems hw39: 8.30 multivariable calculus hw40: 8.32 genome assembly
15	38. 05/09 M hash table - 11.2 separate chaining	39. 05/11 W hash table - 11.4 open addressing	40. 05/13 F (wrap-up)
Final Exam: 05/17 Tuesday 08:15–10:15 (topics)

Course Information

• Official course title: Algorithms and Advanced Data Structures
• Official course description: Fundamental algorithms, algorithm analysis, and advanced data structures.
• Prerequisites: COS212 (Data Structures) with C- or higher; MAT241 (Discrete Mathematics) with C- or higher
• Textbook: Jon Kleinberg and Éva Tardos, Algorithm Design, 2006, ISBN: 9780321295354.

Course Overview

Algorithms is about solving problems. It is a continuation of what you learned in Data Structures and Discrete Mathematics. There are three major themes:

• Algorithm design. Our textbook puts a lot of emphasis on the intuition behind designing algorithms to solve computational problems arising from a variety of fields (inside and outside of CS). It is important not to only memorize well-known algorithms, but to think and be creative when solving new problems.
• Algorithm techniques. This course builds upon the foundation laid in COS105 (Object-Oriented Programming and Design) and COS212 (Data Structures). Just like there are a number of common data structures that a computing professional needs to be familiar with, there are common and essential algorithms for solving different categories of problems. These algorithms are a major part of the programmer's essential tool kit, and worth knowing by heart.
• Algorithm analysis. As in MAT241 (Discrete Mathematics), our style of inquiry is formal and mathematical. (But essentially everything that we do comes from and directly impacts programming.) The vast majority of homework consists of daily math problem sets (with proof), occasionally sprinkled with small programming projects.

Topics

We will follow the textbook closely, tentatively covering Chapters 1–8, though omitting several sections. Supplementary topics will be covered as time permits.

• Review of asymptotic analysis and graphs (Chapters 2 and 3)
• Major algorithmic design techniques: greedy algorithms, divide and conquer, dynamic programming (Chapters 4–6)
• Computational complexity and NP-completeness (Chapter 8)

Objectives

By the time you've completed the course, you will be able to:

• Describe and utilize standard algorithms and techniques for common computational problems.
• Analyze algorithms for correctness and efficiency.
• Have intuition for which algorithms are optimal for various scenarios.
• Design new algorithms to tackle difficult computational problems that arise in other CS courses, non-CS courses, and a variety of real-life settings.

Structure and Adjustments

Grading

Your grade will be determined by a weighted arithmetic mean of various components with weights listed in the table on the right. The total score will be converted to a letter grade whose lower bounds are: 93% A, 90% A-, 87% B+, 83% B, 80% B-, 77% C+, 72% C, 69% C-, 66% D+, 60% D, 0% F.

Note that there is no preset curve of how many of each letter grade will be given. If you all do A-level work, you will each get an A. As such, you are encouraged to help each other in the pursuit of perfection.

In many courses I intentionally make one exam harder than others, which gives me information (in a mathematical sense) in separating an A performance from an A- performance. Typically, I will let you know and adjust that exam's scores upward. What this means is that you should NOT care about how hard an exam is. If you do A-level work, you will get an A, regardless of the raw numerical score prior to adjustment.

Besides possibly adjusting scores upward for difficult exams, I also reserve the right to lower the grade cutoffs. Both of these help you. I will not hurt you by adjusting your exam scores downward or increasing the grade cutoffs.

Requirements

Whatever you do, work at it with all your heart, as working for the Lord, not for human masters, since you know that you will receive an inheritance from the Lord as a reward. It is the Lord Christ you are serving.

- Colossians 3:23–24 NIV

I will be trying to make these verses true for me as I work with you throughout this course, and I hope that you will, too.

Attendance and participation. I expect you to attend class. You may not notice me taking attendance during class meetings, but I will notice if you are not in class. Occasional absences will not impact your grade because what I look for is not mere attendance, but engagement and participation.

Indeed, coming to class is not just about showing up; it is also about being fully engaged in the learning experience. If you have a question, others in the class may also be wondering the same thing. So, please speak up and ask questions anytime you need to. Not only will you be helping yourself, but also you will be helping your peers. Attending office hours is another great opportunity to ask questions.

Be mindful of others. Refrain from using mobile phones or laptops for activities unrelated to the learning process. There is research that suggests taking notes by hand is better for long-term retention (P. A. Mueller and D. M. Oppenheimer, The pen is mightier than the keyboard, Psychological Science 25 (2014), 1159–1168).

In general, you are expected to keep your video on most of the time to make your engagement more clear. Let me know if there are legitimate reasons why you need to be off-camera frequently.

It is my sincere hope that every one of you get all the points for attendance and participation.

Reading. Read the book! You should prepare for class by looking over the sections we will cover. Your aim is not to understand every detail, but to get a sense of where we are headed. Even a few minutes of pre-reading can help with class time. We will not have time to cover every single detail in class. As such, after class, read the sections carefully again to fill in the gaps. Keep up with the reading: reading large sections right before an exam is less effective.

Homework. Homework will be assigned most days. The goal of the homework is to give you an opportunity to continuously engage directly with the material. Some of the homework questions are meant to be challenging and to stretch you; simply put, I believe that the homework is where you will do the vast majority of your learning in this class. Grapple with the questions; talk to classmates about solution strategies if you are feeling stuck; do the homework.

• LaTeX. Solutions must be typeset with $\LaTeX$. LaTeX is the standard tool for communicating technical material (in math, computer science, and beyond), and so it is valuable to be familiar with it. Here are some helpful links to references, tutorials, and a template you may use.
  • (optional) homework template: hw-template.tex
  • editors: Overleaf (cloud-based) | MiKTeX (cross-platform)
  • getting started: a short introduction | more detailed tutorials
  • reference: the not so short introduction | a reference guide [Cambridge] | the LaTeX Wikibook
  • tools: a symbol finder | a table editor
  If you have diagrams that you would like to submit as part of your homework solutions that are overly painful to typeset in LaTeX, hand-drawn supplements are acceptable (but they too must be submitted electronically). You may find it easiest to print your solution, draw in your diagrams, scan the printout, and submit the resulting PDF. Or you can scan or photograph just the diagram, include \usepackage{graphicx} in the preamble and use \includegraphics{image-file-name} at the place where you want your image. Make sure your result is legible and clear.
• Grading. For the sake of providing better feedback, only a random subset of homework problems will be graded. Do all of the homework problems to ensure you get credit. Most questions will be graded on a four-point scale: quality deserving of being a solution set (4); correct with minor errors or flaws of presentation (3); essentially correct idea but with significant technical or presentation errors (2); some good ideas but fundamentally flawed solution (1); no genuine attempt (0).
• Late work policy. Homework is due at the beginning of the class period on the day it is due, unless otherwise stated. In general, late work is not accepted. If there are special circumstances, talk to the instructor. To alleviate your anxiety from accidentally forgetting to submit homework before class, illness, emergencies, or other situations beyond your control, the lowest four (4) assignments will be dropped.
• Tips.
  • Unless indicated to the contrary, you must formally prove the correctness of your solution to every homework and exam problem. Solving a question that asks you to "given an algorithm" requires you to do three things: (1) describe an algorithm (include an example if it is hard to understand); (2) prove that your algorithm is correct; and (3) analyze your algorithm's running time.
  • Treat your homework as you would an essay for an English class. Draft. Edit. Rewrite. Think about clarity as you write your answers; you are trying to communicate a solution.
  • On any question in which you give a complicated proof or construction, please also give an English description of your ideas. This will help the reader understand what you have written, and will help you get the partial credit you deserve.
  • Answers to homework questions are not always supposed to be obvious to you—you should have to think and struggle to answer some of the questions. To calibrate your personal expectations: do not worry if you cannot solve every problem! (Getting an A does not require solving all the questions.) Write up whatever progress you have made on each question. You will receive partial credit, especially for an answer like "Here's where I got stuck. I can't see how to finish the argument because $x$." (On the other hand, getting an A does require solving most of the problems; just do not panic if there is a question once every three or four weeks that stumps you.)
  • If you are totally stuck on a question, find someone (me or a classmate) with whom to chat about it.

Programming projects. Occasionally I may give you some (small) programming projects. Typically you are free to write your solutions in a (common) programming language of your choice. Details on how to submit projects will be included when they are assigned.

Exams. There are several in-class midterm exams (see calendar for a tentative schedule). Subsequent exams will mainly focus on the material covered since the previous exam, but can include previous material too. There will be a final exam during the official final exam period covering the entire course.

There are no make-up exams except in circumstances recognized by the instructor as beyond the control of the student. To receive this consideration, the instructor must be notified of the problem before the exam unless this is impossible, in which case as soon as possible.

Time outside of class. I expect a typical student to spend about two to three hours outside of class for each hour in class. Some students need to spend a bit more than that (which is okay). If you are spending more than 10 hours per week on this course outside of class time, please come talk to me so we can find ways to help you learn the material without spending so much time.

Illness. You should make every effort to attend class when you are healthy. If you become ill, for your well-being, you should not come to class. Yes, this sounds like common sense, but it is tempting to try and power through as normal so as not to fall behind. If you become ill, or know that you will need to miss class for some reason, please contact me as soon as you are able, and we will work together to plan how you will keep up and/or make up any missed work.

Policies

Learning integrity.

Search me, O God, and know my heart;
Try me, and know my anxieties;
And see if there is any wicked way in me,
And lead me in the way everlasting.

- Psalm 139:23–24 NKJV

Collaborative work is an integral part of many successful ventures. As such, I expect that you should collaborate with your classmates a lot during your time in this course. However, it is important to understand that there is a big difference between thinking about and solving a problem as part of a group (which is good, both educationally and morally) and copying an answer or letting someone else copy your answer (which is bad, educationally and morally, and has punitive consequences).

In short, I trust you to maintain the utmost level of academic integrity in this course. Please do not break this trust; if you do, there will be repercussions. The formal policy below lays this out explicitly, and supplements Bethel's academic honesty policy.

Collaboration policy.

• You may collaborate on the homework assignments to the extent of formulating ideas as a group, but you may not collaborate in the actual writing of solutions (unless explicitly allowed in the instructions).
• In particular, you may not work from notes taken during collaborative sessions.
• You may not consult any materials from any previous offerings of this course or from any other similar course offered elsewhere unless explicitly permitted.
• You may not look up solutions in any form, including from solution manuals or online repositories.
• You are required to completely understand any solution that you submit and, in case of any doubt, you must be prepared to orally explain your solution to me. If you have submitted a solution that you cannot verbally explain to me, then you have violated this policy.

Accommodation policy. Bethel University is committed to accessibility for students with disabilities and the Office of Accessibility Resources and Services (OARS) is a resource to ensure students experience access. The instructor will provide accommodations after the student initiates the process.

• Students with a documented disability may contact OARS to learn more about how to register for accommodations. Reasonable accommodations are approved after an interactive process with the student and OARS.
• Students registered with OARS are responsible for logging in to their AIM Accessibility Accommodation portal (via MyBethel) each term to request their Faculty Notification Letter of Accommodations. Accommodations cannot be applied prior to the faculty’s receipt of the letter.

OARS recommends the student and faculty discuss how accommodations may apply in the specific course. Accommodations cannot modify essential requirements or fundamentally alter the nature of the course. Consultation with OARS may be necessary to clarify reasonable accommodations based on the course. If there are any questions or concerns, connect with OARS at accessibility-services@bethel.edu or 651.638.6833.

Concerns and appeals. If you have any concerns regarding the course, your grades, or the instructor, see the instructor first. If needed, see Bethel's academic appeals policy.

Getting Help

If you need help there are multitude of resources you can use:

• Yourself. If you're stuck on a problem or struggling with a concept from class, take a break and think about something else (e.g., your Hebrew assignment, the economics of Star Trek) for a few hours and then try a fresh start.
• The book. Our text is very readable; it's a great place to turn if you are having any trouble.
• Your classmates. You are each other's best resource: talking through the course material with someone else who is also trying to master it is a great way for you both to learn. (And don't discount the learning that you will do while trying to explain to a classmate an idea covered during class that you think you understand; I can't count the number of times that I've discovered that I didn't really understand something until I tried to teach it to someone.) The homework assignments are meant to challenge you, and figuring some of them out together is a great approach.
• CS Lab. The Math/CS Department offers support for students enrolled in CS classes by providing a CS Lab. Hours, as well as logistics for attending (in person or remotely) will be provided on Moodle. If you are having any difficulty with your homework in this class, please seek help from the tutors in CS Lab. Plan CS Lab hours into your weekly schedule and develop this habit early on in the course.
• The instructor. Come to my (remote) office hours or email to make an appointment. Please read and follow instructions.