data stucture
Data Structures and Algorithm Analysis
Spring 2020 - Final Exam – 100 points + 5 bonus
NAME:
1. Big-O: What is meant by f(n)=O(g(n))? Give the definition and explain what it means in your own terms. – 4 points
2. Show that , where . Make sure you use the definition and justify the inequalities and constants used. – 4 points
Pseudocode for selection sort:
for( i = 0; i < n-1; i++)
min = i;
for( j = i+1; j < n; j++)
if( A[j] < A[min])
min = j;
end if
end for
if( min != i)
swap A[i] and A[min]
end if
end for
3. What is the worst-case time complexity of selection sort? Justify your answer. – 4 points
4. Show the steps when sorting (smallest to largest) the following array of numbers using selection sort i.e. every time a swap occurs, show what the current state of the array looks like, including the final sorted array. – 4 points
[5, 10, 7, 8, 4, 3, 9, 1, 6, 2]
5. What principle governs how you add/remove elements in a stack? Spell it out and briefly explain. – 4 points
6. What principle governs how you add/remove elements in a queue? Spell it out and briefly explain. – 4 points
Consider the following graph (pseudocode for BFS and DFS given on next page):
7. Write the order in which the nodes would be visited in when doing a breadth first search (BFS) traversal starting at node 6. Also, write the distances from 6 to every other node. - 6 points
8. Write the order in which the nodes would be visited in when doing a depth first search (DFS) traversal starting at node 6. Also specify the order in which vertices are removed from the stack. - 6 points
BFS Pseudocode (for graph with n vertices):
Input: grapharray[n][n], source
queue<int> Q
int distance[n] (array to keep track of node distances (from source), all values set to -1 except source which is set to 0 i.e. -1 = not visited)
Q.push(source)
while(Q is not empty)
v = Q.front
Q.pop()
for each neighbor w of v
if distance[w] == -1
print w
distance[w] = distance[v]+1
Q.push(w)
end if
end for
end while
DFS Pseudocode (for graph with n vertices):
Input: grapharray[n][n], source
stack<int> S
int visited[n] (array to keep track of nodes visited, all values set to 0 except source which is set to 1 i.e. 0 = not visited, 1 = visited)
S.push(source)
while(S is not empty)
v = S.top
S.pop()
for each neighbor w of v
if visited[w] == 0
print w
visited[w] = 1
S.push(w)
end if
end for
end while
9. Draw the binary search tree that would be constructed by inserting the following values in the exact order given (starting with an empty tree i.e. first value will be the root of the tree): - 4 points
Binary search tree: 12,14,6,13,3,7,15,9,18,1,5,8,16,20
10. What is the max-heap property in a binary heap? - 4 points
Pseudocode for heap sort:
Array: A[n], indexed from 1 to n. LEFT(i) = 2i, RIGHT(i) = 2i+1
***
MAX-HEAPIFY(A,i)
l=LEFT(i)
r=RIGHT(i)
if l <= A.heap-size and A[l] > A[i]
largest = l
else largest = i
if r <= A.heap-size and A[r] > A[largest]
largest = r
if largest != i
swap A[i] with A[largest]
MAX-HEAPIFY(A, largest)
***
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = floor(A.length/2) down to 1
MAX-HEAPIFY(A,i)
***
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length down to 2
swap A[1] with A[i]
A.heap-size = A.heap-size-1
MAX-HEAPIFY(A,1)
***
11. For the given arrays, show the steps in sorting each array using heap sort. That is, after each MAX-HEAPIFY is called in HEAPSORT, write out the max-heap (in array form or draw it) and the sorted values at the end of the array. Remember: each time, the size of the max-heap decreases by 1, and the number of values in sorted order at the end of the array increases by 1. Note: the given arrays are already max-heaps so no need to call BUILD-MAX-HEAP at the start in these examples. - 12 points
· Array: [10, 6, 8, 4, 5, 3, 1]
· Array: [13,5,9,2,1,7,6]
12. What is the worst case time complexity of Heapsort? Justify your answer in detail (especially for MAX-HEAPIFY). – 4 points
13. What is meant by “chaining” in the context of hash tables and hash functions? – 4 points
14. What is the definition of “universal hashing”? – 6 points
15. Suppose we are hashing a value k, 0<k<1, into one of m slots (labeled 0,1,…,m-1) using the function i.e. the floor of k*m. Give the value of h(k) for the following values of k and m. – 6 points
· m=10, k=0.6
· m=20, k=0.5
16. Suppose we are hashing a value k, into one of m slots (labeled 0,1,…,m-1) using the function . Give the value of for the following values of k, m, p, a, b. – 8 points
· m=7, p=17, a=4, b=3, k=10
· m=7, p=13, a=3, b=7, k=6
17. What is the definition of the complexity class P of decision problems? – 4 points
18. What is the definition of the complexity class NP of decision problems? – 4 points
19. What is the definition of the complexity class NP-Hard of decision problems? – 4 points
20. Give the names of two NP-Complete problems. – 4 points
Extra Credit 1. Show that , make sure you use the definition and justify the inequalities and constants used. – 2.5 points
Extra Credit 2. What is the “division method” for creating hash functions? Give the general hash function. – 2.5 points