Algorithms Answers

(i) Identify two problems in each category of the following time complexities and derive the

complexity of these identified problems.

O(n log n), and O(n2).

(ii) Suppose you are given n sets: S1, S2…..Sn.. Each set is having n elements. The problem is

to find whether some pairs of these sets are disjoint, i.e. there are no common elements

in these sets. Write pseudo code and calculate its time complexity.

Calculate the time complexity of the following program fragments.

(a) 𝑓𝑜𝑟 (𝑖 = 1; 𝑖 ≤ 𝑛; 𝑖 ∗ = 2)

{

𝑥 = 𝑥 + 1

}

(b) 𝑓𝑜𝑟 (𝑖 = 1; 𝑖 ≤ 𝑛; 𝑖 + +)

𝑓𝑜𝑟 (𝑗 = 1; 𝑗 ≤ 𝑛; 𝑗 = 𝑗 ∗ 2)

{

… .

… .

}

(a) Write a brute force method and Horner’s algorithm to evaluate a polynomial expression

and compute their complexities

(b) Evaluate the following polynomial expression using Horner’s rule. Assume the value of x

is 3.

p(𝑥) = 10𝑥⁵ + 6x⁴ + 3𝑥³ − 6𝑥² + 8𝑥 + 15

Show all the intermediate steps.

Let us consider you are going to be create a AVL tree by inserting one by one up to 15 nodes with the help of Random number generation function. At each node, after insertion you should maintain the tree as balanced one. Sketch the Avl tree from the first node insertion to last 15^th node insertion step by step. Then you have start to delete operation with 5^th,10th and 15^th input of inserted node. You have to follow the given details mentioned below for node input.

Sl.No

Student’s Roll Number

Range of Input

Insertion

Deletion

1

201IT101 - 201IT117

1 - 75

Totally 15 randomized numbers from the Specified range

Delete the 5^th , 10^th and 15^th randomized input number when inserted.

2

201IT118 - 201IT134

76 - 150

3

201IT135 - 201IT151

151 - 225

4

201IT152 - 201IT168

226 - 300

5

201IT169 - 201IT216

301 - 375

6

201IT218 - 201IT234

376 - 450

7

201IT235 - 201IT251

451 - 525

8

201IT252 - 201IT269

526 – 600

Program ( 5 Marks)

Tree Structure step by step (15 Marks) for 15 node insertion.

out of 500 bags of feeds. a supervisor decide to pick 70 bags random as a sample in order to ascertain the quality apply statistical tool assurance. the weight of each bag must be 10kg each. Apply appropriate statistical tool for the quality assurance of the feed

Create flowchart that will read the values of A & B. Compare the two values of A & B then print which of the values is higher including the remark "Higher".

Find the infix equivalents of the following postfix equivalents:

(A) A B + C * D –

Create an algorithm that will able to read the age of an individual and determine if it qualified to vote or not. The qualifying age to vote is 18 and above. If the age is 18 below, display "too young!". Note that there is no such age as 0 or negative however display "Invalid age" if age is above 100 display "Out of range".

short, English phrases used to explain specific tasks within a program.

The sum of two numbers is an example of an