Algorithms (PAPER 2) Flashcards
What are the three key techniques for computational thinking
- Give a brief description of each
- Decomposition
- breaking a complex problem into smaller problems and solving each individually
- Abstraction
- picking out important information and ignore the specifics that do not matter
- Algorithmic Thinking
- a logical way of getting from the problem to the solution. If the steps taken follow an algorithm then they can be reused and adapted to solve similar problems in the future
What is pseudocode
code that is not an actual programming language but follows a similar structure
Why is using pseudocode helpful (2)
- don’t have to worry about syntax (finer details)
- easy to convert into code
Why should pseudocode not be vague
so that it can be converted into code easily
What are boxes with rounded corners used for in flow charts
terminals - beginning and end
What are parallelogram boxes used for in flow charts
anything that is taken out or put into the algorithm
What are rectangular boxes used for in flow charts
general instructions, processes and calculations
What are diamond boxes used for in flow charts
decisions, usually yes or no questions
What are arrows used for in flow charts
connects boxes and show the direction that should be followed
What are sub programs in flow charts
references to other flow charts
What is a sequence in a flow chart
a way to get from start to finish
What is a selection in a flow chart
when there are multiple ways to get from start to finish
What is an iteration
a loop that allows you to repeat a task
What are the two common types of search algorithm
- do the terms have to be sorted or not
Binary Search - the terms must be sorted
Linear Search - the terms can be sorted or unsorted
How does a binary search work
- find the middle item ( (n + 1) / 2 )
- If this is the item then stop
- If not compare the terms - if it is after, then delete the first half and vice versa
- repeat until the item is found
How does a linear search work
- look at first item
- if this is the item then stop
- else look at the next term
- repeat until item is found
What are the three common types of sorting algorithm
- Insertion Sort
- Bubble Sort
- Merge Sort
What are the steps to bubble sorting
1 - Look at first two items
2a - If they are in the right order, leave them.
2b - If they are in the wrong order, swap them
3 - Move to the next pair and repeat step 2
4 - Repeat step 3 until the end of the list (1 pass)
5 - Repeat 1-4 until there are no swaps in a pass
What is a pass
when you reach the end of a list during a bubble sort
What are the pros of using bubble sort (3)
- simple algorithm that can be easily implemented on a computer
- efficient way to check if a list is already in order
- Doesn’t use much memory as all sorting is done using the original list
What are the cons of using bubble sort (2)
- inefficient way to sort a list
- does not cope well with a large list of items
What is the largest amount of comparisons that must be done when bubble sorting a list of ‘n’ items
n ( n - 1 ) / 2
What two facts does merge sort capitalise on
- small lists are easier to sort than large lists
- It is easier to merge two sorted lists than two unsorted lists
What are the steps to merge sorting
1 - Split the list in half (sub-lists)
2 - Keep repeating step 1 until all the lists have only 1 item
3 - Merge pairs of sub-lists so that each sub-list has twice as many items. Sort the items into the right order each time
4 - Repeat step 3 until all the sub-lists have formed one list
