Register

IIT Madras MS written test 2019 - Algorithms - 1

1,285 views
0 0 votes

Let SP be the problem of finding the shortest path between 2 nodes, and LP be the problem of finding the longest path between 2 nodes, in an unweighted, undirected graph. Which of the following is true?

  1. SP is NP-hard, LP is not
  2. LP is NP-hard, SP is not
  3. Both are NP-hard
  4. Neither SP nor LP is NP-hard

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · IIT Madras MS writte...Next → · IIT Madras MS writte...
← Previous in category · ISI 2018 PCB C5Next in category → · Mimimum number of co...
Position:
Show:

Related questions

0 0 votes
1 answers 1 answer
1.1k
1.1k views
SPluto asked May 2, 2019
1,106 views
IIT Madras MS written test 2019 - TOC - 1
Let L1 and L2 be 2 languages which are not regular. Which of these is true?The union of L1 and L2 is not regular.The intersection of L1 and L2 is not regular.Both I and I...
0 0 votes
0 0 answers
851
851 views
SPluto asked May 2, 2019
851 views
IIT Madras MS written test 2019 - OS - 1
A scheduler – such as an OS scheduler – can suffer from the priority inversion problem, in which a lower priority process indirectly pre-empts a higher priority process, ...
0 0 votes
2 2 answers
972
972 views
SPluto asked May 2, 2019
972 views
IIT Madras MS written test 2019 - DBMS
Which of the following statements about SQL queries is true?The GROUP BY clause has nothing to do with Aggregate functions.The GROUP BY clause can only be used when Aggre...
1 1 vote
1 answers 1 answer
1.3k
1.3k views
SPluto asked May 2, 2019
1,279 views
IIT Madras MS written test 2019 - C prog.
for(; i != 0; i) { printf("\nIITM"); i; }If i is initialized to 100, then IITM will be printed 50 timesIf i is initialized to 101, then IITM will be printed 51 timesBot...