Algorithms

What is decomposition?

Breaking a complex problem down into smaller problems and solving each one individually

What is algorithmic thinking?

A logical way of getting from the problem to the solution

What is abstraction?

Picking out the important bits of information from the problem, ignoring the specific details that dont matter

What is pseudocode? What are the advantages of it?

Pseudocode clearly shows an algorithms steps without worrying about the finer details

• Quick to write

• Easy to understand

What do flowcharts do?

A flowchart is a diagram that visually represents the steps and decisions in a process or workflow

What does the box with rounded corners show in a flowchart?

The beginning/end of the algorithm

What is the parallelogram box in a flowchart?

Anything thats put into or taken out the algorithm

What does is rectangular box in a flowchart?

General instructions, calculations or processes

What is the dimond box in a flowchart?

A decision

What is the rectangle box with lines in a flowchart?

A sub program

What is the arrow in a flow chart?

Shows which way to follow and connects boxes

Describe sequences flowcharts

A flowchart where there is only one way from start to the end

Describe selections flowcharts

A flowchart with selections/mutiple ways to get from start to stop

Describe iterations flowcharts?

Contains a loop which allows you to repeat a task

What does a binary search do?

Looks for items in a ordered list

How is bineary search carried out?

• Find the middle item in the ordered list ((n + 1) / 2 = the middle number - round up if neccesary)

• If this is the item your looking for, stop the search

• If not, compare the item you looking for with the middle item and figure out which side of the middle item it will be on

• Remove the side (first half or second half) the item your looking for is not on

• Youll be left with a list half the size of the original list

• Repeat the steps on the smaller list until you found your item

What does linear search do?

Looks for items on unordered list

How is linear search carried out?

• Look at the first item in the unordered list

• If this is the item your looking for - stop the search

• If its not the item, look at the next item on the list

• Repeat these steps until you find iy

What does a bubble sort do?

Compares pairs of items and sorts an unordered list

How is a bubble sort carried out?

• Look at the first two items of the list

• If they are in the right order you dont have to do anything but if they are in the wrong oder, swap them

• Move on to the next pair of items (2nd and 3rd)

• Repeat these steps until there is no more to swap

What are the advantages of bubble sorts?

• Simple algorithm that can be easily carried out on a computer

• Efficient way to check a list is already in order

• Doesnt use much memory

What are the disadvantages of bubble sorts?

• Inefficient way to sort a list

• Does not cope well with large lists

What does a merge sort do?

Splits the list apart then merges it back together into the right order

How are merge sorts carried out?

• Split the list in half (the smaller list is called the sub-list)

• Keep repeating step one until all the list only contain one

• Merge pairs of sub-lists so that each sub-lists has twice as many items

• Order it while doing this

• Repeat step three until you’ve merged all the sub-lists

What are the advantages to merge sorts?

• More efficient and quicker then bubble sort

• Consistent running time regardless of how unordered the items on the original list are

What are the disadvantages to merge sorts?

• Slow for small lists

• Even if a list is already sorted it stil goes through the whole process

• Uses more memory

What does insertion sorts do?

Orders items on a list as it goes

How are insertion sorts carried out?

• Look at the second item on the list

• Compare it to all items before it and insert the number into the right place

• Repeat these steps while going down the rest of the list until its ordered

What are the advantages to insertion sorts?

• Very efficient

• Easy to code

• Works well with short lists

• Doesnt require a lot of memory

• Quick to add items to a already ordered list

• Quick at checking the list is already ordered

What are the disadvantages to insertion sorts?

• Doesnt cope well with very large lists