#### 1. Differentiate between Union and Structure

Union | Structure |
---|---|

A union is a user-defined data type that allows multiple data types to be stored in the same memory location. | A structure is a user-defined data type that allows a collection of variables to be grouped together under a single name. |

In a union, only one member can be accessed at a time. Accessing one member overwrites the other members. | In a structure, all members can be accessed individually. |

The size of a union is determined by the largest member in the union. | The size of a structure is determined by the sum of the sizes of all its members. |

Unions are typically used when the memory needs to be conserved or when we want to interpret a piece of memory in different ways. | Structures are typically used when we want to group together related data items. |

Unions are less commonly used compared to structures. | Structures are more commonly used compared to unions. |

#### 2. Differentiate between Primitive and Non-Primitive Data Structure

Primitive Data Structure | Non-Primitive Data Structure |
---|---|

Primitive data structures are basic data types that can be directly operated upon by the machine. | Non-primitive data structures are derived data types that are created by combining or aggregating primitive data types. |

Primitive data structures have a fixed size in memory. | Non-primitive data structures can have a variable size in memory. |

Primitive data structures are usually not dynamic, meaning that their size cannot be changed during runtime. | Non-primitive data structures are often dynamic, meaning that their size can be changed during runtime. |

Primitive data structures are passed by value, which means that the actual data value is copied to a new location in memory. | Non-primitive data structures are passed by reference, which means that only the memory address of the data is passed to a new location. |

Examples of primitive data structures include integers, floating-point numbers, characters, and boolean values. | Examples of non-primitive data structures include arrays, lists, trees, graphs, and objects. |

#### 3. Differentiate between Linear and Non Linear Data Structure

# | Linear Data Structure | Non-Linear Data Structure |
---|---|---|

1 | A linear data structure is a data structure where data elements are arranged sequentially or linearly, and each element has a predecessor and a successor except the first and last elements. | A non-linear data structure is a data structure where data elements are not arranged sequentially or linearly, and each element may have zero, one or many predecessors and successors. |

2 | Linear data structures are easy to traverse and search, and are suitable for many applications such as arrays, stacks, queues, and linked lists. | Non-linear data structures are more complex to traverse and search, and are suitable for applications such as trees, graphs, and hash tables. |

3 | Examples of linear data structures include arrays, stacks, queues, and linked lists. | Examples of non-linear data structures include trees, graphs, and hash tables. |

4 | Linear data structures can be easily represented using arrays or linked lists. | Non-linear data structures require more complex representations such as trees, graphs, or hash tables. |

5 | Linear data structures have a linear space complexity, which means that the amount of memory used is directly proportional to the number of data elements. | Non-linear data structures can have a non-linear space complexity, which means that the amount of memory used may not be directly proportional to the number of data elements. |

#### 4. Differentiate between `getchar();`

and `putchar()`

getchar() | putchar() | |
---|---|---|

Definition | Reads a single character from the standard input stream. | Writes a single character to the standard output stream. |

Input | Reads input from the keyboard or a file. | Writes output to the screen or a file. |

Output | Does not output anything. | Outputs a single character to the screen or a file. |

Return value | Returns the ASCII value of the character read from input. | Does not return anything. |

Syntax | `int getchar(void)` |
`int putchar(int character)` |

Parameters | Does not take any parameters. | Takes a single parameter, which is the character to be written to output. |

Looping | Often used in a loop to read multiple characters from input. | Often used in a loop to write multiple characters to output. |

Buffering | Uses buffering; characters are read into a buffer before being processed. | Uses buffering; characters are written to a buffer before being displayed on the screen or written to a file. |

Error handling | Returns EOF (End of File) when it encounters an error or reaches the end of a file. | Does not have any error handling mechanism. |

Examples | Read input from the keyboard: `char c = getchar();` |
Output a single character to the screen: `putchar('A');` |

#### 5. How to analyze time complexity of any program. Read about Recursive methods, back-successive methods and master theorem.

Time complexity is an abstract way to represent the running time of an algorithm in terms of the rate of growth and Big-O notations only. It is an approximate estimation of how much time an algorithm will take for a large value of input size. To analyze the time complexity of a program, we need to follow the following steps:

- Identify the basic operations: Determine the operations that contribute most to the program's running time, such as comparisons, assignments, and arithmetic operations.
- Determine the input size: Identify the input size (n) that affects the program's running time. It could be the number of elements in an array, the length of a string, or the size of a matrix.
- Count the frequency of basic operations: Analyze the algorithm and count how many times each basic operation is performed in terms of the input size (n).
- Express the total count as a function of the input size (T(n)): Combine the counts of each basic operation and express them as a function of the input size (n).
- Find the highest order term: Identify the highest order term in T(n), as this term will dominate the growth of the function for large values of n.
- Remove the constant factors: Simplify the highest order term by removing any constant factors, as they become less significant as n grows.
- Express the time complexity using Big O notation: Represent the simplified highest order term using Big O notation (e.g., O(n), O(n^2), O(log n), etc.) to provide an upper bound on the program's running time.

#### 6. Analyze the complexity of the following program:

