Component 2.2 - Algorithms And Programming Constructs Flashcards
What is an algorithm?
An algorithm is a set of instructions that can be used to solve a given problem
What two things must the instructions of an algorithm be?
- clear
- in the correct order to produce the solution
Algorithms are a ___ for writing a computer program to ___
Starting point, solve the given problem
What programming language should an algorithm be presented in?
Algorithms should be presented in a way that it can be used in different programming languages. It should NOT be in computer code
What is pseudo code?
Pseudo code is a way of writing instructions in plain english
What is a flowchart?
A flowchart is a diagram showing the instructions to be carried out in the order they should be carried out
What 3 things must a good algorithm be?
- Be finite - must not never end trying to solve a problem
- have well defined instruction (each step must be clear)
- be effective (it should give the correct result/solution)
What does a rounded rectangle mean in a flowchart?
Start/stop
What does a diamond mean in a flowchart?
Decision
What does a parallelogram mean in a flowchart?
Input/Output
What does a rectangle mean in a flowchart?
Operation
What does a circle mean in a flowchart?
Connector
What does a rectangle with two lines near each end mean in a flowchart?
Store/call subroutine
What are the three basic constructs used to design algorithms?
Sequence, selection and iteration
What is the sequence construct of an algorithm?
Algorithms consist of a series of instructions in a specific order. It is the sequence in which instructions must be carried out for the algorithm to work.
What happens if the sequence if an algorithm is not right?
Computers can only follow instructions in the order they are given, if the sequence is not right the computer will still follow the order they are given in
What is the selection construct of an algorithm?
A selection instruction is one where a decision must be made. This is the times in which an instruction in an algorithm may give different options
What is the iteration construct of an algorithm?
Sometimes an algorithm will need a series of steps to be carried out more than once. This is called iteration, often referred to as a loop in a program. (E.g. for next loop)
When will you use a loop with a count or rouge value?
You would use this when you do not know how many times you will need the instructions in the loop to be used
How does a count value loop work?
Count records the-number of times a process is carried out and when it reaches the required number the loop terminates
What is a rogue value?
A rogue value is a value that falls outside the range of possible values for the data that is being processed
How does a rogue galue loop work?
If there is a loop asking for inputs, storing them as var which must be positive, you could input -1 for var which will end the loop (following your code)
What does a sorting algorithm do?
A sorting algorithm will put items in a list into a particular order, alphabetic or numeric
What is merge sort?
Merge sort is a sorting technique based on the idea of ‘divide and conquer’
How is the idea of ‘divide and conquer’ presented in merge sort?
Merge sort first divides the list into two equal halves then combines them in a sorted list
How does the merge sort algorithm work?
Th merge sort algorithm divides lists into two equal halves, then splits the halves into halves and so on until on,y single items are left. It then combines them in the same way they were divided but in order.
What is bubble sort?
Bubble sort is a simple sorting algorithm based on the comparison of adjacent data items, swapping them if they are in the wrong order
What is the disadvantage of bubble sort?
It is not suitable for large data sets
How does bubble aort work?
1) Bubble sort starts by comparing the first two items in a List
2) If the first is smaller than the second it swaps them
3) It then moves onto items 2 and three and does the same
4) It keeps repeating steps 1-3 doing items 2,3 then 3,4 then 4,5 and so on
5) Once it reaches the end of the list it loops over and over again until, no swaps have been done
6) As no swaps means a sorted list
What is linear search?
Linear search is a very simple searching algorithm
How does linear search work?
Each item in the data set is compared with the search condition in sequence till the item is found or the end of the data set is reached. (Basically if you want to find 20, it goes through a list looking at each item one by one comparing it to 20, if it matches it has found it is successful, if it reaches the end of the list it has failed (item does not exist))
How can the efficiency of a search be measured?
You can measure the efficiency of a search by considering the number of comparisons that are made before the required item is found
Why is linear search inefficient?
Linear search may have to go through almost the whole list till items are found since items in the list are not ordered. It also has to go through the whole list to decide that an item doesn’t exist
What needs to be done for a search to be more efficient?
For a search to be more efficient, it is necessary to sort the data into order first
How does binary search work?
1) Firstly the list being searched is sorted
2) The search starts comparing the item requested to the item at the mid point
3) - If the item at the midpoint matches the search item it has been found
- If the item in the midpoint is greater than the search item all items to the right can be discarded (as they are greater)
- Opposite if it is less than
4) This process is repeated on the remaining data till the required item is found, or all items have been discarded
If binary search calculates the midpoint with a decimal place (e.g. 6.5) what item number is taken as the midpoint?
The midpoint is taken as the integer part of the result (6)
