Project: Priority Queues
Generic implementations of priority queue
Educational Objectives: After completing this assignment, the student should be able to accomplish the following:
-Apply generic algorithms in solving programming problems
-Define and give examples of generic associative containers
-Define and give examples of generic algorithms
-Define the ADT Priority Queue
-Implement the ADT Priority Queue as a generic associative container subject to various constraints, including:
a. Push(t) <= O(size), Pop() = Θ(1)
b. Push(t) = Θ(1), Pop() <= O(size)
c. Push(t) <= O(log size), Pop() <= O(log size)
Use namespaces to develop and test multiple implementations of an ADT.
These last operations are useful in development and performance testing. We could, for example, drop in a "spy" version of order and use GetPredicate to obtain counts of the number of calls, obtaining runtime data on the implementation. Dump gives a snapshot of the underlying container, useful in development and testing.
Priority queues are used in several important applications, including:
- Operating system job schedulers
- Communications Satelite schedulers
- Discrete Event simulations
- Embedded/RealTime Systems
- Control structures for certain algorithms, such as Best First Search
Procedural Requirements -
1. The official development/testing/assessment environment is specified in the Course Organizer.
2. Be sure start and maintain your log.txt.
3. After creating your log.txt, begin by copying all of the files from LIB/proj8 into your project directory.
4. Create and work within a separate subdirectory. The usual COP 4530 rules apply (see Introduction/Work Rules). In particular: It is a violation of course ethics and the student honor code to use, or attempt to use, files other than those explicitly distributed in the course code library.
5. Place all work in one file named pq.h.
6. Turn in the files pq.h and log.txt using the submit script LIB/scripts/submit.sh and the configuration file LIB/proj8/deliverables.sh.
Technical Requirements and Specifications
1. Place all work in one file named pq.h. The code should use 6 distinct namespaces: std, fsu, pq1, pq2, pq3, pq4, pq5, and pq6.
2. The first two namespaces are those encountered in the standard and course libraries. The other six are defined in the submitted code.
3. Every method implementation must be one of three types:
i. Type 1 (no search is required): the body consists of a single call to an operation of the underlying container.
ii. Type 2 (search is required): the body uses a member function or a generic search algorithm with a minimum of ancillary code.
iii. Type 3 (heap-based): the body uses a generic heap algorithm with a minimum of ancillary code.
4. Your submission is required to run correctly with the distributed client program tests/fpq.cpp. We will assess using fpq.cpp and another client program that uses a priority queue to sort data.
5. The log file should contain (1) statements of the runtime of the various priority queue methods, (2) explanations [informal proofs] that your statements are correct, and (3) testing procedures and results of testing.
6. The file level documentation should contain brief descriptions of the design for each implementation of priority queue. Please also include this in your log file.
Attachment:- Priority Queues Assignment.rar