4.4.4 Classification of algorithms

Question 1

How can algorithms be compared?

Answer 1

1) Algorithms can be compared on how long it takes them to solve a problem
2) Known as time-complexity

Question 2

What is execution time and how is it important?

Answer 2

1) Execution time is important as the faster an algorithm can be solved the better
2) Faster execution time reduces the financial impact

Question 3

Why is space important for the efficiency of an algorithm?

Answer 3

1) An algorithm that takes up less space (memory) is better
2) Less RAM is used up
3) More algorithms can be run on the same hardware and this increases productivity

Question 4

Why is efficiently implementing algorithms important?

Answer 4

1) Taking up minimal amounts of resources and running algorithms at high speeds is important for data sets such as Big Data

Question 5

What is a function?

Answer 5

1) A mapping from one set of values (domain) to another set of values (co-domain)
2) E.g. ℕ → ℕ.

Question 6

What is a linear function?

Answer 6

1) A Straight line graph

2) E.g. f(x) = 2x and f(x) = 7x + 1

Question 7

What is a polynomial function?

Answer 7

1) E.g. Uses Quadratics and cubics
2) f(x) = 5x2

3)

Question 8

What is a Exponential function?

Answer 8

1) Function where input value exponentially increases rapidly

Question 9

What is a Logarithmic function?

Answer 9

1) Function involving the calculation of the logarithm of the input
2) E.g. log2(x)

Question 10

What is meant by permutation of a set of objects?

Answer 10

1) A permutation is the number of ways of arranging the object
2) E.g. 3 objects A, B, C to choose the first object there are 3 choices, 2 choices for 2nd object
3) 3 x 2 = 6 ways to arrange the first two objects and one way for the third object

Question 11

How do you calculate the permutations of an object?

Answer 11

1) Written in factorial so for four objects it would be 4!

2) For 6 objects = 6 x 5 x 4 x 3 x 2 x 1

Question 12

What is Big-O Notation and how many different time complexities are there and what are they?

Answer 12

1) Big-O notation is used to express the time complexity or performance of an algorithm ( 0 stands for order)

• constant time
• logarithmic time
• linear time
• polynomial time
• exponential time
• Factorial

Question 13

What does O(1) represent?

Answer 13

1) Constant time: Same time to execute irrespective of the size of the input

E.g. length

Question 14

What does O(n) represent?

Answer 14

1) Linear time: Performance grows in linear time directly proportionate to the size of the data set
2) 1000 unsorted items will take 1000 times longer than searching an array for 1 item

Question 15

What does O( log n) represent?

Answer 15

1) Logarithmic time complexity

2) The time taken to execute an algorithm of order O(log n) grows slowly as the data set size increases

Question 16

What does O(n!) represent?

Answer 16

1) Factorial

2) Time taken to execute will grow very quickly faster than O(n2)

Question 17

What does O(n squared) represent?

Answer 17

1) Polynomial-time complexity

2) Performance is directly proportional to the square of the size of the data set

Question 18

What is a Tractable problem?

Answer 18

1) Problems that have a polynomial (or less) time solution and can be solved

Question 19

What is an Intractable problem?

Answer 19

1) Problems that have no polynomial (or less) time solution cant be solved

Question 20

What is meant by heuristic methods and how can they be used to solve intractable problems?

Answer 20

1) Heuristic methods are used to solve a problem by employing an algorithm that does not guarantee a perfect or optimal result

Question 21

What is meant by a computable problem?

Answer 21

Problems that can be solved algorithmically

Question 22

What is meant by a Non-computable problem?

Answer 22

Problems that cannot be solved algorithmically

Question 23

What is the Halting Problem?

Answer 23

1) The Halting problem is the problem of determining whether, for a given input, a program will finish running or continue forever

Question 24

What is the significance of the Halting problem?

Answer 24

1) The Halting problem demonstrates that there are some problems that cannot be solved by a computer

Question 25

What is a Turing Machine?

Answer 25

1) Turing machine can be viewed as a computer with a single fixed program

Question 26

Is O(1) Constant time complexity tractable?

Answer 26

Tractable

Question 27

Is O(log n) Logarithmic time complexity tractable?

Answer 27

Tractable

Question 28

Is O(n) Linear time complexity tractable?

Answer 28

Tractable

Question 29

Is O(n squared) Polynomial-time complexity tractable?

Answer 29

Tractable

Question 30

Is O(2n) Exponential time complexity Tractable?

Answer 30

No, it is Intractable

Question 31

Is O(n!) Factorial time complexity Tractable

Answer 31

No, it is Tractable

Question 32

What is the order of time complexities (Hint: Remember FEPLL)

Answer 32

1) Factorial
2) Exponential
3) Polynomial
4) Linear
5) Logarithmic

Factorial lowest Logarithmic highest

Question 33

How is the Turing machine expressed?

Hint remember symbols, square sand snakehead all in a machine

Answer 33

1) A Finite alphabet of symbols
2) An infinite tape with marked-off squares
3) A sensing read-write head that can travel along the tape one square at a time
4) A finite set of states in a state transition diagram

Question 34

What is a Start state?

Answer 34

A turing machines initial starting state

Question 35

What is a Halting state?

Answer 35

A state with no outgoing transitions that halts a Turing machine

Question 36

Explain why both Universal turing machines and Turing machines are important towards the subject of computation?

Answer 36

1) Turing machines provide a (general/formal) model of computation and define what is computable

Question 37

What are Transition functions?

Answer 37

1) A transition function expresses the rules for any Turing machine