ALGORITHMS Flashcards
(16 cards)
What is DECOMPOSITION
breaking a complex problem into smaller problems and solving each one individually
WHAT IS ABSTRACTION
picking out important bits of information from the problem and ignoring specific detail which don’t matter
what is ALGORITHMIC THINKING
a logical way of getting from the problem to the solution.
what is computational thinking important
decomposition, abstraction and algorithmic thinking is used to turn a complex problem into small problems that a computer can then help to solve
whats the purpose of pseudocode
clearly shows and algorithm’s steps without worrying about the finer details of any particular programming language
why are the advantages of using pseudocode
- quick to write
- can be easily converted into any programming language
what are the 4 different shapes you need to know for flowcharts
start/end = rectangle with rounded corners
inputs/outputs = parallelogram
processes = rectangles
decisions = diamond
How does binary search work
- find the middle item in a ordered list
- check if this middle item is the item you are looking for
- if not, compare item you are looking for with this middle item. If item is greater than middle item, get rid of anything before the middle value. If item is less than middle item, get rid of anything after the middle value
- repeat steps 1-3 with the new list with less items until you find the item
how does linear search work
- look at first item in any list
- check to see if this item is the item you are looking for
- if not, move onto next item in the list
- repeat steps 2-3 until you find the item or you have check every item in the list
what are the advantages and disadvantages of binary and linear search
linear:
- simpler than binary search
- can be used on any list (ordered and unordered)
- inefficient, can only be used in small lists
binary:
- more efficient than linear search
- list has to be ordered
How does bubble sort work
- look at first two items in the list
- check to see if they are in the right order. If it is, don’t do anything. If it not, swap them around
- move onto next pair of items (2nd and 3rd) and repeat step 2
- repeat step 3 until you reached the end of the list (1 pass). Last item is now in the correct place
- repeat steps 1-4 until they are no swaps in a pass
what are the advantages and disadvantages of bubble sort
ADVANTAGES:
- simple algorithm
- efficient to check if list is already in order
DISADVANTAGES:
- inefficient way to sort a list
- not good for large lists binary
how does merge sort works
- split the list in half, creating 2 sub-lists
- repeat steps 1 until each list contains 1 item
- merge pairs of sub-lists so that each sublist has twice as many items. each time you merge, sort the items in the right order
- repeat steps 3 until all sublists are merged together
what are the advantages and disadvantages of merge sort
ADVANTAGES:
- more efficient and quicker than all the other sorting algorithms
- consistent running time
DISADVANTAGES:
- slower than other algorithms for small lists
- not efficient at checking if list is ordered or not
how does insertion sort work
- look at second item in a list
- compare it to all the items before it and insert into correct place
- repeat steps 2 for every item until last item has been inserted into correct place
WHAT ARE THE ADVANTAGES AND DISADVANTAGES OF INSERTION SORT
ADVANTAGES:
- can be easily coded
- efficient with small lists
- very quick to add items to a ordered list
- good at checking if list is in order
DISADVANTAGES:
- not good with large lists
