Introduction of Algorithms Flashcards
Characteristics/ Criteria of an algorithm
1.)Input: 0 or more external inputs
2.)Output: At least one o/p
3.)Finiteness: Algo must terminate in finite time and have finite number of steps
4.)Definiteness: Each step in algo must unique (clear and unambiguous)
Give example of algo with no i/p
Random number generator
Steps to design algo
1.)Device an algo
2.)Validation of an algo
3.)Analysis of an algo
4.)Testing of computer program
Analysis of an algo
Estimation of CPU execution time and main memory space required to complete execution of an algo
Differentiate between Decidable and Undecidable Problem
Decidable problem (Key Characteristic)
A problem for which an efficient algorithm exists
Decidable Problem - Time Complexity
A problem which required polynomial time to solve by using a deterministic algorithm for finite input
Decidable Problem - CPU Computations
For n inputs, the number of computations to solve the problem is
{n, n², nlogn, nᶜ} indicating polynomial CPU computations.
Undecidable Problem - Key Characteristic
A problem for which no efficient algorithm exists
Undecidable Problem - Time Complexity
A problem which required exponential time to solve by using a deterministic algorithm for finite input
Undecidable Problem - CPU Computations
For n inputs, the number of computations to solve the problem is
{2ⁿ,3ⁿ,n!,nⁿ} indicating exponential CPU computations
Decidable Problem - Termination
A decidable problem always terminates in finite time.
Undecidable Problem - Termination
An undecidable problem may or may not terminate in finite time.
Asymptotic notations
Used for asymptotic comparisons
O, Ω (uppercase omega), Θ (theta), ω(lowercase omega)
Asymptotic comparision
Growth rate between non-negative functions f(n),g(n) for large n values [n->∞]
here f(n),g(n) non-negative functions
Asymptotically comparison between f(n) and g(n) where f(n), g(n)<0. (3)
Big O notation
Omega Notation
Relationship between omega and big O notation
Relationship between omega and big O notation
