Wikijunior:Programming for Kids/Writing Your Algorithms

Wikijunior:Programming for Kids
Top-Down or Bottom-Up?	Writing Your Algorithms	Variables and Data Types

You probably have an idea of what an algorithm is. It's something used by a computer to do something. What exactly is that something?

What is an algorithm?

An algorithm is a series of step-by-step procedures for performing calculations or processing data. Algorithms are independent of programming languages. That means an algorithm can be converted into any programming language. When we write algorithms, we need not consider elements unique to the language of our choice. Here's an example of an algorithm describing how to play a game of scissors-paper-rock whereby you need to win two rounds out of three:

Step 1: Both people pick one from: scissors, paper, rock
Step 2: If the two choices are the same, redo step 1
Step 3: If the two choices are different:
- Step 3.1: If the first person picked scissors and the second picked paper, then the first person gets a point
- Step 3.2: If the first person picked scissors and the second picked rock, then the second person gets a point
- Step 3.3: If the first person picked paper and the second picked scissors, then the second person gets a point
- Step 3.4: If the first person picked paper and the second picked rock, then the first person gets a point
- Step 3.5: If the first person picked stone and the second picked scissors, then the first person gets a point
- Step 3.6: If the first person picked stone and the second picked paper, then the second person gets a point
- Step 3.7: Repeat steps 1 to 3 until one person has two points

The above algorithm is not represented in a standard way, however. There are two main ways to represent an algorithm: flowcharts and pseudocode.

Flowcharts

Flowcharts represent algorithms in a graphical manner. There is a standard set of rules we must follow when we draw flowcharts. Don't feel intimidated by the descriptions: we'll cover them one by one in the next few chapters.

Symbol	Name	Description
	Beginning of the algorithm	The 'start' symbol looks like the stadium we met a few chapters back. It denotes the start of the algorithm. Everything in the algorithm comes ultimately from this symbol.
	Input statement/ Output statement	Input statements either read from another file or receive input from the user. Ouput statements output information onto the screen. Input statements are not always located at the beginning of an algorithm, and output statements at not always at the end.
	Assignment statement	Assignment statements assign a value to a variable.
	Procedure call	This symbol 'calls' a pre-defined procedure or function.
	Condition/ Decision	A condition represents a 'fork' in the algorithm, usually 'yes' and 'no'. After reaching a condition component, the incoming path splits into two separate paths.
	End of the algorithm	The 'end' symbol is used like the 'start' symbol. All 'branches' of the code must ultimately lead to the end.

Of course, we can't make a flowchart with only a bunch of boxes. We also need to represent the flow between them. We use arrows and connectors for this purpose.

Symbol	Name	Description
	Arrow	Arrows are drawn from one box to another to represent the flow between boxes. They are 'broken up' by the condition boxes.
	Connector	If arrows have split paths, they must first converge before performing any common actions. A connector is used to achieve this. The connector is often omitted, leaving only a point of intersection.

Here are some examples:


Connectors help converge forked arrows together.	They are sometimes omitted, but the convergence stays.	We cannot point both paths to the same box without converging them first! This is incorrect!

Pseudocode

Pseudocode is an informal way to represent an algorithm in a narrative manner. There is no standard for pseudocode, but there are established conventions we can follow. This includes keywords, which are usually capitalised, and formatting features like indentation. Here is an example of pseudocode:

10 READ i, j
20 IF i < j THEN
30    PRINT 'i is the smaller one.'
40 ELSE
50    PRINT 'j is the smaller one.'
60 ENDIF

Like flowcharts and algorithms in general, pseudocode is independent of programming languages. Nobody will actually put it through a compiler. Therefore, we can use English statements if we want to:

PROGRAM find_square_area
10 READ width
20 IF width is a positive integer THEN
30    PRINT width * width
40 ELSE
50    PRINT 'Invalid input!'
60 ENDIF

The above code is equivalent to this:

PROGRAM find_square_area
10 READ width
20 IF (width > 0) AND (width MOD 2 = 0) THEN
30    PRINT width * width
40 ELSE
50    PRINT 'Invalid input!'
60 ENDIF

Don't be afraid if you don't understand these algorithms; again, we will learn them later.

Line numbers are often included in pseudocode for easy reference. They increase by 10 each time.

Programming paradigms and programming languages

A programming paradigm is a pattern that a programming language follows. There are many different programming paradigms out there. One is called declarative programming. In declarative programming, commands are written and executed one by one without any 'forks' in the flowchart. The commands are presented in a sequential manner. Query languages and spreadsheets are good examples. Here is an example of SQL, a well-known query language:

CREATE DATABASE Books;
CREATE TABLE FavouriteBooks(
   BookID CHAR(6) NOT NULL UNIQUE,
   BookTitle VARCHAR(100) NOT NULL,
   BookAuthorFirst VARCHAR(30),
   BookAuthorLast VARCHAR(30),
   BookPublisher VARCHAR(30),
   PRIMARY KEY(BookID)
)
INSERT INTO FavouriteBooks(BookID, BookTitle, BookAuthorFirst, BookAuthorLast) VALUES('000006', 'Pride and Prejudice', 'Jane', 'Austen');
INSERT INTO FavouriteBooks(BookID, BookTitle, BookAuthorFirst, BookAuthorLast) VALUES('000006', 'A Christmas Carol', 'Charles', 'Dickens');
INSERT INTO FavouriteBooks(BookID, BookTitle, BookAuthorFirst, BookAuthorLast) VALUES('000006', 'Animal Farm', 'George', 'Orwell');
SELECT * FROM FavouriteBooks WHERE BookAuthorFirst = 'Jane';

Declarative programming is contrasted with imperative programming, whereby we tell the computer to do a series of actions using control flow. Instead of having one arrow that flows from Start to End, we can 'fork' arrows as well as having them return to a previous box. Goto used to be a common way to describe control flow, whereby we 'jump' from one position in the code to another. However, goto has been on the decline and has been replaced by structured programming. Structured programming uses sequence, iteration and selection to describe the flow of the program. We will learn these three structures in detail in later chapters. Procedural programming extends structural programming and allows us to divide our program into many modules called procedures, subprograms or functions. Procedural programming favours modularisation and the top-down approach.


Declarative programming	Structured programming	Procedural programming

Procedural programming is further extended in object-oriented programming, whereby the program consists of 'objects' that have different properties and perform different methods. There are two main types. In prototype-based programming, each object has a prototype (say, a blank book). The prototype defines all the properties and methods of the object. Then we clone the object and get different full-fledged objects (say, a large book with lots of text and diagrams, complete with a nice hard cover). Class-based programming takes a different approach. In class-based programming, types of objects are defined in classes. If we want to add more properties and methods to the class, we can extend the class. In both cases, to make a new object, we need to call its constructor. Here's a prototype in JavaScript:

var Book = function(title, pages, coverType) {
      this.title = title;
      this.pages = new Array(pages);
      this.cover = new Cover(coverType);
};

Book.prototype = {
   cover: new Cover();
   pages: new Array(1);
   title: "";
   currentPage: 0;

   flip: function(){
      try{
         if(currentPage >= pages.length - 1){
            throw "No more flipping!";
         }
         currentPage++;
      } catch (e){
         alert(e);
      }
   }
}

package {
   public class Book{
      public var cover:Cover;
      public var pages:Array;
      public var title:String;
 
      private var currentPage:uint;

      public function Book(title:String,
                           pages:uint, coverType:uint){
         this.title = title;
         this.pages = new Array(pages);
         this.cover = new Cover(coverType);
      }

      public function flip(){
         try{
            if(currentPage >= pages.length - 1){
               throw "No more flipping!";
            }
            currentPage++;
         } catch (e:Error){
            trace(e);
         }
      }
   }
}

Prototype in JavaScript

Class definition in ActionScript

Some programming languages only support one paradigm. For example, Java is a pure class-based object-oriented language. JavaScript is a prototype-based language. Others support more than one. For example, ActionScript can be procedural, class-based or a mix of the two.

A dialect is an extension of another programming language that is reasonably similar to the original. JavaScript (originally developed for Netscape), JScript (Internet Explorer) and ActionScript are all dialects of ECMAScript, a standard originally created for JavaScript and JScript. BASIC, an easy programming language designed for beginners, was later extended into various dialects, including Visual Basic. Most notably, C++ and C# are common dialects of C which, unlike C, support many different programming paradigms.

Here are three code snippets in JavaScript, ActionScript and PHP respectively. Note the similarities between JavaScript and ActionScript.

var numberOfItems = 10;
var fibonnaci = new Array();
fibonnaci[0] = 1;
document.writeln(fibonnaci[0]);
fibonnaci[1] = 1;
document.writeln(fibonnaci[1]);
for(var i = 2; i < numberOfItems; i++){
   fibonnaci[i] = fibonnaci[i-1]
   + fibonnaci[i-2];
   document.writeln(fibonnaci[i]);
}

var numberOfItems:uint = 10;
var fibonnaci:Array = new Array();
fibonnaci[0] = 1;
trace(fibonnaci[0]);
fibonnaci[1] = 1;
trace(fibonnaci[1]);
for(var i:uint = 2; i < numberOfItems; i++){
   fibonnaci[i] = fibonnaci[i-1]
   + fibonnaci[i-2];
   trace(fibonnaci[i]);
}

$numberOfItems = 10;
$fibonnaci = array();
$fibonnaci[0] = 1;
echo (string) $fibonnaci[0]."<br/>";
$fibonnaci[1] = 1;
echo (string) $fibonnaci[1]."<br/>";
for($i = 2; $i < $numberOfItems; $i++){
   $fibonnaci[$i] = $fibonnaci[$i-1]
   + $fibonnaci[$i-2];
   echo (string) $fibonnaci[$i]."<br/>";
}

JavaScript

ActionScript

PHP

Statements and expressions

A statement tells the computer to do an action. They are similar to imperatives in English, e.g. Eat a cake! Go to sleep! Brush your teeth! Clean the blackboard! These are all examples of statements in pseudocode:

Input x
Output y
Put x into y
Call brushTeeth

An expression is not quite the same thing. An expression has a value. They cannot do anything on their own.

x
3
6+8
1/2
4.5 + y * 3

An expression can be a variable or a constant. It can contain operators, but it may not. Now to the next chapter... Variables and data types!