Return to the Competition Programming home page
Course Meetings
Wednesdays 6:30–9:30 in Wean 5419-D.
Official Course Description
The focus of the course is the development and implementation of advanced algorithms, as well as the skills required for programming competitions. The course will include a review of various algorithms and data structures, including indexing structures, trees, graphs, strings, numeric methods, computational geometry, and heuristic search.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, programming homework, and algorithm-theory readings.
Units
Students may take this course for either 6 or 9 units. The 6-unit course runs through Friday, April 1, whereas the 9-unit version is the full-semester course.
Prerequisites
15-211 or permission of an instructor
Textbook
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, first or second edition, McGraw Hill.
Web site
The course web site, www.andrew.cmu.edu/course/15-295, contains homework assignments, readings, policy documents, and other resources.
Instructors
Greg Kesden and Eugene Fink
Contact Information
Greg Kesden
- gkesden@cs.cmu.edu
- http://www.cs.cmu.edu/~gkesden
- 412-268-1590 (office) or 412-687-6198 (home), either rolls to cell phone
- Office hours: Monday, Wednesday, and Friday 1:30-2:30
- Frequently available in the evenings, from 9:30-10:30AM, or by appointment
Eugene Fink
- eugene@cs.cmu.edu
- http://www.cs.cmu.edu/~eugene
- 412-268-6593
- Office hours: Wednesday and Thursday 4:30-5:30, or by appointment
Please call or e-mail if you need help -- that is why we are here.
Course Attendance
Attendance is expected at all classes. In fact, simple open-eyed and otherwise participatory attendance is 30% of the course grade. Absences cannot be excused, at least without a request from your academic dean, because there is no way of replacing the lost opportunity for team work or mitigating the effect that an absent member has on a team.
Need Help?
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.
Assignments and Grading
- Attendance: 30%
This is, very simply, a grade awarded based on the amount of the course meetings for which you are present. 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.
- Practice problems (in class, team): 10%
Much of class time will be spent solving competition style problems in teams. Scoring is weighted to normalize for team size and the difficulty of the problem set. It is a critical part of the course; however, because the problems are very difficult, it is assigned only small percentage of the course grade. It enables students who work hard to do well, even with a low score for in-class exercises. It also minimizes the "pulled along by team members" effect on the overall course grade.
- Practice problems (homework): 30%
Problems that have not been completed in class are completed individually as homework. This weighs more in the course grade than the teamwork, because it is an individual effort, and because time is not constrained. 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 strictly against the rules to discuss the problems with anyone, or to otherwise share information about the problems with anyone. The homework problems are an individual effort.
- Readings: 30%
Another form of homework involves reading about data structures, algorithms, problem solving techniques, programming techniques, or tools, and producing an example implementation or otherwise demonstrating understanding of the reading. As with the problem sets, the deliverable assignment is an individual effort. It is however allowed and even encouraged to discuss the reading, and the topic more generally, with others.
Grade Corrections
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. If you are asked to provide a copy of the work or feedback in question, or to provide your concerns in writing or e-mail, you are required to do this before your concern is addressed.
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.
In general, grading concerns should be addressed within one weeks, 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. In the extremely unlikely event that neither of us remains at the university, is on leave, or is otherwise inaccessible, contact an administrator in the Computer Science department.
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 and/or the academic dean in the home department. It can also be done formally using the policy outline in the Academic Regulations.
Collaboration
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 towards any graded work may be, at the discretion of the instructors, considered Academic Dishonesty under the applicable University, School, Department, and/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. This 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.
Late Work
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.Please note: This policy was revised on January 17, 2005. It replaces a prior policy accepting late submissions for only seventy-two hours.
No Email Attachments
Unless otherwise directed by an instructor, do not send files as attachments via e-mail. For technical reasons, this mode of file transmission is extremely inefficient. 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.
The PTS group gkesden:staff-295 contains both instructors. If this does not make sense to you, send e-mail to us and ask for instructions for sending the files.
Topical Outline
Important Note
There will be no class on Wednesday, April 6th because the instructors, and our World Final Contender team, will be in China for the World Finals. Cheer them on!