Algorithms Test...

What is the worst-case and average-case time complexity of the Binary search?

Consider the below-given statement written in C language:

int A = {25, 9, 15, 30, 11, 17 , 22}

Bubble sort is applied on array A. Which element is present at index 2 after the second iteration?

What is the time complexity for the below given block of code where i, j, n are integers and lines of code do contain any extra line space between them?

                for(i = 0; i < n; i ++ )

                for(j = m ; j > 0; j = j/2)

Consider the following table:

If T(n) = 2T(n/2)+nlogn then T(n)?

If G = (V,E) is a directed graph, then length of adjacency list is ______ and it requires ______ amount of memory.

Consider 5 array of size 25, 31, 37, 49, 57 respectively. All arrays are sorted. All the arrays into a single array by using the optimal algorithm and the single array is again a sorted array. What is the maximum number of comparisons that will be needed in the worst case?

Consider an array A of size 63, which consists of only 1’s or 0’s in it. In array A elements are arranged in ascending order. The maximum number of probes needed to find the minimum index j of A for which A[j] = 1 using optimal algorithm is _____.

Consider a hypothetical system in which merge sort is implemented on an array of size of 2 bytes each. The size of the array is 2 MB. The maximum time taken by the merge sort to process the array is 256 seconds. What is the size of the input in MB of a problem that can be solved in 81.92 minutes?

Consider two strings M = ”abababbaa” and N = ”babaa”.  The length of the longest common subsequence between two given string is r and the number of times the length of the longest common subsequence repeated in the matrix is n while using Dynamic programming. What is the value of r + r×n + n² ?

NOTE: Common subsequence may not necessarily be contiguous

Consider the following statements:

(i). The height of any binary search tree with n nodes is \(O(logn)\)

(ii). Inserting into an AVL tree with n nodes requires \(\theta (logn)\) rotations.

(iii). In a max-heap, k^th largest element will always be on k^th level.

Which of the above statements is/are FALSE?

Consider the 10 Jobs for A to J. The execution of each job takes 1 unit of time. One job can be executed at a time. Each job is related with a profit and a deadline. If job is completed before deadline then the corresponding profit is earned. The maximum profit earned is _____.