Algorithms 1. Definition and Complexity

Question 1

What is an algorithm?

Answer 1

An algorithm is a finite sequence of operations for carrying out a procedure or solving a problem.

Question 2

What may an algorithm be communicated in?

Answer 2

An algorithm may be communicated by using pseudocode or a flowchart.

Question 3

What is an iterative process?

Answer 3

A repeating process which uses a loop

Question 4

What is a pass?

Answer 4

Working through the loop once is known as a pass.

Question 5

How can an algorithm be proved correct using proof by exhaustion?

Answer 5

Proof by exhaustion may be appropriate if the number of possible inputs is small.

Question 6

How can an incorrect algorithm be disproved?

Answer 6

An incorrect algorithm can sometimes be disproved by counter-example.

Question 7

What is algorithm complexity?

Answer 7

The study of how algorithms scale in both time and space

It can be used to compare difference algorithms to see which perform better and may also help establish performance expectations for different sized data

Concerns how fast or slow a particular algorithm performs.

Question 8

What does O(n^2) mean?

Answer 8

Quadratic complexity

This would mean that if n is doubled a computer program would take approximately four times as long to run the algorithm.

Question 9

What is pseudocode?

Answer 9

Concise instructions that could form the structure of a computer code but have no particular computing language / syntax
-Common sense should be used and applied to instructions

Question 10

Why are pseudocode written in numbered lines e.g. 10?

Answer 10

Easy reference / adaptation if we want to add step in between e.g. step 15 in-between steps 10 and 20