Midterm Questions

profileOliverPope23

These questions are Based on:
A C++ Prime
Object-Oriented Design Array
Analysis Tools Stacks
Queues
Deques
List
Iterator ADTs
Trees


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)

    • 3 years ago
    • 10
    Answer(0)