INN701 Lecture 1
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 1 (Part 2): Introduction to
Algorithms and Complexity
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R
Aims of this lecture
• To present the motivation for studying algorithms and complexity
• To learn the concepts of data structure, algorithm, efficiencies of an
algorithm, and analysis of an algorithm
• To introduce pseudocode notations that will be used for expressing
algorithms
• To show how an algorithm is described in pseudocode
2
CRICOS No. 00213J
a university for the worldreal R
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Pearson, third edition, 2012. Chapter 1, and Appendix A.
• T. H. Cormen etc. Introduction to Algorithms. MIT, third edition,
2009. Chapter 1.
Electronic versions of the above references are available at QUT
library.
3
CRICOS No. 00213J
a university for the worldreal R
What is an algorithm?
• A sequence of unambiguous instructions for solving a computational
problem, i.e., for obtaining a required output for any legitimate input
in a finite amount of time
• Algorithms are independent from programming languages
– An algorithm can be implemented in different programming
languages
– An implementation of an algorithm is a computer program
4
CRICOS No. 00213J
a university for the worldreal R
Pseudocode
• Pseudocode allows us to reason about programs abstractly, without
getting distracted by language-specific trivia
• A given pseudocode algorithm can be implemented in a variety of
programming or scripting languages
• In the following, we will look at the pseudocode notations to be used
in our algorithm descriptions
5
CRICOS No. 00213J
a university for the worldreal R
Pseudocode notations
• Let v, w, … be variable names; E, F, … be expressions; B, C, … be
Boolean-valued expressions; N, M , … be integer-valued
expressions; S, T , … be (compound) program statements; P, Q, …
be procedure names; and x, y, … be parameter names
• Expressions
(2 ∗ v) + x
• Parameterised procedure declarations
P(x, y, …)
S
• Procedure calls
P(E, F, …)
6
CRICOS No. 00213J
a university for the worldreal R
Pseudocode notations
• Returned values
return E
• Variable and type declarations
– These are usually left implicit in pseudocode algorithms
• Informal bits
– Sometimes algorithms describe ‘obvious’ actions informally,
such as the ‘swap’ action in the SelectionSort algorithm
7
CRICOS No. 00213J
a university for the worldreal R
Pseudocode notations
• Assignment
v ← E
• Sequential composition
S T or S; T
• Choice
if B S else T
• Iteration (pre-tested)
while B do S
8
CRICOS No. 00213J
a university for the worldreal R
Pseudocode notations
• If-then statements (‘one-armed’)
if B S
• For loops
for v ← N to M do
S
which are semantically equivalent to
v ← N
while v ≤ M do
S
v ← v + 1
9
CRICOS No. 00213J
a university for the worldreal R
Pseudocode notations
• Iteration (post-tested)
repeat
S
until B
which is semantically equivalent to
S
while ¬B do
S
10
CRICOS No. 00213J
a university for the worldreal R
Pseudocode notations
• Primitive types (numbers, characters, Booleans, etc)
3.1425926, ‘c’, true
• Arrays (also known as vectors)
A[i]
• Sets
{4, …, 10}
11
CRICOS No. 00213J
a university for the worldreal R 12
Algorithm description in pseudocode
ALGORITHM ArrayMax(A[0..n − 1])
// Given an array A, of length n ≥ 1, returns
// the value of the largest number in A
max ← A[0]
for i ← 1 to n − 1 do
if A[i] > max
max ← A[i]
return max
CRICOS No. 00213J
a university for the worldreal R
Algorithm efficiency and algorithm analysis
• Algorithm efficiency is usually represented as a mathematical
function describing the resource requirements of the algorithm in
terms of the amount of data the algorithm must process
• There are two main efficiency measures for the efficiency of
algorithms:
– Time efficiency – a mathematical function describing the
amount of time an algorithm takes in terms of the amount of
input to the algorithm
– Space efficiency – a mathematical function describing the
amount of space (storage) an algorithm takes in terms of the
amount of input to the algorithm
• In computer science, algorithm analysis is the determination of the
efficiency of algorithms
• In this unit, we focus on the time efficiency of algorithms
13
CRICOS No. 00213J
a university for the worldreal R
Analysis of the time efficiency of an algorithm
• To measure the time efficiency of an algorithm we could implement
it as a program and measure the program’s execution time
experimentally
– However, the results will depend on the particular choice of
computer processor, programming language, language compiler
or interpreter, and operating system, as well as the system load
when the experiment was performed
• Instead, analysis of the efficiency of an algorithm is done in a
language and machine independent way.
14
CRICOS No. 00213J
a university for the worldreal R
Analysis of algorithms
• In the worst case, the computation time of this algorithm can be
approximated by the following mathematical function:
T(n) = c1+(c2+c3)(n-1)+c4
where c1, c2, c3 and c4 are machine dependent.
15
ALGORITHM ArrayMax(A[0..n − 1])
// Given an array A, of length n ≥ 1, returns
// the value of the largest number in A
max ← A[0] c1
for i ← 1 to n − 1 do
if A[i] > max c2
max ← A[i] c3
return max c4
CRICOS No. 00213J
a university for the worldreal R
Analysis of algorithms
• For a particular machine, c1 = 3 microseconds, c2 = 2 microseconds, c3
= 3 microseconds and c4 = 1 microsecond
T(n) = 3+(2+3)*(n-1)+1 = 5n -1
• When n = 10, T(10) = 5*10 -1 = 49 microseconds
• When n = 100, T(100) = 5*100 -1 = 499 microsecond
• When n = 1000000, T(1000000) = 5*1000000 -1 = 4999999 microseconds
16
CRICOS No. 00213J
a university for the worldreal R
Computers are fast and memory is cheap,
so why worry about efficiency?
• Consider an algorithm which solves a problem of size n by
processing 2n cases, that is, T(n) = 2n , implemented on a computer
which processes each case in 0.000000005 seconds:
Problem size Solution time
10 5.1 microseconds
20 5.2 milliseconds
30 5.4 seconds
40 1.5 hours
50 9.3 weeks
60 183 years
70 1872 centuries
80 192 million years
17
CRICOS No. 00213J
a university for the worldreal R
Demo – the Tower of Hanoi problem
• Given a tower of discs, initially stacked in increasing size on one of
three rods, the objective is to transfer the entire tower to one of the
other rods.
• Rules:
– Only one disc can be moved at a time
– No disc may be placed on top of a smaller disc
– All discs must be on a rod after a move
18
A B C
CRICOS No. 00213J
a university for the worldreal R
The basic ideas behind the algorithm for
solving the Tower of Hanoi problem
• It is extremely difficult to design an iterative algorithm to solve the
problem. But, it is straightforward to come up with a recursive
algorithm.
19
To move 4 discs from rod A to rod C
Step 1: move the top 3 discs from rod A to rod B;
Step 2: move the bottom disc from rod A to rod C;
Step 3: move the 3 discs from rod B to rod C.
A B C
A B C
A B C
A B C
CRICOS No. 00213J
a university for the worldreal R
Algorithm description
20
ALGORITHM TowerOfHanoi(n, a, b, c)
// Find a solution to the problem of moving n disks from rod a to rod c
// using b as a temporary rod without violating the rules
// n is the number of disks; a is the start rod;
// b is a temporary rod; c is the end rod
if n > 0
TowerOfHanoi(n-1, a, c, b)
move top disk from a to c
TowerOfHanoi(n-1, b, a, c)
CRICOS No. 00213J
a university for the worldreal R
Demo – Tower of Hanoi
21
CRICOS No. 00213J
a university for the worldreal R
Data Structure
• In computer science, a data structure is a way to store and
organise data in order to facilitate access and modification
• There are many popular data structures, such as
– Array
– Linked list
– Binary tree
– Tree
– Graph
– Hash table
• No single data structure works well for all purposes
• Thus, it is important to know their properties, strengths and
limitations
22
CAB301 Algorithms and Complexity��Lecture 1 (Part 2): Introduction to Algorithms and Complexity
Aims of this lecture
References
What is an algorithm?
Pseudocode
Pseudocode notations
Pseudocode notations
Pseudocode notations
Pseudocode notations
Pseudocode notations
Pseudocode notations
Algorithm description in pseudocode
Algorithm efficiency and algorithm analysis
Analysis of the time efficiency of an algorithm
Analysis of algorithms
Analysis of algorithms
Computers are fast and memory is cheap,�so why worry about efficiency?
Demo – the Tower of Hanoi problem
The basic ideas behind the algorithm for solving the Tower of Hanoi problem
Algorithm description
Demo – Tower of Hanoi
Data Structure