Topic 1 Problem Solving Flashcards
What is an algorithm?
A step-by-step procedure for solving a problem or carrying out a task. It is not programming code.
Why are algorithms needed?
To improve efficiency by removing the need for human input.
Describe the algorithm construct - SEQUENCE
Instructions provided and executed in the correct order.
Describe the algorithm construct - SELECTION
Choosing which part of an algorithm to run based on a condition being true or false.
Describe the algorithm construct - ITERATION
Steps in an algorithm are repeated for a set number of times, or until a condition is met.
How might algorithms be represented?
Pseudo-code / Flowcharts / Structured English.
What is Pseudo-code?
A way of expressing an algorithm in English, that resembles a computer language.
What is a flowchart?
A diagrammatic way of representing an algorithm using symbols/text linked with arrows to show the ‘flow’ through the algorithm.
In flowcharts, what symbol is used to represent the start/end?
Rounded rectangle.
In flowcharts, what symbol is used to represent a decision/selection
Diamond, with two possible outcomes, Yes/No, True/False etc.
In flowcharts, what symbol is used to represent a process?
Rectangle.
In flowcharts, what symbol is used to represent control passing between other symbols?
Arrow.
In flowcharts, what symbol is used to represent a subroutine?
Rectangle, with an extra line at both sides.
What is a dry-run?
Using a pen/paper to investigate the FUNCTIONING of an algorithm.
What is the purpose of a trace table?
To write down (pen/paper) the values of each variable during the execution of an algorithm.
What is meant by a syntax error?
An error in the language used, eg PINT instead of PRINT
What is meant by a logic error?
An error which produces an incorrect result/output. Eg Multiplies instead of divides.
What is meant by a run-time error?
An error that would cause the program to crash during execution. Eg divide by zero.
Describe the linear search algorithm.
An attempt to find an item in an array which starts at the beginning of the array, checks each item in turn, stops when the item is found, or the end of the array is reached.
Describe the binary search algorithm.
Array must be sorted first. Select the middle value and compare with the search item. If the search item is lower, discard the middle value and the higher items to the right. If the value is higher, discard the middle value and the lower items to the left. Repeat until the search item is found, or not in the list.
Describe the bubble sort algorithm to sort into ascending order.
Go through the array starting at the second item. Compare this with the value before it. If first value is higher than second value, swap the items. Repeat this until all items are in their correct place.
Describe the merge sort algorithm.
An array is divided into two repeatedly until each array has only one item. The arrays are then progressively merged with the items into the correct order.
What is meant by decomposition?
Breaking a large problem down into sub-problems or components. These smaller components are easier to understand and solve. Once all of the components are solved, the large problem is solved.
What is meant by abstraction?
Identifying the essential elements of a real world scenario needed for use in an algorithm/program, and ignoring all non-essential elements. Eg Google Maps shows roads/names/main buildings as opposed to a photograph in Google Earth which would show every detail.
