Algorithms Flashcards
An algorithm
A series of steps taken to complete a task.
Two ways to present algos
Flow charts
Pseudo code
Decomposition is
Breaking down on large problem into several smaller sub problems
Decomposition advs
Easier for teams to tackle problems
Easier to solve
Abstraction
Removal of unecessary details from a problem
Abstraction is used in what and advs
Weather models
Makes it less cluttered and easier to see the problem
Computational thinking concepts
Algorithmic thinking
Abstraction
Decomposition
Algorithm symbols for Start/End Process Input/output Decisions
Oval
Rectangle
Parallelogram
Diamond with yes down and no to the side
3 basic programming constructs
Sequence
Iteration
Selection
Sequence
The order in which execution occurs
Selection (pseudocode)
If then else (pseudo code)
Choose between two options
Iteration (pseudocode) and types
Repetition of instructions
For loop - definite amount of times action must be repeated eg for 5
Repeat until - indefinite iteration - condition controlled - until it is true wont move on
While loop - action occurs only while the condition is true
Two search algorithms are
Linear search
Binary search
Linear search is
When data is unsorted, you start at the beginning and search through every item till you find it. Eg
Start at first name
Repeat
Examine current name
IF it’s the one you’re looking for THEN
END IF
UNTIL found = true
Binary search is
If the list is sorted in binary or alphabetical order. Repeatedly divide the the data in half till there is only item in the list
Eg
We are trying to find the number 100
We start at fifty
If the number at fifty is lower then we discard everything in the first half and keep on halving the second half till we find it
Linear search and binary search advantages and disadvantages
LS is hard for large items cos it will take longer
Binary is quicker but only works on sorted lists
Two ways to sort algorithms
Bubble sort
Merge sort
Bubble sort is
Repeatedly swapping adjacent elements into the correct order
Eg we want numbers of temp in ascending order it will keep 3&6 the way they are and swap 10& 9.
So from 3 6 10 9
It changes to 3 6 9 10
Merge sort
Stage 1 - list is divided in half until each sub list has a length of one
Stage 2 - each pair of sub lists are repeatedly merged to produce new sorted sub lists that then are in order eg
42 31 12 3
Becomes one length long
Then 41 & 31 are swapped & so is 12&3
So 3 12 31 41
Compare merge sort and bubble sort
Bubble sort is slow and inefficient for lists that are longer than 3 or 4
Merge sort is a difficult algorithm and hard for inexperienced users
