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(N^1/2) (b) O(N)

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

How many multiplications do you need to compute 2¹⁰⁰ 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;

log₂(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 2n², respectively. Determine n₀ such that A is better than B for n n₀.

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