1. Define O (big oh) notation and prove or disprove the following using the basic definition of O (big oh)

2n^3 n^2 10 Order the following functions in increasing order of notation
3^n n^2 2n^2 5n 2
Traverse the following graph using Depth First Search the starting node is <img src='./qimages/8437-1c.jpg'> Write Prim's algorithm and apply it to find the minimum cost spanning tree for the following graph:

<br><br> <img src='./qimages/8437-1d.jpg'>
2.(a) What is a recurrence relation Define Fibonacci sequence using a recurrence relation.
Write bubble sort algorithm and find its time complexity.

3.(a) Suppose you are given scoring shots a cricketing batsman can score on one shot. Further it is assumed that there is no limit to a batsman to score on any shot. The problem is to find the minimum number of shots to score 100 runs, using Greedy approach. Show the sequence of steps for selection and rejection of shots.

3.(b) Explain best case and worst case in linear search algorithm.

4.(a) Define the following terms in an undirected graph, where V is the set of vertices and E is the set of edges Path
Cycle

(iii) Tree
Spanning Tree
Sort the following list using Quick-Sort algorithm. Show the intermediate steps in the process <img src='./qimages/8437-4b.jpg'> Define Asymptotic lower bound of a function.
Define Space complexity
Define Asymptotic upper bound of a function
Write the general form of a recurrence relation for a divide-and-conquer algorithm and explain the different parts of this recurrence relation.