Aspire Faculty ID #18797 · Topic: UGC NET Computer Science Sep 2022 (Paper II) · Just now
UGC NET Computer Science Sep 2022 (Paper II)

Consider the following statements of approximation algorithm:

Statement I: Vertex-cover is a polynomial time 2-approximation algorithm.
Statement II: TSP-tour is a polynomial time 3-approximation algorithm for travelling salesman problem with the triangle inequality.
Which of the following is correct?

Solution

Statement I:

For the Vertex Cover problem, there is a standard polynomial time approximation algorithm.

It repeatedly chooses an edge and includes both endpoints in the vertex cover.

This gives a solution whose size is at most $2$ times the optimal solution.

So, Vertex-cover has a polynomial time $2$-approximation algorithm.

Therefore, Statement I is true.

Statement II:

For Travelling Salesman Problem with triangle inequality, the standard MST based TSP-tour approximation algorithm gives a $2$-approximation.

It does not give a $3$-approximation as the standard result.

So, the statement saying it is a polynomial time $3$-approximation algorithm is not correct in the standard form.

Therefore, Statement II is false.

Previous 10 Questions — UGC NET Computer Science Sep 2022 (Paper II)

Nearest first
1
Consider the following:List IList II(A) Stack algorithm(I) Deadlock(B) Elevator algorithm(II) Disk scheduling(C) Priori…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
2
Consider the following algorithms and their running times:List IList II(A) Breadth First Search(I) $\theta(V+E)$(B) Rab…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
3
Match List I with List II:List IList II(A) Physical layer(I) Routing of the signals, divide the outgoing message into p…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
4
Match List I with List II:List IList II(A) BIND(I) Block the caller until a connection attempt arrives(B) LISTEN(II) Gi…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
5
Match List I with List II:List IList II(A) DES(I) Key size - 256(B) AES(II) Key size - 1024(C) 3 DES(III) Key size - 56…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
6
Match List I with List II:List IList II(A) Firmware(I) Number of logical records into physical blocks(B) Batch file(II)…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
7
Match List I with List II: List I List II (A) Least frequently used (I) Memory is distributed among processors (…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
8
Match List I with List II:List-IList-II(A) Ontological Engineering(I) Organizing subclass relations(B) Taxonomy Hierarc…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
9
Match List I with List II:List IList II(A) Type 0(I) Finite Automata(B) Type 1(II) Turing Machine(C) Type 2(III) Linear…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
10
Match List I with List II:List-IList-IIA. LocalizationI. EncapsulationB. Packaging or binding of a collection of items.…
Topic: UGC NET Computer Science Sep 2022 (Paper II)

Next 10 Questions — UGC NET Computer Science Sep 2022 (Paper II)

Ascending by ID
1
Consider the following statements:Statement I: Conservative 2 PL is a deadlock-free protocol.Statement II: Thomas's wri…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
2
Consider the following statements:Statement I: Composite attributes cannot be divided into smaller subparts.Statement I…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
3
A top down approach to programming calls for:Statement I: Working from the general to the specific.Statement II: Postpo…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
4
Consider the following statements:Statement I: LALR parser is more powerful than canonical LR Parser.Statement II: SLR …
Topic: UGC NET Computer Science Sep 2022 (Paper II)
5
Consider the following statements about Context Free Language (CFL):Statement I: CFL is closed under homomorphism.State…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
6
Consider the following in Boolean Algebra$X:a\lor(b\land(a\lor c))=(a\lor b)\land(a\lor c)$$Y:a\land(b\lor(a\land c))=(…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
7
A good software requirement specification does NOT have the characteristic
Topic: UGC NET Computer Science Sep 2022 (Paper II)
8
Given below are two statements: one is labelled as Assertion (A) and the other is labelled as Reason (R):Assertion (A):…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
9
Of the following, which is NOT a logical error?
Topic: UGC NET Computer Science Sep 2022 (Paper II)
10
Given below are two statements: one is labelled as Assertion (A) and the other is labelled as Reason (R):Assertion (A):…
Topic: UGC NET Computer Science Sep 2022 (Paper II)
Ask Your Question or Put Your Review.

loading...