Final Exam Review In addition to the below questions, Please Review Midterms 1 & 2 Guides Linked from Course Schedule Page. Note: Answer key for DFS, BFS and Heap questions attached at the bottom of this page.
Graphs Write the adjacency list representation of below graph in the format shown in class. Trace DFS on the above graph
Then, draw the DFS Forest
Queue: Also Draw the BFS Tree. How do the tracings for BFS and DFS differ? Write the adjacency list representation of below graph in the format shown in class. Trace DFS on the above graph
Then, draw the DFS Forest Next, remove the edge from 3 to 4. Then, trace BFS on the above graph with 3 as the source vertex and also with 6 with the source vertex.
Queue: Also Draw the BFS Tree. What is the Big-O runtime of DFS and BFS? BFS: O ( ) DFS: O ( ) Heaps
Diagram Array
A = [3, 5, 9, 4, 7, 8, 12, 6] 1. 2. A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ]
3. A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ] 4. A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ]
Diagram Array
1. A = [100, 90, 80, 70, 60, 50, 40, 30, 20, 10] 2. A = [ ___, ___, ___, ___, ___, ___, ___, ___, ___, ___, ___ ]
3. A = [ ___, ___, ___, ___, ___, ___, ___, ___, ___, ___, ___ ] 4. A = [ ___, ___, ___, ___, ___, ___, ___, ___, ___, ___, ___ ]
Diagram Array
1. A = [5, 3, 4, 2, 1] 2. A = [ ___ , ___, ___, ___, ___ ]
3. A = [ ___ , ___, ___, ___, ___ ] 4. A = [ ___ , ___, ___, ___, ___ ] 5. A = [ ___ , ___, ___, ___, ___ ] 6. A = [ ___ , ___, ___, ___, ___ ] 7. A = [ ___ , ___, ___, ___, ___ ] 8. A = [ ___ , ___, ___, ___, ___ ] Write the pseudocode for the mergeSort operation. Note that you do not need to write the helper method merge. mergeSort(A, low, high) What is the Big O run-time of MergeSort, HeapSort and BubbleSort in the best, worst and average cases? Best: O ( ) Average: O ( ) Worst: O ( ) Give an example of a sorting algorithm that we have studied in this class that falls into each of the following categories: An in-place sorting algorithm: A comparison-based sorting algorithm: A divide-and-conquer sorting algorithm: |