American Computer Science League

ResourceImplementation
Contest

#1

December
13 - 17
2007

How ACSL Works

Topics To Master For Contest #1

  1. ACSL Handout: Computer Number Systems

    Computer Number Systems Handout To Prepare For ACSL Contest #1

    Click here for links to further resources on number systems.

    What you must know about number systems for the 2007/08 ACSL Contest #1:

    1. Count in the binary, octal and hexadecimal number systems.

    2. Convert numbers from one base (decimal, binary, octal, hexadecimal) to another.

      • Convert a decimal number to a binary number.
      • Convert a binary number to a decimal number.
      • Convert a decimal number to an octal number.
      • Convert an octal number to a decimal number.
      • Convert a decimal number to an octal number.
      • Convert an octal number to a binary number.
      • Convert a binary number to a hexadecimal number.
      • Convert a hexadecimal number to a binary number.
      • Convert a binary number to a binary number.
      • Convert a decimal number to a binary number.

    3. Add, subtract, multiply and divide in the number systems.

      Convert everything to decimal → do the math → convert to target base.

    4. Solve for the unknown value X in an equation with values of the same base.

      Example:      X16 = FEED16 - 6ACE16
    5. Solve for the unknown value X in an equation with values of different bases.

      Example:      X378 = 1XF16

  2. ACSL Handout: Recursive Functions

    An extensive treatment of Recursion Using Java offers a wealth of instruction on how recursion is applied in computer programming, but note that the ACSL contest requires the mathematical treatment of recursion.

    Learn about applying recursion in the Java programming language by studying the Recursion Tutorial [csg] [web] retrieved from the web site of North Carolina teacher Ruth Hartsook but note that the ACSL contest requires the mathematical treatment of recursion.

    Three Rules For Recursion:

    1. Find out how to take just one step.

    2. Break each journey down into one step plus a smaller journey.

    3. Know when to stop.

    Source: How TO teach and NOT TO teach Recursion (opinions from the experts?), page 14 [pdf] by Fran Trees


  3. ACSL Handout: LISP Programming

  4. Take Home Computer Program Problem Syntax - using IF ... THEN

    Sample Java Contest Program CalcWages.java
    Read Input from File & Write Output to Screen wpd

    CalcWages.java with Documentation
    CalcWages.java with Loop & No Docs
    Data File:    CalcWages.in

    See Donaldson's published solutions for both [ ] [ wpd ] as well as source code solutions of Intermediate Triangles.java and Senior Triangles.java

Contest #1 Schedule
30 Minute TestFriday14 Dec 2007
Take Home ProblemFriday14 Dec 2007
Return ProblemMonday17 Dec 2007

ResourceImplementation
Contest

#2

February
8
2008

Topics To Master For Contest #2

  1. ACSL Handout: Boolean Algebra

    Boolean
    Algebra

    In past years students successfully practiced Boolean Logic with Electronic Workbench 5.12. It is more powerful than Eck's xLogicCircuits Java applet, but has a steeper learning curve. Eck's xLogicCircuits applet is sufficient to practice all of the electronic aspects of Boolean Logic that we require. Less powerful but interesting programmes that allow us to practice Boolean logic are:

    1. xLogicCircuits applet and labs & other applets
    2. DLSim 2.2
    3. Leggo My Logg-O
    4. Logic Gates Circuit Simulation Program
    5. Digital Workshop
    6. Multimedia Logic
    7. Xilinx ISE WebPACKTM
    8. The Iowa Logic Specification Language

    Check out former student web pages on this topic:

    1. Boolean Logic by Lisa Chen (2002).
    2. Boolean Logic by Brian Lau (2003).
    3. Karnaugh Maps by Jacky Yeung (2003).

    Boolean Algebra

    The ACSL Handout: Boolean Algebra [doc] offers a brief introduction.

    Read How Boolean Logic Works on the web site How Stuff Works.

    Digital Logic by Ken Bigelow offers a structured and cohesive introduction to Boolean Logic.

    Richard Jones' treatment of IB - Boolean Logic as found on his web site, IB Computing Home clarifies IBO's expectations.

    Check out xLogicCircuits Lab 1: Logic Circuits from David Eck's book, The Most Complex Machine: A Survey of Computers and Computing.

    Do all 10 exercises in Eck's LogicCircuits Lab 1: Logic Circuits [csg] [web].

    You cannot normally save from an applet. Do a screen dump to a wordprocessor or paint programme to capture the image: Focus (mouse click) on the applet --> [Alt-PrtScn] --> Go to wordprocessor or paint program --> Focus --> [Ctrl-v].

    Note: It is possible to import the files associated with the applet into Eclipse, launch the applet from within Eclipse, and then save the diagrams from the applet. To do this:

    1. Download the applet's source code files from Eck's Source Code Page:

      • the folder:   xLogicCircuits/
      • the file:   xLogicCircuitsApplet.java
      • the file:   xLogicCircuitsFrame.java
      • the file:   xLogicCircuitsLauncher.java

      OR

      import the Eclipse project from this Circuit directory.

    2. To import the project into Eclipse, do this:

      Launch Eclipse → File → Import... → Existing Projects in Workspace → Next> → Select root directory: copy path of the Circuit directory → Browse → Check the box of the Project "Circuit" → Finish → Expand (click "+" sign) the newly imported project "Circuit" → Expand the directory "src" → Expand the package "tmcm" → Select (right mouse click) "xLogicCircuitsLauncher.java" → Run as → Java applet.

    3. Circuit Diagrams may now be named, saved and loaded from within Eclipse.

    Check out xLogicCircuits Lab 2: Memory Circuits from David Eck's book, The Most Complex Machine: A Survey of Computers and Computing.

    Do all 9 exercises in Eck's xLogicCircuits Lab 2: Memory Circuits [csg] [web].

    You cannot normally save from an applet. Do a screen dump to a wordprocessor or paint programme to capture the image: Focus (mouse click) on the applet --> [Alt-PrtScn] --> Go to wordprocessor or paint program --> Focus --> [Ctrl-v].




  2. ACSL Handout: Bit-String Flicking

    Bit and Shift
    Operations

    OperatorLogicalBitwise
    NOT!~
    AND&
    &&
    &
    OR|
    |  |
    |
    XOR^ ^
    shift leftNot Applicable<<
    arithmetic shift rightNot Applicable>>
    bitwise shift rightNot Applicable>>>

    Check out this TopCoder article that applies bit-wise operators to challenging computing programming contest problems: A bit of fun: fun with bits

    The ACSL Handout Bit-String Flicking [doc] uses the slang but colourful term flicking to describe these operations which change a one to zero and vice versa.

    Review interesting presentations of Boolean Expressions and Short-circuit Operators and Truth Tables and De Morgan's Rules by Bradley Kjell.

    Bit and Shift operations are summarized in Horstmann's Big Java 2nd Ed, Appendix M, pages 1158-1160.

    This topic is better described as Binary Numbers and Logical Operators. It is an extension of the larger topic about Java Operators.

    Note that a pair of symbols are used for the logical operations, "logical AND" [&&] and "inclusive OR" [ | | ] whereas a single symbol is used for bitwise operations, "bitwise AND" [&], "inclusive OR" [ | ], and "exclusive OR" [^].

    The usefulness and application of these operations are seen in context in Kjell's course for assembly language programming, Programmed Introduction to MIPS Assembly Language. See in particular Kjell's chapters:

    1. Immediate Operands and Bitwise Logic
    2. Shift Instructions and Logic Instructions

    Bit and shift operations compare equivalent binary patterns of decimal or other integers. See example below.

    public class BooleanOps
    {
       public static void main(String[] args)
       {
          System.out.println(3 & 22);                 // 2
          System.out.println(13 ^ 6);                 //11
          System.out.println(0 & (3-3));              // 0
          System.out.println(45 | 16);                //61
          System.out.println((2 & 5) | ((7^3) & 5 )); // 4
       }
    }
    XOR is supported by Java, but it is not possible to short-circuit an XOR expression because overall evaluation of the XOR expression always depends upon both operands. Java uses the caret (aka "circumflex") [^] as its XOR operator.

    public class DemoXOR
    {
        public static void main( String[] args )
        {
            int x = 5, z=10 ;
            if ( (x<10) ^ (z>5) )
                System.out.println("True Block") ;
            else System.out.println("False Block");
        }
    }
    
    Read about getting binary, using hex and octal literals, using bitwise operators, and using shift operators in a pdf bonus chapter, Twiddling Your Bits [csg] [web], from Java All-in-One Desk Reference For Dummies (2nd Ed) ISBN: 0470124512 by Doug Lowe and Barry Burd (Wiley Publishing, Inc, 2007).

  3. ACSL Handout: Computer Number Systems

  4. Computer Java Program Example:   Rolodex.java      Rolodex.in

    An interesting reference for this level of programming is Book IV: Strings, Arrays, and Collections, essentially a "unit" found in the hardcover book (Yes, Virginia, they do still exist.) Java All-in-One Desk Reference For Dummies (2nd Ed) ISBN: 0470124512 by Doug Lowe and Barry Burd (Wiley Publishing, Inc, 2007). Click here for source code of the examples.

    Strategies and Tactics For Reading and Processing Data From A Text File

    1. Before doing anything else, Get ready to code by first launching Java's current API.

      Ideally, you should download and install Java's current API to your work station rather than relying upon Internet access.

      Java's API is the official "Java Dictionary". It is the single most important reference that there is for working with the Java programming language. Consult it often!!

      You should immediately familiarize yourself with methods of the following classes.

      1. java.io.FileReader
      2. java.io.BufferedReader
      3. java.util.StringTokenizer
      4. java.lang.String
      5. java.lang.StringBuffer
      6. java.lang.StringBuilder
      7. java.util.ArrayList<Element>
      8. java.lang.Math
    2. Use the most current stable version of Java and your IDE. Java is a moving target. There were huge changes from Java 1.4 to Java 1.5 (aka Java 5.0) in generics (where structures such as an ArrayList can handle "generic" objects of many different types), autoboxing and unboxing (where Java automatically converts between primitive and wrapper types), an enhanced for loop (which automatically and safely iterates over collections and arrays), et cetera.

      Failure to use current tools explains why code written that uses those tools does not work!

      Duh!! Personally, I could throw quite the party if I had a nickel for every "error message" thrown after I tried to run code using current features with legacy versions of a language and/or IDE.

      In Eclipse, set the IDE to use a current Java JDK (Java Development Kit) version with:   Window → Preferences... → Expand "Java" → Compiler → Use the drop down menu to set the "Compiler compliance level". At the time of writing this point (February 2008) the most recent version of Java is 6.0. The most recent version of Eclipse is 3.3.1.

    3. Master the use of the Eclipse Debugger.

      The Debugger is used for development and not just error identification!!

      • Create a breakpoint where you want to start inspecting the state of your program while it executes, line by line.

        To set a breakpoint:   Double click the gutter to the immediate left of the targeted line of source code.   The Breakpoint tells the debugger to pause at this point.   To eliminate a breakpoint:   Double click the breakpoint.

      • To initially START a debug session from within the Java Perspective:   Run → Debug As → Java Application → Editors → There appears the dialogue box "Confirm Perspective Switch" → Check "Remember my decision" → Yes.   Eclipse switches to the Debug perspective.

        Thereafter simply press <F11>.

      • In any "perspective", keep open only those frames that contain information that you will use.

        When initially using the Debug Perspective, open the Edit, Breakpoints, Variables, Console and Tasks frames. Close all other frames. Rearrange and resize the remaining open frames for optimal viewing.

        Place Edit frames vertically on the left separated by tabs. Place the Variables and Breakpoints frames vertically on the right separated by tabs. Place the Console and Tasks frames horizontally on the bottom separated by tabs.

      • To STOP a debug session:   Press the stop button.

      • To start a NEW debug session:   Press the Debug Button.

      • Use control keys to walk through the code line-by-line while inspecting values of variables.

        All Eclipse action keys are documented in the Eclipse Run Menu Actions documentation. Begin by using the following debug actions when generating and debugging code.

        FunctionButtonHot KeysPurpose
        Debug   Begin execution until reaching a breakpoint or end of program.
        Resume <F8> Continue execution until another breakpoint or end of program.
        Terminate   Stop the debug session.
        Step Into <F5> Move into the method or constructor being called and pauses.
        Step Over <F6> Execute current line of code and stop at next line.
        Step Return <F7> Finish current method then return to the calling method.
        Debug Last <F11> Debug last launch or debug current selection.
        Run Clean <Ctrl><F11> Run last launch or run current selection without debugging.

    4. Use knowledge of the common behaviours (methods) that many classes share.

      1. All Java classes inherit all methods of the Object class, which means that all Java objects have the following (and other) methods in addition to their own inherited methods.   A method inherited is a method realized.

        • equals(Object obj) indicates "true or false" that the content of some other object is "equal to" this one.

          Mathematical equality "==" is not used because it compares values of addresses. Two otherwise identical objects in terms of their values may be located in different parts of memory and therefore have different addresses.

          The programmer may override default criteria for comparing two objects.

        • toString() returns a string representation of the object.

          The programmer may override the default way of representing an object as a string.

        • hashCode() usually (but not always) produces distinct integer results for two objects that are unequal according to the equals(Object obj) equals(java.lang.Object) method.

      2. Many classes have "getter" and "setter" methods.

        • Getter methods retrieve specific values of an object.

        • Setter methods assign specific values to an object.

      3. The eight primitive types each have a corresponding "wrapper class" with methods that act upon or express the value of the primitive. Example methods are:

        • returns a new primitive initialised to the value represented by a specified String [ eg: double price = Double.parseDouble("123.45") ].

        • returns a string representation of the primitive [ eg. String myAge = num.toString( ) ].

        • tests whether a character is a letter or digit or lowercase, etc. [ eg. Character.isLetter('5') == false ].

        The eight primitives and their corresponding wrapper classes are:

        PrimitiveWrapper
        byte Byte
        short Short
        int Integer
        long Long
        PrimitiveWrapper
        float Float
        double Double
        char Character
        boolean Boolean
    5. Display line numbers:   Window → Preferences... → General → Editors → Test Editors → Check the box "Show line numbers" → OK.

    6. Import a XML file that sets code style format to your preferred style:   Select (highlight) the project → Window → Preferences... → Expand (click "+" sign) "Java" → Expand "Code Style" → Formatter → Import... → Locate XML file → Open → OK.

      The file CPSC211CodeFormat.xml forces conformity to a style of source code advocated by Cay Horstmann in his textbook Big Java.

      Force your preferred format often with:   Right Mouse Click → Source → Format.

    7. Use "baby steps" to break up big problems into small problems. It is emphatically easier to solve small problems than large problems. Remember the "KISS Principle".

      KISS = Keep It Simple Stupid.

      When a task becomes complex, solve it in it's own method.

    8. Close all open editor windows to avoid accidentally editing code of an incorrect file:   File → Close all.

    9. Also close all other (non-editor) Eclipse windows that you don't intend to use with the current project, thus reducing distractions and maximizing the real estate used by windows that you do use.

      You can always reopen any window in a given perspective after:   Window → Show View → whatever.

    An Example of Reading and Processing Data From A Text File

    1. Create the data base in a text file:   Rolodex.in :   Select the project → File → New → File → "Rolodex.in" → Finish.

      Gerry Donaldson 123_Anywhere_Street Calgary    AB 4032899241  456.26
      John Blow       987_Crescent        Cranbrook  BC 6045559875 98273.4
      Jane Doe        89_DeerHunt_Way     Huntsville SK 3063968148   29.44

      Your program will bomb if it does not find a data file to read. If you get error messages like the following, ensure that your data file is located in the project directory outside of any package directory!! Drag and drop the data file into the selected (blue) project directory if need be.

      Exception in thread "main" java.io.FileNotFoundException: Rolodex.in
      (The system cannot find the file specified)
      	at java.io.FileInputStream.open(Native Method)
      	at java.io.FileInputStream.(Unknown Source)
      	at java.io.FileInputStream.(Unknown Source)
      	at java.io.FileReader.(Unknown Source)
      	at Rolodex.main(Rolodex.java:11)
    2. Create a class:   Rolodex.java

    3. Create a java.io.FileReader object which reads text data as a stream of characters.

      FileReader charStream = new FileReader ( "Rolodex.in") ;

      Create a java.io.BufferedReader object to read the character-input stream (spooled into a buffer of memory by the FileReader object), buffering characters so as to provide for the efficient reading of characters, arrays, and lines.

      BufferedReader in = new BufferedReader( charStream ) ;

      Instead of giving the FileReader object a separate identifier (Example: charStream) as above, it is customary to immediately pass the FileReader object (charStream) anonymously as a parameter to the constructor of the BufferedReader object.

      BufferedReader in = new BufferedReader(   new FileReader ( "Rolodex.in")   ) ;

    4. The BufferedReader class method readLine( ) captures strings of characters, line by line, passing each string onto a String object, "line".

      String line = in.readLine() ;
    5. Use a while loop to continuously read BufferedReader objects of strings to the end of the file. Determine that the end of file has been reached when the address of a string "line" == null. Two critical decisions must be followed.

      1. Prime the while loop* by reading the first string of data BEFORE reaching the while loop. The test to enter the while loop is whether the String object "line" continues to contain data. After the last data object has been read, line == null, thus it is false that " line != null ", thus execution proceeds to the first instruction coming AFTER the end of the body of the while loop.

        * "Prime the while loop" is a metaphor that refers to the need to prime (place water in) an outdoor water pump to create a partial vacuum before water will start flowing. Once there is some water in the water pump, the flow ("processing") of the water proceeds until there is no more water in the pump. Similarly, the while loop continues to process data until there is no more data read from the buffered stream of characters. .
      2. Continuously read the next String data object just before the END of the while loop so that it may be immediately tested for "line != null" to determine whether there continues to be data that can be processed by re-entering the while loop.

        String line = in.readLine() ;
        while ( line != null )
        {
           // TODO: Process line
        
           line = in.readLine() ;
        }
    6. Pass each string of data into a method for the sole purpose of storing all the data as records in an java.util.ArrayList<Element> object.

      placeRecordInArrayList ( line ) ;
    7. Create an inner class that will act as a "blueprint" for records of fields of each string of data.

      Declare the record class to be static so that it may be used without having to create native record objects.

      static private class Record
      {
         public String field1 ;
         public long   filed2 ;
         public double field3 ;
      }
    8. Create a java.util.ArrayList<Element> object, each cell of which will contain a separate record of the data read from the text file data base.

      The ArrayList<Element> class implements operations for processing the ArrayList<Element> list of data objects.

      Note that you must use a Java compiler of version 1.5 or later to support an ArrayList that may contain "generic" types of data objects, such as the records of data. Ensure a sufficiently recent compiler "level" of Java:   Window → Preferences... → Expand "Java" → Compiler → Set the "Compiler compliance level" to 1.5 (5.0) or higher. → OK.

      static private ArrayList<Record> list = new ArrayList<Record>() ;
    9. Create a java.util.StringTokenizer object which breaks the string object into "tokens" of substrings of the string that was used to create the StringTokenizer object ... the string containing a record of data. The white space may be a single character or sequence of characters.

      Use a while loop to determine that there continues to be yet a "next" token. So long as there continues to be yet another token, enter the loop and assign each token to a field of the string "record". (Each string object is deemed to contain a record of fields of data.) Build a temporary record within each loop by assigning each token to a separate field of the data record.

      After assigning a value to each field of the temporary record, add the temporary record to the ArrayList<Element> object.

      StringTokenizer st = new StringTokenizer (record) ;
      
      Record temp = new Record() ;
      
      while ( st.hasMoreTokens() )
      {
         temp.var1 = st.nextToken() ;
         temp.var2 = Long.parseLong(  st.nextToken()  )
         temp.var3 = Double.parseDouble(  st.nextToken() ) ;
         list.add(temp);
      }
    10. Process data using loops, ArrayList<Element> methods, and methods of classes that manipulate strings and characters.

      Kjell's Tutorial, ArrayLists and Iterators, in an excellent introduction to Java's ArrayList class.

Contest #2 Actual Problems & Donaldson Solutions Posted 17 February 2008
Level 30 Minute
Tests
30 Minute
Solutions
72 Hour
Problem
Donaldson's
Solutions
Problem
Data
Test
Data
Eclipse
Project
Inter Test.doc Soln.doc Prob.doc Compress.java
Anna.java
Compress.in Test.in Project
Senior Test.doc Soln.doc Prob.doc Compress.java
Devon.java
Compress.in Test.in Project

Contest #2 Schedule
30 Minute TestFriday8 Feb 2008
Take Home ProblemFriday8 Feb 2008
Return ProblemMonday11 Feb 2008

ResourceImplementation


ResourceImplementation
ACSL


13 December 2007
8 February 2008
7 March 2008
11 April 2008


ACSL
Invitational
Team
All-Star
Contest
Saturday
8 May 2008

The American Computer Science League (ACSL) is a non-profit organization devoted to computer science education at the secondary school level. ACSL is on the approved activities list of the NASSP. The purpose of this flier is to tell you about the organization, and to invite your school to participate in it.

ACSL administers computer science contests for junior and senior high school students, publishes a newsletter containing the results of each contest and items of interest, and awards prizes (computer equipment, books, and trophies) to outstanding students and schools at local and regional levels. This past year, our 29th year of operation, about 225 schools in the United States and Canada participated. In addition, ten teams from Europe and Asia participated in ACSL last year.

ACSL will provide a unique and exciting educational opportunity for your school’s computer enthusiasts. Contest problems motivate students to study computer topics not covered in their school’s curriculum and to pursue classroom topics in depth. At many schools, the League is the focal point both for extracurricular clubs and for entire courses.

The competition consists of 4 contests. Each is held at the participating school thereby eliminating the need for travel, and an unlimited number of students from all grade levels may compete at each school. A school’s score is the sum of the scores of its three or five highest-scoring students. In each contest, students are given short theoretical and applied questions, and then a programming problem to solve within the following three days. Programming is done on any school or home computer using any language allowed by the advisor. A faculty advisor administers the contest at each school and results are returned to ACSL for tabulation. At the end of the year, an Invitational Team All-Star Contest, based upon cumulative scores, is held at a common site.

ACSL DIVISIONS

The American Computer Science League consists of four divisions to appeal to the varying computing abilities and interests of students.

One registration fee allows all students at a school to compete. The advisor reports the sum of the 3 or 5 best scores as the team score. We encourage schools to join more than one division so that the material does not intimidate novice students, nor are advanced students bored. All divisions cover similar material, but in varying levels of detail and difficulty.

The Senior and Intermediate divisions allow 5-person and 3-person teams. Teams compete for prizes and invitations to the All-Star Contest against same-sized teams; students will compete for individual awards independent of the team size. A school may not register both a 5-person team and a 3-person team in the same division.

  • The Senior Division is geared to those high school students with experience programming computers, especially those taking a Computer Science AP course. We suggest that schools do not register for the Senior Division during their first year of ACSL participation.

  • The Intermediate Division is geared to senior high school students with little or no computer programming experience, and to advanced junior high students.

  • The Junior Division is geared to junior high and middle school students with no previous experience programming computers. No student beyond grade 9 may compete in the Junior Division.

  • The Classroom Division is open to students from all grades. It consists of a selection of the non-programming problems from the other three divisions. As its name implies, this division is particularly well suited for use in the classroom


URL:   http://www.comscigate.com/    Last Revised:  November 30, 2007