4.04 Classification Of Algorithms.

Question 1

Define computability:

Answer 1

Concerned with where a problem can or cannot be solved.

Question 2

Define feasibility.

Answer 2

Concerned with how efficiently a problem can be solved.

Question 3

What are the two standard measureS of the efficiency of an algorithm.

Answer 3

Space and time.

Question 4

What is time?

Answer 4

How long the algorithm takes to execute.

Question 5

What is space?

Answer 5

How much memory the algorithm uses for the storage of data during execution.

Question 6

What happens when more than one algorithm exists which can solve a problem?

Answer 6

There is a trade off between time and space e.g. one solution may be quicker but requires more memory than another solution.

Question 7

How do we measure efficiency?

Answer 7

The amount of space and time required varies depending on the number of inputs to the algorithm, therefore efficiency is normally expressed as a function of the number of inputs to an algorithm, commonly referred to as ‘n’.

Question 8

How else can we measure efficiency.

Answer 8

Space complexity.
Time complexity:
processor clock speed
Efficiency of hardware implementation of
operations used.
Other processes executing concurrently.

Question 9

How do we measure time complexity?

Answer 9

Using the big O notation, which allows us to focus on the algorithm rather than the hardware it is being executed on.

Question 10

How can the order or magnitude of an algorithm be expressed?

Answer 10

As a function of it size.

Question 11

What does a function map do?

Answer 11

A function maps one set of values onto another.

Question 12

How do we express linear function?

Answer 12

f(x) = ax+c

Question 13

How does fx increase?

Answer 13

In a straight line.

Question 14

How do we express a polynomial function?

Answer 14

f(x) = axm + bx + c

Question 15

How do we express an exponential function?

Answer 15

f(x) = ab^x

Question 16

How do we express a logarithmic function?

Answer 16

f (x)= a logn x

(Little n)

Question 17

What is a logarithm of a number?

Answer 17

The power that the base must be raised to to make it equal to the number.

Question 18

What is the permutation of an object?

Answer 18

The permutation of a set of objects is the number of ways of arranging the objects within that set.

Question 19

Outline an example of permutation.

Answer 19

Example : with 3 objects A,B,C, we can choose any to be the first object.
You then have two choices for the second object which gives use 3x2=6 possible permutations
ABC,ACB,BAC,BCA,CAB,CBA

Question 20

What is formula for calculating the number of permutations n objects?

Answer 20

N factorial or expressed as n!

Question 21

How is the time efficiency of an algorithm established?

Answer 21

Identify the basic operation that is performed by the algorithm.
Established how many times this operation is carried out as a function of the number of inputs (n).
Consider how quickly this value grows and identify the dominant part it this (e.g. in 4n^2+3 the dominant part is n^2 as it will have the most impact).
This is the order of complexity of the algorithm. It is written as as O(g) where g is the growth rate.

Question 22

Linear time complexity algorithm example:

Algorithm for summing a list of numbers in a file:

TOTAL = 0
WHILE NOT at end of file 
READ Number from file
Total = Total + number
END WHILE
PRINT TOTAL

What is the basic operation?

How many times is it carried out?

Som if a file contained n items, how many times would it be carried out?

What is the order complexity?

Answer 22

Total = Total + Number

It is in a loop, executed once for each number in the file.

So, if a file contained n items the basic operation would be executed n times.

The algorithm is said go have order complexity O(n)l

Question 23

What else does the efficiency of some algorithms depend on?

Answer 23

The values of the inputs made to them.