```
a() {
int i, j, k, n;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i^2; j++) {
for (k = 1; k <= n/2; k++) {
printf("Hello");
}
}
}
}
```

The answer is O(n^4). Lets us check how.

Method 1

The input size affecting the program’s running time is n. The outer loop i runs n times. The middle loop j tuns i^2 times for each outer loop iteration. The inner loop k runs n/2 times for each iteration of the middle loop. By expressing the total count as a function of an input size (T(n)), we get T(n) = Σ [i^2 * (n/2)] for i = 1 to n. We the find the highest order term: T(n) = (n/2) * Σ [i^2] for i = 1 to n The sum of squares of the first n integers is given by the formula: Σ [i^2] = n * (n + 1) * (2n + 1) / 6 or it can be written as: T(n) = (n/2) * n * (n + 1) * (2n + 1) / 6 Removing the constant figures we get: T(n) = n^2 * (n + 1) * (2n + 1) / 12. Thus, as n grows large, the terms n^2, n, and 2n+1 dominate the growth of the function. And so, we get the time complexity of the given program is O(n^4), as the highest order term is n^2 * n * 2n, which is n^4.

Did not understand? Here's the easier Way:

Let's analyze the time complexity of the given code snippet:

- The outer loop runs n times.
- The middle loop runs i^2 times, where i is the current iteration of the outer loop. Since it is nested inside the outer loop, the number of iterations will be the sum of squares of all integers from 1 to n, which can be expressed as (n * (n + 1) * (2n + 1)) / 6.
- The innermost loop runs n/2 times, and it is nested inside both the outer and middle loops.

To calculate the total time complexity, we multiply the number of iterations of each loop:

- Outer loop: n
- Middle loop: (n * (n + 1) * (2n + 1)) / 6
- Innermost loop: n/2

Total time complexity: n * (n * (n + 1) * (2n + 1)) / 6 * n/2

Now we simplify the expression and keep the highest order term:

- The highest degree term in the expression is n^4, as it is the term that dominates the growth of the function for large values of n.

Therefore, the time complexity of the given code snippet is O(n^4).

#### 7. How to find the address of an element present in an array

Array is a collection of homogeneous data. To find the address of an element present in an array, you can use the following formula:

Address of element = Base address + (Index of element * Size of data type)

Here, the base address is the memory location of the first element in the array, the index of the element is its position in the array (starting from 0), and the size of the data type is the memory required for a single element in the array (in bytes).

#### 8. Design an algorithm to find the greatest / largest number within the elements of the array.

For finding the largest number within the elements of the array, we can use the following algorithm:

- Initialize a variable max and set its value to the first element of the array.
- Iterate through the array from the second element to the last element.
- For each element, compare it with the max value.
- If the current element is greater than max, update the value of max to the current element.
- After iterating through the array, the value of max will be the largest number in the array.

We can implement the above steps in the following manner:

```
#include <iostream>
using namespace std;
int main() {
int n, max;
cout << "Enter the number of elements in the array: " ; cin>> n;
int arr[n];
cout << "Enter the array elements: " ;
for(int i=0; i < n; i++) {
cin>> arr[i];
}
max = arr[0];
for(int i = 1; i < n; i++) {
if(arr[i]> max) {
max = arr[i];
}
}
cout << "Largest number in the array: " << max << endl;
return 0;
}
```

#### 9. Using the continue statement WAP in C to read 15 integers from the user and print the sum of only the positive integer.

In C, we can write the program which follows the above requirements in the following manner:

```
#include <stdio.h>
int main() {
int i, num, sum = 0;
for (i = 0; i < 15; i++) {
scanf("%d", &num);
if (num < 0) {
continue;
}
sum += num;
}
printf("Sum of positive integers: %d\n", sum);
return 0;
}
```

And in C++ we can write the program which fulfills the above requirements in the following way:

```
#include <iostream>
using namespace std;
int main() {
int num, sum = 0;
for (int i = 0; i < 15; i++) {
cin >> num;
if (num < 0) {
continue;
}
sum += num;
}
cout << "Sum of positive integers: " << sum << endl;
return 0;
}
```

#### 10. Differentiate between an AVL tree and explain the balance factor in an AVL tree.

Property | Binary Search Tree | AVL Tree |
---|---|---|

Definition | A node-based binary tree data structure. | A self-balancing binary search tree. |

Child Nodes | Each node has at most two child nodes. | Same as BST but with additional balancing properties. |

Balancing | No strict rules for balancing the tree height. | Strictly balanced based on the balance factor. |

Time Complexity | Can become unbalanced, leading to O(n) worst-case time. | Guarantees O(log n) time complexity for operations. |

Subtree Constraints | No additional constraint on the left and right subtree. | Left & right subtree heights differ by at most 1. |

The balance factor of a node in an AVL tree is the difference between the height of its left subtree and the height of its right subtree. Mathematically, it can be defined as:

Balance Factor = Height(Left Subtree) - Height(Right Subtree)

A node is considered balanced if its balance factor is -1, 0, or 1. If the balance factor of any node becomes less than -1 or greater than 1, the tree is considered unbalanced and needs to be rebalanced through rotations. These rotations can be single (left or right) or double (left-right or right-left) depending on the imbalance scenario.