Outline/Policy

Each year the ICPC conducts an International Collegiate Programming Contest for undergraduate students. Teams are chosen for this contest via Regional Programming Contests (LSU hosts the ACM South Central Regional Programming Contest that covers Louisiana, Oklahoma and Texas). The top team(s) from each region are invited to compete in the International contest.

Many of the schools in our region compete. The LSU Computer Science Department fields at least one team each year for our regional contest to represent LSU and Louisiana. Since LSU is the flagship university of the state, LSU should send a well-prepared, competitive team.

Team preparation varies from school to school. Many schools use a formal class to prepare participants for Programming Contests. This has the advantage of providing a structured, regular training and practice environment that the students are motivated to take part in.

This course is a one hour class to create that environment at LSU. The goal this semester will be to instill fundamentals in students that will better prepare them for competition.

Next fall, a follow-up course should be offered to hone the skills of the students that decide to actually compete in the next ACM Regional Programming Contest.

Return to Top of Page

The obvious purpose of this course is to help students who are interested in competing in the ACM Regional Programming Contest. But the class will do much more than that.

The primary focus of this class is improving individual and group problem solving skills. As the students progress through this class, they will utilize the skills that have learned in other classes to solve problems. This process will result in improvements in the following areas:

• Communication skills
• Time management
• Resource management
• Problem evaluation
• Hidden complexity recognition
• Data structure use
• Algorithm use
• Software design
• Software implementation
• Software testing
• Rapid development
• Software efficiency
• Numerical precision

The real benefit of this class is that students at various levels will work together to understand and solve problems. They will learn to read problems, analyze them, discuss them, recognize which data structures and algorithms make sense for various problems, improve their coding skills, and learn better testing techniques. They will collectively hone their computer science skills.

The benefits are numerous. The students become better problem solvers, better software designers, better programmers, better testers and better debuggers. They learn to work as teams and to manage time and resources. Because they have improved and because they see more benefits of their previous classes, they become better students in future classes. This leads to them representing LSU better in their future jobs.

Return to Top of Page

The course will generate one hour of credit. It will be treated as a lab class so that two contact hours a week would occur. Grades would be determined by class participation, successful problem submission, and completing a final exam.

Each class meeting will be made up of combinations of lecture, problem analysis, data structure discussion, algorithm discussion, solution design, solution implementation and testing. The problems discussed each time will provide a pool that the students can write and submit to an existing online judge system for evaluation. Since a class is about 14-16 weeks long, students would be expected to solve at least eight problems (from the ones presented in class) during the semester.

The course will rely on online resources and text books. Obviously, the texts the students already have will be valuable to them. Here is a brief list of some the resources they will use and/or have access to:

• Required
  • Competitive Programmer’s Handbook by Antti Laaksonen (Local copy)
  • Art of Programming Contest by Ahmed Shamsul Arefin
  • UVA Problem Archive
  • UVA Online Judge (Local information about UVA Online Judge)
  • ICPC Web Site -- create account for use in contest (practice/region)
  • LSU Student Code of Conduct - corrected
  • LSU Faculty Handbook - corrected
• Additional
  • Sphere Online Judge
  • Codeforces
  • Programming Challenges by Steven S. Skiena and Miguel Revilla
  • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
  • Competitive Programming by Steven Halim, Felix Halim
  • Problems on Algorithms by Ian Parberry
  • The Psychology of Computer Programming - Silver Anniversary Edition by Gerald M. Weinberg

Return to Top of Page

This course will be organized so that each of the different areas that the students need to gain expertise in are covered. Most activities will concentrate on a small number of areas at a time. Below is a list of many concepts that the student will be exposed to during this course:

• Problem Evaluation - A number of problems will be presented to the students for them to analyze. During this phase, the students will be trying to recognize the actual problem underneath the written problem description. The goal is to determine what algorithm(s) will solve this problem.
• Hidden Complexity Recognition - Many contest problems have something that makes them harder than they would appear that does not usually show up until after a solution is determined. These hidden gotchas often make a simple appearing problem into a very difficult/complex problem. Recognition of these pitfalls can help a team avoid wasting a lot of time on a deceptive problem.
• Problem Ranking - After evaluating several problems, a team must decide which ones to implement in what order. Since penalty points are accrued for how long each problem remains unsolved, it is important to solve as many problems as possible as quickly as possible, Choosing the easiest problems first is critical.
• Solution Testing - Taking example data and running through proposed solutions or even coded solutions is an important part of a successful effort.
• Algorithm Implementations - Many of the problems rely on variations of a few different algorithms. Learning how to implement and adapt those algorithms can dramatically improve the success of the team. Examples of some of the algorithms are:
  • Sorting
  • Searching
  • Elimination from a list
  • Combinations
  • Permutations
  • Pattern Matching
  • Parsing
  • Numerical Principles/Relationships (rules of divisibility, sieves, clock arithmetic, ...)
• Data Structure Tricks - Solving many of the problems easily involves coming up with a data structure that models the problem but is easy to code, modify and debug. These approaches are often referred to as tricks. Knowing a number of these tricks and be comfortable working with them can be instrumental simplifying the solution to a problem. Examples of some of these data structures include:
  • Bitmaps
  • Large-number Representations
  • Sparse Data Storage
  • Circular Queues
• Coding Techniques - Most algorithms can be implemented many different ways. Some methods are easier to write, modify and debug than others. Being aware of multiple approaches and learning how to decide which to use when can make a huge difference in length, complexity and development time of solution.
• Debugging Techniques - Unfortunately, not all code works the first time. Even if it works, it does not necessarily solve the problem at hand. Being able to quickly isolate why and determine what to do to transform the code is a skill that all programmers need. Being able to do it quickly may be the difference between solving an extra couple of problems.
• Time Management - The most common statement heard after every contest is "If I/we just had a little bit longer we could have completed 1/2/3 more problems". Learning to manage time can produce the equivalent of an extra 30 to 60 minutes.
• Resource Management - During a competition, a team has a lot of resources that must be managed: physical time, keyboard time, computation time, problem sets, paper, people skills and adrenaline. Proper management of these resources will definitely increase the probability of the team being successful.
• Psychology - Learning to manage individual pressures and group dynamics is essential to not only success at the contest but continued friendship after the contest. Many people react very differently while under the pressure of a live contest. These difference in reactions quite often take the rest of the team by surprise. Crises management is also a potential problem. Learning to handle the stresses that can occur is essential to successful completion of the contest.
• Linux Use - Students will become familiar with Linux, its gui, editors, compilers and software development tools. Since ACM contests are run on Linux, it is necessary to make sure that students feel comfortable in that environment.

Return to Top of Page

The best way to think of this class is as a lab class. Most of what you learn will come from the class discussions, attempting to solve problems, and working with others. From that perspective, the grading is oriented to encourage class participation. Basically, each interaction you miss, results in a letter grade loss (or the need to do outside work to compensate for the loss).

• A - 92-100 points
• B - 84-91 points
• C - 78-83 points
• D - 71-77 points
• F - less than 71 points

This class will meet the following days:

• February 16 - No class, Mardi Gras Holiday
• April 20 - Final

Your grade will be based on the following:

• Class Participation
• Homework (Programming Assignments)
• Extra Activities/Assignments
• Taking the Final

Each class that you attend and participate in will be worth 4 points. By participating (which requires attending) in the activities, you can collect 4 points (14 classes * 4 = 56).

You must implement an Online Judge accepted solution to 8 problems this semester. Eeach program is worth 4 points (8 times 4 = 32 points). Note: You must turn in all 8 programs to pass!

If you have participated in each class and turned in each program, you are 4 points from an A. Additional points can be earned via the following activities (permission in advance required):

• Compete in the ACM Qualifier Programming Contest
• Compete in the ACM Regional Programming Contest
• Helping debug the regional contest image/web site
• Additional programming assignments
• Presenting a topic with sample problem in class
• Other items to be named later

You will have more than adequate opportunities to make an A+ in this class. You should take advantage and knock out extra points early on to free you up at end of semester.

Knock out the minimum number of programs early -- do not let them get in the way of other classes.

If you miss a class or have other issues, get in touch with me. We can work it out.

The final will be the last scheduled class meeting (because this is a lab class, the final happens BEFORE regular finals start). You MUST attend and take the final.

Return to Top of Page