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?
My understanding of Large Language Models (LLMs) and their uses is evolving. I think there's a chance that LLMs can be used as be powerful tools in our search for knowledge and understanding. But it's also clear that they can be used in ways that inhibit learning. I want to develop course policies that will incentivize my students to use LLMs only in the former ways rather than the latter. But for now I just have a few general principles and a few case studies to offer as guidance.
First, some principles.
- I am not going to prohibit the use of LLMs for this class, even though I think such prohibitions are a reasonable choice at this moment.
- Whenever you use text drawn verbatim or in summary form from another source, you should cite that source. This includes LLMs.
- Proper citation of an LLM's contributions includes quotation marks around verbatim quotation, plus the name and version of the specific LLM you used, as well as the exact prompts you used to generate the text you quoted or summarized.
- Properly quoting and citing an LLM's work will, in this course, prevent you from violating Carleton's academic integrity standards; it will not, however, prevent you from getting a low score. See the examples below.
- Sometimes LLMs produce very good work. (For example, if you ask ChatGPT to write you an implementation of Selection Sort in whatever language, you'll probably get sensible code.) But sometimes LLMs produce results that are mediocre or nonsensical or flat-out wrong. It's up to you to determine which you're looking at.
- Your goal in this course should be to gain as deep an understanding as possible of the algorithms, algorithm paradigms, proof techniques, applications, etc. that we will study. If you find yourself outsourcing the job of understanding to an LLM, then you're not using this tool effectively and you should talk to me about better ways to use (or not use) LLMs in your studies.
- Incorporating LLMs into our learning toolbox is an on-going conversation among educators, students, policy-makers, etc. I will introduce this conversation in class a few times during the term. I encourage you to share with me and your classmates your experiences of using LLMs effectively or ineffectively in your learning.
Here are a few concrete examples of potential uses of LLMs.
- OK: You ask for a walkthrough of Dijkstra's Algorithm on a graph of the LLM's choice.
- OK, BUT YOU GET A ZERO: You ask for a walkthrough of Dijkstra's Algorithm on a graph from a homework assignment, and you do cite the LLM.
- NOT OK, AND I REPORT YOU TO THE ACADEMIC STANDING COMMITTEE: You ask for a walkthrough of Dijkstra's Algorithm on a graph from a homework assignment, and you do not cite the LLM.
- PLEASE JUST DON'T: You ask for a walkthrough of Dijkstra's Algorithm on a slight modification of a graph from a homework assignment.
- OK: You ask for a list of common problems that can be solved with dynamic programming.
- OK: You ask for a proof of a theorem that is proved in our textbook so you can compare proof approaches. You also read the LLM's "proof" carefully to see whether you believe it to be correct and persuasive (and if not, why not).
- OK: You write your own proof for a homework assignment and ask the LLM for suggestions on improving it, and you cite the LLM. Remember, proper citation includes giving me the complete prompt you gave to the LLM, so I'll be able to see the difference between your final proof and the proof you started with.
- OK: You ask the LLM for an ASCII art portrait of Richard Karp.
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