American Computer Science League

Source: acsl.org

This booklet is designed to help advisors and students prepare for the American Computer Science League contests.  Do not become alarmed if the material looks difficult!  Although the topics cover basic areas in computer science, few secondary schools normally teach them (at least not until they’ve been involved in ACSL!).  However, these categories are all manageable at the junior and senior high school levels, as experience from past years has proven.  Each contest contains at most one or two new categories, and most advisors find that about one hour is sufficient to introduce students to each new category.  Some topics late in the year are based on topics given earlier in the year.  For example, Digital Electronics is based on Boolean Algebra, which in turn, is derived from the well-known area of Set Theory.  The information contained in this booklet supercedes all previous years’. 

The purpose of this booklet is not to serve as a textbook; rather, it is intended to be used as a reference for the types of problems which are likely to be asked, to give references for further reading, and to present some actual problems which were used in the past.

_____________________________________________________________________________

TABLE OF CONTENTS

  1. League Organization
  2. General Contest Procedures
  3. How ACSL Works
  4. Syllabus   
    1. Assembly Language Programming
    2. Bit-String Flicking                            
    3. Boolean Algebra                                
    4. Computer Number Systems              
    5. Data Structures                                  
    6. Digital Electronics                                        
    7. Graph Theory                                    
    8. LISP Programming                            
    9. Prefix/Infix/Postfix Notation
    10. Recursive Functions
    11. What Does This Program Do?

League Organization

Membership: Any secondary school that agrees to abide by these rules shall be admitted to the American Computer Science League (ACSL) upon application and receipt of the League dues.  There are four divisions: Senior, Junior, Intermediate, and Classroom.

Participation and Team Structure: The Senior Division is geared to senior high schools; the Junior Division to junior high schools; the Intermediate Division for advanced junior high schools and for senior high schools that are just starting computer courses; the Classroom Division is for all students but does not have a programming problem.

   The Senior Division is geared to those senior high schools that have well established programs in computers.  We strongly suggest that schools do not register for the Senior Division during their first year of ACSL participation.  In addition, any student taking an Advanced Placement course in Computer Science should be registered on a team in the Senior Division, except as noted above. 

   The Intermediate Division is geared to advanced junior high schools and for senior high schools that are just starting computer programs.  This division is for students taking a first course in computer science and for non-AP schools that are competing in the League for the first time.

   The Junior Division is geared to junior highs and middle schools that are just starting computer courses.  Students must be in the 9th grade or below to participate in this division.

   Schools are encouraged to enroll in more than one division, so that both advanced and novice students will find material at their respective levels.  If a school is enrolled in more than one division, its students may compete in any division – but not in more than one – for each contest.  Scores are not transferable between divisions.

   An unlimited number of students may compete at each school in each contest.  For each contest, a school’s score in each division is the sum of the scores of its three or five highest scoring students in that division.

Contest Dates: Except in unusual circumstances, all contests must be held during the scheduled week.  In the event of unscheduled school closings, special administrative functions, testing days, severely inclement weather, etc., permission is granted to conduct the contest late.  Do not call the League requesting an extension; administer the contest as soon as possible, and include a written explanation with the results.  If it is known ahead of time that a contest cannot be held during the contest week (e.g. the official date falls during a school vacation), administer it before the scheduled week. 

Awards: At the completion of the school year, awards will be presented to outstanding schools and individuals at regional levels in all divisions.  In addition, each team will receive an award to be given to a top student on the team, per the advisor’s discretion. 

Contest Problems: Each contest will be administered in two parts: Short Problems and a Programming Problem.  If for any reason a problem must be dropped (as decided by the Appeals Judge), no replacement will be made and no credit will be given for any answer to a problem thus discarded

Contest Materials Package: The Contest #1 materials should be received by each school by the end of November.  Each contest contains the following pages: Short Problems, Short Problems Solutions, Programming Problem, and Test Data and Solutions to the Programming Problem.  Faculty advisors are expected to make as many copies of the contest sheets as required, so that each participant has his/her own copy.  The advisor is responsible for the clarity of reproduced copies.

Study Aids: In addition to this booklet, previous years’ contest materials are available for a nominal fee (see flyer).

Communications: In addition to the Contest Materials Package, all schools will receive a Newsletter after each contest containing the contest results, general announcements, and items of interest.  Questions, comments, interesting solutions to any of the problems, etc. are welcomed by the League at all times, and often will be included in the Newsletters.  Student and advisor solutions to the Programming Problem must include the programmer’s name and school in a comment at the start of the program.  All programs submitted become property of ACSL.

Role of the Advisor: Since many of the topics are new to most students, the advisor will usually take an active role in presenting the material.  Advisors should not look at, or reproduce, the actual contest sheets until just before the contest.  This will eliminate the possibility of inadvertently “teaching the test.”  Advisors must not discuss any aspect of the programming problem with students.

General Contest Procedures

After each contest the advisor will complete a form for each team.  The TEAM SCORE is the sum of the top 3 or 5 students on the team.  The SCORE column is the total score for a student on that contest, an integer from 0 to 10, based upon the number of points from the short answer questions and the programming problem.  The CUM column is the total of the scores from all previous contests for that student.  Advisors must maintain the CUM data from contest to contest.  The GRADE column is the school year of the student, 9 - 12.

