1) What is the time complexity of linear search?
Θ(n)
2) What is the time complexity of binary search?
Θ(log2n)
3) What is the major requirement for binary search?
The given list should be sorted.
4) What is binary search?
It is an efficient method of finding out a required item from a given list,
provided the list is in order.
The process is:
- First the middle item of the sorted list is found.
- Compare the item with this element.
- If they are equal search is complete.
- If the middle element is greater than the item being searched, this process
is repeated in the upper half of the list. - If the middle element is lesser than the item being searched, this process is
repeated in the lower half of the list.
5) What is parental dominance?
The key at each node is greater than or equal to the keys at its children.
6) What is heap?
A heap can be defined as a binary tree with keys assigned to its nodes
( one key per node) provided the following two conditions are met:
1 The tree’s shape requirement – The binary tree is essentially complete ( or
simply complete), that is, all its levels are full except possibly the last level,
where only some rightmost leaves may be missing.
- The parental dominance requirement – The key at each node is greater than
or equal to the keys at its children.
7) What is height of Binary tree?
It is the longest path from the root to any leaf.
8) What is the time complexity of heap sort?
Θ( n logn)
9) What is Merge Sort?
Merge sort is an O (n log n) comparison-based sorting algorithm.
Where the given array is divided into two equal parts. The left part of the array
as well as the right part of the array is sorted recursively. Later, both the left
part and right part are merged into a single sorted array.
10) Who invented Merge Sort?
John Von Neumann in 1945.
11) On which paradigm is it based?
Merge-sort is based on the divide-and-conquer paradigm.
12) What is the time complexity of merge sort?
n log n.
13) What is the space requirement of merge sort?
Space requirement: Θ(n) (not in-place).
14) When do you say an algorithm is stable and in place?
Stable – if it retains the relative ordering.
In – place if it does not use extra memory.
15 ) Name the design strategy used in Selection Sort.
Brute force
16) Define Brute force strategy.
Brute force is a straight forward approach to solving a problem, usually
directly based on the problem’s statement and definitions of the concepts
involved.
17) What is the time complexity of Selection Sort algorithm?
(n2)
18) Is Selection Sort Inplace?
Yes.
19) Is Selection Sort stable?
Yes.
20) Why is the name Selection Sort?
Algorithm selects the smallest number in the array and places it in its final
position the sorted array.
21) When is Selection Sort algorithm useful?
Selection Sort algorithm is useful for small inputs because it requires
(n2) comparisons.
Selection Sort algorithm requires (n-1) swaps & hence (n) memory
writes. Thus it can be very useful if writes are the most expensive operation.
22) What are the drawbacks of Selection Sort?
Inefficient on large lists.
It requires same number of iterations no matter how well-organized the
array is.
It uses internal sorting, means it would require the entire array to be in
main memory.
23) When is a problem said to have overlapping sub problems?
A problem is said to have overlapping subproblems if it can be broken down into
subproblems which are reused multiple times. This is closely related to
recursion.
24) What is principle of optimality?
The optimal solution to any instance of an optimization problem is composed
of optimal solutions to its subinstances.
25) Can knapsack problem be solved in any other technique?
It can be solved using many other techniques such as BruteForce, Greedy
technique, Branch and bound etc..
26) Mention few applications of dynamic programming.
Can be applied to find factorial, fibonacci numbers in which the required value
may depend on previously computed values.
To find the longest common substrings of the strings “ABAB”, “BABA” and
“ABBA” are the strings “AB” and “BA” of length 2. Other common substrings are
“A”, “B” and the empty string “”. etc..
27) Compare Dynamic programming and Divide and conquer.
Dynamic programming differs from the “Divide and Conquer” (D-and-C)
method in the fact that the problems solved by D-and-C can have many non-
overlapping subproblems – i.e, new subproblems may be generated when the
method is applied.
Both use recursion.
28) Who invented Dijkstra’s Algorithm?
Edsger Dijkstra invented this algorithm.
29) What is the other name for Dijkstra’s Algorithm?
Single Source Shortest Path Algorithm.
30) Which technique the Dijkstra’s algorithm is based on?
Greedy Technique.
31) What is the purpose of Dijkstra’s Algorithm?
To find the shortest path from source vertex to all other remaining vertices
32) Name the different algorithms based on Greedy technique.
Prim’s Algorithm, Kruskal’s algorithm
33) What is the constraint on Dijkstra’s Algorithm?
This algorithm is applicable to graphs with non-negative weights only.
34) What is a Weighted Graph?
A weighted graph is a graph with numbers assigned to its edges. These
numbers are called weights or costs.
35) What is a Connected Graph?
A graph is said to be connected if for every pair of its vertices u and v there
is a path from u to v.
36) What is the time complexity of Dijkstra’s algorithm?
For adjacency matrix, It is O(IVI*IVI)
For adjacency list with edges stored as min heap, it is O(IEIlogIVI)
37) Differentiate b/w Traveling Salesman Problem(TSP) and Dijkstra’s Algorithm.
In TSP, given n cities with known distances b/w each pair , find the shortest
tour that passes through all the cities exactly once before returning to the
starting city.
In Dijkstra’s Algorithm, find the shortest path from source vertex to all other
remaining vertices
38) Differentiate b/w Prim’s Algorithm and Dijkstra’s Algorithm?
Prim’s algorithm is to find minimum cost spanning tree.
Dijkstra’s algorithm is to find the shortest path from source vertex to all
other remaining vertices.
39) What are the applications of Dijkstra’s Algorithm?
It finds its application even in our day to day life while travelling.
They are helpful in routing applications.
40) Who was the inventor of the Quicksort?
C.A.R.HOARE, a British Scientist.
41) Which design strategy does Quicksort uses?
Divide and Conquer
42) What is Divide and Conquer Technique?
(I) Divide the instance of a problem into two or more smaller instances
(II) Solve the smaller instances recursively
(III) Obtain solution to original instances by combining