### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# D1 - Chapter 1- Algorithms

No description
by

## Peter Scott

on 9 September 2016

Report abuse

#### Transcript of D1 - Chapter 1- Algorithms

me creating art
What is it?
Flow Charts
combustion!
meeting the big cheese!
pick up kids
Decision Mathematics is an area of mathematics that only deals with discrete data.
with
Mr Scott

Decision
Mathematics

CHAPTER 1:
Algorithms

An Algorithm is a set of precise instructions which if followed will solve a problem.
A flow chart is a visual way of providing instructions for an algorithm
Rectangular blocks contain operations to be carried out. They only have one route leading from them.
Diamond blocks contain YES/NO questions and have 2 routes leading from them.
Oval shaped blocks indicate a terminus. They show you where the algorithm starts or stops.
Question
Implement this algorithm and state what the algorithm actually produces
START
STOP
A = 1
B = A
2
Is
B 100
>
Write B
A = A+1
yes
no
Create a flow chart that (
without using a divide operation
) checks whether a number is divisible by 9
Lesson 1
Sorting Algorithms
Lesson 2
This lesson we are going to have a look at 2 different types of sorting algorithms.
Bubble Sort
Quick Sort
and
you will need to learn these so you can implement them in an exam.
A sorting algorithm is a data processing task that will sort an unordered list into alphabetical or numerical order.
The first is the bubble sort algorithm
1) Start at the beginning of the list. Pass through the list and compare adjacent values . For each pair of values...
if they are in order, leave them
if they are not in order, swap them
2) When you get to the end of the list repeat step 1
3) When a pass is completed without any swaps, the list is in order.
Example: Use the bubble sort to arrange this list in ascending order:
24, 18, 37, 11, 15, 30
24 18 37 11 15 30
1st comparison:
swap
2nd comparison:
leave
3rd comparison:
swap
4th comparison:
swap
5th comparison:
swap
18 24 37 11 15 30
18 24 37 11 15 30
18 24 11 37 15 30
18 24 11 15 37 30
18 24 11 15 30 37
End of first pass
After the second pass the list becomes:
18 11 15 24 30 37
After the third pass the list becomes:
11 15 18 24 30 37
The fourth pass produces no swaps so the list is in order
In an exam you may be asked to show each comparison for 1 pass or just the state of the list after each pass
The other sort you need to learn is the
Quick Sort
The
pivot
is the number in the middle of a group or if there is an even amount in the group then it is the number to the right of the middle.
The quick sort is more efficient because it uses a
PIVOT
to split a group into sub groups.
2)Write down all the items that are less than the pivot, keeping their order, in a sub-list.
3) Write down the pivot.
4) Write down the remaining items (those greater than the pivot) in a sub-list
5) Apply steps 1-4 to each sub-list.
6) When all items have been chosen as pivots stop.
1) Choose the item at the midpoint of the list to be the first pivot.
Example: Use the quick sort to arrange this list in ascending order:
21 24 42 29 23 13 8 39 38
Each number has been chosen as a pivot so the list is in order
choose the pivot
write all the numbers below 23
write the pivot
write the rest
select the new pivots for the sub-groups
repeat the process for each subgroup
repeat the process for each subgroup
Ok, Lets try exercise 1C!
LMAO! :)
Binary Searching &
Bin Packing

Lesson 3
Bin packing is a problem in mathematics that involves fitting a set of different sized
boxes
into
bins
of a set size. The
question is what order do you pack the boxes so as to use the least amount of bins as possible!
You need to learn 3 different packing algorithms
1) First-Fit
2) First-Fit Decreasing
3) Full Bin
First-Fit
Lower Bound
To find the lower bound ie. the minimum number of bins that could be possible
(not the same as the minimum number possible),
just imagine all the boxes could be cut up and fill each bin to the brim. How many bins would you need then?
Add together the heights of all the boxes then divide by the height of the bins. If you get a decimal answer, round it up.
1) Take the items in the order given.
2) Pack each item in the first available bin that can take it. Start from bin 1 each time.
First-Fit Decreasing
1) Reorder the items so that they are in descending order.
2) Apply the first-fit algorithm to the reordered list.
Full-bin Packing
1) Use observation to find combinations of items that will fill a bin. Pack these items first.
2) Use First-fit to pack the rest.
Disadvantage: Unlikely to give a good solution
Advantage: Usually gives a fairly good solution and is easy to do.
Disadvantage: You might not get the optimal solution
Advantage: Usually gives a good solution
Disadvantage: Difficult to do, especially when there are lots of awkward shaped boxes.
CHAPTER 2:
Graphs and Networks

Graph Theory is a branch of mathematics where we turm real life problems into a mathematical model.
The Google Maps car has to get footage of all these roads. What path should it take so that it uses the least amount of fuel?
21 13 8
21 13 8 23
21 13 8 23 24 42 29 39 38
21 24 42 29 23 13 8 39 38
21 13 8 23 24 42 29 39 38
8 13 21 23 24 29 42 39 38
8 13 21 23 24 29 42 39 38
8 13 21 23 24 29 38 39 42
Next up is the
Binary Search Algorithm
It's used to find an item in an
ordered
list and give its position (for example a name from a list of names).
Here's the algorithm to search an ordered list of size
n
for a target
T
.

1) Select the middle item in the list, m.
n+1
2
use
and round up if necessary
2)
(i) if T=m, the target is located and the search is complete,
(ii) if T is before m, it cannot be in the second half of the list, so that half, and m, are discarded.
(iii) if T is after m, it cannot be in the first half of the list, so that half, and m, are discarded.
3) Repeat steps 1 and 2 to the remaining list until T is found.
Lets use the algorithm to locate Connock from this list.
1) Berry
2) Connock
4) Sully
5) Tapner
6) Walkey
7) Ward
8) Wilson
Bin Packing
try,

Exercise 1E
Question 3
try
Execise 1D
Question 3a
Full transcript