The travelling salesman problem can be solved in: (A) Polynomial time using dynamic programming algorithm (B) Polynomial time using branch-and-bound algorithm (C) Exponential time using dynamic programming algorithm or branch-andbound algorithm. (D) Polynomial time using backtracking algorithm.

The travelling salesman problem can be solved in: (A) Polynomial time using dynamic programming algorithm (B) Polynomial time using branch-and-bound algorithm (C) Exponential time using dynamic programming algorithm or branch-andbound algorithm. (D) Polynomial time using backtracking algorithm.
by

1 Answer

Answer :

(C) Exponential time using dynamic programming algorithm or branch-andbound algorithm.
by

Related questions

Which of the following algorithm design technique is used in the quick sort algorithm? a) Dynamic programming b) Backtracking c) Divide-and-conquer d) Greedy method

Description : Which of the following algorithm design technique is used in the quick sort algorithm? a) Dynamic programming b) Backtracking c) Divide-and-conquer d) Greedy method

Last Answer : Which of the following algorithm design technique is used in the quick sort algorithm? a) Dynamic programming b) Backtracking c) Divide-and-conquer d) Greedy method

Dijkstra’s algorithm is based on (1) Divide and conquer paradigm (2) Dynamic Programming (3) Greedy Approach (4) Backtracking paradigm

Description : Dijkstra’s algorithm is based on (1) Divide and conquer paradigm (2) Dynamic Programming (3) Greedy Approach (4) Backtracking paradigm

Last Answer : 3

Which of the following statements is true for Branch-and-Bound search? (A) Underestimates of remaining distance may cause deviation from optimal path. (B) Overestimates can’t cause right path to be overlooked. (C) Dynamic programming principle can be used to discard redundant partial paths. (D) All of the above

Description : Which of the following statements is true for Branch-and-Bound search? (A) Underestimates of remaining distance may cause deviation from optimal path. (B) Overestimates can't cause right path to be ... Dynamic programming principle can be used to discard redundant partial paths. (D) All of the above

Last Answer : (C) Dynamic programming principle can be used to discard redundant partial paths.

An all-pairs shortest-paths problem is efficiently solved using: (A) Dijkstra' algorithm (B) Bellman-Ford algorithm (C) Kruskal Algorithm (D) Floyd-Warshall algorithm

Description : An all-pairs shortest-paths problem is efficiently solved using: (A) Dijkstra' algorithm (B) Bellman-Ford algorithm (C) Kruskal Algorithm (D) Floyd-Warshall algorithm

Last Answer : (D) Floyd-Warshall algorithm

The Hungarian method for solving an assignment problem can also be used to solve: a. A transportation problem b. A travelling salesman problem c. A linear programming problem d. Both a and b

Description : The Hungarian method for solving an assignment problem can also be used to solve: a. A transportation problem b. A travelling salesman problem c. A linear programming problem d. Both a and b

Last Answer : b. A travelling salesman problem

Which of the following is/are true w.r.t. applications of mobile computing? (A) Travelling of salesman (B) Location awareness services (1) (A) true; (B) false (2) Both (A) and (B) are true. (3) Both (A) and (B) are false. (4) (A) false; (B) true.

Description : Which of the following is/are true w.r.t. applications of mobile computing? (A) Travelling of salesman (B) Location awareness services (1) (A) true; (B) false (2) Both (A) and (B) are true. (3) Both (A) and (B) are false. (4) (A) false; (B) true.

Last Answer : Answer: 2

The BACKTRACKING-SEARCH algorithm in Figure 5.3 has a very simple policy for what to do when a branch of the search fails: back up to the preceding variable and try a different value for it. This is called chronological-backtracking. It is also possible to go all the way to set of variable that caused failure. a) True b) False

Description : The BACKTRACKING-SEARCH algorithm in Figure 5.3 has a very simple policy for what to do when a branch of the search fails: back up to the preceding variable and try a different value for it. This is ... also possible to go all the way to set of variable that caused failure. a) True b) False

Last Answer : a) True

