###### Operating-Systems

October 3, 2023###### Database-Management-System

October 3, 2023# Algorithms

Question 17 |

Match the algorithms with their time complexities:

AlgorithmTime complexity(P) Towers of Hanoi withndisks (i) Θ(n^{2}) (Q) Binary search givennstored numbers (ii) Θ(n log n) (R) Heap sort givennnumbers at the worst case (iii) Θ(2^{n}) (S) Addition of twon×nmatrices (iv) Θ(log n)

P→(iii), Q→(iv), R→(i), S→(ii) | |

P→(iv), Q→(iii), R→(i), S→(ii) | |

P→(iii), Q→(iv), R→(ii), S→(i) | |

P→(iv), Q→(iii), R→(ii), S→(i) |

Question 17 Explanation:

In this problem, we have to find Average case of different algorithms

→ Tower of Hanoi with n disks takes θ(2

It is a mathematical game or puzzle.

It consists of three rods and a number of disks of different sizes, which can slide onto any rod.

The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.

3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves.

The minimal number of moves required to solve a Tower of Hanoi puzzle is 2

→ Tower of Hanoi with n disks takes θ(2

^{n}) timeIt is a mathematical game or puzzle.

It consists of three rods and a number of disks of different sizes, which can slide onto any rod.

The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.

3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves.

The minimal number of moves required to solve a Tower of Hanoi puzzle is 2

^{n}-1, where n is the number of disks. → Binary Search given n sorted numbers takes Ɵ(log_{2} n)

→ Heap sort given n numbers of the worst case takes Ɵ(n log n)

→ Addition of two n×n matrices takes Ɵ(n^{2})

Correct Answer: C

Question 17 Explanation:

In this problem, we have to find Average case of different algorithms

→ Tower of Hanoi with n disks takes θ(2

It is a mathematical game or puzzle.

It consists of three rods and a number of disks of different sizes, which can slide onto any rod.

The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.

3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves.

The minimal number of moves required to solve a Tower of Hanoi puzzle is 2

→ Tower of Hanoi with n disks takes θ(2

^{n}) timeIt is a mathematical game or puzzle.

It consists of three rods and a number of disks of different sizes, which can slide onto any rod.

The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.

3. No disk may be placed on top of a smaller disk.

With 3 disks, the puzzle can be solved in 7 moves.

The minimal number of moves required to solve a Tower of Hanoi puzzle is 2

^{n}-1, where n is the number of disks. → Binary Search given n sorted numbers takes Ɵ(log_{2} n)

→ Heap sort given n numbers of the worst case takes Ɵ(n log n)

→ Addition of two n×n matrices takes Ɵ(n^{2})

Subscribe

Login

0 Comments