Session 04 & 05

Question 1

Priority Queue?

Answer 1

An abstract data type which behave similar to the linear queue except that each element has priority.

Question 2

Charactistics of Priority Queue?

Answer 2

• Every element have some prority
• Higher priority elemets will be removed first, lowest priority elements will be last.
• If two elements have same priority, they will be removed according to the FIFO

Question 3

Linked list prority queue is not good stratergy?

Answer 3

• Time complexity for insertion becomes O(N)
• For peek() also O(N)
• Diffifult time and memory management.

Question 4

Heap ?

Answer 4

• Tree like data structure that form complete binary tree.
• If a parent node always ordered with respect to child nodes, like
  parent node value >= child node value or
  parent node value <= child node value,
  it is considered as Heap.

Question 5

Two types of Heap?

Answer 5

• Max Heap : value of parent node greater than child node
• Min Heap : value of parent node smaller that child node

Question 6

Priority queue types?

Answer 6

• Min Priority Queue : Element with least value have high priority
• Max Priority Queue : Element with highest value have high priority

Question 7

Find positions of nodes in Heap?

Answer 7

Parent node : A[(i-1)/2]
Left child : A[(2 . i) + 1]
Right child : A[(2 . i) + 2]

Question 8

Applications of Priority Queue?

Answer 8

• Digital mapping services in Google Maps
  Dijkstra’s shortest path algorithm uses priority queue to find out the optimal path
• Data compression in formats like GZIP, WINZIP
  Huffman encoding algorithm using priority queue to map data from different file

Question 9

Types of computational complexity classes?

Answer 9

1. P class
   * Polynomial time
   * EX :
   i) Find maximum matching
   ii) Searching
2. NP class
   * Nondeterministic Polynomial time
   * EX :
   i) Hamiltonian path problem
   ii) Graph coloring
   iii) Travelling salesman problem
3. NP hard
4. NP complete