Question 1 (5 Marks): All items are equally weighted . 1. At most, how many comp

ID: 3874092 • Letter: Q

Question

Question 1 (5 Marks): All items are equally weighted.

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)

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)

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

e. (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

Explanation / Answer

There are too many questions to be answered, so answerd only 5

1 a
We need to serach [log (n)] number of times

2 b
right array may contain 1 extra item, so the answer is ceil of n/2

3 b
vertices adjacent to

4 is true (hence the name linear)

5
We know that O(log N) < O(N) and also O(N^1/2) < O(N). SO the slowest is O(N)

1 a
We need to serach [log (n)] number of times

2 b
right array may contain 1 extra item, so the answer is ceil of n/2

3 b
vertices adjacent to

4 is true (hence the name linear)

5
We know that O(log N) < O(N) and also O(N^1/2) < O(N). SO the slowest is O(N)

Navigate

Question 1 (45 pts) Transmission Through A Bandlimited Channel A baseband 16-ary

Question 1 (5 Points) During 2015, Edwards Corporation, a calendar year C corpor

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

Question 1 (5 Marks): All items are equally weighted . 1. At most, how many comp

Question

Explanation / Answer

Related Questions

Navigate