Computing GCSE 2.1- Algorithims

What are the principles of computational thinking?

Abstraction, decomposition, algorithmic thinking

What is the definition of decomposition?

breaking a complex program down into smaller problems and solving each on individually

What is the definition of algorithmic thinking?

a logical way of getting from the problem to the solution, if the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solver similar problems in the future

What is the definition of abstraction?

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

What may algorithmic thinking involve?

coming up with some logical steps to reach a descisions

How would computational thinking help to sort a list of product names into alphabetical order?

- one part of the decomposition might decide what alphabetical order means
- another part of the decomposition might look at comparing the entries
- abstraction will help the programmer focus on the important bits
- algorithmic thinking will put the tasks into a step by step process

What does the start/stop command look like and do in a flowchart?

the beginning and the end of the algorithm are put in boxes with rounded corners

What does the input/output command look like and do in a flowchart?

anything thats put into or taken out of the algorithm goes into a parallelogram box

What does the process command look like and do in a flowchart?

general instructions, process and calculations go in rectangular boxes

What does the decision command look like and do in a flowchart?

often a yes or no question are put in diamond boxes

What does the sub program command look like and do in a flowchart?

reference other flowcharts

What do arrows do in a flow chart?

connect boxes and show the direction you should follow, some boxes may have multiple arrows coming in or going out of them

What is a syntax error?

errors which break the grammatical rules of the programming language, they stop it from being run/translated

What is a logic error?

errors which produce unexpected output, on their own they wont stop the program running

What are the steps for a binary search?

1. find the middle item in ordered list
2. if this is the item youre looking for then stop the search
3. if not, compare the item youre looking for to the middle item
if it comes before the middle item, get rid of the second half of the list
if it comes after, get rid of the first half of the list
4. repeat steps 1-3 on the smaller list

What are binary searches used for?

looking for items in an ordered list

What are linear searches used for?

on an unordered list

What are the steps for a linear search?

1. look at the first item in the unordered list
2. if this is the item you're looking for then stop the search
3. if not then look at the next item on the list
4. repeat steps 2-3 until youve found the item or checked every item

What are pros of a linear search?

it is much simpler than a binary search, it can be used on any type of list it doesnt have to be ordered

What are cons of a linear search?

it is inefficient so only used on small lists

What are pros of a binary search?

once its been ordered its much more efficient than a linear search, in general it takes fewer steps which makes it more suitable for large lists of items

What is a bubble sort used for?

to sort an unordered list of items

What are the steps of a bubble sort?

1. look at the first two items in the list
2. if they are in the right order, dont do anything
if they are in the wrong order swap them
3. move onto the next pair and repeat step 2
4. repeat step 3 until you get to the end of the list- this is called one pass
the last item will be in the right place so dont include it in the pass
5. repeat steps 1-4 until there are no swaps left so everything is in the right order

What are pros of a bubble sort?

- it's a simple algorithm that can easily be implemented on a computer
- an efficient way to check if a lists already in order
- doesnt use very much memory as all the storing is done using the original list

What are cons of a bubble sort?

- is an inefficient way for sorting a list
- does not cope well with large lists as it is inefficient

What is a merge sort used for?

an example of a divide- and-conquer algorithm that takes advantage of
- small lists are easier to sort than large lists
- its easier to merge two ordered lists than two unordered lists
it splits the list apart and then merges it back together

What is the method for a merge sort?

1. split the list in half, start at the middle item
2. keep repeating step 1 until all the lists only contain one item
3. merge pairs of sub lists so that each sub-list has twice as many items
each time you merge sub lists, sort the items into the right order
4. repeat step 3 until youve merged all the sub lists together

What are pros of a merge sort?

- in general its much more efficient and quicker than the bubble sort and insertion sort algorithms for large lists
- it has a very consistent running time regardless of how ordered the items in the original list are

What are cons of a merge sort?

- it is slower than other algorithms for small lists
- even if the list is already sorted, it still goes through the whole splitting and merging process
- it uses more memory than the other sorting algorithms in order to create the separate lists

What is the method for an insertion sort?

1. look at the second item in the list
2. compare it to all items before it and insert it into the correct place
3. repeat step 2 for all the items in the list until the last number in the list has been inserted into the correct place

What are pros of insertion sorts over the other sorting algorithims?

- its an intuitive way of sorting things and can easily be coded
- it copes very well with small lists
- all the sorting is done on the original list so it doesnt require very much additional memory
- its very quick to add items to an already ordered list
- its very quick to add items to an already ordered list
- its very quick at checking that a list is already sorted

What is the main disadvantage of an insertion sort?

it doesnt cope well with very large lists