The _______ is a touring problem in which each city must be visited exactly once. The aim is to find the shortest tour. a) Finding shortest path between a source and a destination b) Travelling Salesman problem c) Map coloring problem d) Depth first search traversal on a given map represented as a graph

Description : The _______ is a touring problem in which each city must be visited exactly once. The aim is to find the shortest tour. a) Finding shortest path between a source and a destination b) Travelling ... c) Map coloring problem d) Depth first search traversal on a given map represented as a graph

Last Answer : b) Travelling Salesman problem

Which of the following statements is false? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming. (B) Breadth-first search cannot be used to find connected components of a graph. (C) Given the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely. (D) Depth-first-search can be used to find the components of a graph. (1) A (2) B (3) C (4) D

Description : Which of the following statements is false? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming. (B) Breadth-first search cannot be used to find connected components of a graph. (C) ... used to find the components of a graph. (1) A (2) B (3) C (4) D 

Last Answer : Answer: 2

The map colouring problem can be solved using which of the following technique? (A) Means-end analysis (B) Constraint satisfaction (C) AO* search (D) Breadth first search

Description : The map colouring problem can be solved using which of the following technique? (A) Means-end analysis (B) Constraint satisfaction (C) AO* search (D) Breadth first search

Last Answer : (B) Constraint satisfaction

What is the most appropriate function of Memory Management Unit (MMU) ? (A) It is an associative memory to store TLB (B) It is a technique of supporting multiprogramming by creating dynamic partitions (C) It is a chip to map virtual address to physical address (D) It is an algorithm to allocate and deallocate main memory to a process

Description : What is the most appropriate function of Memory Management Unit (MMU) ? (A) It is an associative memory to store TLB (B) It is a technique of supporting multiprogramming by creating dynamic partitions ... to physical address (D) It is an algorithm to allocate and deallocate main memory to a process 

Last Answer : (C) It is a chip to map virtual address to physical address

Distance vector routing algorithm is a dynamic routing algorithm. The routing tables in distance vector routing algorithm are updated ........... (1) automatically (2) by server (3) by exchanging information with neighbour nodes. (4) with back up database

Description : Distance vector routing algorithm is a dynamic routing algorithm. The routing tables in distance vector routing algorithm are updated ........... (1) automatically (2) by server (3) by exchanging information with neighbour nodes. (4) with back up database

Last Answer : Answer: 3

Merge sort uses a) Divide-and-conquer b) Backtracking c) Heuristic approach d) Greedy approach

Description : Merge sort uses a) Divide-and-conquer b) Backtracking c) Heuristic approach d) Greedy approach

Last Answer : a) Divide-and-conquer

A perceptron is a ______________ a) Feed-forward neural network b) Backpropagation algorithm c) Backtracking algorithm d) Feed Forward-backward algorithm

Description : A perceptron is a ______________ a) Feed-forward neural network b) Backpropagation algorithm c) Backtracking algorithm d) Feed Forward-backward algorithm

Last Answer : a) Feed-forward neural network

Match the following types of variables with the corresponding programming languages: (a) Static variables (i) Local variables in Pascal (b) Stack dynamic (ii) All variables in APL (c) Explicit heap dynamic (iii) Fortran 77 (d) Implicit heap dynamic (iv) All objects in JAVA Codes: (a) (b) (c) (d) (A) (i) (iii) (iv) (ii) (B) (iv) (i) (iii) (ii) (C) (iii) (i) (iv) (ii) (D) (ii) (i) (iii) (iv)

Description : Match the following types of variables with the corresponding programming languages: (a) Static variables (i) Local variables in Pascal (b) Stack dynamic (ii) All variables in APL (c) Explicit heap dynamic (iii) Fortran 77 (d) Implicit ... (ii) (C) (iii) (i) (iv) (ii) (D) (ii) (i) (iii) (iv)

Last Answer : (C) (iii) (i) (iv) (ii) 

A perceptron is a ——————————–. a) Feed-forward neural network b) Back-propagation algorithm c) Back-tracking algorithm d) Feed Forward-backward algorithm e) Optimal algorithm with Dynamic programming

