Algorithms Algorithms 4

Question 1

What is the time complexity of inserting an element into a balanced BST (e.g., AVL tree)?

Accepted Answer

O(log n)

Answer

A balanced BST maintains height O(log n), so insertion requires at most O(log n) comparisons.

Question 2

Which algorithm solves the single-source shortest path problem with negative edge weights (but no negative cycles)?

Accepted Answer

Bellman-Ford

Answer

Bellman-Ford handles negative edge weights by relaxing all edges V-1 times, unlike Dijkstra's which requires non-negative weights.

Question 3

What does 'P vs NP' refer to in computational complexity theory?

Accepted Answer

Whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time

Answer

P vs NP asks whether every problem verifiable in polynomial time (NP) can also be solved in polynomial time (P).

Question 4

Which traversal of a binary search tree produces elements in sorted order?

Accepted Answer

In-order

Answer

In-order traversal visits left subtree, root, then right subtree, producing a sorted sequence in a BST.

Question 5

What is the key invariant maintained by Quick Sort's partition step?

Accepted Answer

All elements to the left of pivot are smaller, all to the right are larger

Answer

After partitioning, all elements less than the pivot are on its left and all greater are on its right.

Algorithms Practice Test