2.1 Algorithms

Question 1

Decomposition

Answer 1

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

Question 2

Abstraction

Answer 2

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

Question 3

Algorithmic Thinking

Answer 3

a logical way/set of instructions to solve a problem -> as an algorithm

Question 4

What do computer systems do?

Answer 4

Input -> process -> output

Question 5

Flowcharts

Answer 5

Visually represent an algorithm

Question 6

Flowchart: Arrow

Answer 6

Connects boxes
Shows flow of data through program

Question 7

Flowchart: Rectangle

Answer 7

Process
General instructions, processes and calculations

Question 8

Flowchart: Parallelogram

Answer 8

Input/output

Question 9

Flowchart: Diamond

Answer 9

Decision -> YES or NO

Question 10

Flowchart: Curved cornered rectangle

Answer 10

Terminal -> Start/Stop

Question 11

Flowchart: rectangle with lines

Answer 11

Sub program - refers to other flowcharts

Question 12

Pseudocode

Answer 12

Shows the outline of an algorithm without worrying about fine details (syntax)

Question 13

Trace Tables

Answer 13

Give a simple way of testing a piece of code is working correctly

Question 14

What do columns in trace tables represent?

Answer 14

Variables

Question 15

What do rows in trace tables represent?

Answer 15

Values that the variable can take at a particular point in an algorithm

Question 16

Standard searching algorithms

Answer 16

Binary
Linear

Question 17

Binary Search

Answer 17

1. Find middle term in ordered list
2. If this is the item you are looking for, stop search
3. If not, compare item being looked for with middle term
4. If it is before the middle term, get rid of the second half of the list
5. If it is after the middle term, get rid of the first half of the list
6. Repeat with the smaller list until the item is found

Question 18

Advantage of Binary Search

Answer 18

Efficient

Question 19

Disadvantage of Binary Search

Answer 19

only works with ordered/sorted lists

Question 20

Linear Search

Answer 20

Check each term in a sequence sequentially until the item being looked for is found

Question 21

Disadvantage of Linear Search

Answer 21

inefficient, only can be used for small list

Question 22

Standard sorting algorithms

Answer 22

Bubble
Merge
Insertion

Question 23

Bubble Sort

Answer 23

1. Look at first 2 terms
2. If ordered move on to next pair
3. If not ordered, swap them
4. Repeat until you get through all the terms once = 1 pass
5. Repeat until there are no swaps in a pass

Question 24

Advantage of Bubble Sort

Answer 24

Simple algorithm, efficient to check if a list is in order, little memory used

Question 25

Disadvantage of Bubble Sort

Answer 25

Inefficient to sort a list, doesn’t work well with large lists

Question 26

Merge Sort

Answer 26

1. Split list in half (creates 2 sub lists) 2. Repeat until all the sub lists contain only 1 term 3. Merge 2 sub lists together and sort into right order 4. Repeat step 3 until all the sub lists have been merged together

Question 27

Advantage of Merge Sort

Answer 27

More efficient than bubble sort and insertion sort for large lists

Question 28

Disadvantage of Merge Sort

Answer 28

Even if the terms are already sorted, it goes through the whole process, uses lots of memory

Question 29

Insertion Sort

Answer 29

1. Look at 2nd term in list 2. Compare it to the terms before it and insert number in right place 3. Repeat step 2 for all terms

Question 30

Advantage of Insertion Sort

Answer 30

Easily coded, good with small lists, quick

Question 31

Disadvantage of Insertion Sort

Answer 31

Doesn't cope with large lists