Description : A perceptron is a ——————————–. a) Feed-forward neural network b) Back-propagation algorithm c) Back-tracking algorithm d) Feed Forward-backward algorithm e) Optimal algorithm with Dynamic programming

Last Answer : a) Feed-forward neural network

Synthetic curve pass through defined data points and thus can be represented by a.polynomial equations b.exponential equations c.partial differential equations d.differential equations

Description : Synthetic curve pass through defined data points and thus can be represented by a.polynomial equations b.exponential equations c.partial differential equations d.differential equations

Last Answer : a.polynomial equations

In an organization that has high centralization…………… (a) Problem can be quickly and efficiently solved (b) The corporate headquarters is located centrally to branch offices (c) Top managers make all the decisions-lower-level managers merely carry out directions (d) All top-level officials are located within the same geographic area

Description : In an organization that has high centralization (a) Problem can be quickly and efficiently solved (b) The corporate headquarters is located centrally to branch offices (c) Top managers make ... merely carry out directions (d) All top-level officials are located within the same geographic area

Last Answer : (c) Top managers make all the decisions-lower-level managers merely carry out directions 

The message 11001001 is to be transmitted using the CRC polynomial x3+1 to protect it from errors. The message that should be transmitted is (A) 110010011001 (B) 11001001 (C) 110010011001001 (D) 11001001011

Description : The message 11001001 is to be transmitted using the CRC polynomial x3+1 to protect it from errors. The message that should be transmitted is (A) 110010011001 (B) 11001001 (C) 110010011001001 (D) 11001001011

Last Answer : (D) 11001001011

Which of the following statements is not true about disk-arm scheduling algorithms ? (A) SSTF (shortest seek time first) algorithm increases performance of FCFS. (B) The number of requests for disk service are not influenced by file allocation method. (C) Caching the directories and index blocks in main memory can also help in reducing disk arm movements. (D) SCAN and C-SCAN algorithms are less likely to have a starvation problem.

Description : Which of the following statements is not true about disk-arm scheduling algorithms ? (A) SSTF (shortest seek time first) algorithm increases performance of FCFS. (B) The number of requests for disk ... arm movements. (D) SCAN and C-SCAN algorithms are less likely to have a starvation problem.

Last Answer : (B) The number of requests for disk service are not influenced by file allocation method.

Using data p=3, q=11, n=pq, d=7 in RSA algorithm find the cipher text of the given plain text SUZANNE (A) BUTAEEZ (B) SUZANNE (C) XYZABCD (D) ABCDXYZ

Description : Using data p=3, q=11, n=pq, d=7 in RSA algorithm find the cipher text of the given plain text SUZANNE (A) BUTAEEZ (B) SUZANNE (C) XYZABCD (D) ABCDXYZ

Last Answer : (A) BUTAEEZ

Using p=3, q=13, d=7 and e=3 in the RSA algorithm, what is the value of ciphertext for a plain text 5? (A) 13 (B) 21 (C) 26 (D) 33

Description : Using p=3, q=13, d=7 and e=3 in the RSA algorithm, what is the value of ciphertext for a plain text 5? (A) 13 (B) 21 (C) 26 (D) 33

Last Answer : Answer: Marks to all Explanation: p=3, q=13, d=7, e=3, M=5, C=? C = Me mod n n = p*q  = 3*13 = 39 C = 53 mod 39 = 8 Answer is 8.

Let R be the rectangular window against which the lines are to be clipped using 2D Sutherland-Cohen line clipping algorithm. The rectangular window has lower left-hand corner at (-5,1) and upper righthand corner at (3,7). Consider the following three lines for clipping with the given end point co-ordinates: Line AB: A(-6,2) and B(-1,8) Line CD: C(-1,5) and D(4,8) Line EF: E(-2,3) and F(1,2) Which of the following line(s) is/are candidate for clipping? (A) AB (B) CD (C) EF (D) AB and CD

Description : Let R be the rectangular window against which the lines are to be clipped using 2D Sutherland-Cohen line clipping algorithm. The rectangular window has lower left-hand corner at (-5,1) and upper righthand corner at (3,7). ... s) is/are candidate for clipping? (A) AB (B) CD (C) EF (D) AB and CD

