Given the BST to the right, provide the following (Each is independent of the others) (8pts)
a. Show the result of inserting 17
b. Show the result of removing 27
c. Show the result of removing 50
d. Show the result of removing 20
2. For the graph to the right, provide the following(each is independent of the others) (15pts)
a. Show the node order and spanning tree that results from BFS(5)
b. Show the node order that results from BFS(4)
c. Show the node order that results from the DFS(5)
d. Show the node order that results from the DFS(4)
e. Construct an adjacency matrix representation for this graph
f. Construct an adjacency list representation for this graph
g. Find the shortest path from 1 to all other nodes
3. Below is the adjacency matrix for a directed weighted graph. Draw the visual representation of the graph it represents (6pts)
1 2 3 4
1 3 4
2 1 6 8
3 7 9
4
4. What big O family would you classify the following code fragment as? Why? (6pts)
while(val> 0)
{
sum += val;
val /= 2;
}
5. The below code fragments can be used to implement a list with LIFO behavior(6pts)
N++ | val = L[n];
L[n] = val | n–;
This code is simple however your boss believes you need to go through all the extra pieces of work and fully implement a stack and follow stack naming conventions. Why would that be preferable to the easy to use and implement code above?
6. Now for a little bit of a thinker. It is possible that we can see a O(n^2) algorithm perform a task faster then a O(n) algorithm. Explain how that may be possible and do these sorts of cases show O() is not useful. (6pts)
7. Show the state of each listed data structure after the insertion of the following data
5, 2, 7, 13, 4
Then show me the state of the structure after 1 REMOVE operation. Diagrams are preferable, ensure whatever you choose is very clearly marked. (14pts)
Stack
Max heap
Binary search tree
Hashtable(5 buckets, mod number by 5 for hash algorithm, use chaining for collisions)
8. Linked list operations. Write a code fragment for each(code fragment, not entire program!)(8pts)
– p, q, and r are pointers into the list
– Each node in the list has a val and next field
– Assume p, q, and r are initialized properly
a. Print the larger of the 2 values of p and q
b. Insert r between p & q in the list, where p & q are consecutive items
c. Assume p and q point to items in a linked list and that p is to the left of q (p is before q). Write a loop that forces r to visit each node between p and q
d. p points to a node in the middle of the list(not beginning or end). Delete the node after p.
9. In class, we discussed both Prim’s &Kruskal’s algorithms and how they may result in the same or different MST. Provide a graph where they will provide a different MST.(6pts)
10. Consider the QuickSort algorithm. Show a reasonable state of the list after the first round of choosing a pivot point and partitioning the list(6pts)
List: 17, 45, 11, 30, 47, 12, 33
11. When studying O() we always end up with terms like O(N), O(N^2), O(N^3) even though there are other statements in the code that make up the overall efficiency of the program. For instance take the code below
for(i = 0; i< x; i++)
{
for(z = 0; z < x; z++)
{
Val *= 2;
Tmp += 1;
}
}
while(x != 0)
{
Val –= x;
x–;
}
Return 0;
Would become O(2n^2 + 2n + 1). Why does it make sense to drop all of the other numbers and just take the highest-powered term? In this case O(n^2). (6pts)
12. Given the graph below, find the solutions to the requested operations and show the process you took to reach those solutions in as much detail as possible(13pts)
a. Show the steps in solving the shortest path problem according to Dijkstra’s algorithm when starting at node 6.
b. Construct the MST for the graph according to Prim’s algorithm starting at vertex 1
c. Construct the MST according toKruskal’s algorithm
