The difference between two sequences of the small length {a1, a2, a3, ..., an} and {b1,b2,b3,...bn} can be defined as the sum of the absolute differences between their respective elemenets:

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

For the given sequences a and b {not neccessarily having the same lengths), find the subsequence a' or a and sequence b' of b such that diff{a',b') is minimal. Return the diffrence.

Example:

A ={1,2,6}, b={0,1,2,3,4,5}, the output should be smallestDifference(a,b) = 2, where the best subsequence will b' = {1,3,5}

The goal of this assignment is to use dynamic programming techniques to write a recursive solution to the problem, convert that solution to an amortized solution, and then to identify a way to convert that solution to a loop-based solution.

I need help implementing a recursive version of the smallestDifference function in the smallestDifference_recursive_utility function. There is no time restriction on this solution (it will take a while to run larger tests) I need to implement an amortized version of the smallestDifference function in the smallestDifference)amortized_utility function. The maximum time for this function to identify the solution is 500ms (regardless of input size) I need to implement a loop-based version of the smallestDifference function in the smallestDifference_optimized function. The maximum time for this funcion to identify the solution is 500ms (regardless of input size) The length of a will be in the range [3,1000] The length of b will be in the range [a.length, 1000] The values in each array will be in the range [-1000,1000] Only smallest_difference.cpp get changed the rest stay untouched.

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.cpp

#include #include #include "smallest_difference.h"

/*********************************************************************\ Smallest Difference using Recursive techniques \*********************************************************************/ int smallestDifference_recursive_utility(const std::vector& a, const std::vector& b, int aPos, int bPos) {

}

int smallestDifference_recursive(const std::vector& a, const std::vector& b) { return smallestDifference_recursive_utility(a, b, a.size(), b.size()); }

/*********************************************************************\ 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) { }

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); }

/*********************************************************************\ Smallest Difference using non-Recursive techniques \*********************************************************************/ int smallestDifference_optimized(const std::vector& a, const std::vector& b) { }

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__