CSC2901 – Discrete
Structures
Lesson 4: Introduction to Algorithms
Objectives
• At the end of this lesson you are expected to be able to
• Explain what an algorithm is
• Outline the properties of an algorithm
• Express an algorithm using pseudocode
• Follow the execution of flowchart
• Design simple algorithms
• Count number of operations in an algorithm
Outline
• Overview
• Pseudocode
• Control Structures
• Arrays
Overview
• Definition
• An algorithm is a finite set of precise instructions to solve a specific problem.
It is sometimes referred to as an effective procedure.
• Every Computer program, implements an algorithm.
• Every algorithm is meant to solve a particular problem
• It usually follows the input-process-output cycle i.e.
• Input: it is given data to work with, usually as parameters
• Process: it the works on this input
• Output: returns the results of processing, could be by displaying to the
console or saving to memory
Characteristics
• An algorithm has the following characteristics
• Precision
• Steps are precisely stated
• Uniqueness
• Intermediate steps are uniquely defined and depend on inputs
• Finiteness
• The algorithm terminates.
• Input
• Receives data to be processed
• Output
• Produces output
• Generality
• Should apply to a set of inputs
Metrics of Algorithms
• An algorithm is designed, it is evaluated against the following
• Correctness
• It should be able to produce correct results for any given set of legal inputs.
• Efficiency
• How efficient does the algorithm utilizes the computing resources?
• Resources include
• CPU time
• Execution time
• Memory
• Bandwidth
• Simplicity
• In terms of design and implementation
Example
• An algorithm for a simple adding machine could be described as
follows
• Adder
• Read two numbers
• Add them
• Display the sum
Notation for Algorithms
• Algorithms can be specified in
• Plain English (or any natural language)
• Appropriate for humans not computers
• Difficult to transform into a computer program
• Computer program
• Too specific
• Language and at times platform dependent
• In between these two extremes is pseudocode
• Resembles actual code but allows descriptions in English for complex procedures.
• It is precise, structured and not specific to a programming language
• Provides notation for programming control structures, like looping and alternation
Building blocks for Algorithms
• Constants
• 2, 2.4, “Text” etc
• Variables
• Alphabetical letters, A, B, C, …
• All arithmetic operations are accepted
• +, -, *, /, <, >, >=, <=
• Arithmetic expressions
• 2+A(B – C)
• Assignments
• Storing data to variables
• Variable := expression e.g. A := 2, B := A + 3
• Functions
Example
• Adder problem revisited
• Adder
• A := read from user
• B := read from user
• Z := A + B
• Display Z
• Commands
• For input we will use READ to read from user
• For output we will use
• RETURN to return the processed result or
• PRINT to display to standard output console
• PRINTLN, PRINT with carriage return
Notation for Algorithms
• Still our Adder problem
• Adder
• A := READ
• B := READ
• Z := A + B
• PRINT Z
Arrays
• A variable holds only one element
• Most programs process collections of data, e.g. MIS, Payrolls e.t.c.,
have databases in the backend.
• We will use an array, a collection of similar objects denoted by the
name of array followed by ‘(‘ and ‘)’. E.g. X() is an array named X.
• Each slot has a unique identifier called an index with the first slot indexed 0.
• So an array of size n has indices 0 t0 n-1
• To access individual slots we use X(index), e.g. X(0) refers to the first slot in
the array named X
Our Pseodocode Syntax
Control Structures
• Control structures determine the flow of control through any
given algorithm
• Implemented with three basic types
• Sequential: default mode. Sequential execution of code statements (one
line after another) -- like following a recipe
• Selection: or alternation, used for decisions, branching -- choosing
between 2 or more alternative paths.
• if
• if/else
• Repetition: used for looping, i.e. repeating a piece of code multiple times
in a row. In C++, there are three types of loops:
• For
• while
Selection
• The IF <condition> THEN statement, decides, based on the condition,
whether a body of statements should be executed.
• Syntax
• IF <condition> THEN DO
• BODY
• END IF
• Example
• IF N >= 2 DO
• PRINT “N is greater than 2”
• END IF
Selection
• The IF <condition> THEN..ELSE statement, decides, based on the condition, which
of the two, usually mutually exclusive body of statements should be executed.
• Syntax
• IF <condition> THEN DO
• TBODY
• ELSE
• FBODY
• END IF
• Example
• IF N >= 2 DO
• PRINT “N is greater than 2”
• ELSE
• PRINT “N is less than 2”
• END IF
Repetition
• Otherwise known as loops, execute a body of
statements as long as the condition is true. It has
• Initialiser
• Condition
• Body
• Adjuster/update
[Link]
Repetition
• The FOR statement executes a body of statements a given number of
times.
• Syntax
• FOR <iterator> := Lower TO Upper [STEP GAP] DO
• BODY
• NEXT
• END FOR
• Example
• FOR I := 0 TO 10 STEP 2 DO
• PRINT I
• NEXT
• END FOR
• Also DOWNTO version.
Repetition
• The WHILE statement suitable when a number of loops is not known
beforehand
• Syntax
• Initialiser
• WHILE <condition> DO
• BODY
• Adjuster
• END WHILE
• Example
• I := 0
• WHILE I <= 10 DO
• PRINT I
• I:= I+2
• END FOR
[Link]
Structure of Functions
• Algorithm <name> ( arglist )
• Body
• End.
• Body describes inputs and outputs followed by a list of statements
• E.g.
Algorithm adder()
Input: none
Output: sum of two numbers read in
A := READ
B := READ
Z := A + B
RETURN Z
END.
Structure of Functions
• Example
• Write an algorithm printHello, which prints hello a given number of times.
• Solution
Algorithm printHello(n)
Input: n the numbr of times to print “Hello World”
Output: printing of “Hello World” to console
For I := 1 to n DO
Print “Hello World!”
NEXT
End For
END.
Structure of Functions
• Example
• Write an algorithm printHello, which prints hello a given number of times, using the
WHILE statement.
• Solution
Algorithm printHello(n)
Input: n the numbr of times to ptint “Hello World”
Output: printing of “Hello World” to console
I := 1
WHILE I<=n DO
Print “Hello World!”
I:= I +1
END WHILE
END.
Processing Arrays
• To access an index i in the list or array A, we use A(i).
• There are times that you wish to process the entire list, say search,
sort or even apply an operation to all elements of an array e.g. double
all elements in the array. How do we do this?
• Loops, the FOR statement in particular, happen to be the most
convenient way of doing this.
• If we know the size of the array to be N, then we let the iterator, say I,
loop through 0 to N-1 and at each stage, process the element at that
position
Processing Arrays
• E.g, To double elements of array A of size N use
FOR i:= 0 TO N-1
A(I) := 2*A(I)
END FOR
Processing Arrays
• Example
• Write an algorithm sumList, which takes a list of n integers, and returns the sum of all
numbers in the list
• Solution
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• Simulate sumList({1, 2, 3, 4, 5}, 5) for sumList defined below
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END. S=30
Processing Arrays
• N = 5, N-1 = 4,
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END. S=30
Class Exercise
• Write a FOR version of sumList below
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Class Exercise
• Convert the program to avgList, so it returns the average instead of
sum
Algorithm sumList(A, N)
Input: A an array of n integers
Output: sum of all numbers in A
I :=0
S:=0
WHILE I <= N-1 DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Class Exercise
• Write a program which takes a list of numbers and returns the largest
number in the list
Algorithm findMax(A, n)
M:= A(0)
for i:=1 to n-1 do
if A(i) > M then
M:=A(i)
End if
Next
End For
Return M
End.
Class Exercise
• Write a program that receives a positive integer n and prints numbers
1 to n
Example
• Write a program arithSum(N) which gets a positive integer N and
returns the sum of the first N integers (1 + 2 +..+ N) .
• Solution Algorithm arithSum( N)
Input: N, a positive integer
Output: returns 1 + 2 + .. + N
I :=0
S:=0
WHILE I <= N DO
S:=S+A(I)
I:= I +1
END WHILE
RETURN S
END.
Example
• Write a program rem(N,M) which gets positive integers M and N and
returns the remainder of dividing N by M, using only addition and
subtraction operations.
• Solution
• Lets devise an algorithm
• We see that if M is greater than N then we
• return N.
• Otherwise we repeatedly subtract M from N and assigning the balance to N, until N is
less than M
Example
• Write a program rem(N,M) which gets positive integers M and N and returns the
remainder of dividing N by M, using only addition and subtraction .
• Solution
Algorithm rem(N, M)
Input: M, N, positive integers
Output: returns remainder of N/M
WHILE N > M DO
N := N - M
END WHILE
RETURN N
END.
Example
• Write a program div(N,M) which gets positive integers M and N and returns the the
number of times M is in N (the whole part of N/M), using only addition and subtraction .
• Solution
Algorithm div(N, M)
Input: M, N, positive integers
Output: returns 1 + 2 + .. + N
I := 0
WHILE N > M DO
N := N – M
I := I + 1
END WHILE
RETURN I
END.
Example
• Write a bits(N), which gets a positive integer and prints the bits in the binary
representation of N.
• Solution
Algorithm bits(N)
Input: N, a positive integer
Output: returns whole part of N/M
WHILE N > 0 DO
PRINT rem(N, 2)
N := div(N,2)
END WHILE
RETURN N
END.
Nested Loops
• Sometimes the body of a loop construct, could be a loop as well.
• E.g.
• Consider this loop below
FOR J:= 1 TO 10 DO
PRINT J
PRINT “ “
END FOR
• What the output of this code?
It prints numbers 1 to 10 separated by a single space
1 2 3 4 5 6 7 8 9 10
Nested Loops
• Suppose want this printing of the numbers 1 to 10 to be done 10
times
FOR J:= 1 TO 10 DO
PRINT J
END FOR
• What do I do?
• I will define another loop, iterating 10 times
• Whose body writes numbers 1 to 10
Nested Loops
• Suppose want this printing of the numbers 1 to 10 to be done 10
times
FOR J:= 1 TO 10 DO
PRINT J
END FOR
• What do I do?
• I will define another loop, iterating 10 times
• Whose body writes numbers 1 to 10
• But these lists will be on the same line
• So, after printing a list of numbers, take cursor to next line
Nested Loops
FOR I := 1 TO 10 DO 12345678910
FOR J:= 1 TO 10 DO 12345678910
PRINT J 12345678910
END FOR 12345678910
PRINTLN 12345678910
END FOR 12345678910
12345678910
12345678910
12345678910
12345678910
Nested Loops
FOR I := 1 TO 5 DO The output is
FOR J:= 1 TO 5 DO
PRINT “* “
END FOR *****
PRINTLN *****
END FOR *****
*****
*****
Class Exercise
• E.g.
FOR I := 1 TO 5 DO
FOR J:= 1 TO I DO
PRINT I*J
PRINT “ “
END FOR
PRINTLN
END FOR
What is the output of this program?
Nested Loops
FOR I := 1 TO 5 DO The output is
FOR J:= 1 TO I DO
PRINT “* “
END FOR *
PRINTLN **
END FOR ***
****
*****
Class Exercise
FOR I := 1 TO 5 DO
FOR J:= 1 TO 5 DO 1 2 3 4 5
PRINT I*J 2 4 6 8 10
PRINT “ “ 3 6 9 12 15
END FOR 4 8 12 16 20
PRINTLN 5 10 15 20 25
END FOR
What is the output of this
program?
Nested Loops
• Example
• Write a program, duplicates, which takes an array of N integers and returns true if there is any duplicates in the array
• Solution
Algorithm duplicates(A, N)
Input: A, an array of N integers
Output: returns true if there are duplicates in A and false otherwise
FOR I := 0 TO N-2 DO
FOR J:= I +1 TO N-1 DO
IF A(I) = A(J) THEN DO
RETURN TRUE
END IF
NEXT
END FOR
NEXT
END FOR
Return False
END.
Examples – Search Algorithms
• Linear search
• Binary search
Examples – Sorting algorithms
• Bubble Sort
• Insertion Sort
• Merge Sort
Summary
• We looked at
• algorithms, their characteristics and metrics, pseudocode and flowcharts
• Control structures
• Sequencing
• Selection
• Repetition
• Arrays
• Nested loops
• Examples
• Search algorithms
• Sorting algorithms
• ?????QUESTIONS?????