Solution

Categorical data, which represents distinct groups or categories, is best represented by string data types in a data warehouse. Integer or float are typically used for numeric data, and boolean represents true/false values.

Solution

Data normalization primarily aims to reduce redundancy and inconsistency in the data by organizing it into well-structured relational tables. It involves dividing larger tables into smaller ones to remove repeating groups or duplicates.

Solution

Discretization converts continuous data into a series of intervals or bins, which helps in categorizing data and making it easier to analyze, especially for certain machine learning models or statistical methods.

Solution

The total number of cells in the cube is: 365×50×100=1,825,000

Thus, there are 1,825,000 cells in the data cube.

Solution

After a 60% reduction, the number of rows is:

New rows=40 million×(1−0.60)=40×0.40=16million

Since compression reduces storage but not the number of rows, the number of rows remains 40 million, not 24 million.

Thus, rows are unchanged, but compressed storage would be reduced by 60%.

Solution

For equal-frequency binning, divide the dataset into 4 bins, each containing 2 or 3 values: 1st bin: [2, 5, 6]

2nd bin: [10, 12]

3rd bin: [14, 20]

4th bin: [22, 25, 30]

Thus, the second bin contains the range [10, 12].

Solution

Inorder traversal of a binary search tree always produces the keys in increasing order.

But the question Reverse ordering of natural numbers are used i.e. 19 is assumed to be the smallest and 10 to be the largest. So the sequence in increasing order will be 19, 18, 17, 16, 15, 14, 13, 12, 11, 10. So, option (D) is correct.

Solution

When we delete the root node, the root node position will be empty. It can be replaced by either inorder successor or an inorder predecessor.

Inorder successor of 16 nodes is the 24.

Inorder predecessor of 16 is 13.

Successor is the leftmost element in the right subtree.

Predecessor is the rightmost element in the left subtree.

Solution

For an k-ary tree where each node has k children or no children, following relation holds

L = (k-1)*n + 1

Where L is the number of leaf nodes and n is the number of internal nodes.

since its a complete k tree, so every internal node will have K child

Let us see following for example for a full ternary tree.

k = 3

Number of internal nodes n = 4 ………………[This includes root node too]

Number of leaf nodes = (k-1)*n + 1

= (3-1)*4 + 1

= 9

Solution

The starting vertex can be any one of the N vertices. Once the starting vertex has been chosen, the next vertex can be chosen in N-1 ways, as every other vertex is directly connected to starting vertex.

Again next vertex can be picked in (N-2) ways.

next vertex can be picked in (N-3) ways.

…

….

Last vertex can be picked in 1 way.

Total number of DFS traversals = N * (N-1) * (N-2)* (N-3)....* 1 = N!

Solution

Hashing is a data structure which is used to map a given value with a particular key for faster access of elements. Whereas arrays, linked list, BST doesn’t have that motivation to do, hence those can’t be the answer.

In a direct access table where we make a big array and use phone numbers as index in the array. An entry in the array is NIL if the phone number is not present, else the array entry stores a pointer to records corresponding to the phone number. Time complexity wise this solution is the best among all, we can do all operations in O(1) time. For example, to insert a phone number, we create a record with details of given phone number, use phone number as an index and store the pointer to the created record in the table.

This solution has many practical limitations. First problem with this solution is that the extra space required is huge. For example if phone number is n digits, we need O(m * 10n) space for a table where m is the size of a pointer to record. Another problem is an integer in a programming language may not store n digits.

Due to above limitations Direct Access Table cannot always be used. Hashing is the solution that can be used in almost all such situations and performs extremely well compared to above data structures like Array, Linked List, Balanced BST in practice. With hashing we get O(1) search time on average (under reasonable assumptions) and O(n) in the worst case.

Hashing is an improvement over Direct Access Table. The idea is to use a hash function that converts a given phone number or any other key to a smaller number and uses the small number as index in a table called hash table.

Solution

When the tree is skew tree, in both cases of BT and BST, in worse case the time complexity will be O(n)

As the height of balanced BST is logn so the search time will be of order logn in worse case scenario too.

In the case of min heap, searching a minimum number takes O(1) time but searching any other element in the worst case will take O(n) , as it can also be of skewed structure.

Solution

a b c d e f g is wrong. Because b,c,g are adjacent nodes of a hence after b, c there must be g.

Instead a b c g d e f is correct.

All other options are correct

Solution

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph.

For example, another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).

Solution

Total number of candidate keys possible with ‘n’ attributes is (2^n)-1.

Solution

While converting the ER model into the relational model, we should create a separate table for each multivalued attribute. Hence, {Roll_no, Mob_no} and {Roll_no, Email_id} are the valid attribute sets for the newly created relations among the given options.

Solution

The candidate key is HI. There are no parts of the key that are determined by the non prime attributes. Hence, the relation R is in 2NF

Solution

The given set of FDs F is:- A → BC CD → E B → D E → A

The left side of each FD in F is unique. Also none of the attributes in the left side or right side of any of the FDs is extraneous. Therefore the canonical cover Fc is equal to F.

Solution

Solution

The data can be sorted using external sorting which uses a merging technique. This can be done as follows:

Step-1. Divide the data into 10 groups each of size 2 GB.

Step-2. Sort each group and write them to disk.

Step-3. Load 10 items from each group into the main memory.

Step-4. Output the smallest item from the main memory to disk. Load the next item from the group whose item was chosen.

Step-5. Iterate step-4 until all items are not outputted.

Solution

