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

Description

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 303) from 9:00-9:50 on Tuesdays and Thursdays (other than March 11th) and from 11:30-12:20 on Mondays and Fridays (other than March 12th), 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 max@gustavus.edu 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 http://gustavus.edu/+max/courses/S2010/MCS-394/.

Honor

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, namely this year's regional contest for our region. Each time we approach the point of exhausting our current problem set, I'll add another to the list.

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.) The problems no one claims 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, 2007: problem 1, problem 2, problem 3, problem 4, problem 5, problem 6, problem 7, problem 8, problem 9. See also the clarifications.

  3. North Central North America, 2002

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.

Grading

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:

GPsGrade
0-59F
60-66D
67-69D+
70-72C-
73-76C
77-79C+
80-82B-
83-86B
87-89B+
90-92A-
93 or moreA

Accessibility

If you have a learning, psychological, or physical disability for which a reasonable accommodation can be made, I would be happy to refer you to the college's disability services coordinator, and to cooperate in the accommodation process. It is generally best if this can be done as soon as possible.

Class meeting days

I anticipate meeting on all of our regularly scheduled meeting days (Mondays, Wednesdays, and Fridays) except that we will not meet on March 12th, when I will be attending a conference.


Instructor: Max Hailperin <max@gustavus.edu>