Topic 1 - Problem Solving

Question 1

What is an algorithm?

Answer 1

A set of instructions that perform a specific task.

Question 2

What are algorithms used for?

Answer 2

Calculations, data processing and automated reasoning.

Question 3

What are the 5 different representations of algorithms?

Answer 3

Flowcharts, Pseudocode, Structured English, Written descriptions and program code.

Question 4

What are flowcharts?

Answer 4

Diagrams consisting of geometric shapes that help visualise a problem.

Question 5

What is Pseudocode?

Answer 5

An informal description of a program or algorithm.

Question 6

What is Structured English?

Answer 6

Similar to Pseudocode except symbols are often written out (e.g. ADD instead of +)

Question 7

What is the purpose of algorithms?

Answer 7

To visualise the logical steps of a task.

Question 8

What is a Quick Sort?

Answer 8

A quick and efficient algorithm used to put data into a particular order (often ascending/descending or rearranging letters of the alphabet)

Question 9

What are the 4 steps to execute a Quick Sort algorithm?

Answer 9

1. Select a pivot from the list
2. Write down all the items less than and bigger than the pivot, keeping the order, in a sub-list.
3. Write down the remaining items, keeping the order, in a sub-list.
4. Repeat steps 1-3 until all items are chosen as a pivot.

Question 10

What is a Bubble Sort?

Answer 10

An algorithm that works by repeatedly stepping through a list, comparing each item with the following item, swapping them if necessary.

Question 11

What is a Selection Sort?

Answer 11

An algorithm that splits the input list into two imaginary sub-lists: a sorted list and an unsorted list.

Question 12

What are the steps to execute a Selection Sort algorithm?

Answer 12

1. Swap the smallest element in the list with the first element in the list.
2. Repeat the process with the nth smallest element and replace it with the element in the nth position in the list.
3. Continue until the list is sorted.

Question 13

What is a search algorithm?

Answer 13

Finds a specific item within a larger group.

Question 14

How does a Linear Search algorithm work?

Answer 14

Checks every single item in the list until you find your search item, or fail to find it at all.

Question 15

Why is a Linear Search algorithm not very efficient?

Answer 15

The time it takes is related to how long and where in the list the item is.

Question 16

How does a Binary Search algorithm work?

Answer 16

Continually divides your list by two (hence BINARY), eliminating the part of the list that cannot have your item in it.

Question 17

How does a Breadth First Search (BFS) work?

Answer 17

Works by visiting nodes closest to the starting point first.

Question 18

How does a Depth First Search (DFS) work?

Answer 18

Works by visiting nodes as far into the graph as possible before backtracking to visit the previously unvisited nodes.

Question 19

How is algorithmic efficiency measured?

Answer 19

In terms of time (how long it takes to run) and space (how much memory is required).

Question 20

What are the factors that affect algorithmic efficiency?

Answer 20

• How well designed the data structures are
• The software and hardware
• The programming language and translator used

Question 21

What is decomposition?

Answer 21

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

Question 22

What are two advantages of decomposition?

Answer 22

1. Different people can work on different sub-problems

2. Able to compute the solution in parallel

Question 23

What are two disadvantages of decomposition?

Answer 23

1. The problem must be understood well.

2. It can be difficult to combine the solutions