Syllabus for MCS-394 Topics in Computer Science: Programming Challenges (Spring 2012)


Real-world problems don't come with any hint regarding the appropriate algorithm design technique or data structure to use. They aren't positioned within a course unit addressing a particular topic. Instead, you have to identify relevant techniques, brainstorm possibilities, and innovate or adapt as necessary. In this course, we will practice this skill set by working problems from regional and international programming contests. Prerequisite: MCS-375 (Algorithms: Analysis and Design)

Office hours

I will be available in my office (OHS 306) from 9:00-9:50 on Mondays, Tuesdays, Thursdays, and Fridays, as well as by appointment. Or try your luck: just stop by and see whether my door is open. You may send me electronic mail at or call me at extension 7466. I'll try to put any updates to my office hours on my web page, so check there if in doubt.

World Wide Web

All course materials will be available through my World Wide Web page. The URL for this course is We also started using the course's moodle forum as a repository for the work we did as a class, but then we switched to using bitbucket.


Any substantive contribution to a solution you present that comes from another person or from an online or printed source should be properly acknowledged. Failure to do so is plagiarism and will necessitate disciplinary action.

You are expected to be familiar with the college academic honesty honor code policy and to comply with that policy. If you have any questions about it, please ask.

Problem sets

We will work through a succession of problem sets, each drawn from either the regional or the international level of the Association for Computing Machinery's International Collegiate Programming Contest (ACM ICPC). I will start by posting just one here. Each time we approach the point of exhausting our current problem set, I'll add another to the list. You can also ask for another at any point.

Each time we have a new problem set, I will ask you to read through it and indicate any problem you want us to not work on in class because you plan to develop a solution on your own to present. (It is OK if more than one student wants to work on the same problem; we'll just make sure no one presents until everyone has either solved the problem or given up.) If you have previously worked one of the problems (for example, as part of a contest team), you should also flag it as one not to work on in class. Other students can work that problem individually, but you shouldn't. The remaining problems we will work as a class.

  1. North Central North America, 2009 (post-contest version: clarifications issued during the contest have been incorporated)

  2. North Central North America, 2011 (see also the clarifications)

  3. North Central North America, 2007: problem 1, problem 2, problem 3, problem 4, problem 5, problem 6, problem 7, problem 8, problem 9. See also the clarifications.

  4. North Central North America, 2010: problem 1, problem 2, problem 3, problem 4, problem 5, problem 6, problem 7, problem 8, problem 9.

  5. Word Finals, 2011

  6. Extra problem: Isopsephism

Presenting solutions

When you think you have solved a problem, you should email me your program so that I can verify it behaves as specified. Once your program passes this testing, I will ask you to present your solution to the class. Your presentation should include a clear explanation of the algorithmic ideas you used as well as a walk-through of the code. In presenting the algorithmic ideas, you may want to use techniques such as drawing diagrams of data structures, working a small problem instance by hand, or referring by name to a well-known algorithm you adapted. If the problem specification indicates the maximum instance size, you should include any analysis you did to be sure your program could solve instances that large.

You will receive credit for at most one presentation in which all your variables store individual numbers, strings, booleans, or procedures. Any further presentations will need to make meaningful use of some other sort of data structure.

To receive credit for more than two presentations, at least one of your designs needs to make use of dynamic programming, memoization, or a graph algorithm.


You will earn grade points (GPs) for participation in class and for presenting solutions. Each time you participate in class by contributing an algorithm design idea (typically on the white board) or doing some programming (typically using the keyboard), you earn 2 GPs, up to a maximum of 66 GPs that you can earn in this way. Each time you present a solution, you earn 10 GPs. Your course grade will be recorded as follows:

93 or moreA

We will use poker chips as tangible tokens of the GPs. White, blue, and black chips are worth 2 GPs each and are earned through class participation. You can exchange 5 of these chips for a red chip worth 10 GPs. Green chips are also worth 10 GPs and are earned through presentations. (The distinction between red and green chips is that red chips have to stop at 66 GPs.) I recognize that many people have difficulty perceiving the difference between red and green; I would be happy to help out if this is an issue.

Programming languages

So far as I'm concerned, we can use any language. We might learn different things depending on which language we use, but I don't have any preconceived notion of what the right things to learn are, so that doesn't bother me. You might choose a language that was very well suited, and learn how elegantly it fits the situation, or a language that was poorly suited, and learn how to work around the difficulties. You might choose a language you already are comfortable with and learn how to make the most of that leverage, or a language you don't know at all and learn the basics of the language. Any of those would be fine with me.

When we work together in class, we'll have to achieve some degree of consensus on what we are doing. I hope that will be possible, not because everyone will have the same language they are comfortable with, or the same language they are itching to learn, but because you'll all be flexible at taking turns being in different relationships with the language. That is, on a given problem, student X may be in comfortable territory and student Y may be learning a new language; on the next problem, they may switch.


Gustavus Adolphus College is committed to ensuring the full participation of all students in its programs. If you have a documented disability (or you think you may have a disability of any nature) and, as a result, need reasonable academic accommodation to participate in class, take tests or benefit from the College's services, then you should speak with the Disability Services Coordinator for a confidential discussion of your needs and appropriate plans. Course requirements cannot be waived, but reasonable accommodations may be provided based on disability documentation and course outcomes. Accommodations cannot be made retroactively; therefore, to maximize your academic success at Gustavus, please contact Disability Services as early as possible. Disability Services ( is located in the Advising and Counseling Center.

Support for English Language Learners (ELL) and multilingual students is available via the College's ELL Support staff person, Andrew Grace ( or x7395). He can meet individually with students to consult about academic tasks and to help students seek other means of support. In addition, ELL and multilingual students can seek help from peer tutors in the Writing Center. Please let me know if there is any accommodation in the course that would enable you to more fully show your abilities.

Instructor: Max Hailperin <>