Algorithms Algorithms 3

Question 1

What does the term 'amortized time complexity' refer to?

Accepted Answer

The average time per operation over a sequence of operations

Answer

Amortized analysis spreads the cost of expensive operations across many operations to give a per-operation average.

Question 2

Which algorithm is used to find the Minimum Spanning Tree of a graph by always adding the globally cheapest edge that doesn't create a cycle?

Accepted Answer

Kruskal's Algorithm

Answer

Kruskal's algorithm sorts all edges by weight and greedily adds the smallest edge that doesn't form a cycle.

Question 3

What is the time complexity of heap sort in the worst case?

Accepted Answer

O(n log n)

Answer

Heap sort builds a max-heap in O(n) and extracts elements n times each in O(log n), giving O(n log n) worst case.

Question 4

In the context of dynamic programming, what is memoization?

Accepted Answer

Caching the results of subproblems to avoid redundant computation

Answer

Memoization stores results of already-computed subproblems in a table so they aren't recomputed.

Question 5

Which graph algorithm can detect negative-weight cycles?

Accepted Answer

Bellman-Ford Algorithm

Answer

Bellman-Ford detects negative-weight cycles by checking if any distance can still be reduced after V-1 relaxations.

Algorithms Practice Test