2.1 Algorithms STARTED Flashcards
Define linear search
A sequence that checks every item in a list 1 by 1 until it finds the desired item.
Define binary search
A sequence that finds the desired item of a list according to the midpoints.
What happens if the midpoint is greater than the desired item?
It scraps the midpoint and the data to its left and checks again.
What happens if the midpoint is smaller than the desired item?
It scraps the midpoint and the data to its right.
Define bubble sort
Bubble sort makes multiple passes through a list. It compares items and changes those that are out of order. Each pass through the list places the next largest value in its proper place.
How are numbers sorted in bubble sort?
Compares 1st 2 items and swaps them if necessary.
Define pass
A full cycle of swapping (doesn’t mean list is sorted).
Define insertion sort
A more efficient version of bubble sort. Each pass would insert each number into its correct place.
How are numbers sorted in insertion sort?
Compares 1st 2 items and inserts the necessary item into its complete correct position rather than swapping them. Has 2 lists, unsorted and sorted.
Where is insertion sort very efficient?
A small data set or where data is mostly sorted. E.g. a pack of cards.
What is merge sort?
An efficient sequence that divides an unsorted list into sublists with 1 item each and merges the lists together until it has a complete sorted list.
Define computational thinking
Use of computers to solve problems.
Define abstraction
Representing “real world” problems in a computer using variables and symbols and removing unnecessary elements from the problem.
Define decomposition
Breaking down a large problems into smaller sub-problems.
Define algorithmic thinking
Identifying the steps involved in solving a problem.
Computational thinking
Describes the thought processes involved in understanding problems and formulating solutions in such a way that they can be carried out by computers
Decomposition
Reduces a problem into sub-problems or components. These smaller parts are easier to understand and solve
Decomposition is an example of what type of approach?
Divide-and-conquer
Abstraction
Identifies essential elements that must be included in the computer models of real-life situations and discards the inessential ones
What is pattern recognition sometimes called?
Generalisation
Pattern recognition is used to identify where constructs such as what can be used?
selection and iteration
Pattern recognition is used to identify where sections of code can be ______ (functions and procedures)
reused
Pattern recognition is used to recognise a problem that is similar to…
one you have solved in the past
Pattern recognition is used to reuse code, functions and procedures from past programs to…
carry out similar functions in a new program
Algorithmic thinking is a subset of computational thinking that involves…
defining a clear set of instructions to solve a problem
With algorithmic thinking, once a successful solution to a problem has been found…
it can be used repeatedly for the same problem
The process of adding up all the numbers and diving the total by the number in the set to calculate the mean is an example of…
Algorithmic thinking
Algorithms provide instructions needed to…
solve a problem
All computer programs are what?
Algorithms
An algorithm is a step-by-step procedure for…
solving a problem or carrying out a task
How are algorithms often used to improve efficiency?
By removing the need for human input - a computer following an algorithm can do things in split seconds compared to humans
What are the three constructs used in an algorithm?
Sequence, selection and iteration
Sequence
Instructions need to be given in the correct order
Selection
Decisions have to be made and a course of action selected
Iteration
Previous steps are repeated until there is a desired outcome
Once an algorithm has been written, it can be…
reused with slight changes for solving similar problems
Why do we reuse algorithms?
It is much quicker than starting from scratch each time
True/False: Algorithms can be displayed using pseudocode
True
Pseudocode is a way of expressing an algorithm in…
structured English that resembles a computer language
True/False: There is only one way to write pseudocode
False, there are many different varieties of pseudocode
Pseudocode uses what similar to those found in computer languages?
Commands, keywords and structures
Pseudocode can/cannot be understood by computers
cannot
Pseudocode is used to develop the logic of an algorithm without having to bother about what?
syntax
A human can/cannot follow the logic of an algorithm even if there are spelling mistakes or missing brackets
can
A human can follow the logic of an algorithm even if there are spelling mistakes or missing brackets but a computer…
cannot execute code if there are similar syntax errors
A solution in pseudocode is converted into…
a programming language such as Python or Java
How can you add comments to code?
// or #
Why are comments used in code?
To help others follow programmers’ logic, and to act as a reminder of the logic
How does indenting help with the logic of an algorithm?
It shows dependency
What does this symbol in a flowchart represent?
Start/stop
What does this symbol in a flowchart represent?
Input/output
What does this symbol in a flowchart represent?
A decision - shows yes/no or true/false decisiopns where there are two possible outcomes
What does this symbol in a flowchart represent?
A process - for example a calculation
What does this symbol in a flowchart represent?
A subroutine - shows a function or procedure that has its own flow diagram
What do lines in flow charts represent?
Control passing between symbols
What does the start/stop symbol in a flow chart show?
The start and end of an algorithm
What does the input/output symbol in a flowchart show?
Input or output of data
What does the decision symbol in a flowchart show?
Yes/no or true/false decisions where there are two possible outcomes
What does the process symbol in a flowchart show?
Data processing, for example a calculation
What does the subroutine symbol in a flowchart show?
A function or procedure that has its own flow diagram
When large amounts of data are searched, it is essential that the searching algorithm is as…
efficient as possible
What type of algorithm are linear and binary?
Standard search algorithms
