- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- Who invented the inclusion-exclusion pri...

Q. |
## Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem? |

A. | karp |

B. | leonard adleman |

C. | andreas bjorklund |

D. | martello |

Answer» C. andreas bjorklund | |

Explanation: andreas bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of hamiltonian cycles. |

View all MCQs in:
Design and Analysis of Algorithms

- There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
- Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
- Hamiltonian path problem is
- Which of the following problems is similar to that of a Hamiltonian path problem?
- Who formulated the first ever algorithm for solving the Hamiltonian path problem?
- In what time can the Hamiltonian path problem can be solved using dynamic programming?
- Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
- For a graph of degree three, in what time can a Hamiltonian path be found?
- What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
- You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?

Login to Continue

It will take less than 2 minutes

Report MCQ