CSC 150 Chapter 2: Representing algorithms
primary information resource: An Invitation to Computer Science (Java), Third Edition, G. Michael Schneider and Judith L. Gersting, Course Technology, 2007.

[ previous | schedule | next ]

Two that come to mind are: a natural language (e.g. English) or a programming language (e.g. Java)

Critique English as means for representing an algorithm.
(ADV: well known notation; DIS: ambiguous, too loosely structured)

Critique Java as a means for representing an algorithm.
(ADV: structured and nonambiguous; DIS: too highly structured, not abstract enough)

middle ground approach normally used:  pseudocode .
structured subset of English with programming language symbols used to efficiently write calculations and expressions

establish consistent notation for the three kinds of operations (once again, what are they?)
1. sequential operations
2. conditional operations
3. iterative operations

The pseudocode language used in the textbook and lab manual is pretty simple.

Sequential operations (computation/assignment, input, output) have the formats:

• Set the value of variable to expression
• Get the value for variable
• Get the values for variable1, variable2,...
• Output the value of variable
• Output the values of variable1, variable2,...
• Stop

• If condition then operation_list
• If condition then operation_list1 else operation_list2

• While condition Do operation_list End of loop
• Do operation_list While condition

Additional notes about While loops:

• The condition is known as a continuation condition. If the condition is true, we continue on to another loop iteration. Otherwise the loop is terminated.
• The first loop format shown above is called a pre-test loop: the continuation condition is tested before entering the loop body.
• The second loop format is called a post-test loop: the continuation condition is tested at the end of the loop body. Such a loop always completes at least one iteration.  It is normally used when the loop begins by getting some input.
• In the first form, you can replace "Do" with "Do steps m through n" where m and n represent a range of numbered steps. The "End of Loop" is then not needed. The result is something like this: While condition, Do steps m through n operation_list

Keep in mind that the actual syntax does not have to conform exactly to these formats.  It is important, however, that the meaning is unambiguous and clear.  For example, the operation "Add 1 to count" means the same as "Set the value of count to count+1" (and is probably clearer, to boot).
 

Given the pseudocode language, let's create some algorithms.

Get length and width of piece of carpet in feet, and cost per square yard.  Compute and output total cost including 6% sales tax.

Sample solution

Input the beginning and ending electric meter reading for a month in kilowatt hours (KWH).  Compute charge based on rate of 6 cents per KWH for the first 1000 KWH used and 8 cents per KWH for excess over 1000 KWH.  If less than 500 KWH was used, output a message congratulating customer on conserving energy.

Sample solution

Alice is thinking of a number between 1 and 10.  Two brothers, Bob and Charlie, each guess what it is.  Whoever is closer gets a kiss from Alice.  In case of a tie, both have to kiss their sister Kate.  Write an algorithm to get Bob and Charlie's guesses, determine the outcome and output an appropriate message. Alice's number is fixed at the beginning of the program (e.g., start your program with:  Set Target to 7)

Sample solution

Alice is thinking of a number between 1 and 10.  Bob has three chances to guess it correctly.  If he does, Alice kisses him and the game is over.  If he does not, he has to kiss his sister Kate.  Write an algorithm to get Bob's guess(es), determine the outcome for each guess and output appropriate messages. Alice's number is fixed at the beginning of the program.

Sample solution

Alice is thinking of a number between 1 and 10.  Two brothers, Bob and Charlie, take turns guessing what it is until one guesses correctly.  First correct guesser gets a kiss and then the game is over.  Write an algorithm to get Bob and Charlie's guesses, determine the outcome for each guess and output appropriate messages.  Alice's number is fixed at the beginning of the program.

Sample solution

Homework for next class:  Given a text string, determine whether or not it is a palindrome (spelled the same either forward or backward).  The year 2002 is itself a palindrome, the last one until 2112.  Assume that all spaces and special characters have already been removed from the string.  Write an algorithm to get a string, conduct the test, and output the result.