Course information
Thanks to my colleagues
Though I have taught this class several times over the past 25 years, the materials I am using this term were developed by my colleague Layla Oesper, who in turn borrowed many ideas from David Liben-Nowell. I am grateful to both of them for their guidance, great ideas, and generosity.
Book
Most of your readings will come from Algorithm Design, by Jon Kleinberg and Eva Tardos. If you have trouble getting a copy, let me know.
Class time during a lingering pandemic
Barring a new surge in the pandemic, we'll be pretty close to normal this term (though I understand that there really is no "normal" for a 20-year-old college student in 2022). My default expectation is that you will attend class and I will not make special arrangements for remote instruction. If you want to learn what's going on in class, you should come to class.
However, there may be times when one or more of you will have to isolate for COVID. On such days, I will fire up Zoom and constrain my visual aids to the screens in Leighton 304 so I can share the screen with anybody coming in via Zoom. The Zoom link for those days will be the one posted on my office hours page.
If you need to Zoom for class, please let me know ahead of time. I won't set up the remote class infrastructure unless I'm aware of a student who needs it.
Masks in class
For now, the CS department has decided to continue last year's masking policies in the various rooms on 3rd Olin. But since CS 252 will meet in Leighton 304, I plan to adhere to whatever the college's policy is at the time. (At this writing on September 10, that means this announcement.) Unless the college policy changes, I do not plan to require masks in class (though of course you are welcome to wear one).
Homework
Readings and reading reactions. For each reading assignment during the term, I will ask you to make a brief post on Slack in the #readings channel. This post can be any kind of reaction that engages directly with the content of the reading. You can ask a simple question, you can answer somebody else's question, you can make an observation about something you found interesting or compelling or mistaken, etc.
Each reading assignment will include a hashtag for you to include in your reaction post (e.g., #reading17). This will help me collate your responses so I can easily give you the points and also use your responses to prepare for the next class. If you forget the hashtag, go ahead and edit your post to include it.
Reading reactions are worth 1 point apiece. If you make a good-faith comment that reflects the reading, you'll get the point as long as it is posted by 11:59PM on the day the reading assignment is listed on the course website. Zero points otherwise. I will drop your worst 2 reading scores, so you can miss a couple reading reactions without losing any points. (But do the readings anyway!)
Problem sets. During most weeks you will have a problem set consisting of 2-4 problems. Each problem set will have two due dates. By 11:59PM Sunday, you will hand in a solution for one problem. That solution will be graded not on correctness, but on completeness (as judged by the grader or me). This checkpoint submission will be worth 1 point. Your completed solutions for all problems on the problem set will be due by 11:59PM Wednesday.
Each problem will be given a score between 0 and 4 points:
- 4 — quality deserving of being included in a solution set
- 3 — correct with minor errors or flaws of presentation
- 2 — essentially correct idea but with significant technical or presentation errors
- 1 — some good ideas but the solution as a whole is fundamentally flawed
- 0 — no genuine attempt to solve the problem
Submitting your work. Unless otherwise directed, submit each homework assignment as a PDF file via Moodle.
LaTeX. You will typeset your homework submissions using LaTeX. See this set of LaTeX guidelines for more information on my expectations.
Grading
Your grade will be determined by your performance on homework (36%), three exams (18% apiece), and the final project (10%).
Late homework
You may submit up to three late homework assignments. To use one of your free late assignments, just hand in the homework up to 48 hours late—no need to tell me ahead of time. You may only use one extension per assignment without prior permission. Once you have used your three late assignments, late work will receive zero credit. If an assignment is late by a small amount (half an hour or less), I won’t count it as late.
Collaboration and use of outside resources
You may collaborate with your classmates on homework assignments to the extent of formulating ideas as a group, but you may not collaborate in the actual writing of solutions, unless the assignment description explicitly allows you to do so.
You must cite all sources, including books, websites, and individuals from whom you obtained ideas. Failing to properly cite your resources is a violation of the academic honesty policy for this class.
You may not consult any materials from any previous offerings of this course or from any other similar course offered elsewhere.
Some examples
- NOT OK. You find a solution for an assigned problem online and use it as inspiration for your solution.
- NOT OK. You ask your roommate who has taken this class previously to look up old homework solutions so you can check your solution for correctness.
- OK WITH CITATION, NOT OK WITHOUT CITATION. You are having trouble remembering how priority queues work, so you search online for help, which you end up using in your writeup.
- OK. You talk with a couple classmates about how to solve a problem. You all write up your solutions without consulting each other further.
- NOT OK. You read a portion of a classmate's written solution to a problem before (or during) the time you write up your own.
- NOT OK. You allow a classmate to read part or all of your written solution of a problem.
If you have any questions about acceptable collaboration or resource uses, ask me.
Office hours
(Here are the times and Zoom link.)
I love talking with you, whether it’s about class content or life as a programmer or tech new & ethics or your personal programming project or your search for internships or Carleton history or a good movie you saw recently or whatever. Really. Conversations with you are the main reason I keep doing this job instead of going out into the software industry.
This thing called "office hours" should probably be called "Jeff's personal invitation to you to come talk". I set aside a few hours per week when I promise to be available for conversation. I'm often available at other times, too, but it depends on what meetings I have to go to, what deadlines I'm working under, etc. So my official office hours are a way for me to clear my schedule for you.
During 2020-2021, Zoom office hours worked really well. They enabled students to get quick answers conveniently, and I saw a larger number of students in office hours than I would normally see in person. So I'm going hold office hours by sitting in my office (Olin 301A) and also firing up Zoom, which will enable you to choose whether you want to talk to me in person or online.
How to get help
Everybody gets stuck. Learning is tough sometimes. When you’re stuck or confused, here are some things you can do.
- Ask a question in class
- Talk with me during office hours
- Talk with a classmate
- Talk with your prefect
- Revisit the relevant textbook sections
- Take a break, get some sleep, eat, take a walk. Coming back to a problem fresh often helps you solve it on your own.
- Post on our Slack #questions channel. Making your question public to your classmates will help other students, since if you have a question X, you can be guaranteed that some of your classmates are confused about X too. Addressing your question to the whole class will also maximize your chances of getting a quick response. I monitor Slack closely and often answer questions myself, but it's also common for some other student to provide an answer before I can get to it.
- Send me a question via Slack direct message. For the vast majority of questions, I prefer that you post in #questions, but occasionally a question is private or so idiosyncratic to you that it's not suitable for a public forum, in which case DM is fine.
- Talk with a lab assistant in the Olin 3rd-floor labs.
Rough schedule
I may adjust some things along the way, but the schedule will look more or less like this:
- Week 1: asymptotics and proof-writing (chapter 2); LaTeX
- Week 2: stable matching (chapters 1, 2)
- Week 3: graph algorithms (chapter 3)
- Week 4: greedy algorithms (chapter 4)
- Exam 1: in class Friday, October 7
- Week 5: minimum spanning trees (chapter 4)
- Midterm break. Monday, October 17
- Week 6: divide-and-conquer algorithms (chapter 5)
- Week 7: dynamic programming (chapter 6)
- Exam 2: in class Friday, October 28
- Week 8: shortest paths revisited (chapters 6, 7)
- Week 9: network flows (chapter 7)
- Exam 3: in class Friday, November 11
- Week 10: algorithmic bias; wrap-up
- Monday, November 21 (last day of finals): final project due