Implement advanced data structure

Assignment Help Data Structure & Algorithms
Reference no: EM131251172

Value Sequences

Objectives
- Implement more advanced data structure.
- Practice using basic C++ data structures.
- Practice working with C++ classes.
- Practice working with partially provided code.

Introduction

There are times when certain simple functionality is best achieved by a data structure that builds on top of other, standard, data structures. Consider this example scenario. In our code, we are dealing with key/value pairs of integers. These are pairs of integers where the first integer is called key, and the second integer is called value. We want to store all key/value pairs such that for each key we know which values and in what order we have inserted. For example, for the following key/value pairs (0, 2), (-1, 3), (3, 7), (0, 5), (3, 2), (3, 5), (-1, 3), (-1, 0) we would like to be able to retrieve sequence (3, 3, 0) for key -1, sequence (2, 5) for key 0 and (7, 2, 5) for
key 3.

Your task is to extend partially implemented, and provided to you, key_value_sequences class, to provide exactly that functionality. So for example, this simple code (that roughly corresponds to the example above):
key_value_sequences A;

A.insert(0, 2);
A.insert(-1, 3);
A.insert(3, 2);
A.insert(0, 5);
A.insert(3, 7);
A.insert(3, 5);
A.insert(-1, 3);
A. insert(-1, 0);

auto p = A.data(3);
for (int i = 0; i < A.size(3); ++i) std::cout << p[i] << " ";

when compiled with properly implemented key_value_sequences should produce: 2 7 5.

As usually, your implementation has to be efficient and you have to work under certain con- straints. Specifically, you cannot use any external or standard C++ headers except of <algorithm>,
<list> and <vector>.

Hints

The simplest and reasonably efficient approach to this assignment is to use a combination of double-linked list (std::list<>) and vector (std::vector<>). Do not be afraid to make a list of vectors or vector of lists. Do not hesitate to leverage std::list<>::iterator, it is a type as any other C++ type. std::vector<> provides method data() that perfectly meets requirements you will need to implement method data() in key_value_sequences. This is one of many ways in which this problem can be approached.

Instructions

1. Create directory A3 where you will place your code.

2.Download A3-handout.tar from:
https://www.jzola.org/courses/2016/Fall/CSE250/A/A3-handout.tar.

3. Untar handout, and move a3.hpp and a3.cpp to your A3 directory.

4. Implement missing elements in a3.hpp taking into account the following:

(a) a3.hpp is the only file you are allowed to modify. a3.cpp is a simple test program demonstrating functionality that your implementation of key_value_sequences must support. You must use it to perform the most basic initial testing of your code. If your code fails to work with a3.cpp you will not be graded. You are not allowed to make any changes to a3.cpp.

(b) Analyze carefully a3.hpp and a3.cpp to better understand key_value_sequences. This class should implement functionality of multiple sequences, where each sequence stores integers and is "identified" by an integer key.

(c) Missing parts of the code that you are expected to implement are marked with IMPLEMENT ME. In short, you have to implement three critical methods: insert(), size() and data().

(d) Method insert() is the workhorse of the class. Its purpose is to take a key/value pair,
i.e. two integers, and push back the second integer (which is a value) into the sequence identified by the first integer (which is a key).

This is the only modifying method.

(e) Method data() is the main method to access the stored values. Its purpose is to take one integer (which is a key), and return a pointer to a sequence of all integers inserted with that key. If no element had been inserted with given key it should return nullptr. If a sequence exists for the key, the method should return pointer to the continuous block with that sequence. Elements in the sequence must be in the same order in which they had been inserted (refer to examples above).

(f) Method size() is another access method. Its purpose is to take one integer (which is a key), and return the total number of elements inserted with that key. If no element had been inserted with given key the method should return -1.

(g) You can add, remove or modify code in key_value_sequences without limits as long as it correctly compiles and executes with the provided a3.cpp and the only included headers are <algorithm>, <list>, <vector>. To compile a3.cpp with your a3.hpp you should use basic compiler setting, e.g.: g++ -std=c++11 -O2 a3.cpp -o a3. If your code satisfies the most basic requirements for grading, you should see pass printed when executing a3.