Last Answer : (D) AB and CD

Consider a disk queue with I/O requests on the following cylinders in their arriving order: 6,10,12,54,97,73,128,15,44,110,34,45 The disk head is assumed to be at cylinder 23 and moving in the direction of decreasing number of cylinders. Total number of cylinders in the disk is 150. The disk head movement using SCAN-scheduling algorithm is: (1) 172 (2) 173 (3) 227 (4) 228

Description : Consider a disk queue with I/O requests on the following cylinders in their arriving order: 6,10,12,54,97,73,128,15,44,110,34,45 The disk head is assumed to be at cylinder 23 and moving in the direction ... . The disk head movement using SCAN-scheduling algorithm is: (1) 172 (2) 173 (3) 227 (4) 228

Last Answer : (2) 173

Below are the few steps given for scan-converting a circle using Bresenham's Algorithm. Which of the given steps is not correct? (1) Compute d = 3 – 2r (where r is radius) (2) Stop if x> y (3) If d<0, then d=4x+6 and x=x+1 (4) If d≥0,then d=4 *(x-y)+10, x=x+1 and y=y+1

Description : Below are the few steps given for scan-converting a circle using Bresenham's Algorithm. Which of the given steps is not correct? (1) Compute d = 3 – 2r (where r is radius) (2) Stop if x> y (3) If d

Last Answer : If d≥0,then d=4 *(x-y)+10, x=x+1 and y=y+1

In link state routing algorithm after construction of link state packets, new routes are computed using: (1) DES algorithm (2) Dijkstra's algorithm (3) RSA algorithm (4) Packets

Description : In link state routing algorithm after construction of link state packets, new routes are computed using: (1) DES algorithm (2) Dijkstra's algorithm (3) RSA algorithm (4) Packets 

Last Answer : Answer: 2

If the primal Linear Programming problem has unbounded solution, then it’s dual problem will have (A) feasible solution (B) alternative solution (C) no feasible solution at all (D) no bounded solution at all

Description : If the primal Linear Programming problem has unbounded solution, then it’s dual problem will have (A) feasible solution (B) alternative solution (C) no feasible solution at all (D) no bounded solution at all 

Last Answer : (C) no feasible solution at all

A basic feasible solution of a linear programming problem is said to be ............... if at least one of the basic variable is zero. (A) degenerate (B) non-degenerate (C) infeasible (D) unbounded

Description : A basic feasible solution of a linear programming problem is said to be ............... if at least one of the basic variable is zero. (A) degenerate (B) non-degenerate (C) infeasible (D) unbounded

Last Answer : (A) degenerate 

The region of feasible solution of a linear programming problem has a ............... property in geometry, provided the feasible solution of the problem exists. (A) concavity (B) convexity (C) quadratic (D) polyhedron

Description : The region of feasible solution of a linear programming problem has a ............... property in geometry, provided the feasible solution of the problem exists. (A) concavity (B) convexity (C) quadratic (D) polyhedron

Last Answer : (B) convexity

Let G(x) be generator polynomial used for CRC checking. The condition that should be satisfied by G(x) to correct odd numbered error bits, will be: (1) (1+x) is factor of G(x) (2) (1-x) is factor of G(x) (3) (1+x2) is factor of G(x) (4) x is factor of G(x)

Description : Let G(x) be generator polynomial used for CRC checking. The condition that should be satisfied by G(x) to correct odd numbered error bits, will be: (1) (1+x) is factor of G(x) (2) (1-x) is factor of G(x) (3) (1+x2) is factor of G(x) (4) x is factor of G(x)

Last Answer : (1+x) is factor of G(x)

Which is used for utility functions in game playing algorithm? a) Linear polynomial b) Weighted polynomial c) Polynomial d) Linear weighted polynomial

Description : Which is used for utility functions in game playing algorithm? a) Linear polynomial b) Weighted polynomial c) Polynomial d) Linear weighted polynomial

