SECTION 5 - Algorithms

Question 1

Three key techniques for computational thinking

Answer 1

Decomposition, abstraction, algorithmic thinking

Question 2

Decomposition

Answer 2

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

Question 3

Abstraction

Answer 3

Focusing only on important pieces of information from the program and ignoring the specific details that are not important.

Question 4

Algorithmic thinking

Answer 4

A logical way of getting from problem to solution. Algorithm can be reused and used to solve other similar problems.

Question 5

Pseudocode

Answer 5

Mixture of English and programming language to show steps that program takes.

Question 6

What is flowchart symbol for start/stop?

Answer 6

Oval

Question 7

What is flowchart symbol for input/output?

Answer 7

Parallelagram

Question 8

What is flowchart symbol for processes?

Answer 8

Box

Question 9

What is flowchart symbol for decision?

Answer 9

Diamond

Question 10

Binary search process

Answer 10

1. Find middle item in ordered list
2. If this is item, stop search.
3. If not, compare middle item with item you are looking for.
4. If it is after middle item, remove first half of list. If it is before middle item, remove second half of list.
5. Repeat until item is found.

Question 11

Linear search process

Answer 11

1. Look at first item of list.
2. If this item, stop search.
3. If not repeat 1-2 until item is found

Question 12

Bubble sort process

Answer 12

1. Look at first 2 items, if in correct order, nothing will happen but if they are in incorrect order, they will be swapped.
2. Move on to next pair of items and repeat 1.
3. Repeat 3 until end of list is reached - called one pass. DO NOT INCLUDE LAST NUMBER IN NEXT PASS as it will now in correct place.
4. Repeat passes until list is ordered.

Question 13

Pros of bubble sort

Answer 13

• Simple algorithm
• Efficient way to check if list is already in order
• Does not use a lot of memory

Question 14

Cons of bubble sort

Answer 14

• Inefficient
• Due to being inefficient, it cannot cope with large lists

Question 15

Merge sort process

Answer 15

1. Split list in half into 2 subsists. Second sub list should start at the middle item.
2. Repeat 1 until all sub lists only contain 1 item
3. Merge pairs of sublist, so each one has twice as many items. Each time sublist is merged, sort items in correct order
4. Repeat 3 until all items are ordered.

Question 16

Pros of merge sort

Answer 16

• More efficient that bubbe, insertion sort
• Consistent running time

Question 17

Cons of merge sort

Answer 17

• Slower that other sorts for short lists
• Even list already ordered, carries out same slow process
• Uses more memory

Question 18

Insertion sort process

Answer 18

1. Looks at second item in list
2. Compares to items before and inserts items before into correct order
3. Repeat 2 for every other item until last item is inserted correctly

Question 19

Pros of insertion sort

Answer 19

• Very quick at checking if list is already ordered
• Intuitive way of sorting, can be easily coded
• Copes well with small lists

Question 20

Cons of insertion sort

Answer 20

• Does not cope well with large lists