CS130-lecture-20201207

Exercise solutions #

IMAGE IMAGE

Single source shortest paths #

IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE

TYPO fixed in column 5 relax 4:

IMAGE IMAGE IMAGE IMAGE

IMAGE

The max space taken by the IndexMinPQ is O(V - 1).

IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE

Decimal to binary, and back

IMAGE

Is a BST seach a P problem? Yes It is also a NP problem. It is not a NP-Complete problem.