Last Answer : d) Linear weighted polynomial

Which is used for utility functions in game playing algorithm? a) Linear polynomial b) Weighted polynomial c) Polynomial d) Linear weighted polynomial

Description : Which is used for utility functions in game playing algorithm? a) Linear polynomial b) Weighted polynomial c) Polynomial d) Linear weighted polynomial

Last Answer : d) Linear weighted polynomial

Mathematical models using linear, dynamic, integer, or algorithm models are considered A. Project selection criteria B. A form of expert judgment C. Project selection methods D. A form of historical information

Description : Mathematical models using linear, dynamic, integer, or algorithm models are  considered  A. Project selection criteria B. A form of expert judgment C. Project selection methods D. A form of historical information

Last Answer : C. Project selection methods

Consider the following schemas: Branch = (Branch-name, Assets, Branch-city) Customer = (Customer-name, Bank-name, Customer-city) Borrow = (Branch-name, loan-number, customer account-number) Deposit = (Branch-name, Account-number, Customer-name, Balance) Using relational Algebra, the query that finds customers who have balance more than 10,000 is ................. (A) πcustomer-name(σbalance> 10000(Deposit)) (B) σcustomer-name(σbalance> 10000(Deposit)) (C) πcustomer-name(σbalance> 10000(Borrow)) (D) σcustomer-name(σbalance> 10000(Borrow))

Description : Consider the following schemas: Branch = (Branch-name, Assets, Branch-city) Customer = (Customer-name, Bank-name, Customer-city) Borrow = (Branch-name, loan-number, customer account-number) Deposit = ... )) (C) πcustomer-name(σbalance> 10000(Borrow)) (D) σcustomer-name(σbalance> 10000(Borrow))

Last Answer : (A) πcustomer-name(σbalance> 10000(Deposit)) 

The asymptotic upper bound solution of the recurrence relation given by T(n)= 2T(n/2)+n/log n is: (1) O(n2) (2) O(n log n) (3) O(n log log n) (4) O(log log n)

Description : The asymptotic upper bound solution of the recurrence relation given by T(n)= 2T(n/2)+n/log n is: (1) O(n2) (2) O(n log n) (3) O(n log log n) (4) O(log log n)

Last Answer : (3) O(n log log n) 

Which of the following sorting algorithm has the running time that is least dependant on the initial ordering of the input? a) Insertion sort b) Quick sort c) Merge sort d) Selection sort

Description : Which of the following sorting algorithm has the running time that is least dependant on the initial ordering of the input? a) Insertion sort b) Quick sort c) Merge sort d) Selection sort

Last Answer : d) Selection sort

A disk drive has 100 cylinders, numbered 0 to 99. Disk requests come to the disk driver for cyclinders 12, 26, 24, 4, 42, 8 and 50 in that order. The driver is currently serving a request at cyclinder 24. A seek takes 6 msec per cyclinder moved. How much seek time is needed for shortest seek time first (SSTF) algorithm? (A) 0.984 sec (B) 0.396 sec (C) 0.738 sec (D) 0.42 sec

Description : A disk drive has 100 cylinders, numbered 0 to 99. Disk requests come to the disk driver for cyclinders 12, 26, 24, 4, 42, 8 and 50 in that order. The driver is currently serving a request at cyclinder 24. A seek takes ... (SSTF) algorithm? (A) 0.984 sec (B) 0.396 sec (C) 0.738 sec (D) 0.42 sec

Last Answer : C

To determine the efficiency of an algorithm the time factor is measured by: (A) Counting micro seconds (B) Counting number of key operations (C) Counting number of statements (D) Counting kilobytes of algorithm

Description : To determine the efficiency of an algorithm the time factor is measured by: (A) Counting micro seconds (B) Counting number of key operations (C) Counting number of statements (D) Counting kilobytes of algorithm

Last Answer : (B) Counting number of key operations

A scheduling Algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (lowest priority). The scheduler re-evaluates the process priority for every 'T' time units and decides next process to be scheduled. If the process have no I/O operations and all arrive at time zero, then the scheduler implements .............. criteria. (A) Priority scheduling (B) Round Robin Scheduling (C) Shortest Job First (D) FCFS

