Your assignment is to implement a linked list data structure with head and tail pointers along with support for efficient Range Minimum Queries.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Your assignment is to implement a linked list data structure with head and tail pointers along with support for efficient Range Minimum Queries (RMQ). The list will store key/value pairs where the types for both the key and the value are template parameters. The list must store the elements in ascending key order and must not allow duplicate keys.

For the RMQ, you must use either Dynamic Programming or Block Decomposition. Specifications For the RMQList class, you must declare the class variables necessary to support RMQ and implement the following methods: Method Description RMQList() Constructor. Creates an empty RMQList object. ~RMQList() Destructor RMQList(const RMQList &rhs) Copy Constructor const RMQList& operator=(const RMQList &rhs) Assignment Operator int size() const Returns the number of elements in the list.

This function is already implemented. bool empty() const Returns true if the list is empty, false otherwise. bool insert(const K& key, const V& value) Inserts an element into the list. The list must be kept in increasing order by key, and duplicate keys are not allowed. The function returns false if there is already an entry with the given key value and returns true otherwise. If the specified key is larger than all keys in the list, then the function should append the new data to the end of the list, avoiding unecessary iteration. bool remove(const K& key) Remove the element with specified key value from the list. Returns false if there is no element with the specified key; returns true otherwise. bool update(const K& key, const V& value) Update the value for the element with the given key value. Returns false if there is no element with the given key; returns true otherwise. V query (const K& k1, const K& k2) Returns the minimum value between k1 and k2 in the list data (including the values associated with k1 and k2). Must be implemented using Dynamic Programming or Block Decomposition, and queries must be efficient for large lists (tens of thousands of entries).

Throws an exception if the list is empty or if an invalid key is passed (see Requirements, below). Void dumpList() const Dump the contents of the linked list. void dumpTable() const Dump the entire RMQ tables. This will depend on which RMQ method you choose to implement. For the block decomposition approach, the function should print the number of blocks, the block size, and the block minimums. For dyanmic programming, the function should print the entire array of pre-computed minimums. Void clear() Reset the RMQList object to its initial, empty state. Requirement: Since the RMQList class is templated, the entire implementation must be in rmqlist.h. Requirement: The following modifications may be made to rmqlist.h: addition of private class variables to support RMQ; addition of private helper function declarations; addition of function implementations. No other changes are permitted. In particular, you must not change the declaration of the required public functions. Requirement: The class must correctly implement either the Dynamic Programming or Block Decomposition solution for RMQ. Your code will be tested for correct running times, and the TAs will visually inspect your implementation.

 

Requirement:

 If you use the Block Decomposition method for RMQ, the blocksize must be?? N?. This can be computed in C++ with (int) sqrt((float) n). Requirement: The query function must throw exceptions as follows: Throws range error if query is called for an empty list. Throws invalid argument if either key value (k1 or k2) is not valid (not in the data). Requirement: No STL containers or additional libraries may be used. Requirement: Your code should not have any memory leaks or memory errors. Requirement: Follow all coding standards as decribed on the C++ Coding Standards. In particular, class variable names must begin with “m_” or “_”. The file rmqlist.h contains the function declarations for two classes: Node — defines the nodes used in the linked list

 The Node class is completely implemented and must not be modified. RMQList — implements the linked list supporting Range Minimum Queries. You will be completing this class. The private class variables for the linked list have been defined and should not be changed; however, you may add private variables to support efficient RMQ.

Whicever RMQ variant you choose to use, you will need some array-type variables. You may only use C/C++ arrays; STL containers may not be used. Additionally, you are responsible for thoroughly testing your program. Your test program, mytest.cpp, must be submitted along with rmqlist.h. For grading purposes, your RMQList implementation will be tested on input arrays of varying sizes, including very large arrays. Your submission will also be checked for memory leaks and memory errors. Finally, you should strive to make your RMQ implementation as efficient as possible. Both RMQ methods require you to precompute tables that are used by the query function. Avoid recomputing the tables unecessarily. Inserting or removing data will invalidate the pre-computed tables for either method; are there cases in which it is possible to update the tables without completely recomputing them? What to submit? rmqlist.h mytest.cpp

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of