Appeals Procedure: Appeals will be awarded because of a disallowed exactly equivalent answer, an incorrect official answer, or a correct answer to a correct alternative interpretation of a problem.  Written appeals must be sent to the League along with the report form.  A complete listing and execution of the appellant’s program must accompany any appeals involving the Programming Problem.  Notification of the decision of the Appeals Judge will be made in the following Newsletter.  Decisions of the Appeals Judge will be final.  Advisors should retain all student answer sheets until the Newsletter is received.  If any appeals have been granted (as reported in a newsletter), advisors should submit the names of any of their students who should receive credit for the problem appealed on the score report form for the new contest.

Procedures: Short Problems

Format: This section may be held at any time during the contest week convenient to the school.  It consists of five problems from designated topics covering basic concepts in computer science.  Students are given 30 minutes in which to solve the problems.  The Classroom Division is given 50 minutes. 

Proctoring: This section must be actively proctored at all times.  Neither the proctor nor anyone else may interpret any problem to any student during the contest.  Each student must work independently.

Materials Allowed: The contestant may use only plain paper and pencil or pen.  No graph paper, compasses, straightedges, rulers, books, calculators, computers or other devices are allowed.

Implementation: Each student will be given a copy of the problem sheet.  Warnings that “ten minutes remain,” that “five minutes remain,” and that “one minute remains,” should be made to all contestants at the appropriate times.  At the conclusion of the Short Problems section, the proctor should collect all contest sheets.

Marking the Answers: At the conclusion of the Short Problems section, the proctor should, after collecting the contest papers, refer to the Solutions to the Short Problems and award one point for each problem correctly solved.  Answers submitted for each problem must appear in the appropriate space in the answer column.  Answers exactly equivalent to the official answer(s) should be given credit.  Incomplete answers should receive no credit.  There is no partial credit. 

Procedures: Programming Problems

Format: Each contestant will be given a copy of the Programming Problem, to be solved at his/her convenience, during the next 72 hours.  (Students may be given the problem the Friday before the contest week, in which case they must complete the program by Monday of the contest week.)  Each contestant must work independently.

Materials Allowed: All reference manuals, textbooks, and inanimate sources may be consulted, provided that no computer program or partial program listings are referenced by the contestant.  Computational devices, including calculators and home/personal computers may be used by a contestant.  Programs may be written in any computer language. 

Implementation: Prior to the completion of the 72 hours, the student will provide the advisor with access to the completed program.  The program may be done at home, and submitted on a diskette or may be done using the school’s computer. 

Marking the Programs: When all contestants have completed their programs, the proctor should refer to the Test Data and Solutions to Programming Problem and execute each student’s program on the test data exactly ONCE.  The only reason to restart a program is to correct bad data entry.  Each contestant will be awarded one point for each answer to the test data which matches the correct output.  For some problems, a tolerance will be allowed to account for different machine round off errors.  This will be noted on the problem sheet, if applicable.  Answers must appear in order unless clearly labeled.

   Students are advised to print out each answer as it is calculated, rather than printing all solutions at the conclusion of the run.  This strategy ensures that a student will not score a zero if his/her program aborts near the end but before any answers are printed.  Students must know their system and be aware of possible round-off errors, the maximum value which can be stored in an integer or floating point number, maximum number of strings which can exist, etc.

How ACSL works

Once you Register

1. ACSL will send the team advisor an ACSL Category Description Booklet, sent on a CD. The booklet contains the rules for each category and some sample problems and solutions. Team advisors will use the booklet and other sample problems to prepare students for the short answer test.

2. Prior to each contest, ACSL will send the team advisor an e-mail file that contains the short answer questions, the programming problem and solutions for both.

3. The team advisor will make copies of the contest questions. Note that for one registration fee every student at a school may take the tests. However, if a school registers for more than one division, a student may only take one of the tests.

4. The team advisor will administer the short answer test and score the results. One point is awarded for each answer that matches the ACSL solution. The time limit is 30 minutes for the Senior, Intermediate and Junior tests. The time limit is 50 minutes for the Classroom Division test. The only materials allowed for the short answer tests are plain paper and a writing implement. Calculators are not allowed.

5. The advisor will give each student a copy of the programming problem. Students have up to 72 hours to submit a programming solution to the advisor. Students must work alone in solving the programming problem. The advisor will run the ACSL test data on each student's programming solution. The program must accept all data in one run of the program. If the program stops for any reason, the program may not be restarted to enter more data. The advisor will award one point for each program output that matches ACSL's test output.

Scoring the results

1. A student’s score is the sum of his/her scores on the short answer test and the programming problem. A maximum score for any one student is 10 points (5 + 5).

2. The team score is the sum of the best 3 or 5 student scores for that contest.

3. The advisor will complete the ACSL Scoresheet and submit it by e-mail to ACSL. If a student score of 10 is reported, the advisor must also attach the programming file for that student.

After each contest

1. ACSL will send each advisor a newsletter containing the team standings and a listing of students with high scores.

2. ACSL will post results on its web site.

3. ACSL will select sample student programs from those submitted and post them on its web site. Programs using several different languages will be posted.

ALL-STAR Contest and Prizes

1. Based upon cumulative results after the four contests, ACSL will invite the top scoring teams in each division to complete at its All-Star Contest. At the All-Star Contest, prizes are awarded to top scoring teams and to top scoring students.

2. Based upon cumulative results after the four contests, ACSL will award plaques to top scoring students and teams based upon previously announced geographic regions. In the case of ties, duplicate awards will be presented.