|
كلية تكنولوجيا المعلومات الواجب الثاني 2021-1
Student Name:
Student ID: □ CS □ SE |
Due:31/12/2021 |
APPLIED SCIENCE UNIVERSITY (ASU) FACULTY OF INFORMATION TECHNOLOGY (FIT) SECOND HW 2021-1
Subject: Design and Analysis of Algorithms
Instructor: Dr. Mohammed Khader |
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?
Good Luck
© 2019-2020 Faculty of Information Technology (FIT), Applied Science Private University, Amman, Jordan. 1
© 2019-2020 Faculty of Information Technology (FIT), Applied Science Private University, Amman, Jordan. 4
