Algorithms Flashcards
What is abstraction?
Hiding or removing unnecessary data to keep something simple
What is decomposition?
Breaking down a problem into smaller subproblems
What is algorithmic thinking?
Identifying the steps involved in solving a problem
What symbol is used to represent an input in a flow chart?
Parallelogram
What symbol is used to represent an output in a flow chart?
Parallelogram
What symbol is used to represent a decision in a flow chart?
Rhombus
What symbol is used to represent a process in a flow chart?
Rectangle
What symbol is used to represent a terminal in a flow chart?
Oval
What symbol is used to represent a subroutine in a flow chart?
Rectangle with two vertical lines near each end of the shape
What is used to connect each symbol in a flow chart?
An arrow
Name two examples of decomposition
- Flow charts
- Structure diagrams
What is a structure diagram?
A way of visually showing the breakdown of a program into individual steps (subroutines)
What are trace tables?
Tables used in testing that show every variable change in a program
When would you use a trace table?
- When testing
- When checking for logic errors
What is a syntax error?
An error that will prevent the code from executing
What is a logic error?
An error that will still allow a program to run, but it won’t work as intended
What are the 2 types of searching algorithm?
- Binary search
- Linear search
What are the 3 types of sorting algorithm?
- Bubble sort
- Merge sort
- Insertion sort
Why would you use a linear search over a binary search?
The list doesn’t need to be ordered
Why would you use a binary search over a linear search?
Because it is usually quicker
How does a linear search work?
Each element in the list is checked in order until the correct one is found
How does a binary search work?
- The midpoint of the list is checked
- If the value is higher than the element being searched for the middle element and all greater than it are discarded
- Otherwise the midpoint and all elements bellow it are discarded
- This happens until the desired element is found
How do you find the midpoint of a list?
Add the two end points (the element number, not the value) and divide them by 2
Which is the most efficient sorting algorithm?
Merge sort
Which is the least efficient sorting algorithm?
Bubble sort
How does a bubble sort work?
- During each pass the first two elements are checked and if in the wrong order is swapped, then the next two elements are checked
- Passes happen until one pass results in no swapping
How does a merge sort work?
- The list is divided into individual elements
- Each element is ordered in a sublist with the one next to it
- The sublists merge whilst being ordered until there is only one list
What is computational thinking?
The use of computers to solve a problem
