4.4.4 Classification of algorithms Flashcards
How can algorithms be compared?
1) Algorithms can be compared on how long it takes them to solve a problem
2) Known as time-complexity
What is execution time and how is it important?
1) Execution time is important as the faster an algorithm can be solved the better
2) Faster execution time reduces the financial impact
Why is space important for the efficiency of an algorithm?
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
Why is efficiently implementing algorithms important?
1) Taking up minimal amounts of resources and running algorithms at high speeds is important for data sets such as Big Data
What is a function?
1) A mapping from one set of values (domain) to another set of values (co-domain)
2) E.g. ℕ → ℕ.
What is a linear function?
1) A Straight line graph
2) E.g. f(x) = 2x and f(x) = 7x + 1
What is a polynomial function?
1) E.g. Uses Quadratics and cubics
2) f(x) = 5x2
3)
What is a Exponential function?
1) Function where input value exponentially increases rapidly
What is a Logarithmic function?
1) Function involving the calculation of the logarithm of the input
2) E.g. log2(x)
What is meant by permutation of a set of objects?
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 do you calculate the permutations of an object?
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
What is Big-O Notation and how many different time complexities are there and what are they?
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
What does O(1) represent?
1) Constant time: Same time to execute irrespective of the size of the input
E.g. length
What does O(n) represent?
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
What does O( log n) represent?
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
What does O(n!) represent?
1) Factorial
2) Time taken to execute will grow very quickly faster than O(n2)
What does O(n squared) represent?
1) Polynomial-time complexity
2) Performance is directly proportional to the square of the size of the data set
What is a Tractable problem?
1) Problems that have a polynomial (or less) time solution and can be solved
What is an Intractable problem?
1) Problems that have no polynomial (or less) time solution cant be solved
What is meant by heuristic methods and how can they be used to solve intractable problems?
1) Heuristic methods are used to solve a problem by employing an algorithm that does not guarantee a perfect or optimal result
What is meant by a computable problem?
Problems that can be solved algorithmically
What is meant by a Non-computable problem?
Problems that cannot be solved algorithmically
What is the Halting Problem?
1) The Halting problem is the problem of determining whether, for a given input, a program will finish running or continue forever
What is the significance of the Halting problem?
1) The Halting problem demonstrates that there are some problems that cannot be solved by a computer
What is a Turing Machine?
1) Turing machine can be viewed as a computer with a single fixed program
Is O(1) Constant time complexity tractable?
Tractable
Is O(log n) Logarithmic time complexity tractable?
Tractable
Is O(n) Linear time complexity tractable?
Tractable
Is O(n squared) Polynomial-time complexity tractable?
Tractable
Is O(2n) Exponential time complexity Tractable?
No, it is Intractable
Is O(n!) Factorial time complexity Tractable
No, it is Tractable
What is the order of time complexities (Hint: Remember FEPLL)
1) Factorial
2) Exponential
3) Polynomial
4) Linear
5) Logarithmic
Factorial lowest Logarithmic highest
How is the Turing machine expressed?
Hint remember symbols, square sand snakehead all in a machine
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
What is a Start state?
A turing machines initial starting state
What is a Halting state?
A state with no outgoing transitions that halts a Turing machine
Explain why both Universal turing machines and Turing machines are important towards the subject of computation?
1) Turing machines provide a (general/formal) model of computation and define what is computable
What are Transition functions?
1) A transition function expresses the rules for any Turing machine