Syllabus

This course is about solving, and about writing about solving, computational problems. By studying some selected applied problems and their distilled classical formulations, we will learn:

• how to identify and isolate computational problems,
• various techniques for solving problems efficiently,
• how to describe an algorithm that solves a given problem, and
• how to prove the properties of a given algorithm.

We are going to cover much of the book. This includes (not necessarily in this order):

• Review of some background (Chapters 2 and 3): graphs, running times, correctness proofs, etc.
• Greedy algorithms (Chapter 4)
• Divide-and-conquer (Chapter 5)
• Dynamic programming (Chapter 6)
• Network flow (Chapter 7)

For more details, please see the schedule page, which will be kept up-to-date as I adjust the schedule throughout the course.

• Attendance. I expect that you will attend every class meeting possible — you are responsible for accommodations if you must miss a class. I won't always take roll, but I reserve the right to do so during any class. You may be absent up to twice when I take roll without it affecting your grade. Unless you've made formal arrangements with me in advance*, there are no excused absences beyond this.
• Presence. “Presence” is more than just physically being there. Turn off your phone, do not text during class, do not use your computer for anything other than in-class activities and note-taking, etc. We've only got a short time together, so let's make the most of it.
• Asking Questions. If you have a question, your classmates are probably wondering about it too. Raise your hand, interrupt me if you need to, but don't stay silent! If my answer to your question isn't helpful, let me know; I'd much rather take the time to answer your question right than to leave you and your classmates confused.
• Readings. Read the book! There will be a (relatively) short reading assigned at the end of each class session that will prepare you for the next class. The great thing about a book is that you can take as much time with it as you want; it's often helpful to return to the reading after class, while you're working on your homework, and while you're studying for exams.
• Homework and Quizzes. Problem sets will be assigned regularly throughout the term, with approximately one problem due per class meeting. There are also a variety of take-home quizzes throughout the term that occasionally take the place of a homework problem. The quizzes are meant to help you focus on abstract concepts and also to give you practice for the exams. The homework and quizzes are important: honestly, they'll probably be the things from which you learn most in this class.
• Exams. There is one in-class midterm exam and one sit-down final exam. If you need accommodations for test-taking because of a disability, please contact me early and we will make appropriate arrangements.
• Talking to Me. Keep me in the loop. If there's anything at all you want to talk to me about, particularly if you're struggling, please stop by my office hours or email me to schedule a time to talk. The whole reason I'm here is to help you learn.

If you need help with an assignment or studying, you can consult with other students, ask a teddy bear (really! It works!), consult the book, search online, post to Piazza, ask a lab assistant, or come to me. We'll talk some in class about good strategies for working through assignments.

I also want to help you if you need it, so please come see me! Though I'll do what I can via Piazza, I can generally give much better answers in person. My office hours are posted on my faculty page; please either stop by then or email me several hours in advance to arrange to meet. I am rarely available on Tuesdays and weekends, as I reserve those for research, other work, and being a person. I try to respond to electronic communication promptly, but I can't promise any faster turnaround than the afternoon of our next class meeting after the day that you contact me.

There are also a number of college-wide resources available through the Academic Support Center: the wonderful Math Skills Center, the Write Place, an Academic Skills Coach, a tutoring program, and others. The library and Student Health and Counseling are also there to support you. Finally, the CS department has a smattering of online resources.

Your grade will be computed as follows:

Your grade will be computed according to the table to the right. I reserve (and often exercise) the right to rebalance these percentages to increase your final grade; I will never change these weights in a way that lowers your grade. Using the above weights, a total of 90% and up will earn you some level of A, 80% and up at least some level of B, 70% and up at least some level of C, 60% and up at least some level of D.

The assignments are generally composed of two or (rarely) three algorithm-design problems, with a very occasional abstract problem thrown in. Generally speaking, there is one (multi-part) problem due each day that way have class. The requirements for these types of problems are somewhat involved, so please refer to the Homework Guidelines page for details about the homework.

Problems turned in early will be rewarded, those turned in late will be penalized, and those turned in more than 72 hours late will receive no credit. Here's the breakdown:

Problems turned in early will be rewarded, those turned in late will be penalized, and those turned in more than 72 hours late will receive no credit. The table to the right shows the breakdown.

This scheme is designed to eliminate the distinction between “legitimate” and “illegitimate” late submissions. Unless something truly extraordinary happens, there will be no extensions given. If you turn something in late, no explanation is necessary or desired. Note that turning in five problems each a day early balances out turning one in half a day late. Note also that there are about 20 problems over the course of the term, comprising 22% of your total grade, so it's not the end of the world if you get low grades on a couple of them.

Each problem in a problem set functions as its own independent assignment; they are generally assigned in weekly batches in order to give you plenty of time to think and work on them. Grades, bonuses, and penalties are all assessed separately on each problem, and the bonuses and penalties are only figured into your grade at the very end of the term. If you ever have a question about how your grade is computed, please ask.

Great work (and great learning) often happens in groups, and you should collaborate with your classmates a lot in this course. There is a big difference, though, between thinking about and solving a problem as a group (which is good), and copying an answer from someone else or letting someone else copy your answer (which is bad). The formal policy below lays this out explicitly, and supplements the College's academic integrity policy and the Dean of the College's detailed guide to academic integrity.

I am obligated by Carleton policy to report any suspected violations to the Dean’s office. The Dean, in turn, brings it to the Academic Standing Committee. The academic penalty for a finding of responsibility can range from a grade of zero on the specific assignment to an F for the course.

If you have any doubt about any aspect of this policy, ask beforehand!