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

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

1 Answer

Answer :

(D) Floyd-Warshall algorithm
by

Related questions

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.

Description : 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.

Last Answer : (C) Exponential time using dynamic programming algorithm or branch-andbound algorithm.

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.

The _________ routing uses the Dijkstra algorithm to build aroutingtable. A) distancevector B) link state C) path vector D) none of the above

Description : The _________ routing uses the Dijkstra algorithm to build aroutingtable. A) distancevector B) link state C) path vector D) none of the above

Last Answer : link state

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

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

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 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

STRIPS addresses the problem of efficiently representing and implementation of a planner. It is not related to which one of the following ? (A) SHAKEY (B) SRI (C) NLP (D) None of these

Description : STRIPS addresses the problem of efficiently representing and implementation of a planner. It is not related to which one of the following ? (A) SHAKEY (B) SRI (C) NLP (D) None of these

Last Answer : (C) NLP

Sussman Anomaly can be easily and efficiently solved by partial order planning. a) True b) False

Description : Sussman Anomaly can be easily and efficiently solved by partial order planning. a) True b) False

Last Answer : a) True

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 critical path A. Is a path that operates from the starting node to the end node B. Is a mixture of all paths. C.Is the longest path D.Is the shortest path

Description : The critical path  A. Is a path that operates from the starting node to the end node  B. Is a mixture of all paths.  C.Is the longest path  D.Is the shortest path

Last Answer : C.Is the longest path

Consider a disk queue with request for input/output to block on cylinders 98, 183, 37, 122, 14, 124, 65, 67 in that order. Assume that disk head is initially positioned at cylinder 53 and moving towards cylinder number 0. The total number of head movements using Shortest Seek Time First (SSTF) and SCAN algorithms are respectively (A) 236 and 252 cylinders (B) 640 and 236 cylinders (C) 235 and 640 cylinders (D) 235 and 252 cylinders

Description : Consider a disk queue with request for input/output to block on cylinders  98, 183, 37, 122, 14, 124, 65, 67  in that order. Assume that disk head is initially positioned at cylinder 53 and moving ... and 252 cylinders (B) 640 and 236 cylinders (C) 235 and 640 cylinders (D) 235 and 252 cylinders

Last Answer : Answer: 236 and 208 cylinders Explanation: SSTF Initial head position =53 The closest queue to initial head position=65 head moves from 53 to 65=12 head moves from 65 to 67=2 head moves from 67 ... 122=24 head moves from 122 to 124=2 head moves from 124 to 183=59 Total head movement=208 

A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes. A) vertices, edges B) edges, vertices C) vertices, paths D) graph node, edges

Description : A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes. A) vertices, edges B) edges, vertices C) vertices, paths D) graph node, edges

Last Answer : A) vertices, edges

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.

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

Which of the following scheduling algorithms may cause starvation? a. First-come-first-served b. Round Robin c. Priority d. Shortest process next e. Shortest remaining time first (1) a, c and e (2) c, d and e (3) b, d and e (4) b, c and d

Description : Which of the following scheduling algorithms may cause starvation? a. First-come-first-served b. Round Robin c. Priority d. Shortest process next e. Shortest remaining time first (1) a, c and e (2) c, d and e (3) b, d and e (4) b, c and d

Last Answer : Answer: 2

A station in a network forwards incoming packets byplacing them on its shortest output queue. Whatrouting algorithm is being used? A. hot potatorouting B. flooding C. static routing D. delta routing E. None of the above

Description : A station in a network forwards incoming packets byplacing them on its shortest output queue. Whatrouting algorithm is being used? A. hot potatorouting B. flooding C. static routing D. delta routing E. None of the above

Last Answer : hot potatorouting

Which of the following routing algorithms can be used for network layer design? a. shortest path algorithm b. distance vector routing c. link state routing d. all of the mentioned

Description : Which of the following routing algorithms can be used for network layer design? a. shortest path algorithm b. distance vector routing c. link state routing d. all of the mentioned

Last Answer : d. all of the mentioned

The basic algorithm initially attempts to use the _________context. a. Small b. Shortest c. Longest d. Zero

Description : The basic algorithm initially attempts to use the _________context. a. Small b. Shortest c. Longest d. Zero

Last Answer : c. Longest

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

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

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

For every context free grammar (G) there exists an algorithm that passes any w ∈ L(G) in number of steps proportional to (A) ln|w| (B) |w| (C) |w|2 (D) |w|3

Description : For every context free grammar (G) there exists an algorithm that passes any w ∈ L(G) in number of steps proportional to (A) ln|w| (B) |w| (C) |w|2 (D) |w|3

Last Answer : (D) |w|3

Bresenham line drawing algorithm is attractive because it uses (A) Real arithmetic only (B) Integer arithmetic only (C) Floating point arithmetic (D) Real and integer arithmetic

Description : Bresenham line drawing algorithm is attractive because it uses (A) Real arithmetic only (B) Integer arithmetic only (C) Floating point arithmetic (D) Real and integer arithmetic

Last Answer : (B) Integer arithmetic only

A virtual memory based memory management algorithm partially swaps out a process. This is an example of (A) short term scheduling (B) long term scheduling (C) medium term scheduling (D) mutual exclusion

Description : A virtual memory based memory management algorithm partially swaps out a process. This is an example of (A) short term scheduling (B) long term scheduling (C) medium term scheduling (D) mutual exclusion

