Pseudocode

Pseudocode

• “False code”
• Not a real programming language -- but more human readable
• Defining algorithms
• Different conventions can be followed
• Modules/functions defined after the main algorithm
• Variables are not declared

Reserved and Optional Words

• Reserved:
• If, then, else, for, to, do, step, case, while, repeat, until, and, or, not, return
• Optional (but good to have)
• Endif, elsif, endfor, endwhile, endcase, input (precondition), output (postcondition), begin, end
• forall

General Structure

• Layout is important!
• Indentation must be used
• One statement per line
• Variable names must be meaningful
• Mark end of branches and loops
• endif, endwhile, endfor, until

General Structure

QuickSort(A, first, last)

Input: Array of integers A, integers first and last to mark beginning and end of the array

Output: Sorted integer array A

Statement 1

Statement 2

…

Variables

• No need to declare: no type, no size
• Arrays
• Set and access using [] operator
• Indices are usually assumed to be 1-based
• Range of indices can be defined with “..”
• A[1..n]

Statements

• Simple and single action, simple English statements
• Set x=1
• x ← 1
• Read x (from a file, terminal, etc.)
• y ← m ⨉ a + b
• Function call: sqrt(x)
• Conditional: if
• Loop: for, while, repeat

Simple statements

• Should not be ambiguous
• “Get x” - BAD
• “Read x from terminal” - GOOD
• Be brief
• “Multiply x by 3 and store in y” - BAD
• y←3 ⨉ x - GOOD
• Be simple
• “Calculate circumference of circle” - BAD
• Circumference ← 2 ⨉ π ⨉ radius
• “Calculate FFT” - BAD

Function calls

• Should be easy to understand. Multiple ways possible
• square (IN: x, OUT: y)
• void square(int x, int *y) { *y = x * x;}
• y←square(x)
• int square(int x){return x*x;}

Conditions

• IF statements

IF (expression) THEN

Statements…

ELSIF (expression) THEN

Statements…

ELSE

Statements

ENDIF

Conditions - example

IF (a=1) THEN

a←a*2

ELSEIF (a=2) THEN

a←a*3

B←a+5

ELSE

a←a*a*a;

ENDIF

Roots of a quadratic function

Read a, b, c from terminal

d←b*b - 4*a*c

IF (d<0) THEN

Write “no roots”

ELSIF (d=0) THEN

r1← -b / (2*a)

Write “Root: ”, r1

ELSE

r1←(-b + sqrt(d)) / (2*a)

r2←(-b - sqrt(d)) / (2*a)

Write “Roots: ”, r1, r2

ENDIF

Logical Operators

• Standard comparators
• <, >, <=, >=, =, !=
• AND, OR, NOT in conditional expressions

IF (a=1 AND b=2) THEN

…

IF (a=1 OR c>=5) THEN

…

Invalid expressions

• Expressions should be easily calculated
• Simple comparisons (<, =, >= …)
• Logical combinations (AND, OR, NOT)
• Complex expressions are invalid:
• IF (the value 7 in the array…)
• IF (the smallest value in the array is <10)
• IF (the WHILE loop above repeated 10 times)
• IF (day is a public holiday)

CASE statement

CASE (expression) IS

Const1:

Statements…

Const2:

Statements…

…

DEFAULT:

Default behaviour statements…

ENDCASE

​

CASE example

Read option from keyboard

CASE (option) IS

‘a’:

Read num from keyboard

value←value+num

‘b’:

value←0;

‘c’:

value←10000;

DEFAULT:

Write “Invalid option” to the screen

ENDCASE

​

​

FOR loops

FOR variable IS start TO end STEP inc DO

Statements…

ENDFOR

• variable is assigned to start; iterates until end, stepping by inc (assumed to be 1 if not mentioned)
• IS can be replaced by =

for (variable = start; variable <= end, variable=variable+inc){

Statements…

}

FOR loop example

sum←0

FOR i = 0 TO N-1 DO

sum←sum+array[i]

ENDFOR

average←sum/N

Write “Average is:”, average

WHILE loops

WHILE (expression) DO

Statement 1

Statement 2

..

ENDWHILE

WHILE example

n←0

WHILE (n < 100) DO

Write “N: ”, n

n←n+1

ENDWHILE

REPEAT loops

REPEAT

Statement 1

Statement 2

Statement 3

…

UNTIL (expression)

REPEAT example

REPEAT

Display menu on the screen

Read user choice as x

UNTIL (x = ‘e’)

Quicksort

Quicksort (A,p,r)

IF (p < r) THEN

q ← Partition(A,p,r)

Quicksort (A,p,q)

Quicksort (A,q+1,r)

ENDIF

​

​

​

​

Quicksort/Partition

Partition (A,p,r)

pivot ← A[p]

i = p - 1

FOR j = p TO r - 1

IF A[j] < pivot

i ← i + 1

swap A[i] and A[j]

ENDIF

ENDFOR

swap A[i + 1] and A[p]

RETURN i + 1

​