Midterm Questions

Q1: Suppose you are given a flow network N and a maximum flow f for N. Suppose d, a positive integer, is added to the capacity of one edge of N.

 1. Give an efficient algorithm to compute a maximum flow for the new network.

 2. What is the worst case time complexity of your algorithm?

______________________________________________________________________________ 

 Q2 . In a heap, the heights of the left and right subtrees of a node differ by atmost 1.

 2. The best case running time of Bubble Sort is O(n).

 3. The best case running time of Merge Sort is O(n).

 4. The worst case complexity of Quick Sort is O(n2).

 5. The worst case complexity of AVL Tree insertion is O(n)