4.4.4 Classification of algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

How can algorithms be compared?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is execution time and how is it important?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Why is space important for the efficiency of an algorithm?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Why is efficiently implementing algorithms important?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a function?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a linear function?

A

1) A Straight line graph

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a polynomial function?

A

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

3)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a Exponential function?

A

1) Function where input value exponentially increases rapidly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Logarithmic function?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is meant by permutation of a set of objects?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How do you calculate the permutations of an object?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does O(1) represent?

A

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

E.g. length

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does O(n) represent?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does O( log n) represent?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What does O(n!) represent?

A

1) Factorial

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

17
Q

What does O(n squared) represent?

A

1) Polynomial-time complexity

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

18
Q

What is a Tractable problem?

A

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

19
Q

What is an Intractable problem?

A

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

20
Q

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

A

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

21
Q

What is meant by a computable problem?

A

Problems that can be solved algorithmically

22
Q

What is meant by a Non-computable problem?

A

Problems that cannot be solved algorithmically

23
Q

What is the Halting Problem?

A

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

24
Q

What is the significance of the Halting problem?

A

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

25
Q

What is a Turing Machine?

A

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

26
Q

Is O(1) Constant time complexity tractable?

A

Tractable

27
Q

Is O(log n) Logarithmic time complexity tractable?

A

Tractable

28
Q

Is O(n) Linear time complexity tractable?

A

Tractable

29
Q

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

A

Tractable

30
Q

Is O(2n) Exponential time complexity Tractable?

A

No, it is Intractable

31
Q

Is O(n!) Factorial time complexity Tractable

A

No, it is Tractable

32
Q

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

A

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

Factorial lowest Logarithmic highest

33
Q

How is the Turing machine expressed?

Hint remember symbols, square sand snakehead all in a machine

A

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

34
Q

What is a Start state?

A

A turing machines initial starting state

35
Q

What is a Halting state?

A

A state with no outgoing transitions that halts a Turing machine

36
Q

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

A

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

37
Q

What are Transition functions?

A

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