Last Answer : (C) medium term scheduling

If h* represents an estimate of the cost of getting from the current node N to the goal node and h represents actual cost of getting from current node to the goal node, then A* algorithm gives an optimal solution if (A) h* us equal to h (B) h* overestimates h (C) h* underestimates h (D) none of these

Description : If h* represents an estimate of the cost of getting from the current node N to the goal node and h represents actual cost of getting from current node to the goal node, then A* algorithm gives an optimal solution ... h* us equal to h (B) h* overestimates h (C) h* underestimates h (D) none of these

Last Answer : (C) h* underestimates h

Given two sorted list of size 'm' and 'n' respectively. The number of comparison needed in the worst case by the merge sort algorithm will be (A) m x n (B) max (m, n) (C) min (m, n) (D) m + n – 1

Description : Given two sorted list of size 'm' and 'n' respectively. The number of comparison needed in the worst case by the merge sort algorithm will be (A) m x n (B) max (m, n) (C) min (m, n) (D) m + n – 1

Last Answer :  (D) m + n – 1

Consider f(N) = g(N) + h(N) Where function g is a measure of the cost of getting from the start node to the current node N and h is an estimate of additional cost of getting from the current node N to the goal node. Then f(N) = h(N) is used in which one of the following algorithms ? (A) A* algorithm (B) AO* algorithm (C) Greedy best first search algorithm (D) Iterative A* algorithm

Description : Consider f(N) = g(N) + h(N) Where function g is a measure of the cost of getting from the start node to the current node N and h is an estimate of additional cost of getting from the current ... ? (A) A* algorithm (B) AO* algorithm (C) Greedy best first search algorithm (D) Iterative A* algorithm

Last Answer : (C) Greedy best first search algorithm

How many distinct stages are there in DES algorithm, which is parameterized by a 56-bit key ? (A) 16 (B) 17 (C) 18 (D) 19

Description : How many distinct stages are there in DES algorithm, which is parameterized by a 56-bit key ? (A) 16 (B) 17 (C) 18 (D) 19

Last Answer : (D) 19

Which of the following algorithms is not a broadcast routing algorithm ? (A) Flooding (B) Multidestination routing (C) Reverse path forwarding (D) All of the above

Description : Which of the following algorithms is not a broadcast routing algorithm ? (A) Flooding (B) Multidestination routing (C) Reverse path forwarding (D) All of the above

Last Answer : (D) All of the above

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

Which of the following statements is not true for Multi Level Feedback Queue processor scheduling algorithm? (A) Queues have different priorities. (B) Each queue may have different scheduling algorithm (C) Processes are permanently assigned to a queue (D) This algorithm can be configured to match a specific system under design

Description : Which of the following statements is not true for Multi Level Feedback Queue processor scheduling algorithm? (A) Queues have different priorities. (B) Each queue may have different scheduling algorithm (C) ... to a queue (D) This algorithm can be configured to match a specific system under design

Last Answer : (C) Processes are permanently assigned to a queue

Which one from the following is false ? (A) LALR parser is Bottom - Up parser (B) A parsing algorithm which performs a left to right scanning and a right most deviation is RL (1). (C) LR parser is Bottom - Up parser. (D) In LL(1), the 1 indicates that there is a one - symbol look - ahead.

Description : Which one from the following is false ? (A) LALR parser is Bottom - Up parser (B) A parsing algorithm which performs a left to right scanning and a right most deviation is RL (1). (C) LR parser is Bottom - Up parser. (D) In LL(1), the 1 indicates that there is a one - symbol look - ahead.

Last Answer : (B) A parsing algorithm which performs a left to right scanning and a right most deviation is RL (1).

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

The average case occurs in the Linear Search Algorithm when: (A) The item to be searched is in some where middle of the Array (B) The item to be searched is not in the array (C) The item to be searched is in the last of the array (D) The item to be searched is either in the last or not in the array

Description : The average case occurs in the Linear Search Algorithm when: (A) The item to be searched is in some where middle of the Array (B) The item to be searched is not in the array (C) The item to be searched is in the last of the array (D) The item to be searched is either in the last or not in the array

Last Answer : (A) The item to be searched is in some where middle of the Array

Consider the following statements: (a) Depth - first search is used to traverse a rooted tree. (b) Pre - order, Post-order and Inorder are used to list the vertices of an ordered rooted tree. (c) Huffman's algorithm is used to find an optimal binary tree with given weights. (d) Topological sorting provides a labelling such that the parents have larger labels than their children. Which of the above statements are true ? (A) (a) and (b) (B) (c) and (d) (C) (a) , (b) and (c) (D) (a), (b) , (c) and (d)

Description : Consider the following statements: (a) Depth - first search is used to traverse a rooted tree. (b) Pre - order, Post-order and Inorder are used to list the vertices of an ordered rooted tree. (c) Huffman's algorithm is used to find an optimal ... (d) (C) (a) , (b) and (c) (D) (a), (b) , (c) and (d)

Last Answer : (D) (a), (b) , (c) and (d)

Which raster locations would be chosen by Bresenham’s algorithm when scan converting a line from (1, 1) to (8, 5) ?

Description : Which raster locations would be chosen by Bresenham’s algorithm when scan converting a line from (1, 1) to (8, 5) ?

Last Answer : Answer: C