Design Algorithms MCQ with Answers Set-1

For parameters a and b, both of which are$ω(1),T(n)=T(n^{\frac{1}{a}})+1,and T(b)=1$

Then T(n) is

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.

Amount the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?

There are n unsorted arrays: $A_{1},A_{2},.......,A_{n}$.Assume that n is odd. Each of $A_{1},A_{2},.......,A_{n}$ contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of $A_{1}, A_{2},......., A_{n}$ is

Let G be any connected, weighted, undirected graph.

1. G has a unique minimum spanning tree, if no two edges of G have the same weight.,
2. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Which of the above two statements is/are TRUE?

1. The smallest element in a max-heap is always at a leaf node
2. The second largest element in a max-heap is always a child of the root node
3. A max-heap can be constructed from a binary search tree in $\Theta(n)$ time
4. A binary search tree can be constructed from a max-heap in $\Theta(n)$ time

1. There is a main hash table of size 4.
2. The 2 least significant bits of a key are used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
5. First, the 3^rd least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4^th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places).

The number of permutations of the characters in LILAC so that no character appears in its original position if the two L’s are indistinguishable, is

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is

Consider a graph G=(V,E), where $V = \left\{ V_{1},V_{2},........,V_{100} \right\}, E =\left\{ V_{i},V_{j} |1\le i \lt j\le 100\right\}$, and weight of the edge $(V_{i},V_{j})$ is $\left| i-j \right|$. the weight of minimum spanning tree of G is