2.1 Algorithms

Question 1

What is Computational Thinking?

Answer 1

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.

Question 2

What are three main principles of computational thinking

Answer 2

• Abstraction
• Decomposition
• Algorithmic thinking

Question 3

What is Abstraction and give an example

Answer 3

• *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.

Question 4

What is decomposition?

Answer 4

• *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.

Question 5

What are the advantages of Decomposition?

Answer 5

• 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.

Question 6

What is an Algorithm?

Answer 6

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.

Question 7

What is algorithmic thinking?

Answer 7

• *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.

Question 8

What is an input?

Answer 8

• 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

Question 9

What is a process?

Answer 9

• Consider what calculations need to be performed while the programming is running
• Does data need to change formats or data types

Question 10

What is outputs?

Answer 10

• 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.

Question 11

Draw the different types of flow diagrams

Answer 11

Question 12

What are the two types of error?

Answer 12

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.

Question 13

What are Logic Errors?

Answer 13

• Logic errors are errors which produce unexpected output
• On their own they won’t stop the program running.

Question 14

What are Trace Tables used for?

Answer 14

Trace tables are a great way to spot logic errors

They show the input and the expected result.

Question 15

How does a binary search work?

Answer 15

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.

Question 16

Pros and Cons of Binary search:

Answer 16

• Can be done with letters as well as numbers
• More efficient than a linear search on average and on large sets

• Requires the data set to be in order of a key field.

Question 17

What are structure diagrams used for?

Answer 17

• Structure diagrams illustrate problem decomposition.
• They can be used for developers to understand a problem to code and to share with users during systems analysis.
• They are produced using a method known as step-wise refinement.
• Break problem down using decomposition into ever smaller components.
• Some areas of the program will needed breaking down more than others.
• The lowest level nodes should achieve a single task.
• These can then be coded as a single module or sub-program.

Question 18

How does a Linear Search Work

Answer 18

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 checked until a match is made. Once the item is found, the search ends.

A way to describe a linear search would be:

• *1. Find out the length of the data set.**
• *2. Set counter to 0.**
• *3. Examine value held in the list at the counter position.**
• *4. Check to see if the value at that position matches the value searched for.**
• *5. If it matches, the value is found. End the search.**
• *6. If not, increment the counter by 1 and go back to step 3 until there are no more items to search.**

Question 19

What are Pros and cons of Linear search:

Answer 19

• Doesn’t require the data set to be in order.
• Will work on any type of storage device.
• efficient for small data sets.

• Is very inefficient for large data sets

Question 20

How does a bubble sort work

Answer 20

• 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.

Question 21

Pros and Cons of Bubble sort?

Answer 21

Bubble sort is:

• It is simple
• It doesnt use much memory

But:

• It is inefficient as sometimes it requires alot of passes
• This means it does not cope well with big lists

Question 22

How does a merge sort work?
part 1

Answer 22

• 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.

Question 23

Pros and Cons of Merge Sort?

Answer 23

• It is more efficient on large data sets
• Has consistent running times

But :

• Not suitable for small lists
• uses lots of memory

Question 24

Insertion Sort Pros and Cons?

Answer 24

• Copes well with small lists
• It doesn’t require additional memory

But

• It doesnt cope well with large lists

Question 25

How does Insertion Sort work?

Answer 25

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.**

Question 26

Advantages and Disadvantages of Psuedocode

Answer 26

Advantages and disadvantages of pseudocode Designing an algorithm in pseudocode has benefits: * because pseudocode is **similar to a programming language, it can be quickly and easily converted into an actual programming language** * it is **easy to understand** * it **does not matter if there are errors** in the **syntax** - it is **obvious what is intended** * c**hanges to the design can be incorporated quite easily** Pseudocode also has its disadvantages: * It can be **hard to see how a program flows**, for example, where does following one path as opposed to another take the program? * It can be **time consuming to produce.**

Question 27

What are all the different flowchart diagrams?

Answer 27

Question 28

How do you use sub programs in flowdiagrams?

Answer 28

Put the **name of the function in the terminator**

Question 29

Advangtages and Disadvantages of Flow diagrams?

Answer 29

Designing an algorithm using flow diagrams has benefits: * It is easy to see how a program flows. For example, where does following one path as opposed to another take the program? * Flow diagrams follow an international **standard** - it’s easy for any flow diagram user to pick up a diagram and understand it. Flow diagrams also have their disadvantages: * with a large program, the diagrams can become huge in size and unwieldy to follow * any changes to the design may mean a lot of the diagram has to be redrawn