In the merge step of Merge sort of N elements what is the running time

Please Note that this assignment is 4 pages and with a total of 40 points.

Question 1: [10 points]

Choose the correct answer from the following:

1. In the merge step of Merge sort of N elements what is the running time cost of that step?

a. O(1) b. O(log N) c. O(N) d. O(N log N) e. O(N2)

2. One of the following is used in Topological Sorting:

a. BFS b. DFS c. Heap d. All of them

3. Memory required to represent a graph using adjacency list is:

a. (|E|) b. (|V|2) c. (|V| + |E|) d. None of them

4. Time to determine if (u, v) E in a graph represented by adjacency matrix is:

a. (1) b. (log |V|) c. O (degree(u)) d. O (degree(v)) e. O(|E|)

5. The INCREASE-KEY operation in a priority queue with Size N has running time:

a. O(1) b. O(log N) c. O(N) d. O(N log N) e. O(N2)

 

6. The minimum number of comparisons needed to find the Simultaneous Min, Max values of n even elements is

a. 2n-1 b. (3n-3)/2 c. (3n/2) -2 d. (3n-2)/2

7. The running time of the best algorithm for finding the median of a sorted sequence of n values is in the order (Big-O) of:

a. lg n b. n3 c. 1 d. n

8. The running time needed to determine if the edge (u, v) E and the graph represented by an adjacency list:

a. O(degree(u)) b. (|E|) c. (|V| + |E|) d. (|V|)

9. The running time needed to traverse the adjacent nodes for the node u in the graph represented by an adjacency matrix:

a. (degree(u)) b. (|E|) c. (|V| + |E|) d. (|V|)

 

10. The running time of breadth-first search on a graph G(V, E) represented in an adjacency list is

a. O(E2) b. O(E+V) c. O(V2) d. O (E log V) e. None

Question 2: [7 Points]

Given the following adjacency matrix representation of a graph to answer the followed questions.

0	1	1	0	1
1	0	0	1	0
1	0	0	0	1
0	1	0	0	1
1	0	1	1	0

A. [1 Point] is it directed graph or not and why?

B. [1 Point] How many vertices are there in the graph?

C. [1 Point] How many edges are there in the graph?

D. [3 Point] reRepresent the graph using an adjacency list.

E. [1 Point] Draw the original graph

Question 3: [6 POINTS]

A- [4 POINTS] Apply heap sort in the following array and show your work over the tree you build. Show all your steps.

18	13	11	7	14	10	4	25	5

B- [2 POINTS] How many times the max-heapify function is called through the entire sorting.

Question 4: [17 POINTS]

A) [8 POINTS] Run DFS(G) and show discovery time, finish time and predecessor for each node. And show the DFS forest.

B) [2 POINTS] How many times in total has DFS-Visit has been called?

C) [7 POINTS] Run BFS (G, 0) starting with source 0. Show the Queue after each step. Show also d[], p[] lists and BFS tree.