Differentiate between Quadratic-time and Exponential-time algorithms. Give example of one problem each for these two running times.
________ ____ _______ ________ ________ ______.
___ ____ ____ __________ _____.
_________ ____ _______ _________ ________ ____ ___ _______ _______ _______ _____ ___.
___ _________ ____ _______ _______ _______ _______ _______ _____.
___ _______ _______ _____ __________ ________ _______ _________ ___ ________.
__________ _____ ______ _______ ____ ________.
___ _________ ___ ___ _________ ____ __________ _________ __________ _____ ___ ____.
_________ _______ ____ _____ __________ _________ _____ _______ _________.
______ ________ _______ _________ ______ ______ _______ _____.
____ _______ ____ _______ ______ _____ ___ ____ _______ ________.
____ _____ ____ ________ _______ ________ _____ __________ ________ __________.
_______ _____ ____ ______ ___ ________ ____ _________ _____ ___ _____ ___.
_____ ____ _______ _________ ______ __________ _________ _______ _____ __________.
________ _________ _______ _________ ____ ______.
_______ _________ _____ _____ ________ ________ ___ ________ ________ ________ ________ __________.
_________ _________ _____ _______ _______ __________.
______ __________ _______ __________ _________ ________ ___ ______.
____ ________ ___ ________ ____ ________ ________ ______.
____ ________ ____ ___ ____ __________ ________ _______ ____.
__________ __________ ________ ____ __________ _____ __________ _______.
________ _____ ______ _____ ___ _______ ______ _____.
__________ __________ _________ _________ ________ __________ ________ __________ ___ __________ ________.
______ _______ _______ __________ _______.
__________ _________ ______ _______ ______ ___.
____ ______ _____ ______ ________ _______ ______ ___ _______ _________ _________.
__________ ____ _________ _____ ______ __________ ___ _____ __________ ______.
_____ __________ _______ ____ ___ _______ ___.
____ ___ ___ _______ _______ ________.
________ _________ ____ ________ _________ ____ __________ _______ ____.
____ __________ __________ ___ _________ _____ _________.
__________ _________ _______ _______ __________ _______ ___ _________ ____ ______ _________ __________.
___ ______ ______ _________ _______.
______ ________ ___ ____ _______ ________ ____ ______ _________ ___.
_______ _______ _______ ______ _______ _____ _______ __________ __________.
_______ _______ ____ _________ _______.
_____ _________ ___ __________ __________ __________ ______.
__________ _______ _______ _______ __________ _________ _________ __________ _______ ____.
____ __________ __________ _________ _______.
_______ ___ ______ ______ ____ ______ ____ _____ __________.
___ ______ ___ ______ ____ ____ __________ ________ ___ ___.
______ _________ __________ __________ ____ _______ _________.
_____ _____ ___ ______ ____ __________ _____.
____ _____ _____ _________ __________ _________ __________ ____ ____ ______ __________ ____.
____ ________ _______ _________ __________.
____ _______ ______ ______ ___ __________.
_______ _________ ______ _________ _________ __________ _____ _______ _____ _________ __________ _______.
___ ___ _______ ______ _____ ________ _______ ____ ____ ___.
_______ _________ ___ ____ ______.
_____ ____ ________ _____ __________ ____ _______ ______ ___ ______ ______.
____ ________ ____ _________ ______.
____ _____ __________ ________ ____ _______ _______ _______ ___ ________ _______ ____.
______ _______ ___ _______ _______.
______ __________ ____ ___ ____.
_____ ________ ___.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
✓ Unlock up to 60% of the answer
✓ No payment required
Differentiate between Quadratic-time and Exponential-time algorithms. Give example of one problem each for these two running times.
A sorted array of size n contains several duplicate values. Design an algorithm to search a value in the array. The algorithm should output all the indexes where the searched value exists. Explain the worst time complexity of this algorithm.
Expalin the PARTITION algorithm of the Quick Sort taking the last element as pivot. Demonstrate the use of Quick sort algorithm for sorting the following data of size 8: [1, 5, 8, 11, 16, 19, 29, 38]. Compute the complexity of the worst case of Quick Sort algorithm.
How can an optimisation problem be represented mathematically. Explain with the help of an example. Explain the steps of designing a Greedy solution for an optimisation problem. Also explain the concept of local and global optimal solutions. Solve the following fractional Knapsack problem using greedy approach. Show all the steps.
Write and explain the Insertion sort algorithm. Discuss its best and worst-case time complexity.
Explain the divide and conquer approach of multiplying two large matrices of size 16 x 16. Compute the time complexity of this approach.
Consider the following Graph:
Figure 1: A sample weighted Grари
a) Write the Kruskal's algorithm to find the minimum cost spanning tree of a graph. Also, find the time complexity of Kruskal's algorithm. Demonstrate the use of Kruskal's algorithm and Prim's algorithm to find the minimum cost spanning tree for the Graph given in Figure 1. Show all the steps.
Bellman-Ford's shortest path algorithm for the graph given in Figure 1. Show all the steps of computation.
search (where pi represents the probability that the search will be for the key node ki, whereas qi represents that the search is for dummy node di. Make suitable assumptions, if any)
Design and develop an efficient algorithm to find all the prime numbers in the range 2 to 10000.Access the complexity of this algorithm?