Question 1) Name the basic asymptotic efficiency classes and briefly describe with examples. (For example, log n is the asymptotic classes that are named as logarithmic).
Question 2: Explain a binary search algorithm and apply it to the following array of numbers to search for K=45.
5 20 30 35 40 45 50 70 90 110
Write a recurrence relation and time complexity for a binary search algorithm.
Question 3) Describe the following terms:
(a) Asymptote (b) Worst case (c) Best case (d) Average case
(e) Tight bound (f) Upper bound (g) Loose Bound
Question 4) Describe the operation of Merge sort algorithm with the help of the following example.
7 6 4 8 15 12 3 16
Question 5) Name the four basic fundamental techniques that are used to design the algorithm efficiently with brief description for each.
Question 6) Use the most suitable notation among 0, θ, Ω? to indicate time efficiency.
Question 7) Write down the applications of spanning tree. Write a Prim’s algorithm to find a minimum cost of a spanning tree and show its operation with an example.
Question 8) Explain “Greedy algorithm”? Write its pseudo code.
Question 9) What is complexity of graph search algorithms if a graph is represented by adjancy matrix and adjancy list.