Question

Remarks: In all algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Do not write a program. Write pseudo codes or explain in words

Question 2: 1. Show how to implement a Queue by a Priority Queue. What is the run time per operation? 2. Show how to implement a Stack using Priority Queue. What is the run time per operation?

Answer 1

Solution 1- Priority Queue is a Queue where each element is assigned a priority and elements come out in order by priority. Typical use case of priority queue is scheduling jobs. Each job has a priority and we process jobs in order of decreasing priority. While the current job is processed and new jobs may arrive.

Priority Queue has some main operations:

• Insert(p): Adds a new element with priority p.
• ExtractMax(): Extracts an elements with maximum priority.
• ChangePriority(it, p): Changes the priority of an element pointed by it to p.

Priority Queue is used in many algorithms:

• Dijkstra’s algorithm: finding a shortest path in a graph.
• Prim’s algorithms: constructing a minimum spanning tree of a graph.
• Huffman’s algorithm: constructing an optimum prefix-free encoding of a string.
• Heap sort: sorting a given sequence.
• You can implement priority with unsorted/sorted Array or List
• Unsorted Array/list - Insert take O(1) time and ExtractMax take O(n) time
• Sorted Array/List- Insert take O(n) time and ExtractMax take O(1) time
• Implementing the priority queue
  A priority queue can be implementing using a variety of data structures, each with different tradeoffs
  between memory required, runtime performance, complexity of code, etc. In this assignment, you will
  consider four different implementations. One implementation stores the queue elements in an
  unsorted vector. The second represents the priority queue as a sorted linked list. The third is a hybrid
  cross between an array and a linked list, a chunklist. The last represents the priority queue as
  specially-ordered binary tree called a heap (not to be confused with the heap where memory is
  dynamically allocated by new).

Solution 2

Pseudocode

class Stack {
    class Element { int prio, Key elem; };
    MaxPriorityQueue<Element> q;
    int top_priority = 0;

    void push(Key x) { q.push(Element(top_priority++, x)); }
    Key pop() { top_priority--; return q.pop().elem; }
};

LIFO behavior follows from the fact that every new element is pushed with a priority higher than all the current elements, so it will be popped before any of them.