Transcript Applied Mathematics

Discrete Mathematics
Algorithms
Introduction
Discrete maths has developed relatively recently. Its
importance and application have arisen along with
the development of computing.
Discrete maths deals with discrete rather than
continuous data and does not employ the continuous
methods of calculus.
Computers deal with procedures or
algorithms to solve problems and
algorithms form a substantial part
of discrete maths.
Algorithms
An algorithm is a procedure or set of instructions used
to solve a problem.
A computer programmes are algorithms written in a
language which computers can interpret.
The algorithm enables a person (or computer) to solve
the problem without understanding the whole
process
Sorting algorithms
A frequently needed operation on a computer is a “sort”
Such as sorting data into numerical order
e.g. Sort the following list into numerical order starting
with the smallest. (time how long it takes you)
3, 9, 10, 24, 2, 7, 1, 56, 43, 29, 36, 17, 4, 12,
77, 21, 100.
A computer will do this in much less than a second.
How do you know you have not made a mistake?
How would you cope with a list of 100 numbers or more?
Bubble sort.
Sorting algorithms
This algorithm depends on successive comparisons of
pairs of numbers.
• Compare the 1st and 2nd numbers in a list and swap
them if the 2nd number is smaller than the 1st.
• Compare the 2nd and 3rd numbers and swap them if
the 3rd is smaller.
• Continue in this way to the end of the list.
This procedure is called a pass
Bubble sort
Example :
Use a bubble sort to place the numbers in the list in order.
5, 1, 2, 6, 9, 4, 3.
Original
list
New list
5
1
1
1
1
1
1
1
5
2
2
2
2
2
2
2
5
5
5
5
5
6
6
6
6
6
6
6
9
9
9
9
9
4
4
4
4
4
4
4
9
3
3
3
3
3
3
3
9
This represents one pass and required 6 comparisons and
4 swaps
Bubble sort
The complete algorithm is written as:
Step 1
If there is only one number in the list then stop.
Step 2
Make one pass down the list comparing
numbers in pairs and swapping if necessary.
Step 3
If no swaps have occurred then stop. Otherwise
ignore the last element in the list and return to
step 1.
Example
The table shows the complete bubble sort carried out on the list
given on the previous slide.
Original
list
1st pass
2nd pass
3rd pass
4th pass
5th pass
5
1
1
1
1
1
1
2
2
2
2
2
2
5
5
4
3
3
6
6
4
3
4
4
9
4
3
5
5
5
4
3
6
6
6
6
3
9
9
9
9
9
(The numbers in purple are the ones which are ignored.)
Shuttle Sort
One disadvantage of the bubble sort is that you have to do a
final pass after the list is sorted to ensure the sort is complete.
The shuttle sort partially overcomes this problem.
Ist pass
Compare the 1st and 2nd numbers in the list and swap
if necessary.
2nd pass
Compare the 2nd and 3rd numbers in the list and swap
if necessary. If a swap has occurred, compare the 1st
and 2nd numbers and swap if necessary.
3rd pass
Compare the 3rd and 4th numbers in the list and swap
if necessary. If a swap has occurred, compare the 2nd
and 3rd numbers, and so on up the list.
Shuttle sort
Using the same list of numbers the table below shows a
shuttle sort
Original 1st pass 2nd pass 3rd pass 4th pass 5th pass 6th pass
list
5
1
1
1
1
1
1
1
5
2
2
2
2
2
2
2
5
5
5
4
3
6
6
6
6
6
5
4
9
9
9
9
9
6
5
4
4
4
4
4
9
6
3
3
3
3
3
3
9
The shuttle sort has involved the same number of swaps as
the bubble sort but 14 comparisons instead of 20.
Practice Questions
Exercise 1A page 5
The order of an algorithm
The efficiency of an algorithm is a measure of the “runtime” for the algorithm. This will often be proportional to
the number of operations which have to be carried out.
The size of the problem is a measure of its complexity. E.g.
in a sorting algorithm it is likely to be related to the
number of numbers in the list
The order of an algorithm is a measure of the efficiency of
the algorithm as a function of the size of the problem.
Examples of different orders of algorithms
Algorithm
Size
Efficiency
Order
A
n
5n
n or linear
B
n
n2 + 7n
n2 or quadratic
C
n
2n3 – 3n
n3 or cubic
Packing algorithms
In business and industry, efficient packing to make best
use of space is important and, for example, computerised
systems are used to organise storage.
First-Fit Algorithm
Place each object in turn in the first available space in
which it will fit.
This is the simplest algorithm but rarely lead to the most
efficient solution
Examples
Question
A small ferry has 3 lanes, each 25 metres long. The
lengths of the vehicles in the queue, in the order in which
they are waiting are:
3 5 4 3 14 5 9 3 4 4 4 3 11
Using the first-fit algorithm:
1
Lane 1
2
3
1st (3 m)
Lane 2
Lane 3
4
5
6
7
8
2nd (5 m)
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3rd (4 m)
4th (3 m)
5th (14 m)
9th (4 m)
10th (4 m)
6th (5 m)
8th ( 3 m)
7th (9 m)
11th (4 m)
12th (3 m)
The final 11 m vehicle does not fit. 16 m of space is
unused.
The solution could be improved by putting the 9 m vehicle
(no.7) in lane 3 and then the 11m vehicle (no13) will fit in
lane 2. 5 m of space is unused.
Increasing efficiency
First-Fit Decreasing Algorithm
Order all objects in decreasing size and then apply
the first-fit algorithm
Using the First-Fit Decreasing Algorithm:
First place the vehicles in order of decreasing size.
14
11
9
5
5
4 4 4 4 3 3 3
Then apply the First-Fit Algorithm
3
Example
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Lane 1
1st (14 m)
Lane 2
Lane 3
3rd (9m)
7th (4 m)
8th (4 m)
2nd (11 m )
4th (5 m )
9th (4 m)
5th (5 m)
6th 4 m)
10th (3 m) 11th (3 m) 12th (3 m) 13th (3 m)
This is more efficient than the first-fit algorithm and accommodates
all vehicles and leaving 3 m space.
Flow diagrams
A flow diagram is pictorial representation of an algorithm.
The shape of the box indicates the type of instruction.
Oval boxes are used for starting and
stopping, inputting and outputting data
Stop
Rectangles are used for calculations
or instructions.
Replace m by n
Is x > 5?
No
Yes
Diamond shapes are used for
questions and decisions
Notation
Replace m by n
means “take the number in pigeon hole n
and put it in pigeon hole m.” The notation
for this is m: = n
Similarly
m: = 2 means “put the number 2 in pigeon hole m.”
m: = m – 1 means “ take the number already in pigeon
hole m, subtract 1 and put the result back into pigeon
hole m.”
Pigeon holes are usually called “stores”.
An algorithm has a flow diagram below.
Example
Start
Read N
Is N
even?
(a) What is the output if
N = 57?
No
Yes
(b) What has the
algorithm been
designed to do?
R: = 1
N: = N-1
R: = 0
Write R to
the left of
any numbers
written so far
N: = ½ N
No
Is N = 0
Yes
Stop
Solution
(a) After 6 successive passes around the flow diagram, the
values of N and R are as follows.
Pass
N
R
Written
down
1
28
1
1
2
14
0
01
3
7
0
001
4
3
1
1001
5
1
1
11001
6
0
1
111001
The algorithm converts N into a binary number.
57  (1 32)  (116)  (1 8)  (0  4)  (0  2)  (11)  1110012
Practice questions
Cambridge Advanced Level Maths
Discrete Mathematics 1
Chapter 1
Exercise 1 A
Exercise 1 B
Miscellaneous Exercise 1