Questions on Algorithms

1. What are the complexities of some famous algorithms?

Ans: Some famous algorithms are:

i) Binary Search : O(log n)

ii) Merge Sort : O(n log n)

iii) Insertion Sort : O(n * n)

iv) Quick Sort : O(n log n)

v) Selection Sort : O(n * n)

2. What are the most important types of algorithms?

Ans: There are five important basic designs for algorithms.

i) Divide and Conquer: This is top-down technique for designing algorithms that consists dividing the problem into smaller sub-problems that are similar to the original problem but smaller in size, solve the sub-problems recursively and then combine these solutions to create a solution to the original problem. An example of this approach is "binary search".

ii) Greedy Method: The greedy method suggests that one can devise an algorithm that works in stages, considering on input at a time. At each stage, a decision is made regarding whether a particular input is an optimal solution. An example of this approach is "knapsack problem". Greedy algorithms attempt not only to find a solution, but to find the idle solution to any given problem.

iii) Dynamic Programming: This can be used when the solution to a given problem can be viewed as the result of a sequences of decisions. An example of this approach is "multi stage graph". This class remembers older results and attempts to use this to speed the process of finding new results.

iv) Back Tracking: If we reach a dead-end, we use the stack to pop-off the dead end and try something else we had not tried before. An example of this approach is "8-queens problem". Back tracking tests a solution, if one is found the algorithm has solved, if not it recurs once and tests again, continuing until a solution is found.

v) Branch and Bound: This algorithm form a tree of sub-problems to the primary problem, following each branch until it is either solved or lumped in with another branch.