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.


Graph Basics

  • Write the adjacency list representation of below graph in the format shown in class.
  • Is the below Graph cyclic or acyclic. If there is a cycle, list the cycle.
  • Is the below Graph directed or undirected?
  • Is the below graph a DAG?
  • Is the below graph connected of disconnected? If it is connected, is it weakly or strongly connected?





  • Write the adjacency list representation of below graph in the format shown in class.
  • Is the below Graph cyclic or acyclic. If there is a cycle, list the cycle.Is the below Graph directed or undirected?
  • Is the below graph a DAG?
  • Is the below graph connected of disconnected? If it is connected, is it weakly or strongly connected?




graph with two components


Graphs


Write the adjacency list representation of below graph in the format shown in class.


image source


Trace DFS on the above graph


 VertexAdj []
Color[]
Discovery_Time[]
Finish_Time[]
Parent[]
 1     
 2     
 3     
 4     
 5     
 6     


Then, draw the DFS Forest



Now, trace BFS on the above Graph with 1 as the source vertex.



 VertexAdj []
Color[]
Distance[]
Parent[]
 1    
 2    
 3    
 4    
 5    
 6    


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.



graph with two components

Image source


Trace DFS on the above graph



 VertexAdj []
Color[]
Discovery_Time[]
Finish_Time[]
Parent[]
 0     
 1     
 2     
 3     
 4     
 5     
 6     
 7     
 8     
 9     
 10     


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.


Graph with edge from 3 to 4 removed



 VertexAdj []
Color[]
Distance[]
Parent[]
 0

    
 1    
 2    
 3    
 4    
 5    
 6    
 7    
 8    
 9    
 10    


Queue:



Also Draw the BFS Tree.


What is the Big-O runtime of DFS and BFS?


BFS: O (                    )


DFS: O (                    )



Heaps

  • What is the Max Heap Property? How does it differ from the BST property?
  • What is the Big-O runtime of each of the heap algorithms we discussed in class?
  • Trace each step of the buildMaxHeap operation (diagram and array) on the following:

Diagram                    Array

                       

                        A = [3, 5, 9, 4, 7, 8, 12, 6]

1.






2.                        A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ]   







           

3.                        A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ]   







4.                        A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ]   





5.                        A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ]





6.                        A = [ ___ , ___, ___, ___, ___, ___, ___, ___ ]







  • Trace heapInsert on the below Max Heap and the value 95. Show diagram and array at each step below:


Diagram                    Array

                       

1.                        A = [100, 90, 80, 70, 60, 50, 40, 30, 20, 10]







2.                        A = [ ___, ___, ___, ___, ___, ___, ___, ___, ___, ___, ___ ]






           

3.                        A = [ ___, ___, ___, ___, ___, ___, ___, ___, ___, ___, ___ ]







4.                   A = [ ___, ___, ___, ___, ___, ___, ___, ___, ___, ___, ___ ]    




  • Trace heapSort on the following heap. Show diagram and array at each step below:

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: