Section 1 - Fundamentals of algorithms

Question 1

What is the definition of an algorithm?

Answer 1

Algorithm:

— A series of steps that are followed in order to solve a problem.

Question 2

What does decomposition mean?

Answer 2

Decomposition:

— Breaking down a problem into smaller, more manageable sub-problems.

Question 3

What is abstraction?

Answer 3

Abstraction:

— Removing unnecessary details from a problem to make it easier to solve.

Question 4

What are the flowchart symbols and what are they used for in a flowchart?

Answer 4

• – Oval: used to START and END the flowchart
• – Parallelogram: used to input/output instructions
• – Diamond: decision box that only accepts yes and no answers
• – Rectangle: process box

Question 5

What are the three programming constructs? Explain them in detail.

Answer 5

• – Sequence: writing down steps in the order they happen
• – Selection: picking between different options using IF…THEN…ELSE
• – Iteration: looping a program using FOR…ENDFOR, REPEAT…UNTIL, WHILE…ENDWHILE

Question 6

What are the two ways to search an algorithm? Explain both in detail.

Answer 6

• – Linear search: When data in unsorted, every item is checked till the item being looked for is found
• – Binary search: When data is sorted, the data is continously divided into half and examined till the one you are looking for is found

Question 7

Compare a linear and binary search.

Answer 7

A linear search is beneficial when there aren’t a lot of items in a list but if there a lot of items then a binary search would be more efficient because since half the list is discarded each time, you don’t have to search as many items.

If you need to recognise which search is being shown in a program, look to see if there is a dividing by 2 and that will tell you it is a binary search.

Question 8

What are the two ways to sort an algorithm? Explain in detail

Answer 8

• – Bubble sort: the list is repeatedly gone through and items are compared then swapped if the items are in the wrong order. The number of passes is the number of items in the list -1
• – Merge sort: the list is continuously divided into half forming sublists until there is only sublists of one length. The items in the sublists are then merged into pairs in the correct order until all items are merged and there is only one list remaining.

Question 9

Compare a bubble sort and merge sort.

Answer 9

A bubble sort is very time consuming and inefficient when sorting through a list of more than about eight items because it requires a lot of passes through the list before the list is sorted. The merge sort is more effective because it takes less time to execute however it can be hard for an inexperienced programmer as it requires a lot more programming. A merge sort also requires a lot of memory to store the lists which can be a problem if the list is large.