Course information
Thanks to my colleagues
Though I have taught this class several times over the past 30 years, most of 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.
This course is running during the same term as a section taught by Layla. We will be coordinating assignments, exams, grading, etc. throughout the term.
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.
Homework
Readings and reading reactions. For most reading assignments 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. Each week you will have a problem set consisting of a small handful of problems. Each problem set will have two due dates. By 5:00PM Tuesday, you will hand in a solution for any one numbered problem (that is, a whole problem with a number, not just 1(c) or 2(b)). 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 5:00PM Friday. I will post each week's problem set no later than Friday one week before it is due (except during the first week, in which case I will post the problem set on the first day of class).
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.
Grading
Your grade will be determined by your performance on homework (40%) and three exams (20% apiece).
Finals?
The last homework will be due on the last Friday of the term (May 24). The last exam will be Monday, May 27. There will be no final exam and no final project, so you're free after the 27th. (We'll have some algorithmic fun in class on May 29 to celebrate.)
Late homework
You may submit up to two 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 late assignments, late work will receive zero credit.
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, large language models, 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.
Yeah, but what about ChatGPT, Claude, and their friends?
???? The general principle here is that you can't have
- OK. ...
- NOT OK. ...
- NOT OK. ...
- NOT OK. ...
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.
Sometimes I forget to start Zoom during office hours. If you want to talk to me on Zoom and I'm not there, just Slack DM me, and the little red dot on my screen will call my attention to you.
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)
- Exam 1: in class Monday, April 15
- Week 4: greedy algorithms (chapter 4)
- Week 5: minimum spanning trees (chapter 4)
- Midterm break. Monday, April 29
- Week 6: divide-and-conquer algorithms (chapter 5)
- Exam 2: in class Monday, May 6
- Week 7: dynamic programming (chapter 6)
- Week 8: dynamic programming and shortest paths revisited (chapters 6, 7)
- Week 9: network flows (chapter 7)
- Exam 3: in class Monday, May 27
- Week 10 (i.e., Wednesday, May 29): algorithmic bias; wrap-up; AMA