Syllabus

This course is 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, and
• fallback strategies for when those techniques fail.

We are going to cover much of the book, but not in the same order. This includes (not exactly in this order):

• review of some background (Chapters 2 and 3):
  • graphs
  • running times
  • correctness proofs
• major algorithmic design techniques:
  • greedy algorithms (Chapter 4)
  • dynamic programming (Chapter 6)
  • divide-and-conquer (Chapter 5)
  • network flow (Chapter 7)
• approximation algorithms (Chapter 11)
• randomized algorithms (Chapter 13)

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

• Attendance / Presence. I expect that you will attend every class meeting — missing class is not acceptable. I'll have some sort of weird scheme for taking attendance; more details about this on the first day. “Presence” is more than just physically being there. Turn off your phone, do not text during class, do not use a laptop for non-note-taking purposes, etc. We've only got a short time together, so let's make the most of it.
• Asking Questions. That's right, you are required to ask questions if you have them! (Not that I can enforce that.) Raise your hand, interrupt me if you need to, but don't stay silent! If you have a question, your classmates are probably wondering about it too. My goal for this class is to get you to understand the material (and to love it if possible!), so it's sort of pointless for me to be there droning on to a room full of confused and silent faces. There are other resources available to help you (see below), but liberally asking questions in class is usually the best way.
• Readings. Read the book! There will be a (relatively) short reading assigned at the end of each class session that I will expect you to read before the next one. Furthermore, the book does a great job explaining things, so I highly recommend it for studying after the fact. If you’re struggling with a concept, it may be useful to actually code up the relevant structures.
• Homework. Problem sets will be assigned regularly throughout the term, with approximately one question due per class meeting. (This policy is designed to keep you consistently engaged with the material, but to give you a little while to ponder each homework question.) The point of the homework assignments in this course is to give you an opportunity to engage directly with the course material. The homework questions are meant to be challenging and to stretch you; simply put, I believe that the homework is where you will do the vast majority of your learning in this class. Grapple with the questions; talk to your classmates about solution strategies if you’re feeling stuck; do the homework.
• Exams. There are two in-class midterm exams 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.

• Yourself. If you're stuck on a problem or struggling with a concept from class, take a break and think about something else for a few hours and then try a fresh start. Go through any code you've written line-by-line and simulate the results in your head or on paper. Draw diagrams to help you figure out what's going on. If you haven't written code for something, consider doing so.
• The book (or another book, or Wikipedia). Our textbook is great and it's a very useful place to turn if you're having trouble. Take a shot at the self-test exercises you'll find in each chapter, and compare your answers to those at the end of the chapter. You may find that other textbooks jive better with your way of thinking; check the library. Wikipedia is also a great resource for this course, though the language can get needlessly technical and the terminology that Wikipedia articles use may not match that of our book.
• A teddy bear (or imaginary expert). Seriously! This idea is also known as rubber ducking. When you have a problem, describe it out loud to a teddy bear, or draft an email to a smart person you respect. You'll have to explain the context and particulars of the problem, what you've tried, and why you think what you did doesn't work. In the case of the teddy bear, this is because teddy bears don't generally know a lot of computer science; in the case of the expert, you'll want to be sure to avoid wasting their time by asking about something you haven't really thought through. 90% of the time, you'll find that in the process of explaining your problem to someone else, you realize exactly what the solution is. I still use this trick pretty often, and it's very reliable.
• The course forum. Our Moodle has a forum set up; if you've written a teddy-bear explanation and you're still confused, go ahead and post it to the course forum. Don't worry about being too verbose in your writing; better to be really clear than to leave things out.
• Your classmates. You are each other’s best resource: talking through the course material with someone else who is also trying to master it is a great way for you both to learn. (And don’t discount the learning that you will do while trying to explain to a classmate an idea covered during class that you think you understand! Teaching to others really shows you where the gaps in your knowledge are.) The homework assignments are meant to challenge you, and figuring some of them out together is a great approach. That said, please pay close attention to the Collaboration Policy below.
• Me. My office hours are as follows:
  • Monday 2pm–3pm
  • Wednesday 3pm–4pm
  • Thursday 2:30pm–3:30pm
  • Friday 12pm–1pm

  At these times, you can be sure to find me in my office, CMC 320. I’ll generally be available most of the time from 9am to 5pm on those same days, except when I’m teaching. If you’d like to meet with me outside of my office hours, please check my calendar, email me 24 hours in advance, and propose at least two different meeting times that would work for you. I reserve Tuesdays and the weekends for research, so while I’ll try to answer any emails in a timely fashion during those times, I won’t be available for in-person meetings.

• Other college resources. In this class, as with all classes at Carleton, there are a number of college-wide resources that can be of help. Use the library. Use the Write Place (written communication is an essential part of this course; when you “write up a solution” to a problem, you are writing!). Check out the department's online resources. Feel free to talk to the lab assistants in the CS labs on the 3rd floor of the CMC in the evenings; they are often CS majors who have taken this course and may be able to help. The Math Skills Center may be able to help you with some aspects of the course too. Finally, the college has a tutoring program available, which you can investigate if required.

Your grade will be computed as follows:

Assignments will be submitted via Moodle.

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.

Assignments turned in early will be rewarded; those turned in late will be penalized. Here's the breakdown:

To be clear, assignments turned in more than 72 hours late will receive no credit.

In multi-part assignments, for which different questions may be due different days, each part counts (for the purposes of assessing a bonus or penalty) as a single assignment. That is, if an assignment is broken into three parts, and you turn in one of those parts 24 hours early, you will receive 3 bonus percentage points for just that one part (which itself was worth 1/3 of the total grade), equivalent to 1 bonus percentage point (1/3 of 3 points) overall. You're welcome to contest or question my math on your grades if you'd like.

You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will result in severe punishment, which may include receiving a failing grade in the course or even dismissal from the college. Academic dishonesty has no place in an institute of higher learning; it wastes my time and yours.

Please familiarize yourself, if you haven't already, with the College's academic integrity policy and the Dean of the College's detailed guide to academic integrity.

My motivation for the course’s collaboration policy, which is below, is as follows. I am a major proponent of you learning from each other in a course like this one, and I strongly encourage you to work together in attacking homework exercises. Students who think about problems together almost always learn more and find difficult problems less frustrating than those who work alone. However, there is a major difference between, on the one hand, thinking about and solving a question as a group (which is good, both educationally and morally); and, on the other hand, copying an answer from someone else or giving a answer to someone else to copy (which is bad, educationally and morally, and has punitive consequences). The policy below is formulated to encourage the former while banning the latter.

I am obligated by the Faculty Handbook to report any suspected violations to the Dean’s office. Any student who is found responsible for academic dishonesty in this class will receive an F for the course.

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