1. At most, how many comparisons are required to search a sorted vector of 1023

ID: 3874076 • Letter: 1

Question

1. At most, how many comparisons are required to search a sorted vector of 1023 elements using the binary search algorithm?

(a) 10 (b) 8 (c) 7 (d) 9

2. The right array in the partition algorithm of the merge sort that sorting n elements consists of __________ elements.

(a) floor of n/2 (b) ceil of n/2 (c) floor of n (d) ceil of n

3. A list implementation of a graph might use an array of linked lists, each list containing all the ________ a vertex.

paths containing (b) vertices adjacent to

edges adjacent to (d) trees containing

4. (T/F) The linear search has asymptotic running time of order n.

Time complexities of three algorithms are given. Which should execute the slowest for large values of N?

(a) O(N1/2) (b) O(N)

(c) O(log N) (d) None of these

How many multiplications do you need to compute 2100 using square and multiply algorithm?

(a) 99 (b) 100

(c) 8 (d) None of these

(T/F) The running time of the PerfixAverage2 algorithm is linear function.

Where f is a function, O(f (n)) means _______ f (n).

(a) Exactly; (b) at most;

(c) Roughly proportional to; (d) at least;

log2(1000) is closest to

(a) 3; (b) 10; (c) 50; (d) 100;

10. What is the sum of all natural numbers from 1 to 100?

(a) 3240 (b) 5050 (c) 701 (d) 248

Question 2 ( 15 Marks): Answer the following questions:

Name two algorithms have running time where is the size of the input. (2 Marks)

Write the worst case running time of the corresponding algorithm in the table: (2 Marks)

Algorithm

Its worst case rung time

BFS

………………………………..

Selection sort

………………………………..

Quick sort

……………………………….

How to represent the following directed graph using the adjacency list.

(2 Marks)

……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………

…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………

Discover the trees of the DFS-forest of the following graph: (3 Marks)

Compute the running time of the following algorithm:

(3 Marks)

f. The number of operations executed by algorithms A and B is 8n log n and 2n2, respectively. Determine n0 such that A is better than B for n n0. (3 Marks)

Question 3 ( 20 Marks): Answer the following questions:

Rewrite the linearSearch algorithm given below to output all positions of the element in the array L, where S is the set of all elements in L. ( 5 Marks)

Apply the merge sort algorithm to the sequence of integers A=(20,15, 30, 10, 40, 5, 50, 6, 18), and count the number of comparisons operations. ( 5 Marks)

……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………...........................

Apply the BFS algorithm to the following graph starting from the vertex 3. ( 5 Marks)

Sort the following sequence of numbers

A=(20,15, 30, 10, 40, 5, 50, 6, 18)

Using one of the algorithms Bubble, Selection, and Insertion that gives you less number of swaps. (5 Marks)

Algorithm

Its worst case rung time

BFS

………………………………..

Selection sort

………………………………..

Quick sort

……………………………….

Explanation / Answer

Ans:

[1]

At most, 10 comparisons are required to search a sorted vector of 1023 elements using the binary search algorithm.

[4] True

The worst case of Linear search makes at most n comparisons to get the result, where n is the length of the list.

[5] O(n)

On taking the larger value of n, the value of n in O(n) is greater than the other whuch causes it to work slowly.

[9] 10

Using the change of base formula:

log2 (1000) = Ln(1000) / Ln(2)

= 6.9077 / 0.6931

= 9.9663 (Approx 10)

[10] 5050

Using Arithmetic Progression Formula:

1 + 2 + 3 + 4 + … + 98 + 99 + 100

Formula: sum = n[2a+(n-1)d]/2

where a is the first term,

d is the difference between terms,

and n is the number of terms.

i.e. a = 1, d = 1, and n = 100

Therefore,

sum = 100[2(1)+(100-1)(1)]/2 = 100[101]/2 = 5050.

Ques.- The worst case running time of the corresponding algorithm in the table:

Algorithm Worst Case Time Complexity BFS The worst case time complexity of BFS algorithm in a graph traversal is O( V + E ) since every vertex and every edge of the graphwill be explored in the worst case scenario Selection Sort O(n2) Quick Sort O(n2)

Navigate

1. At least how many Calories does a mountain climber need to climb from sea lev

1. At most, how many comparisons are required to search a sorted vector of 255 e

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

1. At most, how many comparisons are required to search a sorted vector of 1023

Question

Explanation / Answer

Related Questions

Navigate