Here are some recurrence relations that come up in the analysis of Quicksort and or Select. For each recurrence, write one sentence explaining how it relates to Quicksort or Select and give its asymptotic growth rate in Q notation.

see attached file

This problem is about the Floyd-Warshall all pairs shortest paths algorithm

see attachment

This is a problem about Network Flows.

see attachment

Give an example of a weighted directed graph with at most 5 vertices such that Dijkstra's algorithm will NOT give the correct results for the shortest path lengths from source s to every other vertex. algorithm

Give an example of a weighted directed graph with at most 5 vertices such that Dijkstra's algorithm will NOT give the correct results for the shortest path lengths from source s to every other vertex. Your graph may have negative edge weights but NO negative weight cycles. Indicate what answer Dijkstra's algorithm would give a ...continues

Here is a proposed algorithm to solve the single source shortest paths problem in a weighted directed graph G with possibly negative edges weights

Here is a proposed algorithm to solve the single source shortest paths problem in a weighted directed graph G with possibly negative edges weights, but no negative weight cycles: Form the graph G' from G by adding the same positive number, p, to all of the edge weights in the graph. This positive number should be chosen so th ...continues

modify the Bellman-Ford algorithm to find and print a negative weight cycle (reachable from the source, s) in a weighted directed graph G if one exists

Show how to modify the Bellman-Ford algorithm to find and print a negative weight cycle (reachable from the source, s) in a weighted directed graph G if one exists. If there is no negative weight cycle, your algorithm should print out "NO NEGATIVE WEIGHT CYCLE REACHABLE FROM s". If there is a negative weight cycle reachable fr ...continues

ternary trees

Consider a ternary tree, in which each node has 3 children. What are the maximum and minimum number of nodes in a ternary tree of height h?

converting ternary to binary

Write the pseudocode for a recursive function TERNARY TO BINARY, that will convert a ternary tree into a binary search tree.

Heap algorithm implementation

Please look at question number 4 on the pdf attachment on the sample final exam. Thanks

Converting a ternary tree to a binary tree

Please look at question number 3 on the attached pdf file of the sample final exam. Thanks