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
In merge sorting, if a list has 9 items, how many items will be in each sub-list
4 in 1st
5 in 2nd
What are the pros of using merge sort (2)
- much more efficient and quicker than bubble sort and insertion sort for large lists
- consistent running time regardless of how ordered the items are originally
What are the cons of using merge sort (3)
- slower than other algorithms for small lists
- Even if the list is already sorted it still goes through the whole process
- uses more memory than the other algorithms to create separate lists
Which sorting algorithm is used by many programming languages such as Java, Python and Perl
merge sort
How does insertion sort
1 - look at second item in a list
2 - Compare it to all items before it and insert the number into the right place
3 - Repeat step 2 for all remaining items until the last number has been inserted into the correct place
What are the benefits and drawbacks of using a linear search over a binary search
BENEFITS - can be used on an unsorted list, much simpler
DRAWBACKS - much less efficient, poor with large lists,
What are the pros of using insertion sort (5)
- Easy to code
- Copes well with small lists
- does not require much additional memory
- quick to add items to an already ordered list
- quick at checking that a list is already sorted
What is the main disadvantage of using insertion sort
doesn’t cope well with large lists ( n ( n + 1 ) / 2 )