To construct a spanning tree of graph, we have to remove E – V + 1 edges.

Example:

= E – V + 1

= 3 – 3 + 1

= 1

Solution

Given 2, 6, 8, 1, 4, 3

Pass1:

I =0

j = 0: 2, 6, 8, 1, 4, 3

j = 1: 2, 6, 8, 1, 4, 3

j = 2: 2, 6, 1, 8, 4, 3

j = 3: 2, 6, 1, 4, 8, 3

j = 4: 2, 6, 1, 4, 3, 8

Pass 2

I = 1

j = 0: 2, 6, 1, 4, 3, 8

j = 1: 2, 1, 6, 4, 3, 8

j = 2: 2, 1, 4, 6, 3, 8

j = 3: 2, 1, 4, 3, 6, 8

Pass 3

I = 2

j = 0: 1, 2, 4, 3, 6, 8

j = 1: 1, 2, 3, 4, 6, 8

j = 2: 1, 2, 3, 4, 6, 8

Solution

Max MST:

=5+7+3+4+2+5+4+3+2+3

=38

Min MST:

=1+2+1+2+1+1+2+1+2+3

=16

Common: S6, S9 ✓

S7, S10

Solution

The recurrence relation to get minimum number of scalar multiplications are

→ To get maximum value, we are choosing maximum instead of minimum.

We can get a maximum of 5 possible parentheses using standard dynamic programming method (or) using catalan numbers.

Given the matrices A,B,C,D

Assume the dimensions of A=d₀×d₁, etc..,

Below are the five possible parenthesizations of these arrays, along with the number of multiplications:

(AB)(CD) → d₀d₁d₂ + d₂d₃d₄ + d₀d₂d₄ → 300 + 378 + 540 = 1218

((AB)C)D → d₀d₁d₂ + d₀d₂d₃ + d₀d₃d₄ → 300 + 420 + 630 = 1350

(A(BC))D → d₁d₂d₃ + d₀d₁d₃ + d₀d₃d₄ → 210 + 350 + 630 = 1190

A((BC)D) → d₁d₂d₃ + d₁d₃d₄ + d₀d₁d₄ → 210 + 315 + 450 = 975

A(B(CD)) → d₂d₃d₄ + d₁d₂d₄ + d₀d₁d₄ → 378 + 270 + 450 = 1098

→ The maximum number of scalar multiplications are 1350 and optimal parenthesization is ((AB)C)D

→ The minimum number of scalar multiplications are 975 and optimal parenthesization is (A((BC)D))

→ Difference between maximum and minimum scalar multiplications are

= 1350-975

= 375

Solution

→ True. Simply call BUILD-HEAP at the root, which runs in O(n) time.

→ True: The shortest path to t can be easily computed given the shortest paths to all vertices from which there is an edge to t.

→ False: Merge sort is stable whenever the underlying merge operation always breaks ties by selecting from the left sub-array, and it is easy to ensure that this is the case.

→ False. The auxiliary sorting routine in radix sort needs to be stable, meaning that numbers with the same value appear in the output array in the same order as they do appear in the input array. Heapsort is not stable. It does operate in place, meaning that only a constant number of elements of the input array are ever stored outside the array.

Solution

The tree structure is:

X

/ \

Y Z

/ \ /

P Q R

- Starting from 'X':

- 1 (initial) + 3 (from 'Y' subtree) + 2 (from 'Z' subtree) = 6

Thus, the output is 6.

Solution

Breaking down the values:

- w = 3

- x is nested:

- y = 7

- z is nested:

- p = 2

- m is nested:

- n = 1

- o = 4

Total = 3 + 7 + 2 + 1 + 4 = 17

Solution

Given the list `X = [12, 10, 15, 9, 16]`:

- Compare `X[1]` (10) with `X[0]` (12) → 12 - 10 = 2 → `D[1] = 2`

- Compare `X[2]` (15) with `X[1]` (10) → no change → `D[2] = 0`

- Compare `X[3]` (9) with `X[2]` (15) → 15 - 9 = 6 → `D[3] = 6`

- Compare `X[4]` (16) with `X[3]` (9) → no change → `D[4] = 0`

Thus, the final result is `[0, 2, 0, 6, 0]`.

Solution

The function returns the cumulative sum (prefix sum) of the list arr. For the input arr = [2, 4, 6, 8], the cumulative sums at each index are:

Index 0: 2

Index 1: 2 + 4 = 6

Index 2: 6 + 6 = 12

Index 3: 12 + 8 = 20

The result is [2, 6, 12, 20].

Solution

The function computes the sum of the first n terms of a geometric series with a common ratio r. The formula is:

S = (1-r^n) / (1-r)

For n=8 and r = 3, the result is:

s= (1-3^8) / 1-3

=(1-6561)/-2

=-6560/-2

=3280

Solution

The function generates all possible substrings of the string s and then returns the longest one.

For the input string "xyz", the substrings are:

"x", "xy", "xyz",

"y", "yz",

"z"

The longest substring is "xyz", which is returned by the function.

Solution

The function splits the input string "5-15-25" by the hyphen (-), converts each part to an integer, and then sums them up.

For the string "5-15-25", the split parts are: [5, 15, 25].

The sum of these integers is:

5+15+25=50

Solution

The function fun(s, n) repeats the string s exactly n times.

In this case:

fun("X", 4) produces "XXXX",

Adding "Y" results in "XXXXY",

Finally, fun("X", 2) produces "XX".

Concatenating these parts gives the result "XXXXYX".