algorithms

what is abstraction

• Abstraction is the process of removing unnecessary details of a problem to focus on the important features to implement in a solution

example of abstraction

• a computer game that simulates playing a sport

• a simulator such as a car or flight simulator,

• a map of a bus or train route in a city

What is decomposition?

• Decomposition is the process of breaking down a large problem into a set of smaller problems

Benefits of decomposition are:

• Smaller problems are easier to solve

• Each smaller problem can be solved independently of the others

• Smaller problems can be tested independently

• Smaller problems can be combined to produce a solution to the full problem

What is algorithmic thinking?

• Algorithmic thinking is the process of creating step-by-step instructions in order to produce a solution to a problem

what doe algorithmic thinking require

• Algorithmic thinking requires the use of abstraction and decomposition to identify each individual step

What is a searching algorithm?

• Searching algorithms are precise step-by-step instructions that a computer can follow to efficiently locate specific data in massive datasets

Two common searching algorithms are:

binary

linear

What is a binary search?

• A binary search keeps halving a dataset by comparing the target value with the middle value, going left if smaller, right if bigger, until it finds the value or realises it's not there

should data be ordered or unordered for binary search?

should be in order

step one binary search

Identify the middle value

step 2 binary search

Compare to the value you are looking for

step 3 binary search

IF it is the value you are looking for...

• Stop!

step 4 binary search

ELSE IF is it bigger than the one you are looking for... Create a new list with the values on the left of the middle value

step 5 binary search

IF it is smaller than the one you are looking for...

• Create a new list with the values on the right of the middle value

step 6 binary search

repeat with new list

What is a linear search?

• A linear search starts with the first value in a dataset and checks every value one at a time until all values have been checked

is linear search orders or unordered

Unordered

How do you perform a linear search?

1	Check the first value
2	IF it is the value you are looking for STOP!
3	ELSE move to the next value and check
4	REPEAT UNTIL you have checked all values and not found the value you are looking for

advantages of binary search

• Fast for large datasets

• Efficient for repeated searches

disadvantages binary search

• Dataset must be in order

• More complex to implement

advantages of linear search

• Works on unsorted datasets

• Faster (than binary) on very smalldatasets

• Simple to understand and implement

disadvantages of linear search

• Slow for large datasets

• Inefficient, starts at the beginning each time

What is a sorting algorithm?

• sorting algorithms are precise step-by-step instructions that a computer can follow to sort data in massive datasets efficiently

Three common sorting algorithms are:

• Bubble sort

• Merge sort

• Insertion sort

What is a bubble sort?

• A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in 'pairs' and swaps them if they are not in the correct order

how do you perform a bubble sort?

1	Compare the first two values in the dataset
2	IF they are in the wrong order... Swap them
3	Compare the next two values
4	REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)
5	IF you have made any swaps... REPEAT from the start (pass 2,3,4...)
6	ELSE you have not made any swaps... STOP! the list is in the correct order

What is a merge sort?

• A merge sort is a sorting algorithm that uses the 'divide and conquer' strategy of dividing a dataset into smaller sub-datasets and merging them back together in the correct order

How do you perform a merge sort?

1	Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)
2	Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)
3	REPEAT step 2 until all sub-datasets are merged together into one dataset

What is an insertion sort?

• The insertion sort sorts one item at a time by placing it in the correct position of an unsorted list. This process repeats until all items are in the correct position

• Values in the dataset can move as many places as they need

How do you perform an insertion sort?

1	Take the first value in the dataset, this is now the sorted list
2	Look at the next value in the dataset and compare it to the first value IF it is smaller insert it into the correct position to the left
3	ELSE Keep in the same position
4	REPEAT steps 2 & 3 until all values in the dataset have been compared, the list should now be in order