Test my Merit My Results Create Exam

Higher Study | Algorithms

Algorithm Design Techniques Graphs/Spanning Tree and Shortest Paths Asymptotic Worst Case Time and Time Complexity Searching
which of the following is not a stable sorting algorithm in its typical implementation?
What is the best case complexity of QuickSort?
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?
Algorithm design technique used in quicksort algorithm is?
An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE ?
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is 
Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denotes the selling price of a rod whose length is i meters. Consider the array of prices: p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18 Which of the following statements is/are correct about R7?
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: 1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. 2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter. Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string? 
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
Four  matrices  M1, M2, M3 and M4 of dimensions p×q, q×r, r×s and s×t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as [(M1 × M2) × (M3 × M4)] the total number of scalar multiplications is  pqr + rst + prt. When multiplied as [((M1 × M2)× M3)) × M4], the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the minimum number of scalar multiplications needed is:
Which of the following is a correct time complexity to solve the 0/1 knapsack problem where n and w represents the number of items and capacity of knapsack respectively?
Let f(n) = n and g(n) = n(1 + sin n), where n is a positive integer. Which of the following statements is/are correct? I. f(n) = O(g(n)) II. f(n) = Ω(g(n))
Ads