**What is it?**

Flow Charts

the day i learnt about

combustion!

meeting the big cheese!

buy milk

pick up kids

Decision Mathematics is an area of mathematics that only deals with discrete data.

**with**

Mr Scott

Mr Scott

**Decision**

Mathematics

Mathematics

**CHAPTER 1:**

Algorithms

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

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.

Advantage: Quick to do

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

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.

(if T is not found it is not in the list)

Lets use the algorithm to locate Connock from this list.

1) Berry

2) Connock

3) Ladley

4) Sully

5) Tapner

6) Walkey

7) Ward

8) Wilson

**Bin Packing**

try,

Exercise 1E

Question 3

try

Execise 1D

Question 3a