Answer the Questions from the Review Sheets For Midterms 1 & 2. In addition:

Graphs

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

image source

Trace DFS on the above graph

Then, draw the DFS Forest

Now, trace BFS on the above Graph.

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.

Image source

Trace DFS on the above graph

Then, draw the DFS Forest

Next, trace BFS on the above graph.

Queue:

Also Draw the BFS Tree. How do the tracings for BFS and DFS differ?

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 = [4, 9, 7, 18, 2, 3]

1.

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

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

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

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

Diagram                    Array

1.                        A = [21, 11, 13, 2, 9]

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

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

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

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

Diagram                    Array

1.                        A = [100, 90, 80, 70]

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

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

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

Trace the merge sort algorithm on the following array of values:

[50, 2, 12, 17, 6, 1, 4, 52]

[ ___, ___, ___, ___ ] [ ___, ___, ___, ___ ]

[ ___, ___ ]    [ ___, ___]   [ ___, ___] [ ___, ___ ]

[ ___ ]    [ ___ ] [ ___ ]    [ ___ ] [ ___ ]    [ ___ ] [ ___ ]    [ ___ ]

[ ___, ___ ]    [ ___, ___]   [ ___, ___] [ ___, ___ ]

[ ___, ___, ___, ___ ] [ ___, ___, ___, ___ ]

[ ___, ___, ___, ___, ___, ___, ___, ___ ]

Write the pseudocode for the mergeSort operation. Note that you do not need to write the helper function merge.

mergeSort(A, low, high)

What is the Big O run-time of MergeSort in the best, worst and average case?

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:

A parallel sorting algorithm: