Computer Science 302

ALGORITHMS

The Tactics of Programming

CLICK HERE TO INSTALL JAVA & ECLIPSE

Battle Binder

Create a binder that will hold both an electronic and hard copy of all code researched and generated in the course.

• Use dividers to separate it into sections reflecting different categories of code.

• Establish a running index at the front of the binder. Update it after each additional entry.

• Place a hard copy (ie, a paper copy) of resources (eg ASCII table) and source code containing algorithms in the binder.

• Place electronic versions of all source code to a rewritable CD, DVD, or USB flash drive and attach it to the binder. Organize the electronic code into a meaningful directory tree.

American Computer Science League

Complete all ACSL contests that occur while you are enrolled in Computer Science 302. Click on the link above and prepare with resources identified on that web page.

There are two components to each ACSL contest:

1. a 30 minute paper and pencil test of non-programming computer science topics.

2. a 72 hour challenging computer programming problem.

TopCoder brings members together once a week to compete online (Single Round Match) and twice a year both online and on location (Tournaments).

Competitions provide an understanding of a person's capabilities through a demonstration of skill. What was lacking in the world of programming competitions was a format that offered immediate and objective scoring. The solution was the creation of a "Single Round Match".

In addition to regular Single Round Matches, TopCoder holds two major multiple-round, elimination tournaments each year. These tournaments span many weeks and include significant prize purses along three independent tracks of competition: algorithm, component design, and component development.

Three TopCode problems must be completed each week, one of which must be a live competiton.

Qualifying competitions may be high school or single round matches.

Keep all hard copy materials related to assignments in a separate Algorithm Course Binder.

Choose the sequence in which you do the articles with your teacher. Your choice should be determined by selecting the next article that best addresses issues that you are least familiar with but which you believe best fills that lack of understanding.

Attempt to complete an average of one tutorial per hour. This will require that you read and study as vigorously as you can.

For each tutorial article that you read, you should:

1. Print a hard copy of the article. Leave sufficiently wide margins for your written comments. Store the article in a separate section of your course binder.

2. Read the article thoroughly but rapidly. Highlight important phrases or paragraphs that you will want to later review. Dialogue with the author by writing clarifying and arguing comments in the margins.

3. Implement some of the examples and source code used in the articles. You need not implement solutions to all of the problems referenced. Print and store copies of that source code with the article. [ Note: Code may be presented in any of various programming languages, typically C++. You are to implement that code in the Java programming language. ]

4. Make a mind map (aka a recall pattern) of each article, identifying each significant concept and its relationship to other concepts in the article. Store each memory mind map with the related article. Your memory map should be readable but you should not waste time by redoing it so that it is "pretty" or "publishable". It is a learning tool, not a Christmas present.

   Create the shape of each mind map that best represents patterns that you yourself find in the related tutorial. Typical mind maps are:

Spider
Pictorial
Random
Radial
Slash
Linear
Fishbone

COMCON contests [html] [pdf] are computing contests held between teams of 1-4 members. Computer Science 302 students are encouraged to participate in them.

Contests are held about half a dozen times per school year, usually about once a month. The contests are free; there is no fee of any kind. Teams may participate over the internet: there is NO TRAVEL required.

The contest consists of four programs. These are solved by a team (up to four people) using one computer within a two hour limit. Schools can compete alone or against other schools; to compete against other schools successful program solutions must be emailed.

Register to receive your personalized user name and password for the USACO Training Program and USACO Contests. Your name and password will also be immediately sent via return e-mail. If you don't receive the mail, you can double-check your e-mail address after you login (or you can register again).

USACO Training is a set of computer programming problems that become progressively more difficult that require the construction of different types of algorithms as the student progresses. The training was established as practice for competitors of USACO type computer programming contests.

In the spring of 2007 a small group of talented SWC students used the USACO Training as their primary material in a course geared to the study of algorithms. The challenge of the problems was great but, amazingly, the motivation and response of the students was tremendously high. Much motivation came from knowing that implementing the algorithms required to solve the USACO Training problems led to superior performance in problem solving contests. In a word, it made the entire process of studying algorithms fun!

It happens that, in order to successfully and satisfactorily orchestrate computer programming constests, sets of efficacious conventions and processes evolved with the delightful side effect of making it possible to rigorously study algorithms while having a whole lot of fun doing so. In order to negotiate programming contests, competitors learn and value both effectiveness and efficiency. Regardless of the profession that competing students eventually practice later in life, the values and habits accrued from their experience in studying algorithms in the context of contest preparation and involvement will leave those individuals demanding that solutions of all sorts be both effective and efficient in their execution. Fortunate are those future employers who will discover such high performing emplyees. Fortunate too are those imployees, for they will have knowledge and standards that assure success.

test.java is a simple example of code that is typical for most solutions. Note the following parts of code.

• An ID header is bracketed by multiline delimiters /* ... */.

  • ID: your_id_here refers to your USACO username.
  • LANG: JAVA refers to the programming language used.
  • TASK: test refers to the name of the program
  
  

• Necessary packages must be imported.

  • import java.io.*; imports the package that contains the I/O classes RandomAccessFile, PrintWriter, BufferedWriter, and FileWriter.

  • import java.util.*; imports the package containing StringTokenizer which allows you to separate the "tokens" (substrings separated by white space) of a string read from a line.
  
  

• Data is always read from a text file in USACO contests and their training materials.

  • String s = in.readLine();
  
  

• Data is always written to a text files in USACO contests and their training materials.

  • out.println(i1+i2);
  
  

• Always close the output file to ensure that all data has been flushed to the output file.

  • out.close();
  
  

• Always exit the program.

  • System.exit(0);

newPrg.java is a comprehensive example of code that may be used to solve a wide variety of problems. While you may start with this example, you should extend it to include other "chunnks" of code that may be easily modified for application to future solutions.

Your personal template will contain code that reflects specific programming structures and techniques that you personally used to solve other programs. In this way, you will be intimately familiar with the code in your personal template.