Description : A scheduling Algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (lowest priority). The scheduler re-evaluates the process priority for every 'T' time ... (A) Priority scheduling (B) Round Robin Scheduling (C) Shortest Job First (D) FCFS

Last Answer : (B) Round Robin Scheduling

Consider three CPU intensive processes P1, P2, P3 which require 20, 10 and 30 units of time, arrive at times 1, 3 and 7 respectively. Suppose operating system is implementing Shortest Remaining Time first (preemptive scheduling) algorithm, then .............. context switches are required (suppose context switch at the beginning of Ready queue and at the end of Ready queue are not counted). (A) 3 (B) 2 (C) 4 (D) 5

Description : Consider three CPU intensive processes P1, P2, P3 which require 20, 10 and 30 units of time, arrive at times 1, 3 and 7 respectively. Suppose operating system is implementing Shortest Remaining Time first (preemptive scheduling) ... end of Ready queue are not counted). (A) 3 (B) 2 (C) 4 (D) 5

Last Answer : (A) 3

The traveling salesman problem involves n cities with paths connecting the cities. The time taken for traversing through all the cities, without knowing in advance the length of a minimum tour, is ___________ a) O(n) b) O(n2) c) O(n!) d) O(n/2)

Description : The traveling salesman problem involves n cities with paths connecting the cities. The time taken for traversing through all the cities, without knowing in advance the length of a minimum tour, is ___________ a) O(n) b) O(n2) c) O(n!) d) O(n/2)

Last Answer : c) O(n!)

Which of the following sorting algorithm is in-place a) Counting sort b) Radix sort c) Bucket sort d) None

Description : Which of the following sorting algorithm is in-place a) Counting sort b) Radix sort c) Bucket sort d) None

Last Answer : b) Radix sort

Consider the situation in which assignment operation is very costly. Which of the following sorting algorithm should be performed so that the number of assignment operations is minimized in general? a) Insertion sort b) Selection sort c) Heap sort d) None

Description : Consider the situation in which assignment operation is very costly. Which of the following sorting algorithm should be performed so that the number of assignment operations is minimized in general? a) Insertion sort b) Selection sort c) Heap sort d) None

Last Answer : b) Selection sort

Which of the following algorithm pays the least attention to the ordering of the elements in the input list? a) Insertion sort b) Selection sort c) Quick sort d) None

Description : Which of the following algorithm pays the least attention to the ordering of the elements in the input list? a) Insertion sort b) Selection sort c) Quick sort d) None

Last Answer : b) Selection sort

If the given input array is sorted or nearly sorted, which of the following algorithm gives the best performance? a) Insertion sort b) Selection sort c) Quick sort d) Merge sort

Description : If the given input array is sorted or nearly sorted, which of the following algorithm gives the best performance? a) Insertion sort b) Selection sort c) Quick sort d) Merge sort

Last Answer : a) Insertion sort

Which of the following is not an in-place sorting algorithm? a) Selection sort b) Heap sort c) Quick sort d) Merge sort

Description : Which of the following is not an in-place sorting algorithm? a) Selection sort b) Heap sort c) Quick sort d) Merge sort

Last Answer : merge sort

Which of the following is a stable sorting algorithm? a) Merge sort b) Typical in-place quick sort c) Heap sort d) Selection sort

Description : Which of the following is a stable sorting algorithm? a) Merge sort b) Typical in-place quick sort c) Heap sort d) Selection sort

Last Answer : a) Merge sort

Which of the following is not a stable sorting algorithm? a) Insertion sort b) Selection sort c) Bubble sort d) Merge sort

Description : Which of the following is not a stable sorting algorithm? a) Insertion sort b) Selection sort c) Bubble sort d) Merge sort

Last Answer : b) Selection sort

In RSA algorithm,if p=5,q=7,e=7and message=3. What will be the value of ciphertext ?

Description : In RSA algorithm,if p=5,q=7,e=7and message=3. What will be the value of ciphertext ?

Last Answer : 17