(h) You are encouraged to use C++11 containers std::vector and std::list with all their goods to avoid raw pointers.

(i) Your implementation must be efficient. You can expect millions of key/value pairs inserted and your class should be able to handle them in seconds.

(j) You should make no assumptions about the distribution of inserted elements, i.e. keys or values, and the order in which elements will be inserted.

(k) You should be careful with how you utilize memory. If you are too excessive in al- locating memory, your code will exhaust available resources and your code will be terminated and not graded.

1. Remove your binary code and other unrelated files (e.g. your test files).

2. Create a tarball with your A3 folder.

3. Follow tohttps://autograder.cse.buffalo.eduand submit A3.tar for grading.

4. You have unlimited number of submissions, however, any submission after the deadline will have 50% points deducted.

Reference no: EM131251172

Questions Cloud

Write a program that iterates the given numbers : Write a program that iterates through numbers from 0 to 113 using a loop. Print the numbers, one number per line. As you print each number, say x.
What are the cournot equilibrium quantities : What would be the equilibrium price in this market if firms acted as price-taking firms?
Determining the changes in art : For this week, answer all three of the following questions. Cite at least one example in your response for each question. You should reference your book to help you answer these questions. If you use additional sources, you must cite them. Your an..
Write a paper on kirby-bauer diffusion test : Write a paper on Kirby-Bauer Diffusion Test. Can you please correct my paper and add this material: They really want you to focus on the data that you obtained. Based on your data, the S. epidermidis was resistant to penicillin, susceptible to gent..
Implement advanced data structure : CSE250 Fall -  Implementation has to be efficient and you have to work under certain con- straints -  certain simple functionality is best achieved by a data structure that builds on top of other, standard, data structures
What different inparticipation on social justice and peace : Compare your experience with the serviceplacement experience of the student you interviewed. What ways are they similar and different inparticipation on social justice and/or peace? What new insights did you gain from this interviewto understand w..
Formulate and justify an investment policy statement : Formulate and justify an investment policy statement setting forth the appropriate guidelines within which future investment actions should take place.
Display a form allowing the user to enter the players names : Display a form allowing the user to enter the players' names. Display a form that can be used during a game to record the points scored by each player. Display the total points scored by each player and by the team.
International magazines and more : The Super Global International Food Market is filled with nuts, books, vegetables, fruits, rice, foreign DVDs, international magazines and more.

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Algorithm to find maximum sum of contiguous sublist

Using dynamic programming, write an algorithm to find the maximum sum of contiguous sublist of a given list of n real values.

  Describing the data types

Create a 10-12 slide presentation describing the data types. Include the following in your presentation: Introductory slide and Slide for each data type

  Differences between the structured design methodology

differences between the structured design methodology

  Finding approximation algorithm and ratio of the algorithm

finding approximation algorithm and the ratio of the algoirthm.

  Variables constants and data types

The following M.U.S.E. materials may help you with this assignment: Sequential Logic Structures and Variables, Constants, and Data Types

  The decision tree inductive learning algorithm

The Decision Tree inductive learning algorithm may be used to generate "IF ... THEN" rules that are consistent with a set of given examples. Consider an example where 10 binary input variables X1, X2, , X10 are used to classify a binary output variab..

  Declare a global array solution

Declare a global array Solution

  What would ultimate result of algorithm

Single grain of wheat was to be placed on the first square of chess board, two on second, four on third, eight on the fourth, and so on, until all 64 squares had been filled. What would ultimate result of this algorithm have been?

  Definition of a method isreverse

Provide the definition of a method, isReverse , whose two parameters are arrays of integers of equal size. The technique returns true if and only if one array is reverse of the other.

  Performance of two distinct sorting algorithms

This lab assignment requires you to compare the performance of two distinct sorting algorithms to obtain some appreciation for the parameters to be considered in selecting an appropriate sort.

  Complete binary tree

Think about an n-node complete binary tree T, where n=2^d - 1 for some d. Each node v of T is labeled with a real number x_v.

  Explain computer algorithms and its significance

Explain computer algorithms and its significance. Explain some of the technologies that have contributed to the exponential growth of the Internet and the World Wide Web (WWW).

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd