CSCI 170: Conventions for Algorithm Expression

Introduction

An algorithm is a well-ordered collection of unambiguous, effectively computable instructions that produce a result and halt in a finite amount of time.

The instructions that are unambiguous and effectively computable depend on the computing agent executing the algorithm. Establishing a well-ordered collection of those instructions depends on the language used to describe the algorithm. While we can write algorithms for ourselves without deep reflection on this definition (since we understand what is effectively computable and unambiguous for ourselves), if we want to communicate algorithmic solutions to others, we must establish a reasonable common computing agent. Below we describe a set of instructions that will define a language and effectively computable instructions for a pseudomachine that will serve as our target computing agent.

Computational State

Our computing agent must be able to keep track of a variety of values needed in executing the algorithm. The values involved in the execution of an algorithm make up the state of the computation. The state is dynamic over the execution time of the algorithm, as values associated with particular attributes of the algorithm may change as the algorithm executes.

As algorithm writers, we need a way to describe the various values in the state of the computation. Each value will be describe with a name, written in lowercase letters, and called a variable. For example, we may want to write an algorithm that outputs the integers between one and ten. In order to know which value to output next, we could establish a variable count that will represent the count to output next.

As an algorithm designer you should think of a variable as a box holding a value. The name of the variable (e.g. count) is the unique name of the box.

Lists of values and indices

Sometimes we need to keep track of lists of associated values, for example a list of ten names. Rather than think up ten different variable names, we can use list notation and refer to name[0], name[1], ..., name[9] to refer to the ten names - Computer Scientists always begin counting with 0. We say that name is the list of values and that the integer in [] is the index indicating which value in the list we are referring to.
For example: name = ['mikeyg', 'mindy', 'eli', 'sadie', 'molly', 'sara', 'stanley', 'max', 'rosalyn', 'jessie']

When using a list of values, we may use a variable to keep track of which item in the list we are interested in. For example we may have a variable i that keeps track of which name we want to look at. name[i] would then refer to the value in list name found at the index indicated by the value of i.
For example, if i were to hold the value 4, then name[i] would represent 'molly'

Interacting with the User

After an algorithm designer writes an algorithm, a user decides to run the algorithm on a particular computing agent. The computing agent will need to interact with the user at least once, when outputting the result to the user. The agent may also need to receive information from the user.

Output from the computing agent to the user

The following may be used to indicate the agent is outputting information to the user:
print

The command can be followed by text in quotes, which is output verbatim, and variables, whose value is output. Some examples:

print 'Please enter an integer'
print 'The current counter value is ', count

Input from user to agent

Input from the user is indicated by input preceded by a variable that will store the value input from the user. Typically, one also supplies a "prompt" for display so the user knows what to input.

For example,
n = input('Enter your age in years')
inputs a single value, storing it into the variable named n.

Changing the value of a variable

Algorithms need to be able to change the value of variables. To set the value of a variable to a new value we will use the following assignment statement
variable = value
Where variable is the name of the variable whose value the algorithm is changing and value is an expression whose value should be stored in the variable.

What are expressions?

Many times, the expressions set into the variable are mathematical expressions. The usual operators +, -, *, / are available. We also have two other operators, div (/) and mod (%). The value x / y is the integer portion of x / y. The value x % y is the integer remainder of x / y. For example, 7 / 2 is 3 and 7 % 2 is 1 (because 2 goes into 7 three times with a remainder of 1). Finally, 7.0 / 3 = 2.3333

Expressions can also be boolean. Boolean expressions have only two possible values, true or false. The operators used in boolean expressions include the usual comparison operators: <, <=, >, >=, = and logical operators, AND, OR, NOT.

Conditional statements

To describe a point in the algorithm in which steps are executed only if some condition is true, we use the if statement.
if (condition): statements...

where statements... indicates any statements may be placed indented after the if statement. The statements are executed only if the condition expression evaluates to true.

One may also want to indicate an alternative set of statements to be executed if the condition evaluates to false. In this case the statement is written as:

if (condition): statements... else: statements...

Iteration

To indicate repetition of statements in an unambiguous way, the algorithm will use the following construct:

while (condition): statements...

tests the condition. If it is true, the indented statements are executed, and then the condition is tested again. When the condition is false, control falls out of the loop.

Example

The following algorithm inputs an integer and outputs the values between 1 and that value.

n = input('Please enter a positive integer value')
count = 1
while (count <= n):
    print count
    count = (count + 1)

Alternatively one can iterate a specific number of times using the for construct:

for i in range (x):

This iteration construct will repeat the given indented code x times. Furthermore, each time through the iterated code the variable i will be incremented by 1 (starting off with the value of 1).

Example

The following algorithm inputs an integer and outputs the values between 1 and that value.

	n = input('Please enter a positive integer value')
	for count in range(n):
	    print count