Computational Thinking (I) - Algorithms Flashcards
What is computational thinking?
The steps you take to find the best solution to a complex problem
Before a problem can be tackled, the problem itself - and the ways in which it could be solved - needs to be understood
What are the three key techniques of computational thinking?
Decomposition
Abstraction
Algorithmic Thinking
Give an example of computational thinking when planning a visit to the cinema
What does the following show?
Pseudocode
What are algorithms?
Sets of instructions
In real life – recipes / directions / game rues
In computer science – often written as pseudocode
What is pseudocode?
Pseudocode should show an algorithm’s steps without worrying about the finer details (e.g. syntax)
It should be quick to write and then easily converted to a programming language
What is pseudocode not?
A programming language
What should pseudocode be like for it to be useful?
Readable
Easy to interpret
Not too vague
Write an algorithm in pseudocode to calculate the salary of a worker after a 10% pay rise
input salary
newsalary = salary x 1.1
output newsalary
Write an algorithm in pseudocode to check is a password is 6 characters long and different from the username of a user logging into a website. If invalid, it should say why
What is a flowchart?
A flowchart is a diagram that represents a set of instructions
What do flowcharts normally contain?
Flowcharts normally use standard symbols to represent the different types of instructions
What are the symbols of a flowchart used for?
Symbols are used to construct the flowchart and show the step-by-step solution to the problem
Name, draw the image and give the usage for common flowchart symbols
Draw a flow diagram to ask what the best subject is (trying again if it isn’t computer science)
What can flowcharts be used for?
Planning out programs
What can flowcharts show?
Sequences, Selections and Iterations
What is a sequence?
Sequence – only one way from the start to the end
What is a selection?
Selection – multiple ways from start to stop
What is an iteration?
Iteration – contains a loop allowing for a task to be repeated
Draw a flowchart with a sequence
Draw a flowchart with a selection
Draw a flowchart with an iteration
What are the two main types of algorithm search?
Linear search
Binary search
Describe a linear search?
A linear search is the simplest method of searching a data set.
Starting at the beginning of the data set, each item of data is examined until a match is made. Once the item is found, the search ends
Write the instructions for a linear search
Find out the length of the data set
Set counter to 0
Examine value held in the list at the counter position
Check to see if the value at that position matches the value searched for
If it matches, the value is found. End the search
If not, increment the counter by 1 and go back to step 3 until there are no more items to search
What is the advantage / disadvantage of a linear search?
Simple (data does not have to be ordered)
Not efficient – if the search value is at the end of the list, the algorithm will need to go through all previous values first
Describe a binary search
Start by setting the counter to the middle position in the list (if a match the search ends)
If the value at the midpoint is less than the value to be found, the list is divided in ½. The lower ½ of the list is ignored and the search keeps to the upper ½ of the list (and vice versa)
The search moves to the midpoint of the remaining items. The step above continues until a match is made or there are no more items to be found.
What is the advantage / disadvantage of a binary search?
Much more efficient
Requires the list to be ordered
Complete a linear search to find the value 2 in the list
Position 0 (first item) is not value 2 – counter +1 Position 1 is not value 2 – counter + 1 Position 2 is not value 2 – counter + 1 Etc… Position 5 is value 2 – stop search
Complete a binary search to find the value 11 in the list
Midpoint = 8 (highest position) + 0 (lowest position) and dividing by 2 = 4
Midpoint = 8 (highest position) + 5 (lowest position) and dividing by 2 = 7 (r)
Midpoint = 7 (highest position) + 5 (lowest position) and dividing by 2 = 6
What are the three types of algorithm sorting?
Bubble
Merge
Insertion
Describe bubble sorting
Start at the beginning of the list.
Compare the first value in the list with the next one up. If the first value is bigger, swap the positions of the two values.
Move to the second value in the list. Again, compare this value with the next and swap if the value is bigger.
Keep going until the there are no more items to compare.
Go back to the start of the list
In a bubble sort, what is each run through known as?
A pass
Bubble sort the following (first two moves)
What are the advantages of a bubble sort?
Simple algorithm
Efficient way to check for a list is in order – only one pass
Doesn’t use much memory
What are the disadvantages of a bubble sort?
Inefficient to sort a list
Does not cope well with a very large list
Describe merge sorting
A merge sort uses a technique called divide and conquer.
The list is repeatedly divided into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined.
The process is then repeated until the list is recompiled as a whole.
Complete the first divide and conquer of a merge sort for the following
What does the following show?
Divide and conquer – merge sort
What are the advantages of a merge sort?
Efficient and quicker than bubble / insertion with large lists
Consistent running time regardless of how ordered the items are in the original list
What are the disadvantages of a merge sort?
Slower than other algorithms for small lists
Even if the list is already sorted still goes through the whole splitting and merging
Uses more memory than other sorting algorithms in order to create the separate lists
Describe an insertion sort
Comparing values in turn, starting with the second value in the list.
If this value is greater than the value to the left of it, no changes are made. Otherwise this value is repeatedly moved left until it meets a value that is less than it. The sort process then starts again with the next value.
This continues until the end of the list is reached.
Complete the first insertion sort for the following
What does the following show?
Insertion sorting
In an insertion sort, what happens when two adjacent values are compared?
If the second value is greater than the value to the left of it, no changes are made.
Otherwise this value is repeatedly moved left until it meets a value that is less than it.
List the advantages of an insertion sort
Intuitive and easily coded – copes well with small lists
Sorting on original list (minimal memory requirements)
Quick to add items on ordered list and quick at checking
List the disadvantages of an insertion sort
Doesn’t cope well with large lists
