Fundamentals of Algorithms

Topic 1

algorithm

Algorithms are a set of step-by-step instructions in order to produce a solution to a problem

decomposition

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

abstraction

the process of removing unnecessary details from a problem to focus on the important features for implementing a solution

systematic approach to problem solving

means being able to take a logical approach and use algorithmic thinking to solve a problem

what is psuedocode

is a text based tool that uses short English words/statements to describe an algorithm

program language

unlike the generic pseudocode, is specific to a programming language

flowcharts

are a visual tool that uses shapes to represent different functions to describe an algorithm

flowchart syntax

input

is data or information being entered/taken into a program before it is processed in the algorithm

process

is a doing action performed in the algorithm that transforms inputs into the desired output. The central processing unit (CPU) executes the instructions that define the process

output

is the result of the processing in an algorithm and usually the way a user can see if an algorithm works as intended

trace table

• is used to trace through an algorithm and to test algorithms and programs for logic errors that appear when an algorithm or program executes

• Trace tables can be used with flowcharts, pseudocode or program code

• A trace table can be used to:

  • Discover the purpose of an algorithm by showing output data and intermediary steps

  • Record the state of the algorithm at each step or iteration

algorithm efficiency

is how much time it takes to complete an algorithm

In programming, there is often more than one algorithm which can solve a problem

An example of this is a linear search and binary search as both find a value in a list, however, depending on the circumstances, one may be much faster than the other

searching algorithm

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

linear search

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

hA linear search can be performed even if the values are not in order

how to perform a linear search

Step	Instruction
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

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

• To perform a binary search the data must be in order!

• A binary search can be performed on datasets containing numbers or words.

Searching for a word instead of a number is the same process, except comparisons are made based on position in the alphabet (alphabetically) instead of numerical size

how to perform a binary search

comparing search algorithms

Searching Algorithm	Advantages	Disadvantages
Linear search	Works on unsorted datasets Faster (than binary) on very small datasets Simple to understand and implement	Slow for large datasets Inefficient, starts at the beginning each time
Binary search	Fast for large datasets Efficient for repeated searches	Dataset must be in order More complex to implement

sorting algorithms

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

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 to perform a merge sort

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

• One full run of comparisons from beginning to end is called a 'pass', a bubble sort may require multiple 'passes' to sort the dataset

• The algorithm is finished when there are no more swaps to make

how to perform a binary search

Step	Instruction
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

example of a binary search

5

2

4

1

6

3

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

comparing sorting algorithms

Sorting Algorithm	Advantages	Disadvantages
Merge sort	Suitable for large datasets Performs well no matter how unorganised the data is	Uses a lot of memory More complex to implement
Bubble sort	Simple to understand and implement	Slow for large datasets Inefficient, as it iterates through the data multiple times