Analysis
Sieve
Who provided an algorithm for finding prime numbers.
Euclid
Which algorithm is used for finding GCD of two numbers?
Euclid
Who invented Euclid’s algorithm?
O(n)
What is the total running time of Euclid’s algorithm?
GCD (m,n) = GCD (n, m mod n)
What is the formula for Euclidean algorithm?
O(n2 )
What is the total running time of the binary GCD algorithm?
4
What is the GCD of 20 and 12 using Euclid’s algorithm?
Kruskal’s
Which algorithm is used to find minimum spanning tree?
O(E log V)
What is the time complexity of Kruskal’s algorithm?
greedy algorithm
Kruskal’s algorithm is a ____ approach.
Overlapping subproblems
If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.
Divide and conquer
If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________
Memorization
In dynamic programming, the technique of storing the previously calculated values is called ___________
State-space tree
Backtracking algorithm is implemented by constructing a tree of choices called as?
Promising
A node is said to be ____________ if it has a possibility of reaching a complete solution.