Section 4: Algorithms

Question 1

Define Computational Thinking.

Answer 1

The steps a computer takes to solve a complex problem.

Question 2

What are the three key techniques for Computational Thinking?

Answer 2

Decomposition, Abstraction and Algorithmic thinking.

Question 3

Define Decomposition, (computational thinking)

Answer 3

Breaking down a complex problem into smaller problems and solving each one individually.

Question 4

Define Abstraction, (computational thinking)

Answer 4

Picking out important information from the problem, ignoring the specific details that don’t matter.

Question 5

Define Algorithmic Thinking, (computational thinking)

Answer 5

A logical way of getting from the problem to the solution.

Question 6

Define Algorithm.

Answer 6

Algorithms are just sets of instructions for solving a problem.

Question 7

Name the three main types of flow diagrams.

Answer 7

Sequences, Selection and Iteration

Question 8

Describe a Sequence flow diagram.

Answer 8

There is only one way through the diagram, from start to end.

Question 9

Describe a Selection flow diagram.

Answer 9

There are multiple ways through the flow diagram from start to end.

Question 10

Describe a Iteration flow diagram.

Answer 10

A flow diagram that contains a loop, that allows you to repeat a task.

Question 11

What are the two main search algorithms?

Answer 11

Binary Search and Linear Search.

Question 12

State the method of a Binary Search.

Answer 12

1) Find the middle item of the ORDERED list
2) If this is the item you’re looking for, then stop the search - you’ve found it.
3) If not found, compare the item you’re looking for with the middle item, if the middle item is larger then get rid of the second half of the list, if the middle item is smaller then get rid of the first half of the list.
4) Repeat steps 1-3 on this new smaller list until you find the desired item.

Question 13

State the method of a Linear Search.

Answer 13

1) Look at the first item in the UNORDERED list
2) If this is the item you’re looking for, then stop the search - you’ve found it.
3) If not, then look at the next item in the list.
4) Repeat steps 2-3 until you find the item that you’re looking for or you’ve checked every item.

Question 14

Advantages of Binary Search.

Answer 14

1) Binary searches are much more efficient
2) In general, binary searches take less steps to find the item you are looking for, which makes it more suitable for large lists of items.

Question 15

Advantages of Linear Search

Answer 15

1) Linear searches are more simpler
2) Linear searches can be used on any type of list , it doesn’t have to be ordered.
3) Could be better for smaller lists

Question 16

Name the three main types of Sorting Algorithms.

Answer 16

Bubble Sort, Merge Sort and Insertion Sort

Question 17

State the method of a Bubble Sort.

Answer 17

1) Look at the first two items in a list.
2) If they’re in the right order, you don’t have to do anything, if they’re in the wrong order, swap them.
3) Move on to the next pair of items, 2nd&3rd and repeat step 2).
4) Repeat step 3) until you get to the end of the list - this is called one pass. The last item will now be in the correct place, so don’t include it in the next pass.
5) Repeat steps 1-4 until there are no swaps in a pass.

Question 18

Advantages of a Bubble Sort.

Answer 18

1) Its a simple algorithm
2) Its an EFFICIENT way to CHECK if a list is already ordered
3) Doesn’t use much memory.

Question 19

Disadvantages of a Bubble Sort.

Answer 19

1) Its an INEFFICIENT way to SORT a list.

2) Due to being inefficient, bubble sorts aren’t good for larger lists.

Question 20

State the method of a Merge Sort.

Answer 20

1) Split the list in half, (the smaller lists are called sub-lists) - the second sub-list should start at the middle item.
2) Keep repeating step 1) on every sub-list until all the lists only contain one item.
3) Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order.
4) Repeat step 3) until you’ve merged all the sub-lists together.

Question 21

Advantages of a Merge Sort.

Answer 21

1) MORE EFFICIENT for LARGER lists

2) It has a very consistent running time regardless of how ordered the items in the original list are.

Question 22

Disadvantages of a Merge Sort.

Answer 22

1) LESS EFFICIENT for SMALLER lists
2) Even if the list is already sorted, it still goes through the whole splitting and merging process.
3) It uses more memory than other sorting algorithms.

Question 23

State the method of an Insertion Sort.

Answer 23

1) Look at the second item in a list.
2) Compare it to all items before it and insert the item in the right place
3) Repeat step 2) for the 3rd 4th 5th etc. items until the last item in the list has been inserted into the correct place.

Question 24

Advantages of Insertion Sort.

Answer 24

1) Can be easily coded
2) Very efficient for small lists
3) Doesn’t require much memory
4) Very quick at checking a list is already sorted.

Question 25

Disadvantages of Insertion Sort

Answer 25

Its main disadvantage is that it is less efficient when used on larger lists.

Question 26

What is the point of Pseudocode?

Answer 26

Pseudocode clearly shows an algorithms steps without worrying about finer details such as syntax

Question 27

State the five boxes and commands used in flow diagrams.

Answer 27

1) Start/End - Boxes with Rounded Corners
2) Inputs/Outputs - Parallelograms
3) Processes - Rectangles
4) Decisions - Diamonds
5) Sub Routines - Double Rectangle