Question

1. State True of False in each of the following:
   1. 9 | 20.
   2. Ceil( – 3.1 ) – Floor( – 4.9 ) = 2.
   3. A set and its subset cannot have the same size.
   4. It is feasible to use an algorithm with time complexity 3ⁿ for n=90.
   5. If a function is one-to-one and injective, the function is called bijective.     
   6. If × represents Cartesian product, then A×B=B×A.      
   7. In a function, we can have more than one preimage of an image.         
   8. In a function, we can have more than one image of a preimage.
   9. Finding the maximum element from a sorted array cannot be done in O(1) time.
   10. Exponential time algorithms are better than polynomial time algorithms.

           

2. If ‘x’ and ‘y’ are the last and second-last digits of your PMU ID, find (x +₅ y) and (x ∙₅ y). Show the details of your work.

3. Consider X= “last two digits of your PMU ID”. Find the following. Show details of your solution.   (X)₁₆ = (?)₂

4. Using Caesar cipher with a key = last digit of your PMU ID, encrypt your ‘first name’.

5. Exactly how many comparisons are needed to find ‘1’ in the following array using binary search algorithm. Explain in detail.

1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 40

Answer 1

Here are answers for your questions.

True/false

1. True. ceil(-3.1)= -3 and floor(-4.9)= -5 . So, -3-(-5) = 2
2. False. Set is also a subset itself.
3. False.  3^n, n=90 have 8*10^42 iterations. And it is not feasible algorithm to compute.
4. False. One-to-one funtion is also called as injective funtion. Bijective function is a funtion which is one-to-one(injective) and onto(surjective).
5. False. Cartesian product A × B is the set of all ordered pair of elements from A and B. So, commutative property is not applicable.
6. True. A funtion can have more than one preimage of a image.
7. False. A function can't have more than one image of a preimage.
8. False. Finding the maximum element from a sorted array can be done in O(1) time. The element will be at first or last position of the array depending on the type of sort.
9. False. Exponential time is lot worse than polynomial time.

10) For this question, I don't have your PMU ID. But I will tell you how to do it.

For example: my PMU ID = 7245568

x = 8 and y = 6.

x+5y = 8 + 5*6 = 38

x*5y = 8 * 5*6 = 240

11) for example, last 2 digits of my PMU ID 'X'= 68

Each hexadecimal(base 16) digit represents four binary(base 2) digits. Simply convert every digit of hexadeimal number to 4bit binary number. Thier concatination is the binary(base 2) value of given hexadecimal(base 16) number. (You can simply determining which powers of two (8, 4, 2 or 1) sum up to your hex digits.) Example: 2 = 0010(0+0+2+0), 5 = 0101(0+4+0+1), 7 = 0111(0+4+2+1) etc

In my case,

6 = 0110(0+4+2+0) and 8 = 1000(8+0+0+0)

Therefore (68)₁₆ = (01101000)₂

You can eliminate left most 0s in the output final output. 01101000 = 1101000

12) Caeser cipher is simply a type of substitution cipher, i.e., each letter of a given text is replaced by a letter some fixed number of positions down the alphabet. For example with a shift of 2(key), A would be replaced by C, B would become D, C would become E and so on. If it reaches the end. It will continue from begining again i.e., Y would become A and Z would become B.

let my last name is KIRAN, last digit of my ID is 4 (Do it for your name and last digit of your id).

4th letter after K = O

4th letter after I = M

4th letter after R = V

4th letter after A = E

4th letter after N = R

therefore, KIRAN => OMVER

(To cross check, decrypt the encrypted text by replacing each letter with 4th letter before the encrypted letter.)

13) 4

We need 4 comparisions to find 1 in the given array.

{ 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 40 }

initially L=0 and H=16 ==> M = (L+H)/2 = 8

compare Arr[8] with 1. 12 is greater than 1. ==> H=(M-1)=7 ==> M = (L+H)/2 = 3

{ 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 40 }

compare Arr[3] with 1. 5 is greater than 1. ==> H=(M-1)=2 ==> M = (L+H)/2 = 1

{ 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 40 }

compare Arr[1] with 1. 2 is greater than 1. ==> H=(M-1)=0 ==> M = (L+H)/2 = 0

{ 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 40 }

compare Arr[1] with 1. 1 is equal to  1.

Hurray, We found the element. Index = M = 0

Total comparisions 4

-----------------------------------------------------------------------------------------------------------------------

Hope you understood.

If you have any doubts ask me in comment section.

If you like my work, please give me a like and feedback. That helps me a lot. Thank you.

All the best