Computer Science 302

ALGORITHMS

The Tactics of Programming


This is a novel approach to this course. Directions for sequence and timing of instructions and assignments are experimental and will be modified after discussion between Mr. Donaldson and students taking this course. [ 27 January 2008 ]


What Are Algorithms?


CLICK HERE TO INSTALL JAVA & ECLIPSE

Today's files are BIG. Consider a flash drive.
TaskAssignment

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.

TaskAssignment
ACSL

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

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.

Rated TopCoder members are eligible to participate in TopCoder Component Development. Members submit design and development solutions for these challenging and potentially lucrative projects.

TaskAssignment

Computing
Contests

TopCoder's Computing Contests

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.

TaskAssignment

Algorithm
Tutorials

TopCoder's Algorithm Tutorials

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
Assigned Articles
The Importance of Algorithms
How To Dissect a TopCoder Problem Statement
How To Find a Solution
Planning an Approach to a TopCoder Problem: Section 1
Planning an Approach to a TopCoder Problem: Section 2
Mathematics for TopCoders
Geometry Concepts #1: Basic Concepts
Geometry Concepts #2: Line Intersection and its Applications
Geometry Concepts #3: Using Geometry in TopCoder Problems
Introduction to graphs and their data structures: Section 1:
Recognizing and Representing a Graph
Introduction to graphs and their data structures: Section 2
Searching a Graph
Introduction to graphs and their data structures: Section 3
Finding the Best Path through a Graph
Greedy is Good
Dynamic Programming: From novice to advanced
Understanding Probabilities
Data Structures
Features Introduced in Java 1.5
Sorting
Binary Search
A bit of fun: fun with bits
Prime Numbers, Factorization and Euler Function
An Introduction to Recursion, Part 1
An Introduction to Recursion, Part 2
TaskAssignment
COMCON
[html] [pdf]

17 October 2007
14 November 2007
12 December 2007
13 February 2008
No January contest
March, April TBA

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.

TaskAssignment
USACO



Monthly
Algorithmic
Contests

Computing Competitions Help Us Learn To Fall!

Each month students may tackle a set of computing problems requiring the design and implementation of algorithms in a computing contest. The contest will run over the weekend from Friday afternoon until Tuesday morning. The computing problems will be drawn from monthly USACO [USA Computing Olympiad] contests and the single CCC [Canadian Computing Competition] which occurs near the end of February.


USACO TRAINING PROGRAM
TaskAssignment
Register
Click here to register for USACO TRAINING.

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).

TaskAssignment
Resources
Algorithms {Fundamental Techniques} by Macneil Shonle and others pdf Version
Shinji's Overview A former student summarizes strategies and how to do well in contests based on her experiences.
USACO I/O Simple example of how USACO wants you to do input and output.
Analysis of Algorithms 1996 Electronic SUNY Stony Brook Course by Steven Skiena
Skiena's CD on Internet 1997 Electronic Book: The Algorithm Design Manual by Steven Skiena
Design & Analysis of Algorithms Web Site of Lecture Notes by Rashid Bin Muhammad.
TaskAssignment
Hardcover Books
TaskAssignment
Section 0.0
Advantages To Using USACO Training To Study Algorithms.

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.

TaskAssignment
Section 0.1 TEXT USACO Template

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);
TaskAssignment
Section 0.2 TEXT Personal Template

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.

TaskAssignment
Section 1.0 TEXT Introduction The USACO Training and its web site.
Section 1.1 TEXT Submitting Solutions Include an ID header. Read input from file. Write output to file.
PROB Your Ride Is Here Do two names match according to a specific scheme?
TEXT Contest Problem Types Contest problems are grouped into 16 different types!
TEXT Ad Hoc Problems Nonstandard algorithms not falling into a standard category and without well-studied solutions.
PROB Greedy Gift Givers Determine how much more/less money friends give each other.
PROB Friday the Thirteenth Calculate the frequency that each week day falls on the 13th.
PROB Broken Necklace Determine where a necklace is broken so the most beads are collected.
Section 1.2 TEXT Complete Search Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer.
PROB Milking Cows Calculate intervals during which cows are milked and not milked.
PROB Transformations Recognize transformations of patterns of black and white square tiles.
PROB Name That Number Print all valid names of letters associated with a specific telephone number.
PROB Palindromic Squares 
PROB Dual Palindromes 
Section 1.3TEXT Greedy Algorithm 
PROB Mixing Milk 
PROB Barn Repair 
TEXT Winning Solutions 
PROB Calf Flac 
PROB Prime Cryptarithm 
Section 1.4TEXT More Search Techniques 
PROB Packing Rectangles 
PROB The Clocks 
PROB Arithmetic Progressions 
PROB Mother's Milk 
Section 1.5TEXT Introduction to Binary Numbers 
PROB Number Triangles 
PROB Prime Palindromes 
PROB SuperPrime Rib 
PROB Checker Challenge 

On the Internet Since March 9, 1996    URL:   http://www.comscigate.com    Last Revised:   September 14, 2007.