Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Fall 2012 -- CSC 2700 Section 02

[Isaac's Home Page ]  [Mailing List ]  [Class Page ]  [Printable ]  
 Home
 Outline/Policy
 Summary
 Approach
 References
 
 Homework
   View
   Upload
 
 Problems:
   Archive
   Archive Mirror
   Categories
   Guidelines
 
 Coding
   Tips
 
 Contests:
   Regional
   NA Qualifier
 
 Extra:
   Grades
 
 
 
 Class:
   CSC 2700 Section 02
   Tureaud Hall 101
   Tuesday
   6:30 PM - 8:20 PM
 
 Previous:
   2012 Spring
   2011 Fall
 

Outline/Policy

Return to Class Main Page


Introduction

Each year the ACM 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. This semester, this class will help train and choose LSU's Programming Team(s) for the ACM Regional Programming Contest.

Return to Top of Page


Purpose of Course

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

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


Course Implementation

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:

Return to Top of Page


Topics/Concepts to be Covered

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


Grading Policy

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 meetings:

This class will meet the following meetings:
Anticipated Class Meetings
August 21 28
September 4 11 18 25
October 2 9 16 23 30
November 6 13 20 27

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 5 points. By coming to class and participating in the activities, you can collect 70 points.

For each pair of classes, you will have to turn in one (1) programming assignment. The program will be taken from 1 of the programs that I hand out in class (unless otherwise prohibited). You must implement a solution to one of the problems, submit it to the online judge and have it judged correct before turning it in. If turned in on time, each program is worth 3 points (7 time 3 = 21 points). Programs turned in late earn 1 point each. Note: You must turn in all seven (7) programs to pass!

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

  • Participating in the Practice Contest
  • Competing the ACM Regional Programming Contest
  • Assisting the contest
  • Helping debug the 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.

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





[ Powered by Red Hat Linux ] [ Powered by Apache ] [ Powered by PHP ]

The statements and opinions included in these pages are those of only. Any statements and opinions included in these pages are not those of Louisiana State University or the LSU Board of Supervisors.
© 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012 Isaac Traxler