Computational Thinking, Algorithms And Programming Flashcards
What is abstraction?
A technique that simplifies a problem by removing unnecessary detail so that you can focus on the important parts that are relevant to the problem
Give two examples of abstraction in every day life
- Maps
- Money
What is decomposition?
Decomposition means breaking a complex problem into smaller, more manageable sub-problems.
Each smaller part can then be solved individually, before all the sub-solutions are combined to solve the original problem.
Give two advantages of decomposition
- Decomposition allows large teams to each take a part of a problem and work on it.
- Decomposition allows seemingly impossible problems to be solved by splitting them into simple tasks.
What is a structure chart?
- Structure charts are used to visually represent breaking a large problem down into the smaller parts that make it up.
- Each box represents a smaller problem to be solved.
- Lines show which bigger problem the box is a part of.
What is algorithmic thinking?
A way of solving problems by producing algorithms.
What is an algorithm?
An algorithm is a reusable set of instructions (a series of steps) to solve a given problem.
Give two examples of algorithms used in every day life
- Make a cup of tea
- Get dressed
How are algorithms written in computing?
- Algorithms can be written as a set of numbered steps to follow.
- A non-technical example of a written algorithm is a cooking recipe.
- In computing, we often represent algorithms using pseudocode or flow diagrams.
What is pseudo code?
- A way to write out algorithms using code-like statements.
- It is intended to be very readable, and easy to understand.
What is the purpose of pseudo code?
- Pseudocode isn’t a programming language.
- Pseudocode is used to plan algorithms, focusing on the logic and steps rather than language-specific syntax.
What is the main focus of pseudo code?
To set out the logic of an algorithm
What is a flow diagram?
- Flow diagrams are used to visually represent the steps that make up an algorithm.
- A standard set of shapes are used to represent different types of step.
- Arrows represent the flow of control, or what to execute next.
What part of a flow diagram does the oval represent?
Start or end of a program
What part of a flow diagram does the rectangle represent?
A process
What part of a flow diagram does the parallelogram represent?
Input or output
What part of a flow diagram does the diamond represent?
A decision;
* A decision has two labelled arrows coming out of it.
* The ‘Yes’ arrow is followed if the condition in the diamond was true, otherwise the ‘No’ arrow is followed.
Can pseudo code be run on the computer?
No
What is an identifier in an algorithm and how can it help with interpreting?
- Identifiers are the names of variables, constants, and subroutines.
- These often give strong clues about the purpose of an algorithm.
What is a comment and how does it help with interpretation?
- Comments are descriptions of the code.
- Comments will often state the purpose of a given algorithm.
- Comments are often the clearest way to identify an algorithm.
Give three examples of issues in algorithms
- Incorrect identifiers
- Incorrect operators
- Missing lines
How is a trace table used?
- You can draw a table with a column for each variable in the algorithm.
- Use this table to record the value of each variable, and carefully follow through the code until the end.
- Finally, the trace table should include your answer.
Give two methods of completing algorithms
- Identify the algorithm
- Produce a trace table
Give three examples of identifiers
- Subroutine name
- Variable name
- Constant name
What is meant by complete the algorithm?
State the output
What is a search algorithm?
A search algorithm is a set of instructions for finding a specific item of data within a data set.
What is an effective search?
An effective search is one which will always either find the solution or determine that the target data is not present.
What is an efficient search?
An efficient search will find the solution quickly regardless of its location within the data set.
Give two examples of search algorithms
- Linear search
- Binary search
How does a linear search work?
It checks every item until the one needed has been found
Give an example of pseudo code for a linear search
for item in dataset
if item == target then
return True
endif
endfor
return False
Give a pro and a con for linear searching
Pro
* Easy to implement
Con
* Slow on long lists
How does a binary search work?
- Split the list in then disregard the list that does not contain the item
- Repeat this until the item is found
Can binary searches be used on all lists?
No, the list must be ordered
Give a pro and a con of binary searches
Pro
* Faster than linear search
Con
* List must be ordered before searching
What is an efficient sorting system?
An efficient sort algorithm is one which can sort a dataset in a short time.
Give three sorting algorithms
- Bubble sort
- Insertion sort
- Merge sort
What is a sorting algorithm?
A sort algorithm is a set of instructions to arrange a dataset into a particular order.
How does a bubble sort work
Compares the first two items and swaps them if needed, this goes on through the whole list
Give two pros of a bubble sort
- Easy to implement
- Doesn’t use much memory
Give a con of bubble sorting
Not efficient
How does an insertion sort work?
Each item is checked then inserted into the correct place
Give two pros of the insertion sort
- Easy to implement
- Little memory used
Give a con of insertion sorting
- Not very efficient
How does a merge sort work?
- Split the first list into parts and order each item in each part.
- Once all the lists are ordered, merge them together
Give two cons of a merge sort
- Slow for small lists
- Needs additional memory
Give a pro of the merge sort
Very efficient
When is it a bad idea to use merge sort?
On a small list that is unlikely to grow
