11.1. Design and Analysis of Algorithms

Try these first

1. 1.

   What is a heap?

   Hint

   Think about how trees can have children and parent nodes.

2. 2.

   What is the time complexity for insertion in a heap?

   Hint

   Consider how many levels the tree has.

3. 3.

   What is the time complexity for deleting an element from a heap?

   • O(N)
   • O(log N)
   • O(1)

   Hint

   Think about how levels of a tree work.

4. 4.

   True or False: Increasing a value in a min-heap may require moving the updated value downwards.

   • True
   • False

   Hint

   How does value comparison work in heaps?

5. 5.

   Given the following input values: 15, 10, 20, 30, 5, illustrate how to perform heap operations to maintain a min-heap.

   Hint

   Start with the first value as the root.

6. 6.

   Implement a step-by-step demonstration of Dijkstra's algorithm using the following graph: A (0) -> B (4), A (0) -> C (2), B (4) -> D (5), C (2) -> D (8) and show how the heap is updated.

   Hint

   Keep track of reported distances in a table as you iterate over vertices.