2.1 Algorithms Flashcards
What is Computational Thinking?
Computational thinking involves taking a complex problem and breaking it down into a series of small, more manageable problems. Each of these smaller problems can then be looked at individually.
What are three main principles of computational thinking
- Abstraction
- Decomposition
- Algorithmic thinking
What is Abstraction and give an example
- *The process of removing unnecessary details and including only the**
- *relevant details. It is a method of computational thinking that focusses**
- *on what is important in problem solving.**
Example Sat Nav
We have to ask ourselves what is important and not important
Abstraction makes it clear to suggest a function or process in a simple and efficient manner.
One way to design an algorithm we could use flowcharts to represent the algorithm visually
Abstraction allows us to create a general idea of what the problem is and how to solve it. The process instructs us to remove all specific detail and any patterns that will not help us solve our problem. This helps us form our idea of the problem. This idea is known as a ‘model’.
Consider the problem of how a program might be required to calculate the area of any rectangle. All rectangles share general characteristics:
- a width
- a height
- area = width × height
When abstracting, certain details are discarded but others are kept:
- all rectangles have a width, but for the program design the actual rectangle width is not needed
- all rectangles have a height, but for the program design the actual rectangle height is not needed
- area is always width × height
To solve this problem, all the program needs to be able to do is input a width and a height, then calculate the area from those numbers. The actual numbers are irrelevant - they change with every rectangle - and so are discarded.
An example of abstraction is the London Underground map. It details tube and rail lines and the stations that are on them. That is all that is required for a passenger to be able to plan a journey from one station to another. Other details, such as real geographical location, distance between stations, depth underground and number of platforms are not included as they are irrelevant to journey planning on the Underground.
What is decomposition?
- *The process of breaking a complex problem down into smaller more**
- *manageable parts. Dealing with many different stages of a problem at**
- *once is much more difficult than breaking a problem down into a**
- *number of smaller problems and solving each, one at time.**
e.g. Crossing a road.
What are the advantages of Decomposition?
- Makes problems easier to solve as Different people can work on different parts of a problem at the same time.
- Reducing Development time
- Program components developed in one program can be used in other programs.
What is an Algorithm?
An algorithm is a logical, step-by-step process for solving a problem.
Algorithm production is part of algorithmic thinking, an important concept in computational thinking. This focuses on how a desired solution can be reached by identifying the steps needed to get there.
What is algorithmic thinking?
- *A way of getting to a solution by identifying the individual steps needed.** By creating a set of rules, an algorithm that is followed
- *precisely, leads to an answer.**
Algorithmic thinking allows solutions to be
automated.
What is an input?
- Anything which needs to be supplied to the program
- Often input by the user
- Consider an appropriate variable name and data type for the input
What is a process?
- Consider what calculations need to be performed while the programming is running
- Does data need to change formats or data types
What is outputs?
- Consider what your program need to output
- Consider what form this output need to take
- Consider an appropriate variable name and data type for any output.
Draw the different types of flow diagrams
What are the two types of error?
Syntax errors - errors which break the grammatical rules of the programming language. They stop it from being run/translated
Logic Errors - Produce an unexpected output. They will not stop the program from running.
What are Logic Errors?
- Logic errors are errors which produce unexpected output
- On their own they won’t stop the program running.
What are Trace Tables used for?
Trace tables are a great way to spot logic errors
They show the input and the expected result.
How does a binary search work?
A binary search is an efficient method of searching an ordered list.
A binary search works like this:
- *1. Start by setting the counter to the middle position in the list.**
- *2. If the value held there is a match, the search ends.**
- *3. If the value at the midpoint is less than the value to be found, the list is divided in half. The lower half of the list is ignored and the search keeps to the upper half of the list.**
- *4. Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.**
- *5. The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.**
- A binary search is a much more efficient **algorithm** than a linear search. In an ordered list of every number from 0 to 100, a linear search would take 99 steps to find the value 99.
- A binary search would only require seven steps.
- However, a binary search can only work if a list is ordered.
How does a bubble sort work
- A bubble sort is the simplest of the sorting **algorithms**.
Bubble sorts work like this:
- Start at the beginning
- Compare the first value in the list with the next one. If 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
- Once you have reached the end. Go back to the start of the list.
- Each run through the list, from start to finish, is known as a pass. The bubble sort continues until a pass is made where no values have been swapped.
- At this point, the list is sorted.
How does a merge sort work?
part 1
- A merge sort uses a divide and conquer technique . 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.
How does Insertion Sort work?
An insertion sort is less complex and efficient than a merge sort, but more efficient than a bubble sort.
The insertion sort inserts each item into its correct position in a data set one at a time
An insertion sort compares 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.
What are all the different flowchart diagrams?
How do you use sub programs in flowdiagrams?
Put the name of the function in the terminator
