Implement the adt priority queue

Assignment Help Data Structure & Algorithms

Reference no: EM131306564

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

Reference no: EM131306564

Questions Cloud

Calculate the present value of this cash flow stream : Suppose you are to receive $4,500 1 time(s) per year every year for 6 years (starting one year from now) plus $97,000 in 6 years. If the appropriate discount rate is 5.50%, calculate the present value of this cash flow stream.

Sales increase before any new fixed assets are needed : The discussion of EFN in the chapter implicitly assumed that the company was operating at full capacity. Often, this is not the case. For example, assume that Rosengarten was operating at 90 percent capacity. Thorpe Mfg., Inc., is currently operating..

What tools do you find most helpful for managing projects : What tools do you find most helpful for managing projects? How can you use spreadsheet software, such as Microsoft Excel, within the various project management processes?

Compare to current yield-to-maturity on a one-year strips : Use the following information to answer the next question: U.S. Treasury STRIPS, close of business Aug 15, 2016: According to the pure expectations theory of interest rates, how much would you expect to pay for a one-year STRIPS on Aug 15, 2017? What..

Implement the adt priority queue : Implement the ADT Priority Queue as a generic associative container subject to various constraints, including: Push(t)

Do you believe that your city delivers on its marketing : Who are their target customers? For example, are they: businesspeople or tourists; locals or travelers from afar? What benefits do they tout? Do you believe that your city/state delivers on its marketing promises? Why or why not?

Analyze a given enterprise environment : Analyze a given Enterprise environment and use models to design a network architecture that meets the business needs and processes indicated by the enterprise architecture.

Estate tax liability the client will ultimately pay : the 30-year projections in layman’s terms, assuming 3% annual appreciation in the value of the assets of a business. Consider the gift and estate tax liability the client will ultimately pay.

How would your decision affect the overall project : What do you need to consider before accepting or denying the vendor proposal? Explain. How would your decision affect the overall project?

User Account

All Pages