Instructor: Xanda Schofield (Prof. Xanda), Olin 1265, email at x or xanda at cs dot hmc dot edu
Where: Zoom - see Piazza for the link
When:
CS 140 Section 1 (168 Section 3): T/R 9:35-10:50
CS 140 Section 2 (168 Section 2): T/R 1:15-2:30
Weekly Office Hours & Grutor Hours: see the calendar (updating TBD)
Final Exam Slots: One sitting between the start of the exams period and May 14th at midnight
Looking for quick answers about what's changed on the syllabus? Check out the FAQs for Distant Learning page.
Algorithms affect our world and how we interact with it every day. This course serves to provide practical techniques and theoretical truths about how to design correct algorithms for new problems. To build these skills requires a background of algorithmic strategies (such as greed, dynamic programming, divide-and-conquer, and reduction), classic problems (graph traversal, shortest paths, minimum spanning trees, and network flow), and tools for runtime analysis (amortization, recurrence relations), and proofwriting skills to show an algorithm is correct (induction) or will be hard to find (NP-hardness reductions). This course also visits some modern topics of algorithmic design, such as parallelization, approximation algorithms, randomized algorithms, online algorithms, and algorithmic bias.
Upon completing this course, students will be able to:
Algorithms relies on experience with proofwriting and with reasoning about running time and data structures. The course requires Math 55 (discrete math) or equivalent, CS 60 (principles of programming) or equivalent, either CS 70 (data structures) or MATH 131 (real analysis), and CS 81 (computability and logic). Students not meeting these requirements should notify me (Prof. Xanda) by the first day of class.
All problem sets for this course should be typeset using LaTeX. You can install LaTeX here or use Overleaf (though be sure if you’re using Overleaf that you don’t inadvertently make your homework solutions public). All lab machines also have LaTeX installed.
Each problem set will be given with a corresponding LaTeX file, which should provide most of the notation and guidance you need. However, should you need additional resources to help get started, the LaTeX Primer from page 77 and Tobias Oetiker's LaTeX in 157 minutes are both useful resources. If using LaTeX is significantly interfering with your ability to complete homework, please reach out to Prof. Xanda to discuss alternatives.
For several assignments, students will be asked to write code in Python to execute a particular algorithm. A basic Python 3 installation (using python.org or Anaconda) will suffice for this work. While working with classmates in the course is good, we ask you not to look at each others’ code directly. If you are having trouble debugging code, please see a grutor or the professor for help. (If you need to ask course staff a question about a bug directly, it helps to provide both your current file and input, output, and error message you got.)
There is no required textbook for this course, and the material itself should be contained in the course lectures and handouts. However, to supplement lecture, there will often be suggested reading from the book Algorithm Design by Jon Kleinberg and Éva Tardos (available on Amazon, and at Honnold-Mudd Library). Because many of you may have Algorithms by Dasgupta, Papadimitriou, and Vazirani from a previous course iteration, alternative readings on topics will also be offered from there if available. It's also okay to consult Introduction to Algorithms by Cormen, Lieserson, Rivest, and Stein. The first two textbooks are now available through Redshelf via the CUC library! Follow the link for details. https://ccl.on.worldcat.org/courseReserves/course/id/10008973
For some topics, handouts will be distributed in class and made available online through the course website. These handouts will help set up particular homework problems or flesh out proofs from class, and should be read before starting the corresponding homework problem(s). Materials outside the books and handouts listed above and those on the course websites are not permitted for consultation on homeworks (that means no using Google/Wikipedia to reference for homework problems).
Both Prof. Xanda and the intrepid team of Algorithms grutors are excited to offer a number of hours outside of class in which you may drop in without an appointment to talk about homework and review concepts in class. A full calendar of the times for these sessions is pending.
If you’re particularly concerned about your performance in the class, email Prof. Xanda and we can set up a time outside of drop-in office hours to talk.
We have a Piazza site for asking questions about class and homework. When possible, if you have a question that might be useful to other people, please ask it in the forum so other students can see the answer (though please be careful not to give homework solutions away while doing so). If your question is private, e.g. you have a personal matter and might need an extension, please email Prof. Xanda directly. Lecture slides and resources can be found on the Piazza site under Resources.
Note: While Piazza is an awesome site, it also provides student data to employers as part of its business model. This Piazza course is set to disable sharing statistics about your Piazza use with employers, but if your account is set up with Piazza Careers, you should be aware that information about your participation and performances in classes may be shared by them. In the interest of protecting your privacy, grade-related individual questions and other personal matters should be sent to me by email instead of Piazza message.
Each class day, section 2 will be recorded, and usually become available sometime the following day at https://hmc.mediasite.com/mediasite/Catalog/Full/d39ea51a92f5404e8963c538b2ac62bc21 . While these videos are not meant to replace attending lecture, they can be a useful study resource and supplement in the event of travel or an off day.
The grade for the course will be based on the total number of points achieved in the class out of a possible 2000 1800. Letter grades are fixed based on this scale in decreasing intervals of 100: 1700+ is an A, 1600-1699 is an A-, 1500-1599 is a B+, and so on, down to 800-899 as a D. Below 800 constitutes failure of the course. Anyone may at any time elect to switch their grade to pass/fail: as per recent policy, a pass is a C or better (by this scale, 1100+ points). You will be graded according to your campus policy for this semester. I will send out surveys to help students elect what type of course grade they receive (assuming it is a choice their home campus allows); if you don't respond to the survey, I will assume you are taking the course P/NC.
The following gives the breakdown of points available:
The exam scores will be reweighted to sum to 500 points in whichever way gives you the best grade. For a more detailed explanation, see the description in Exams below.
Homework assignments will be posted every Tuesday afternoon to be due the following Tuesday except on exam weeks. These problem sets will usually contain 3-5 problems for which answers must be typeset. Assignments will be submitted as PDFs written using LaTeX via Gradescope by 11:59 PM on the Tuesday due date. TeX files will be provided on the Piazza site under Resources.
Each of the 10 homework assignments for the semester is worth 100 points. Because practice is one of the most important parts of learning algorithmic design, no homework assignment will be dropped. However, while a perfect homework score for the semester will be out of 1000 points, there will be at least 1200 points available on homework during the semester counting both extra credit problems and optional parts of some problems, so it will be possible to receive 1000 homework points (or more!) without completing all homework problems.
Focus problem. One goal for the semester is to work on skills of writing mathematically sound descriptions of algorithms and proofs in English. To help with strengthening this skill, on each homework assignment, there will be one focus problem. Focus problems will be graded more stringently than other problems for clarity of writing and thoroughness, so while we encourage proofreading for correctness on all your problems, it’s particularly important to do so on these problems to ensure that you receive a good grade. If you lose 5 or more points on a focus problem, you may submit a rewrite of a focus problem up to one week after you receive the grade for that problem. The final grade on a focus problem will be the average of the scores of your original writeup and the new writeup.
A student will be automatically granted a 1-day extension on any homework assignment by simply filling out a Google form (https://forms.gle/Bn92bDQWPu6LeCzk7). These should be used to handle cases such as travel, interviews, short-term illness, stressful weeks, etc. There is no limit on the number of homework assignments on which you may use a one-day extension so long as you use the form to request the extension in advance of the deadline.
For situations such as extended illnesses, family emergencies, or other significant and unforeseen circumstances preventing you from working, I’m happy to work with you to try to find a way to give you the space you need while being able to come back to the course when you’re able. The best way to start this conversation is by direct email to me (xanda@cs.hmc.edu). To protect your privacy and to ensure you get the support you need, I may ask you to reach out about this to your campus’ Division of Student Affairs, Dean of Students office, or your Student Disability Services coordinator. You may also choose to reach out to any one of these groups to reach out to me in advance of contacting me yourself if you prefer.
There are two midterms and one in-class exam for this course. Both midterms will be take-home, open-note exams, while the final exam will be taken in-class during either of the two final exam slots for these sections. More information about the format and expectations for these exams will be given near each exam date.
There is no longer a second midterm: there is now one midterm and one multiple choice + short-answer final.
Exam Grades
All together, exams make up 500 points of the course grade. The midterm (written take-home) and final (online multiple choice and short answer) are each worth at least 200 points. The remaining 100 points come from whichever exam you performed best on. For instance, if you received an 80% on the first midterm and an 85% on the final, your final point score would be (200 * .80) + (300 * .85) = 415/500 points.
Policy before Spring Break: Because the core material of the course is offered in lecture, attendance is expected for class. Attendance information is collected based on submission of informal in-class worksheets each day in class (which are graded solely for attempted work, not content). Each student is allowed one unexcused absence. Each unexcused absence after the first will lose 10 points of the 80-point pre-break attendance grade.
Policy after Spring Break: Lecture material will now be offered asynchronously through course videos, so attending synchronous lectures is no longer required (though there will be time to ask questions and connect with colleagues about homework during class time). To verify you attended to the video or equivalent material in class, a short quiz will be available on Gradescope. (Questions should be easy to answer from seeing the lecture.) You will be expected to complete these questions online by 9 PM PST of the day they're released. Missing a set of questions without an excused absence will count for 10 of the 100 points of your post-break attendance grade.
Absences for any reason can be excused (and therefore incurred without penalty) if you notify the instructor before the class you’ll miss starts/your attendance activity is due. However, you are responsible for making up the material missed in class on your own.
For each class, a team of 2-3 students will sign up to build a glossary of useful terms for that day using in-class notes and/or the course texts. You can sign up for your glossary day here. Your team is responsible for completing the glossary prior to the next class period (Thursday for Tuesday class, or Tuesday for Thursday class). Contributing a meaningful effort to filling in the glossary for the day you sign up for is worth 1% of your grade. The collective glossary should serve as a useful guide to the core concepts and terminology from units when reviewing for exams.
(More details pending) In the final unit of the class, we will talk about some broader concepts of modern algorithms. You'll be asked to conduct your own research and writeup of a modern algorithm. I'll provide a list of candidate algorithms, though you are welcome to do your own research to get another algorithm approved by me. Your writeup will be a 3-5 page writeup containing a description of the problem the algorithm is solving, a step-by-step guide to the algorithm, an analysis of its running time, a sketch of the proof of correctness, and a description of how it's used in modern applications. Your report be in your own words and should include mathematical notation and figures where relevant, as well as citations to academic presentation of this content (e.g. textbooks, academic papers, professors' blogs, but not GeeksforGeeks or Wikipedia).
All students in this course, regardless of their home institution, agree by enrolling in this course to abide by the Harvey Mudd Honor Code.
The permitted resources for homeworks are the books, handouts, slides, and other materials posted to the course website as listed in the Course Resources section above. Unless otherwise specified, please do not seek alternate course texts, particularly online, while working on homework assignments. This rule might seem draconian, but it’s both to ensure you don’t accidentally cheat by finding a solution to a similar problem, and to make sure that misleading or poorly-written materials don’t cause more confusion than help. (Wikipedia in particular is not a good companion for this course, and websites for interview prep often don’t help much with proofs of correctness.)
While students intentionally seeking problem solutions online would violate the honor code, if you should happen by mistake across a resource you feel might run afoul of this policy, e.g., while studying for software interviews, just email to let Prof. Xanda know or write a note on the homework problem linking to the resource.
You are allowed (in fact, you are strongly encouraged) to discuss these problems with classmates, grutors, and the course instructor. If you discuss the problem with students in the course, please list their names on your problem submission.
Please don’t share or discuss these problems or their solutions outside of the course’s current staff and students. In particular, distributing or seeking solutions to homework assignments outside of the current students and course staff, including from past course staff or peers at other institutions, constitutes an honor code violation.
When working with a classmate, grutor, or the professors, you may sketch out ideas on a board together. However, you must write up your solutions by yourself. and not share or look at anyone else's written solution. This includes scratch work: while you may retain paper and photos of your own work, you should never take or acquire a photo of any writing or drawing that wasn't done by your own hand. (This means if you do work with someone at a whiteboard, you can write your own version of that work for yourself, but you can't photograph the whiteboard unless you wrote everything on it, nor can you email a picture of your own work to the other person.) Due to the new format of the course, it will be likely necessary to share pictures or text of content you wish to discuss with classmates when working on problem solutions. This is acceptable as long as you ensure that your writing and figures are your own. Because this policy is more lax, Prof. Xanda may conduct some automatic testing for text similarity to ensure plagiarism isn't occurring, so please don't be surprised if you get an email asking about it. Please don't attempt to plagiarize your classmates: it disrespects their work and the instructor (and text similarity happens to be your instructor's research expertise.)
The rules for programming problems are similar: You may talk with your classmates about the approach to a problem but you should write and submit your own code. You should not share code nor look at any other student's code directly. (This includes if you’re stuck with a bug in your code...while your peers can look at the error output, they shouldn’t be looking at the code itself to help you find your bug. Please reach out to the course staff if you need help with this.)
My goal is to make my course material accessible to every student in the class. To request academic accommodations, including extended time on exams, you should contact the relevant disabilities resources person from your institution and have them reach out to me. If you otherwise anticipate or experience academic barriers based on your disability (including mental health, chronic or temporary medical conditions), please let me know immediately so that we can privately discuss options. If you have additional questions, don’t hesitate to let me know so we can work together and figure out what will best help you succeed.
HMC: Brandon Ice - bice@hmc.edu
CMC: Kari Rood - disabilityservices@cmc.edu
Pitzer: Gabriella Tempestoso - Gabriella_Tempestoso@pitzer.edu
Pomona: Disability Resources - disabilityservices@pomona.edu
Scripps: Bianca Vinci - bvinci@scrippscollege.edu
Student Disability Resource Center (SDRC) – Catherine.Calhoun@claremont.edu
CGU: Jami Hinshaw – jami.hinshaw@cgu.edu
KGI: Andrea Mozqueda - Andrea_Mozqueda@kgi.edu
Algorithms are woven into all of our lives, but historically, the era of algorithmic study in which many of the beautiful results of this class are found is defined by a narrow group of white, male scholars. However, the applicability of those results extends well beyond their lived experiences, and the algorithmic theorists of today have both lived experiences and domains of application extending well beyond what these scholars might have imagined.
As the course instructor, I intend to make the spaces of this course respectful of diversity of race, ethnicity, gender, age, sexuality, disability, socioeconomic status, and myriad other aspects that form identity. I ask for your help to do the same by supporting your peers and grutors in shared spaces, and by letting me know right away if there is anything I can do to help improve equity of experience for you or other members of the class.
Algorithms assignments are meant to be fun problem-solving exercises, but the creative thinking and careful writing required for a great solution takes time and focus. Here are some strategies to help approach homeworks: