Algorithms Flashcards
What is abstraction
Identifying the details in a problem that are important to solving the problem and focusing on them while ignoring irrelevant detaisl
What is decomposition
Breaking down a problem into smaller problems and solving each one individually
Define computational thinking
Tackling a problem through decomposition, abstraction and algorithmic thinking
Define algorithmic thinking
Logical way of getting from a problem to a solution by identifying the steps
Advantages of pseudocode
quick to write
easily converted into a programming lanuage
Briefly describe the steps for linear search
Look at the first item in the ordered list
If this is the item you are looking for then stop the search
If not look at the next item in the list
Repeat step 2-3 until you find the item or every item has been checked
Advantages/Disadvantages of linear search
simple easy can be done in an unordered list
Not as effective as other search algorithms - more suited for small data sets
Briefly describe the steps in binary search
Find the middle item in an ordered list
If this is what you are looking for then stop
If not compare the item you are looking for with the middle item
If it comes before the middle get rid of the second half vice versa
Repeat
Pros/Cons binary search
More efficient than linear search as it i sable to find a value in an array much faster
More suited for larger data sets
Briefly describe the steps for bubble sort
Look at first item two item in the list
If they are in the right order leave them, if they are in the wrong order swap them
Repeat step 2 with next to items
Repeat 3 until you reach the end of the list
Repeat step 1-4 until there are no swaps in a pas
Pros/Cons bubble sort
Very simple can be easily implemented
Inefficient to sort large numbers of data
Doesn’t use as much memory
Briefly describe the steps for insertion sort
Look at the second item in the list
Compare it to all the items before it and insert them into the correct place
Repeat tep 2 for each subsequenet item in the list until all of the item in the list has been sorted
Pros/Cons insertion sort
well-suited for small data ets and new data can be quicklu added to an already sorted data set
Good for small lists
Very quick at checking if the list is already ordered
Not well suited to large data set because significant amount of comparisons needed
Briefly describe the steps for merge sort
Split the lit in half
Repeat step 1 until each sub list contains one item
Merge pairs of sublist o that each sub list has twice as many items
Pros/Cons merge sort
More efficient and quicker than bubble sort
Consistent running time
Slower than other algorithms for small lists
Even if the list is already sorted still does the merge sort
Uses more memory than other algorithms
