I need help constructing an amoritzed function in c++ for generating the smallest difference between two sequences. The difference between two sequences of the same length {a1,a2,a3,..,an} and {b1,b2,b3,...,bn} can be defined as the sum of the absolute differences between their respective elements.

diff(a,b) = { |a1-b1|, |a2-b2|, |a3-b3| .... |an-bn|

Here's an example:

So, if A was {1,2,6} and b is {0,1,3,4,5} you first have to find the best subsequence by looking at the values of A and which numbers of B would get the smallest difference. So, the first number in A is 1. 1-0 = 1, 1-1 =0, 1-3=|-2| which is 2, 1-4 = |-3|, 1-5 ] |-4| So the smallest number is 0 which would mean 1 is the golden number for the subsequence. You complete the same method for all of the numbers in the sequence of A which would make the best subequence (1,3,5) and you find the smallest difference by subtracting those numbers by the orginal in A so ((1-1)+|(2-3)|+(6-5)) =2. The smallest difference is 2.

The goal of the program is to use a dynamic programming technique to write an amorited version of a smallestDifference function in the smallestDifference utility function. The maximum time for this function to identify the solution is 500 ms. The length of a will be in the range (3,1000) and the length of b will be in the range [a.lengh, 1000]. The values in each array will be in the range [-1000,1000]

The main.cpp and the smallestDifference.h file is already complete. I just need help implementing the amoritzed function. I have put the main and .h file below whih can not be changed.

main.cpp:

#include #include #include #include #include #include #include #include

#include "smallest_difference.h"

typedef int (*differenceFunction)(const std::vector&, const std::vector&);

void printSet(const std::vector& v, const std::string& name) { std::cout << "Set " << name << ": ["; std::copy(v.begin(), v.end() - 1, std::ostream_iterator(std::cout, ", ")); std::cout << v.back() << "]" << std::endl; }

void findDifference(const std::vector& a, const std::vector& b, differenceFunction func) { std::clock_t start = std::clock(); int d = func(a, b); std::clock_t end = std::clock(); float t = static_cast(end - start) / CLOCKS_PER_SEC; std::cout << "The smallest difference is " << d << ", found in " << std::fixed << std::setw(8) << std::setprecision(6) << std::setfill('0') << t << " seconds." << std::endl; }

int main(int argc, char** argv) { if (argc != 3) { std::cout << "Usage: " << argv[0] << " a-sequence-file b-sequence-file" << std::endl; return 0; }

std::ifstream aIn(argv[1]); std::ifstream bIn(argv[2]);

std::vector a; std::vector b;

std::copy(std::istream_iterator(aIn), std::istream_iterator(), std::back_inserter(a)); std::copy(std::istream_iterator(bIn), std::istream_iterator(), std::back_inserter(b));

std::cout << "Looking for the smallest difference between the following sets:" << std::endl; printSet(a, "a"); printSet(b, "b");

std::cout << "Using Recursive function: "; findDifference(a, b, smallestDifference_recursive); std::cout << std::endl; std::cout << "Using Amortized function: "; findDifference(a, b, smallestDifference_amortized); std::cout << std::endl;

std::cout << "Using Optimized function: "; findDifference(a, b, smallestDifference_optimized); std::cout << std::endl;

return 0; }

smallest_Difference.h:

#pragma once #ifndef __SMALLEST_DIFFERENCE_H__ #define __SMALLEST_DIFFERENCE_H__

#include

int smallestDifference_recursive(const std::vector& a, const std::vector& b); int smallestDifference_amortized(const std::vector& a, const std::vector& b); int smallestDifference_optimized(const std::vector& a, const std::vector& b);

#endif // __SMALLEST_DIFFERENCE_H__

smallestDifference.cpp:

#include #include #include "smallest_difference.h"

/*********************************************************************\ Smallest Difference using Recursive techniques with Amortization \*********************************************************************/

int smallestDifference_amortized_utility(const std::vector& a, const std::vector& b, int aPos, int bPos, std::vector >& results) { //Need to To }

int smallestDifference_amortized(const std::vector& a, const std::vector& b) { std::vector > results(a.size(), std::vector(b.size(), -1)); return smallestDifference_amortized_utility(a, b, a.size(), b.size(), results); }