**CS41: Algorithms, Fall 2021** Course Info =========================== Instructor : Neil Lutz Email : lutz@cs.swarthmore.edu Office : Science Center 253 Office hours : W 1:15–2:45 p.m. and F 3:00–4:30 p.m. Lecture 02 : MWF 11:30 a.m.–12:20 p.m., SC 128 Lab C : M 1:15–2:45 p.m., Clothier 16 Lab D : M 3:00–4:30 p.m., Clothier 16 Discussion forum : [Ed Discussion](https://edstem.org/us/courses/8602/discussion/) Textbook : [Algorithm Design](https://www.amazon.com/Algorithm-Design-Jon-Kleinberg/dp/0321295358), by Kleinberg and Tardos What is the fastest route through a network? How genetically similar are two species? Where should public resources be located to optimize community access? This course explores algorithmic design and analysis at an abstract level, putting aside implementation details to focus on the conceptual cores of computational problems and the algorithms we apply to them. This process of abstraction allows us to master more sophisticated design techniques--powerful, versatile techniques that can help you write blazingly fast code--and it reveals surprising relationships between computational problems. Sometimes, problems with no apparent similarity turn out to be fundamentally identical; other times, seemingly minor details make the difference between tractability and intractability. We will use these structural relationships to improve our algorithms and to explore the limits of efficient computation. In this course, you will learn how to... - Design efficient algorithms using techniques such as divide-and-conquer, dynamic programming, greedy strategies, and randomization. - Describe your algorithms in clear prose and rigorously prove their correctness. - Analyze the performance of complex algorithms in a mathematical notation that is robust to many implementation and hardware changes. - Perform reductions between superficially dissimilar computational problems, showing that a solution to one problem yields a solution to the other. - Recognize when a problem is likely to be computationally intractable and prove its relative hardness using reductions. - Circumvent many cases of computational intractability using approximation algorithms, restrictions, and heuristics. Calendar =========================== !!! Tip This calendar will change. Details and links will be added over time, and some dates will inevitably shift. Check back for updates! Mon, Aug 30, 2021: Lecture 1 - Topic: Introduction - Reading: Chapter 1 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/685372/mod_resource/content/1/cs41-scribe-lec1.pdf) Mon, Aug 30, 2021: Lab 1 - Topic: Induction and the length of $b$-ary natural numbers - [Solutions](https://moodle.swarthmore.edu/pluginfile.php/685556/mod_resource/content/1/lab1-cs41.pdf) Wed, Sep 1, 2021: Lecture 2 - Topic: Asymptotic notation - Reading: Chapter 2 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/687927/mod_resource/content/1/Sep_1_Notes.pdf) Fri, Sep 3, 2021: Lecture 3 - Topic: Asymptotic notation - Reading: Chapter 2 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/688476/mod_resource/content/1/day3-scribe.pdf) Sun, Sep 5, 2021: HW1 due - [Gradescope](https://www.gradescope.com/courses/293834/assignments/1451712) - [Questions](https://moodle.swarthmore.edu/pluginfile.php/689220/mod_resource/content/1/hw1-cs41.pdf) - [Solutions](https://moodle.swarthmore.edu/pluginfile.php/688863/mod_resource/content/1/hw1-sol-cs41.pdf) Mon, Sep 6, 2021: Labor day - No lecture - No lab Wed, Sep 8, 2021: Lecture 4 - Topic: Karatsuba Multiplication - Reading: Sections 5.1, 5.2, and 5.5 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/689635/mod_resource/content/1/cs41-lec4-notes.pdf) Fri, Sep 10, 2021: Lecture 5 - Topic: Recurrences and time complexity - Reading: Chapter 5 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/689748/mod_resource/content/1/cs41-lec5-notes.pdf) Sun, Sep 12, 2021: HW2 due - [Gradescope](https://www.gradescope.com/courses/293834/assignments/1468085) - [Questions](https://moodle.swarthmore.edu/pluginfile.php/689221/mod_resource/content/1/hw2-cs41.pdf) - [Solutions](https://moodle.swarthmore.edu/pluginfile.php/690509/mod_resource/content/1/hw2-sol-cs41.pdf) Mon, Sep 13, 2021: Lecture 6 - Topic: The master theorem - Reading: Chapter 5 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/690409/mod_resource/content/1/cs41-lec6-notes.pdf) Mon, Sep 13, 2021: Lab 2 - Topic: Divide-and-conquer algorithms for matrix multiplication and combined median - [Solutions](https://moodle.swarthmore.edu/pluginfile.php/690410/mod_resource/content/1/cs41-lab2-sol.pdf) Wed, Sep 15, 2021: Lecture 7 - Topic: Quicksort - Reading: Chapter 5 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/691074/mod_resource/content/1/cs41_09_15_21.pdf) Fri, Sep 17, 2021: Lecture 8 - Topic: Linear-time selection - Reading: Chapter 6 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/691350/mod_resource/content/1/lec8scribe.pdf) Sun, Sep 19, 2021: HW3 due - [Gradescope](https://www.gradescope.com/courses/293834/assignments/1488829) - [Questions](https://moodle.swarthmore.edu/pluginfile.php/690642/mod_resource/content/1/hw3-cs41.pdf) - [Solutions](https://moodle.swarthmore.edu/pluginfile.php/692509/mod_resource/content/1/hw3-sol-cs41.pdf) Mon, Sep 20, 2021: Lecture 9 - Topic: Dynamic programming - Reading: Chapter 6 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/691747/mod_resource/content/1/CPSC_041_9_20_2021.pdf) Mon, Sep 20, 2021: Lab 3 - Topic: Dynamic programming: Hotels and probability of $m$ events - [Solutions](https://moodle.swarthmore.edu/pluginfile.php/691668/mod_resource/content/1/lab3-cs41.pdf) Wed, Sep 22, 2021: Lecture 10 - Topic: Dynamic programming - Reading: Chapter 6 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/692510/mod_resource/content/1/cs41-lec10-notes.pdf) Fri, Sep 24, 2021: Lecture 11 - Topic: Dynamic programming - Reading: Chapter 6 - [Notes](https://moodle.swarthmore.edu/pluginfile.php/692532/mod_resource/content/1/lec11-notes.pdf) Sun, Sep 26, 2021: HW4 due - [Gradescope](https://www.gradescope.com/courses/293834/assignments/1509543) Mon, Sep 27, 2021: Lecture 12 - Topic: Dynamic programming - Reading: Chapter 6 - Scribe: Brooke Coneeny Mon, Sep 27, 2021: Lab 4 - Topic: Dynamic programming Wed, Sep 29, 2021: Lecture 13 - Topic: Graph algorithms - Reading: Chapter 3 - Scribe: Bennett Drucker Fri, Oct 1, 2021: Lecture 14 - Topic: Graph algorithms - Reading: Chapter 3 - Scribe: Christopher Brandt Sun, Oct 3, 2021: HW5 due - Link Mon, Oct 4, 2021: Lecture 15 - Topic: Graph algorithms - Reading: Chapter 3 - Scribe: George Schoettle Mon, Oct 4, 2021: Lab 5 - Topic: Wed, Oct 6, 2021: Lecture 16 - Topic: Greedy algorithms - Reading: Chapter 4 - Scribe: Meiqing Jin Fri, Oct 8, 2021: Lecture 17 - Topic: Greedy algorithms - Reading: Chapter 4 - Scribe: Obioha Okoronkwo Sun, Oct 17, 2021: HW6 due - Link Mon, Oct 18, 2021: Lecture 18 - Topic: Greedy algorithms - Reading: Chapter 4 - Scribe: Tiffany Zheng Mon, Oct 18, 2021: Lab 6 - Topic: Greedy algorithms Wed, Oct 20, 2021: Lecture 19 - Topic: Review Wed, Oct 20, 2021: Midterm - 7–10 p.m. in SC 104 Fri, Oct 22, 2021: Lecture 20 - Topic: Network flow - Reading: Chapter 7 - Scribe: Seth Keim Mon, Oct 25, 2021: Lecture 21 - Topic: Network flow - Reading: Chapter 7 - Scribe: Alexander Lehner Mon, Oct 25, 2021: Lab 7 - Topic: Network flow Wed, Oct 27, 2021: Lecture 22 - Topic: Network flow - Reading: Chapter 7 - Scribe: Austin Burgess Fri, Oct 29, 2021: Lecture 23 - Topic: Network flow - Reading: Chapter 7 - Scribe: Natnicha Sukprawit Sun, Oct 31, 2021: HW7 due - Link Mon, Nov 1, 2021: Lecture 24 - Topic: Linear programming and MIP - Reading: - Scribe: Elvis Adorkor Mon, Nov 1, 2021: Lab 8 - Topic: Linear programming and MIP Wed, Nov 3, 2021: Lecture 25 - Topic: Intractability - Reading: Chapter 8 - Scribe: Trung Le Fri, Nov 5, 2021: Lecture 26 - Topic: Intractability - Reading: Chapter 8 - Scribe: Kimberly Kockenmeister Sun, Nov 7, 2021: HW8 due - Topic: Intractability - Reading: Chapter 8 - Scribe: Mon, Nov 8, 2021: Lecture 27 - Topic: Intractability - Reading: Chapter 8 - Scribe: Marshall McArthur Mon, Nov 8, 2021: Lab 9 - Topic: Intractability Wed, Nov 10, 2021: Lecture 28 - Topic: Intractability - Reading: Chapter 8 - Scribe: Rebecca Lin Fri, Nov 12, 2021: Lecture 29 - Topic: Restricted problems - Reading: Chapter 10 - Scribe: Sidhika Tripathee Sun, Nov 14, 2021: HW9 due - Link Mon, Nov 15, 2021: Lecture 30 - Topic: Restricted problems - Reading: Chapter 10 - Scribe: Alyssa Zhang Mon, Nov 15, 2021: Lab 10 - Topic: Restricted problems Wed, Nov 17 , 2021: Lecture 31 - Topic: Approximation algorithms - Reading: Chapter 11 - Scribe: Anika Rajamani Fri, Nov 19, 2021: Lecture 32 - Topic: Approximation algorithms - Reading: Chapter 11 - Scribe: Karin Nakano Sun, Nov 21, 2021: HW10 due - Link Mon, Nov 22, 2021: Lecture 33 - Topic: Approximation algorithms - Reading: Chapter 11 - Scribe: Jill Sekera Mon, Nov 22, 2021: Lab 11 - Topic: Approximation algorithms Wed, Nov 24, 2021: Lecture 34 - Topic: Local search - Reading: Chapter 12 - Scribe: Qingyun Wang Fri, Nov 26, 2021: Thanksgiving break - No lecture Mon, Nov 29, 2021: Lecture 35 - Topic: Randomized algorithms - Reading: Chapter 13 - Scribe: Owen Webb Mon, Nov 29, 2021: Lab 12 - Topic: Randomized algorithms Wed, Dec 1, 2021: Lecture 36 - Topic: Randomized algorithms - Reading: Chapter 13 - Scribe: Timothy Mou Fri, Dec 3, 2021: Lecture 37 - Topic: Randomized algorithms - Reading: Chapter 13 - Scribe: Fangzhou Xing Sun, Dec 5, 2021: HW11 due - Link Mon, Dec 6, 2021: Lecture 38 - Topic: Randomized algorithms - Reading: Chapter 13 - Scribe: David Yang Mon, Dec 6, 2021: Lab 13 - Topic: Randomized algorithms Wed, Dec 8, 2021: Lecture 39 - Topic: Review Sun, Dec 12, 2021: Final exams begin - Date and time of our final exam are TBD Sat, Dec 18, 2021: Final exams end Grading =========================== Your course grade will be calculated as a weighted average as follows. - 35% homework - 30% midterm exam - 30% final exam - 5% participation There is not a predetermined mapping from percentage scores to letter grades, but I will keep you posted on that topic as the class moves forward. Essentially, the class is *partially* curved, meaning that grades will be informed both by my own priors about assignments' difficulty and by students' collective performance. Exams --------------------------- The midterm exam will be on Wednesday, October 20 from 7–10 p.m. in Science Center 104. The final exam will be scheduled by the college. This page will be updated when it has been scheduled. Homework --------------------------- Homework assignments will be released on Monday evenings and due the following Sunday at 11:59 p.m. Your homework for this class should be typeset in LaTeX using [this template](https://moodle.swarthmore.edu/mod/resource/view.php?id=487431) and compiled into a PDF, then submitted on Gradescope. The first three homeworks will be solo assignments. For all subsequent homeworks, you may work with a partner. When working with a partner, you are expected to work as a team on all problems, not to divide up the problems. **Late policy:** You may submit up to three homeworks up to 24 hours late each, for any good or bad reason, without penalty. You do not need to notify me that you are using a late day; just submit on Gradescope as usual. Participation --------------------------- **Mandatory** components of participation: - Attend and actively contribute in all labs. If you need to miss a lab for some reason, talk with me ahead of time to make arrangements. - Act as the designated scribe for one lecture, according to a schedule that will be set on the first day of class. On the day that you are the scribe, you have the following responsibilities. - Take good, thorough lecture notes. - Briefly meet with me that afternoon to go over your lecture notes. - Typeset your lecture notes in LaTeX, using [this template](https://moodle.swarthmore.edu/mod/resource/view.php?id=487432). - Email me the PDF and source files before midnight. I will double-check the completed notes and then post them within 24 hours. **Expected** components of participation: - Attend all lectures and be an active participant. Ask questions when you have them, and engage with questions that I ask the class. If you miss a lecture, it is your responsibility to proactively learn the material that was covered. - Start homework assignments early. As soon as the homework assignments come out, you should read each problem to make sure that you understand what it is asking, and then start thinking about the problem at a high level. - Attend office hours when you want or need help with homework or lecture material. - Ask and answer questions on the class [discussion forum](https://edstem.org/us/courses/8602/discussion/). - There are no *required* readings for this course, but the textbook offers a valuable perspective on many of the concepts we'll discuss. As the semester progresses, I will update the course calendar with the specific textbook sections that most directly correspond to each lecture. Optional Work ---------------------------- **Read and review a book** about ethical, societal, or environmental concerns surrounding algorithms. Some examples are given below, but you are welcome to propose other books. Choose a book that you have not previously read. You may borrow a copy of any of the listed books from me for up to four weeks, on a first come, first served basis, but please check the library first. If you propose another book that I approve and am interested in owning (which is likely!), I'll order a copy that you can borrow. Write a [book review](https://www.hamilton.edu/academics/centers/writing/writing-resources/book-review) (750–1250 words), and email it to me by December 8. Depending on the quality of your review, this can be worth as much as the average homework assignment. - *Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy,* by Cathy O'Neil - *The Ethical Algorithm: The Science of Socially Aware Algorithm Design,* by Michael Kearns and Aaron Roth - *Algorithms of Oppression: How Search Engines Reinforce Racism,* by Safiya Umoja Noble - *An Ugly Truth: Inside Facebook’s Battle for Domination,* by Sheera Frenkel - *Race After Technology: Abolitionist Tools for the New Jim Code,* by Ruha Benjamin - *Twitter and Tear Gas: The Power and Fragility of Networked Protest,* by Zeynep Tufekci - *Technically Wrong: Sexist Apps, Biased Algorithms, and Other Threats of Toxic Tech,* by Sara Wachter-Boettcher - *Invisible Women: Data Bias in a World Designed for Men,* by Caroline Criado Perez - *Atlas of AI: Power, Politics, and the Planetary Costs of Artificial Intelligence,* by Kate Crawford - *Automating Inequality: How High-Tech Tools Profile, Police, and Punish the Poor,* by Virginia Eubanks **Challenge problems** will be provided throughout the semester. Some will simply be more difficult problems, but there might also be problems that are open, unsolvable, or underspecified. Recognizing potential modifications or restrictions that would make a problem solvable but still interesting is an essential research skill, and you are encouraged to apply that skill to challenge problems when necessary. These are just for fun, bragging rights, and potential future recommendation letters. Integrity =========================== Academic honesty is required in all your work. Under no circumstances may you hand in work done with or by someone else under your own name. Discussing ideas and approaches to problems with others on a **general level is encouraged**, but you should **never share your solutions** with anyone else nor allow others to share solutions with you. You may not examine solutions belonging to someone else, nor may you let anyone else look at or make a copy of your solutions. This includes, but is not limited to, obtaining solutions from students who previously took the course or solutions that can be found online. You may not share information about your solution in such a manner that a student could reconstruct your solution in a meaningful way (such as by dictation, providing a detailed outline, or discussing specific aspects of the solution). You may not share your solutions even after the due date of the assignment. In your solutions, you are permitted to include material which was distributed in class, material which is found in the course textbook, and material developed by or with an assigned partner. In these cases, you should always include detailed comments indicating on which parts of the assignment you received help and what your sources were. When working on tests, exams, or similar assessments, you are not permitted to communicate with anyone about the exam during the entire examination period (even if you have already submitted your work). You are not permitted to use any resources to complete the exam other than those explicitly permitted by course policy. (For instance, you may not look at the course website during the exam unless explicitly permitted by the instructor when the exam is distributed.) Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: > Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, > failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for > a second offense, the penalty should normally be expulsion. This policy applies to all course work, including but not limited to code, written solutions (e.g. proofs, analyses, reports, etc.), exams, and so on. This is not meant to be an enumeration of all possible violations; students are responsible for seeking clarification if there is any doubt about the level of permissible communication. *The general ethos of this policy is that actions which shortcut the learning process are forbidden while actions which promote learning are encouraged. Studying lecture materials together, for example, provides an additional avenue for learning and is encouraged. Using a classmate's solution, however, is prohibited because it avoids the learning process entirely.* ***If you have any questions about what is or is not permissible, please contact your instructor.*** !!! Tip For this course, it is fine to use any resource for help with LaTeX. Other than that, you should never search online for help with any part of homework assignments. Accommodations =========================== If you believe that you need accommodations for a disability or a chronic medical condition, please contact Student Disability Services via email at studentdisabilityservices@swarthmore.edu to arrange an appointment to discuss your needs. As appropriate, the office will issue students with documented disabilities a formal Accommodations Letter. Since accommodations require early planning and are not retroactive, please contact Student Disability Services as soon as possible. For details about the accommodations process, visit the [Student Disability Service website](http://www.swarthmore.edu/academic-advising-support/welcome-to-student-disability-service). You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through Student Disability Services. LaTeX Resources =========================== LaTeX is the standard way to prepare documents for publication in computer science and several other scientific fields, so it is a useful skill to learn! There are many LaTeX editors to choose from, but [Overleaf](https://overleaf.com) is a great choice for beginners. This is a popular, cloud-based editor with a simple interface and strong [documentation](https://overleaf.com/learn). For typesetting pseudocode, you may use [`clrscode3e`](https://ctan.org/pkg/clrscode3e?lang=en) or any of the packages described on Overleaf's [documentation page](https://www.overleaf.com/learn/latex/Algorithms) on algorithms. [Detexify](https://detexify.kirelabs.org/classify.html) is a useful tool for finding the names of mathematical symbols in LaTeX. [Homework template](https://moodle.swarthmore.edu/mod/resource/view.php?id=487431) [Scribe template](https://moodle.swarthmore.edu/mod/resource/view.php?id=487432)