CS20 : Representing algorithms



https://docs.google.com/presentation/d/1AiQlh6G94ClsV8vKC_8hrY-WeYdS8Lj5ElskFqratMw/preview
There are various different ways of representing algorithms both textual and graphical.

We are learning ...
  • How to represent algorithms in different ways
So that we can ...
  • Use different ways of representing the same algorithm
    - Written description
    - Structured English
    - Pseudocode
    - Flowcharts

CGP The Revision Guide Page 34, 35
CGP Exam Practice Workbook Page 41, 42, 43

# Get Ready.png

The Big Bang Theory - The Friendship Algorithm (2:27)


All of the activities in this section use a script called Guessing Game.py which you should download first, save in a suitable location in your user space, open using Notepad++ (or equivalent) and print for your folders. If you are lucky, your teacher will give you a copy first.

Rubber duck the script to your shoulder partner paying particular attention to the comments. Try running the script and play the game so you can see how it works.

import random

# Initialise
secret = random.randint(1,99)
guess = 0
guesses = []
tries = 0
limit = 8

# Instructions
print('Guessing Game')
print('-------------')
print('Ahoy! I\'m the Dread Pirate Mills and I have a secret!')
print('It\'s a number from 1 to 99.  I\'ll give ye {0} guesses.'.format(limit))

# Play game
while guess != secret and tries < limit:
    guess = int(input('What\'s yer guess? '))
    guesses.append(guess)
    if guess < secret:
        print('Too low, ye scurvy dog!')
    elif guess > secret:
        print('Too high, landlubber!')
    tries = tries + 1

# Result
if guess == secret:
    print('Avast! Ye got it! Found me secret, ye did!')
else:
    print('No more guesses! Better luck next time, matey!')
    print('The secret number was {0}!'.format(secret))

# Print all guesses
print('Your guesses were ...')
for guess in guesses:
    print(guess,end=' ')

This script contains examples of all major programming structures (sequencing, selection and both types of iteration) to help you with the following activities. See if you can spot them all.

ACTIVITY 1
Written description 
  I   O   A   E 

A written, or oral, description of an algorithm or process to solve a problem is probably the first place you should start when you are developing an algorithm to solve a problem.


Task 1.1 No maths allowed!
Where we learn how to write out an algorithm in pure English


In your notebooks / files

Decode the Guessing Game program into a written algorithm. You should first work with your shoulder partner to 'talk through' the algorithm. We'd normally refer to this as rubber ducking!

HINT : To start you off, I would write ... 

"First, choose a random number from 1 to 99 and store it in a variable called secret."

There are three ways you can tackle this ...
  • Write out each line by hand on a piece of paper
  • Type each line in a bullet pointed list in a word processed document
  • Add comments to the actual script using the hash sign '#'
There are two levels of response to this task, you can either ...
  • Convert the Python code into written English; verbalise it; write it like you'd read it;
  • Decode the instruction; explain what it does / how does it work?


ACTIVITY 2
Structured English 
  I   O   A   E 

Structured English does not use any mathematical operators or symbols. We would normally write them in CAPITAL LETTERS and group them like follows. These are the only commands which you are allowed to use - this is a subset of the English language which forces you to think algorithmicallyWhen you are writing structured English, you should use indentation to structure you code as well.

Remember, you can't use any mathematical operators or symbols either!

Assignment (variables)

  SET [variable] EQUAL TO [value]

Structural

  PROCEDURE ... END PROCEDURE
  FUNCTION ... END FUNCTION
  RETURN

Input / Output

  INPUT / GET / READ
  OUTPUT / PUT / WRITE

Mathematical

  MULTIPLY / DIVIDE / ADD / SUBTRACT / RAISED TO POWER OF
  INCREMENT [variable] BY [value]
  DECREMENT [variable] BY [value]

Comparison / Logical

  NOT / OR / AND / XOR
  TRUE / FALSE
  GREATER THAN / GREATER THAN OR EQUAL TO
  EQUAL TO / NOT EQUAL TO
  LESS THAN / LESS THAN OR EQUAL TO

Iteration (repetition)

  DO WHILE [decision_statement] ... END WHILE
  REPEAT ... UNTIL [decision_statement]
  FOR EACH ... END FOR
  FOR EACH ... IN ... END FOR

Selection (choices)

  IF [decision_statement] THEN ... END IF
  IF [decision_statement] THEN ... ELSE ... END IF
  IF [decision_statement] THEN ... ELSE IF [decision_statement] ... END IF
  IF [decision_statement] THEN ... ELSE IF [decision_statement] ... ELSE ... END IF


OK, I will!


Task 2.1 Writing like a computer might
Where we learn how to write algorithms using Structured English


In your notebooks / folders

