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 communicate 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
• major algorithmic design techniques:
  • 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 / Presence. I expect that you will attend every class meeting possible — you are responsible for accommodations if you must miss a class. “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 and algorithms.
• 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. There are more details on the Homework Guidelines page.
• 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, and note that you should only work on each homework problem with at most two other people; working larger groups is counterproductive for your learning.
• Me. I set aside four hours during the week when you can drop by to see me at my office, CMC 320. They're listed in the “The Essentials” box at the top of the page.

  Though I am generally around except on Tuesdays, please don't drop by my office outside of office hours. If you’d like to meet with me outside of my office hours, please check my calendar, email me as far in advance as possible (24 hours would be nice), 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! 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 the course hand-in directory on your Courses network drive.

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 problem sets are graded on a categorical and non-arithmetical scale; for convenience, each category is given a number (0 to 5) but the mapping from these categories to letter grades is highly nonlinear and changes as the term progresses. That is, two 3s is not the same thing as a 2 and a 4. For more details, see the Homework Guidelines page.

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.

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 assignments a day early balances out turning one in half a day late. Note also that there are 22 assignments, comprising 22% of your total grade.

Since each problem in the problem sets is turned in on a different day, each one is technically a separate “assignment” and bonuses and penalties will be assessed separately on each one. At the end of the term, all your bonuses and penalties will be averaged together and then applied directly to the “Assignments” portion of your grade.

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!