Apply generic algorithms in solving programming problems, Programming Languages

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:
Push(t) <= O(size), Pop() = T(1)
Push(t) = T(1), Pop() <= O(size)
Push(t) <= O(log size), Pop() <= O(log size)
Use namespaces to develop and test multiple implementations of an ADT
Experience applying the following concepts: associative generic containers; generic algorithms; priority queue; and developing and testing multiple implementations using namespace.
Operational Objectives: Design and implement six (6) distinct implementations of the Priority Queue template PriorityQueue based on List, MOList, Vector (2), MOVector, and Deque. Use namespaces pq1, pq2, ... , pq6 to scope the six variations.
Deliverables: Two files pq.h and log.txt
Background:
A priority queue stores elements of typename T with a priority determined by an object of a predicate class P. The operations are syntactically queue-like but have associative semantics (rather than positional semantics, as in an ordinary queue). The operations for a priority queue PQ and informal descriptions of them are as follows:
void Push (const T& t) // places t in the priority queue, position unspecified
void Pop () // removes the highest priority item from the priority queue
T Front () // returns (a copy of) the highest priority item in the priority queue
bool Empty () // returns true iff the priority queue is empty
as well as default constructor, destructor, copy constructor, and assignment operator (i.e., we need priority queue to be a proper type). We will also use the following additional operations (as usual for our course library):
void Clear () // makes the priority queue empty
size_t Size () // returns the number of elements in the priority queue
void Dump (std::ostream& os, char ofc = ''\0'') // display underlying structure
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
Priority queues are traditionally built as adaptations of other data structures using special algorithms. The most sophisticated of these are discussed in the chapter Binary Heaps. However, us usual, "most sophisticated" does not always translate as "best". "Best" is usually determined by client programmers based on the client needs. (Compare g_insertion_sort() with g_heap_sort() for example.)
In this assignment you will build priority queues using (1) one of our familiar Containers Vector, Deque, List, MOVector, MOList as the data storage facility and (2) an appropriate algorithm for the search mechanism. In the case of heap-based priority queue (case 6) two generic algorithms will be required.
Procedural Requirements
The official development/testing/assessment environment is: gnu g++ on the linprog machines.
Be sure start and maintain your log.txt.
After creating your log.txt, begin by copying all of the files from LIB/hw5 into your project directory.
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.
Place all work in one file named pq.h.
Turn in the files pq.h and log.txt using the hw5submit.sh script.
Warning: Submit scripts do not work on the program and linprog servers. Use shell.cs.fsu.edu to submit assignments. If you do not receive the second confirmation with the contents of your project, there has been a malfunction.
Technical Requirements and Specifications
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.
The first two namespaces are those encountered in the standard and course libraries. The other six are defined in the submitted code. These six namespaces define the scope of certain definitions, as shown in the following sample file documentation:
/* pq.h

Various implementations for PriorityQueue < T , P >
organized by namespace as follows:

nmsp stbl container element order central algorithm push pop front
---- ---- --------- ------------- ------------------- ---- --- -----
pq1 y List unordered fsu::g_max_element() O(1) O(n) O(n)
pq2 y MOList sorted MOList::Insert O(n) O(1) O(1)
pq3 n Vector unordered fsu::g_max_element() AO(1) O(n) O(n)
pq4 y Vector unordered fsu::g_max_element() AO(1) O(n) O(n)
pq5 y MOVector sorted OVector::Insert O(n) O(1) O(1)
pq6 n Deque head fsu::g_push/pop_heap() O(log n) O(log n) O(1)

The pq3 version just copy the last element over the element
to be removed, whereas the pq4 version does a leapfrog copy. Note that the
leapfrog copy version is stable, the 1-element copy version is not.

All of the pq namespaces are defined in this file.
*/
Every method implementation must be one of three types:
Type 1 (no search is required): the body consists of a single call to an operation of the underlying container
Type 2 (search is required): the body uses a member function or a generic generic search algorithm with a minimum of ancillary code.
Type 3 (heap-based): the body uses a generic heap algorithm with a minimum of ancillary code.
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.
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. (See specific ABET outcomes iii and iv above.)
The file level documentation should contain brief descriptions of the design for each implementation of priority queue. (See specific ABET outcome v above). Please also include this in your log file.
Hints:
Here is a start on pq1, along with the include files that you will need:
· /* pq.h */
·
· #include // fsu::g_max_element()
· #include // fsu::g_push_heap() , fsu::g_pop_heap()
· #include // fsu::List<> , fsu::List<>::Iterator
· #include // fsu::Vector<> , fsu::Vector<>::Iterator
· #include // fsu::Deque<> , fsu::Deque<>::Iterator
· #include // fsu::MOList<> , fsu::MOList<>::Iterator
· #include // fsu::MOVector<> , fsu::MOVector<>::Iterator
·
· namespace pq1
· {
·
· template
· class PriorityQueue
· {
· typedef typename fsu::List < T > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in unsorted order in list
· // Push(t): PushBack(t)
· // Front(): use fsu::g_max_element() to locate largest, then return element
· // Pop() : use fsu::g_max_element() to locate largest, then remove element
·
· PredicateType p_;
· ContainerType c_;
·
· public:
· PriorityQueue() : p_(), c_()
· {}
·
· explicit PriorityQueue(P p) : p_(p), c_()
· {}
·
· void Push (const T& t)
· {
· // TBS
· }
·
· void Pop ()
· {
· // TBS
· }
·
· const T& Front () const
· {
· typedef typename ContainerType::ConstIterator IteratorType;
· IteratorType i = fsu::g_max_element (c_.Begin(), c_.End(), p_);
· return *i;
· }
·
· void Clear ()
· {
· // TBS
· }
·
· bool Empty () const
· {
· // TBS
· }
·
· size_t Size () const
· {
· // TBS
· }
·
· void Dump (std::ostream& os, char ofc = ''\0'') const
· {
· // TBS
· }
· };
·
· } // namespace pq1
·
· namespace pq2
· {
· // yada dada
Note that we have used in-class implementations, as we did with the adaptor classes Stack and Queue. This is an acceptable practice for classes like PriorotyQueue that are essentially adaptors of existing technology to a new interface.
Clear(), Empty(), and Size() should just call the container operation of the same name. Dump() should output the contents of the underlying container. That leaves only the three operations Push(t), Pop(), and Front() requiring plan-specific implementations.
Note that an implementation of Front() is supplied above, as an illustration of how to apply generic algorithms.
Note that there are two constructors. The first is the parameterless, or "default", constructor. It creates the predicate object using the default PredicateType constructor. The second takes a predicate object as an argument, so that the client can supply whatever exotic priority scheme is desired. By tradition established in the STL, function object arguments are passes by value.
If the model above is followed for all six versions, the default destructor, copy constructor, and assignment operator should work, so neither prototype nor implementation of these operations is necessary. (Can you explain why?)
The following operations can use the identical implementation across all the namespaces: Constructors and other proper type operations, Clear(), Empty(), and Size(). Thus the only operations whose implementation varies from one namespace to another are the three that define the priority queue concept: Push(), Pop(), and Front().
The term "IteratorType" is defined locally as a convenience only. This type is an iterator for the underlying structure, not an iterator for PriorityQueue.
Note the "const correctness" indicated in the example. Methods that should not disturb the priority queue are specified const. And the return type of Front() is a const reference, which prevents clients from modifying the element in the priority queue (which could disrupt the internal structure of the implementation).
Look carefully in fpq.cpp to see how to declare and use PriorityQueue objects, in particular, how the predicate is instantiated. (We will use LessThan or GreaterThan for the predicate class in our tests.)
Here are the "implementation plan" documentation statements for all 6 versions:
· namespace pq1
· {
· ...
· typedef typename fsu::List < T > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in unsorted order in list
· // Push(t): PushBack(t) (or PushFront(t)) will do
· // Front(): use fsu::g_max_element() to locate largest, then return element
· // Pop() : use fsu::g_max_element() to locate largest, then remove
· ...
· } // namespace pq1
·
· namespace pq2
· {
· ...
· typedef typename fsu::MOList < T , P > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in increasing order in list
· // last element is largest
· // Push(t): use MOList::LowerBound ()
· // Front(): return back element of list
· // Pop() : remove last element of list
· ...
· } // namespace pq2
·
· namespace pq3
· {
· ...
· typedef typename fsu::Vector < T > ContainerType;
· typedef T ValueType;
· typedef P PredicateType;
·
· // store elements in unsorted order in vector
· // Push(t): PushBack(t)
· // Front(): use fsu::g_max_element() to locate largest, then return element
· // Pop() : use fsu::g_max_element() to locate largest, then "remove"
· // "remove" can be done two ways:
· // (1) copy last element to popped element, then Popback()
· // Note that (1) is unstable but O(1)
· // (1) suggested by Janice Murillo March 2004
· // (2) "leapfrog" copy elements down one index, starting at popped element, then PopBack()
· // Note that (2) is stable and O(n)
· // In either case, both Front() and Pop() are O(n)
· // due to the call to g_max_element().
· // pq3 uses (1)
· // pq4 uses (2)
· ...
· } // namespace pq3
·
· namespace pq4
· {
· ...
· typedef typename fsu::Vector < T > ContainerType;
·
Posted Date: 4/6/2012 12:28:31 AM | Location : United States







Related Discussions:- Apply generic algorithms in solving programming problems, Assignment Help, Ask Question on Apply generic algorithms in solving programming problems, Get Answer, Expert's Help, Apply generic algorithms in solving programming problems Discussions

Write discussion on Apply generic algorithms in solving programming problems
Your posts are moderated
Related Questions
The creation of the menu will involve writing procedural code, using decision logic, writing a loop, and using the case statement.  Although it is not required for grading, it is r

#1. Every mathematics student likes primes numbers. Every mathematics student like parabolas. Let''s put them together to have some fun: Consider two natural numbers a and b. Of co

Produce a hierarchy chart, a structured flowchart, and a Pascal program (with appropriate comments) to generate the Sales Commission Report shown below. The commission for each sal

An apartment complex has several apartments to rent. The apartments are all similar, and all rent for $750 per month. Currently, all units are occupied. The management, being in bu

Linear Programming Consider the following optimization problem: min x s.t. x ≥ max{a1, a2, . . . , an} Rewrite this problem as a Linear Programming Problem. What is the

For the following Code answer the following questions-: .STACK 100H .DATA COUNT DB 10 TOTAL DW 4126H .CODE MAIN PROC MOV BX, 3F20H MOV AL, BL MOV BL, COUNT MOV

Let us first see the skeleton of a JavaScript file. JavaScript code should be written between the and tags. The value LANGUAGE = "JavaScript" indicates to the browser that J

Dynamic Binding: - Binding refers to the linking of a procedure call to the code to be executed in response to the call. Dynamic binding (late binding) means that the code associa

One of the main strengths of the Perl programming language are its powerful text manipulation features. In this assignment, you will put them to use for writing a Perl program that

(a) Write a recursive procedure (digits n) that computes the number of digits in the integer n using a linear recursive process. For example, (digits 42) should return 2 and (digit