Competition Programming (15-295):
Syllabus

Spring 2006

Tuesdays 6:30-7:20 and Wednesdays 6:30-9:20, in Wean 5419-D.

The focus of the course is the development and implementation of advanced algorithms, as well as the skills required for programming competitions. The students will learn to select appropriate algorithms for a given problem, integrate multiple algorithms for solving a complex problem, design new algorithms, and implement them in C++ or Java. They will also learn skills required for participation in programming contests, which include evaluation of problem difficulty, solving problems in teams, and work under time pressure. We expect that the best students from this course will represent Carnegie Mellon at the regional ACM Programming Competition, and possibly at the international ACM Competition. The course involves in-class programming practices and homeworks.

Students may take this course for either 6 or 9 units. The 6-unit course runs through Friday, March 31, whereas the 9-unit version is the full-semester course.

15-211 or permission of an instructor.

The course does not have a required textbook. You may optionally use the following textbook to look up standard algorithms:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, first or second edition, McGraw Hill.

The course web site, www.andrew.cmu.edu/course/15-295, contains homework assignments, policy documents, and other resources.

Greg Kesden

• gkesden@cs.cmu.edu
• http://www.cs.cmu.edu/~gkesden
• 412-268-1590 (office) or 412-687-6198 (home)
• Office hours: Mn, We, and Fr: 11:30-12:20; Tu and Th: 3:30-4:20; or by appointment
• Frequently available in the evenings

Eugene Fink

• 
• http://www.cs.cmu.edu/~eugene
• 412-268-6593 (office)
• Office hours: Wednesday and Thursday 4:30-5:30, or by appointment

We cannot stress enough that the instructors are dedicated to providing you the highest possible levels of support, inside of the classroom and outside. Please email both instructors with questions or concerns. It will assure you of the fastest possible answers, and also help us to remain coordinated.

Attendance is expected at all classes. Absences cannot be excused without a request from your academic dean, because there is no way of replacing the lost opportunity for team work.

• Attendance: 30%

It is a grade awarded based on the number of attended course meetings. Instructors are free to award partial credit for days on which you arrive late or leave early. But, because of the teamwork nature of class meetings, they are also free to deduct for the full day for any day in which you miss more than ten minutes of the scheduled time.
 
• In-class practices: 30%

Much of class time will be spent solving competition-style problems in teams. Scoring is weighted to account for the team size and the difficulty of the problem set.
 
• Homeworks: 40%

Some of the problems that have not been completed in class should be completed individually as homework. Typically individuals will be allowed to continue using the product of their own group’s in-class work. But, outside of the in-class group work, it is against the rules to discuss the problems.

We try to be careful about scoring your work and maintaining your grades, but we may occasionally make a mistake. If you have any questions about grading, please see one of us. If possible, he will help you "on the spot"; however, if he wants to discuss the issue with the other instructor, he may make a copy of your work and ask you to write down your concerns.

Please keep copies of all of your graded work, electronic submissions, and electronic feedback, until you receive your final course grade and are satisfied that it is correct. Without the original work and the grading information, it is more difficult and time-consuming to correct errors.

Grading concerns should be addressed within one week, and we may refuse to reconsider grades outside of this time period. If concerns arise after one week, but during the semester, please do contact one of the instructors, and we will do our best, within our discretion, to help.

Students do have the right to appeal final course grades. It can be done informally, beginning with the instructor, and then to the student's academic dean or the academic dean in the home department. It can also be done formally using the policy outline in the Academic Regulations.

Unless otherwise specified, all assignments should be completed individually.

If portions of your individual assignments have been significantly influenced by another person, literature, or web materials, you should prominently give them credit for their contribution. Proper attribution is critically important, and it is an absolute defense against charges of "Academic Dishonesty."

Failure to provide proper recognition for the contributions of others toward any graded work may be, at the discretion of the instructors, considered Academic Dishonesty under the applicable University, School, Department, or Intro Group policies.

The Academic Regulations are the only authoritative source for information regarding the University policy on Academic Dishonesty, and related procedural matters; however, the following is an informal summary:

• The instructor can charge a student with academic dishonesty and impose a penalty within the course, including an "R" grade.
• The instructor informs the University of the charge, where it is recorded. If it is a first offense, the University takes no further action. If it is not, a University committee is convened. For other than first offenses, the Committee, not the instructor, determines the penalty, which can include academic actions such as expulsion or suspension, as well as less severe actions. The student may appear at this hearing, and the instructor might also ask to appear or be asked to appear.
• Even on a first offense, the instructor can ask the University to convene a Committee as discussed above. It might be done, for example, in the case of a particularly flagrant case, or under atypical circumstances.
• The student has the right to appeal the instructor's finding of academic dishonesty. Such an appeal is heard by the same Committee as discussed above. In the event that both the student and instructor request a Committee, the same Committee will hear both.
• University procedure provides for the appeal of decisions by the Committee.
• In the event that the instructor charges a student with Academic Dishonesty, it is suggested that the student consider the totality of the circumstances calmly and rationally, and seek advice from the instructor -- as well as third parties, such as the student's advisor, academic dean, or a dean of student affairs. It may not be in the student's best interest to take a rash action, such as attempting to drop the course.
• Students who are charged with Academic Dishonesty should be aware that there will be no prejudice against them in the course, beyond the penalty directly imposed, as a result of the charge, or of any appeal.

Each homework is due in the beginning of the class meeting (that is, at 6:30pm) on the due date. If a homework is submitted within seven days after this deadline, the grade will be reduced by 50%. We will not accept a submission more than seven days after the deadline. If you have a serious reason for requesting an extension, such as illness or family emergency, you should discuss it with one of the instructors as soon as the problem arises, and definitely before the submission deadline.

Unless otherwise directed by an instructor, do not send files as attachments via e-mail. Instead, please submit assignments into AFS or the PC2 system, as directed.

If you need us to view files other than for submission, please create a directory within your AFS space, place the files into that directory, and give "gkesden:staff-295" at least "rl" access. If this does not make sense to you, send e-mail to us and ask for instructions for sending the files.

• Policies and procedures
• Standard libraries in C++
• Standard libraries in Java
• Sorting
• Greedy algorithms
• Dynamic programming
• Basic graph algorithms
• Advanced graph algorithms
• Basic geometry
• Computational geometry
• Strings
• Basic heuristic search
• Advanced search
• Simulation problems

Return to the Competition Programming home page