Algorithm Basic

Nov 18, 2019

This is only for quick revision for syntax. If you want to know deeper, please refer to class ppt or other online tutorials.

Key Points

Four representations of Algorithms

  • Structured English
  • Flowchart
  • Pseudocode
  • Program code (e.g. Python)

Common Datatypes

  • integer 整数 – 53
  • real /float 浮点数 – 23.95
  • boolean 布尔值 – True
  • character 字符 – ‘s’
  • string 字符串 – ‘David’

Variables

  • In Pseudocode, you need to declare a variable before you use it.
  • The name of a variable CANNOT:
  • – Start with a number
  • – Include space

Basic structured programming constructions

  • Sequence
  • Selection
    • if
    • case
  • Repetition / Iteration
    • for
    • while
    • repeat…until

Errors

  • Syntax Error
  • Logical Error
  • Run-time Error

Flowchart

image.png

Pseudocode

Operators

Arithmetic operators:

+ plus – minus * multiply / divide ^ to the power of

% or mod get divide reminder

// or div integer divide

e.g. 5%2 = 1, 5 div 2 = 2

Relational operators:
= equal to             < smaller than               > greater than

>= greater than or equal to     <= smaller than or equal to     <> not equal to

Logical operators:

AND  OR  NOT

if & elseif & else

structure:

if <condition>
    <statement>
elseif <coindition>
    <statement>
else
    <statement>
endif 

example:

Declare A: integer
A ← -3
if A>0
    output 'positive'
elseif A=0
    output 'zero'
else
    output 'negative'
endif


result>>>negative

– there can be no, one or multiple elseif(s)

– end with endif

Nested-if: if-loop contains another if-loop

 if <condition>
    if <condition>
        <statement>
    else
        if <condition>
            <statement>
        else
            <statement>
        endif
           ······ 

Case

structure:

case of <variable>
    <condition1>:<statement1>
    <condition2>:<statement2>
    otherwise:<statement3>
endcase

example:

declare Score: integer
input Score
case of Score:
    0: output 'You Lose'
    100: output 'You Win'
endcase 

– no restriction on the number of conditions

– ends with endcase

for

structure:

 for <condition>
    <statement>
endfor

example:

declare A: integer
for A ← 1 to 5
    output A
endfor


result>>> 
1
2
3
4
5 

– ands with endfor

skip / step

example:

for A ← 1 to 10 skip 2
    output A
endfor


result>>>
1
3
5
7
9
for B ← 100 to 10 skip -20
    output B
endfor


result>>>
100
80
60
40
20 

while

structure:

 while <condition>
    <statement>
endwhile 

example:

declare i: integer
i ← 1
while i <= 5
    output i
    i ← i + 1
endwhile


result>>>
1
2
3
4
5 

– pre-condition loop: when the condition is False, terminate the loop; loop might not be executed at all (if the condition is False in the first place)

– ends with endwhile

repeat…until

structure:

repeat
    <statement>
until <condition> 

example:

declare i: integer
i ← 1
repeat
    output i
    i ← i+1
until i = 5


result>>>
1
2
3
4 

– post-condition loop::when condition is True, terminate the loop; loop will be at least executed once

declaration of an array:

declare <name>: array [lower bound,upper bound] of <data type>

e.g.

image.png

traversing the array:

declare i: integer
for i ← 0 to 99
    input Marks[i]
endfor 

assign value:

Marks[2] ← 89

– one Array may only contain one datatype( int / real / bool / str )

– efficient linear search: once found, come out of the loop

2D Array

declaration of  a 2D array:

declare <name>: array [lower bound1..upper bound1,lower bound2..upperbound2] of <data type>

e.g.

image.png

to initialize (to 0 in this case)

#row-by-row traversal
for r ← 0 to 3
    for c ← 0 to 9
        Num[r][c] ← 0


#col-by-col traversal
for c ← 0 to 9
    for r ← 0 to 3
        Num[r][c] ← 0 

– transpose: convert row into column and column into row

procedure

structure:

#procedure header 
procedure <name>(<parameter1>:<datatype>,<parameter2>:<datatype>)
image.png
#procedure call 
call <name>(<value1>,<value2>)

example:

#procedure definition
procedure Add(a:integer,b:integer)
    declare c: integer
    c ← a+b
    output c
endprocedure

#procedure call
call Add(21,35)


result>>>
56 

definition syntax:

procedure <name>(<parameter>:<datatype>[])

e.g.

procedure Add(ThisArray: string[])

– ends with endprocedure

– use call to execute procedure

– not restriction on number of parameters

function

structure:

#function header 
function <name>(<parameter>:<datatype>,<parameter>:<datatype>) : returns <datatype>
image.png

example:

#function definition
function Add(a:integer, b:integer): returns integer
    declare c: integer
    c ← a + b
    return c
endfunction

#function call
declare c: integer
c ← call Add(51,75)
output c


result>>>
126 

definition syntax:

function <name>(<parameter>:<datatype>[]):  returns <datatype>

e.g.

function Add(ThisArray: string[]): returns integer

– ends with endfunction

– datatype of returned value must be specified

– return value of the call can be directly assigned to variable

Python

operators

Arithmetic operators:

+ plus (or concat strings)   – minus

* multiply                                   / divide

** exponent                              % get divide reminder

// integer divide

e.g. 5%2=1

5//2=2

Relational operators:

== equals           > greater than             < smaller than

>= greater than or equal to      < smaller than or equal to    != not equal to

Logical operators:

and   or   not

if & elif & else

Use colons (“:”) to start python blocks, and “endxxx” is not necessary

structure:

if <condition>:
    <statement>
elif <condition>:
    <statement>
else:
    <statement>

example:

a=-3
if a > 0:
     print('positive')
elif a==0:
     print('zero')
else:
     print('negative')
result>>>
positive 

– there may be no, one or multiple elif(s)

nested-if: if that contains one or multiple other if(s)

if <condition>:
    if <condition>:
        <statement>
    else:
        if <condition>:
            <statement>
        else:
            <statement>
        ......

for

structure:

for <condition>:
     <statement>

example:

for a in range (1,5):
      print(a)

result>>>
1
2
3
4
5

while

structure:

while <condition> and <condition>:
      <statement>
      <statement>

example:

i=0
while i < 5:
     print(i)
     i=i+1

result>>>
0
1
2
3
4
5

– while loop will not automatically manipulate the counter variable

function

structure:

def FunctionName(parameter):
     body_of_function
     return ... 

example:

def add(a,b):
      return a+b
print(add(3,5))


result>>>
8

procedure

structure:

def ProcedureName(parameter):
     body_of_procedure

example:

def add(a,b):
      print(add(a,b)) 
add(3,5)


result>>>
8

– function must return a value,procedure doesn’t return any value

– function and procedure can be used in a program for multiple times

list

# empty list
list = []
# init with values (can contain mixed types) list = [1, "eels"] # get item by index
list = [1, 2, 3, 4, 5, 6]
list[0]  # 1
list[-1]  # 6

2-dimensional list

list = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

list[0][1]  # 2
list[2][2]  # 9
list[-1][2]  # 9
Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.