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)

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