Make some notes on the Structured English constructs that are listed above. If you can, write to relate these to some Python code you are familiar with and write this alongside. Consider using a table to present your work.

Compare Structure English to Python

In a TEXT document

Write out the algorithm for the Guessing Game using structured English. Remember that you can't use any other commands than the ones listed above or any mathematical operators or symbols. Remember also to use indentation to structure the Structured English commands.

This time, you are merely converting the program into Structured English, not decoding it - it's less difficult.


ACTIVITY 3
Pseudocode 
  I   O   A   E 

The term pseudocode literally means falsecode and is a (loosely) accepted standard for representing algorithms in a code like way but which does not represent any particular programming language.

Snails have a pseudopodia or 'false foot'

The difference between structured English and pseudocode is in the use of mathematical operators and symbols. Specifically, one symbol is in use in pseudocode which does not make an appearance in normal coding situations - the assignment operator,  (left facing arrow)

widgets ← 12

... literally means the same as SET widgets EQUAL TO 12 in structured English; much simpler, eh? So we can now replace the words for the following operations by their symbols ...

Assignment (variables)

  [variable] [value]

Mathematical

  *, /, +, -, ^
  ++ (incrementation)
  -- (decrementation)

Comparison

  >, >=
  =, <>
  <, <=


... whilst the remainder of the programming constructs remain the same.


Task 3.1 Pseudopodia
Where we learn to write algorithms using Pseudocode



In your notebooks / folders

Yes, you guessed it! You should convert the program for the Guessing Game into pseudocode and not Structured English. Remember, we still use most of the same commands in pseudocode that we do in Structured English apart from the where the commands involve assignment, mathematics or comparison.


Finally, download yourself a copy of the Structured English and Pseudocode Cheat Sheet for your folders as well!

ACTIVITY 4
Flowcharts 
  I   O   A   E 

We've seen lots of flowcharts so far in this course. You have been asked many times to draw them using software like yEd and Powerpoint or even by hand. You have learnt what the symbols mean, so this should be revision.


Task 4.1 Flowchart symbols and segments
Where we revise the meaning of the standard flowcharting symbols and learn simple segments.


The diagram below shows you standard (and slightly simplified) compound flowchart structures for sequencing, selection and four types of iteration. The iteration structures are subtly different so you'll have to look carefully ...

https://drive.google.com/file/d/0B83yXMOilskaNlRxamRBenpoak0/preview
Click to engage

... and if you didn't look carefully, the following activity will help you to :)

On the worksheet

Download the worksheet 'Flowchart symbols and other challenges' and print yourself a copy (or get one off your teacher). The first part of the worksheet is revision to make sure you know what the standard flowchart symbols are and whether you can draw standard flowchart segments for selection and iteration. The second part asks you to construct a flowchart for the Guessing Game program. 

You should complete this worksheet by hand ...



Flowgorithm is a free piece of software that you can use to draw flowcharts that you can actually run, like a proper computer program. Your teacher will demonstrate how to use Flowgorithm because it can be a little fiddly at first. 

Your teacher will demonstrate how to use Flowgorithm - it's cool!


Task 4.2 Flowgorithm
Where you learn to use Flowgorithm to construct working flowcharts


On the worksheets

There are five flowcharts for you to practice constructing using Flowgorithm, each one has some extra challenges associated with it as well. Download each worksheet and carry out the tasks, remembering to evidence your work. 


If you are struggling, ask your teacher for the solutions or download them from here. You will have to ask your teacher for the password to unzip the archive though ...


Assessment Task (Homework)

Look back over all the programming work you have done through Computing Cafe and whatever other programming platform you have been learning through (Grok for instance). Choose one program you have written which was challenging, but not too challenging, and document a ...
  • Structured English
  • Pseudocode
  • Flowchart
... solution to it in your notebooks or on paper in your folders.

Grading rubric

MASTER : You have chosen a challenging script to reverse engineer into a structured English, pseudocode and flowchart based algorithm. Your script includes most major programming constructs - sequencing, selection and two types of iteration.
APPRENTICE You have chosen a script to reverse engineer but it contains only relatively simple programming constructs such as sequencing, selection and definite iteration.
NOVICE : You have chosen a simple script to reverse engineer which might only include sequencing and selection.

Click to download revision cards
https://docs.google.com/document/d/1kDpEkUAsmc36giI1G-7wai6fG6PbqKyaeZwMrbxzCEc/export?format=pdf
Remember to print them single sided

# Flash cards.png
Click to load key word list to help you make your own flash cards 

https://goo.gl/forms/xd2upSLGuGWBM4yy1
Try to get 5/5!



Hungry for more?

If you love FizzBuzz, you can download a version here. (It's also in the assessment, so well done you for being observant and looking at the extension work!)

FizzBuzz: One Simple Interview Question (7:17)