Section 4 - Algorithms

Question 1

What are the three techniques for computational thinking?

Answer 1

Decomposition, algorithmic thinking, abstraction

Question 2

What is decomposition?

Answer 2

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

Question 3

What is algorithmic thinking?

Answer 3

A logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solve similar problems in the future.

Question 4

What is abstraction?

Answer 4

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

Question 5

What is an algorithm?

Answer 5

A set of instructions for solving a problem, that can be in the from of pseudocode or flow charts

Question 6

Advantages of pseudocode?

Answer 6

• Quick to write

- Easy to convert into any programming language

Question 7

What is the oval for in pseudocode?

Answer 7

Beginning/end

Question 8

What is the parallelogram for in pseudocode?

Answer 8

Inputs/outputs

Question 9

What is the rectangle for in pseudocode?

Answer 9

General instructions, processes and calculations

Question 10

What is the diamond for in pseudocode?

Answer 10

Decisions

Question 11

What is the rectangle with lines for in pseudocode?

Answer 11

Sub routines - reference to other flow diagrams

Question 12

What is the arrow for in pseudocode?

Answer 12

Connecting boxes and showing direction

Question 13

What is a sequence?

Answer 13

A set of instructions in a specific order

Question 14

What is selection?

Answer 14

A section of code that is only run if certain conditions are met

Question 15

What is iteration?

Answer 15

Repeating steps or instructions in a loop until certain conditions are met

Question 16

How does a binary search work?

Answer 16

1. Find the middle item in the list
2. If this is what you are looking for, you’ve found it, stop
3. If not, compare the middle item with the desired number. If it’s larger than the middle, get rid of the first half. If it’s smaller than the middle, get rid of the second half.
4. Keep repeating until you find the item that you are looking for

Question 17

Disadvantages of a binary search?

Answer 17

• Must be in an ordered list

Question 18

Different types of search algorithms?

Answer 18

• Binary search

- Linear search

Question 19

Disadvantages of linear search?

Answer 19

• Very slow as every value must be checked

Question 20

Advantages of linear search?

Answer 20

• Can be done on an unordered list

- Simpler than a binary search

Question 21

How does a linear search work?

Answer 21

1. Look at the first item in the list
2. If this is the right item, stop.
3. If not, look at the next item in the list
4. Repeat step 2-3 until you have checked every item

Question 22

Types of sort algorithms?

Answer 22

• Merge sort
• Bubble sort
• Insert sort

Question 23

Advantages of the bubble sort?

Answer 23

• Simple algorithm that can be easily implemented

- Does not use much memory as sorting is done using the original list

Question 24

Disadvantages of the bubble sort?

Answer 24

• Inefficient

- Does not cope with larger lists

Question 25

How does a bubble sort work?

Answer 25

1. Look at the first two items in the list 2. If they are in the wrong order, swap them 3. Move onto the next pair and repeat step 2 4. Repeat these until you get to the end of the list, this is called one pass 5. Repeat until there are no swaps

Question 26

How does a merge sort work?

Answer 26

1. Split the list in half 2. Keep splitting each sub-list until each sub-list only has one item 3. Merge pairs of sub-lists so each one has twice as many items 4. Sort the items into the right order when you merge one 5. Repeat until they are all merged together in the right order

Question 27

Advantages of the merge sort?

Answer 27

- Efficient and quick for large lists | - Very consistent running time regardless of how they are originally ordered

Question 28

Disadvantages of the merge sort?

Answer 28

- Slower than other algorithms for small lists - Even if the list is sorted, it goes through the process - Uses more memory because it creates separate files

Question 29

How does an insertion sort work?

Answer 29

1. Look at the second item in the list 2. Compare it to all items before it and insert the number into the right place. 3. Repeat for all the values until they are in the correct place

Question 30

Advantages of insertion sort?

Answer 30

- Can be easily coded - Copes well with small lists - Needs no additional memory as done on the original list - Quick to add items to an already ordered list - Quick at checking that a list is already sorted

Question 31

Disadvantage of insertion sort?

Answer 31

- Not good with bigger lists