solve dynamic programming and backtracking project
Budget: €8 – €30 EUR
I need someone to solve this algorithmic project
Project 2: Dynamic Programming and Backtracking
Problem 1: Let us consider a rod that is to be sectioned into fragments of different lengths. Knowing that
each length has a different price, the problem is to determine a way of sectioning the rod with a
minimum price.
Example: For a rod of length 8 for which the fragments prices are p = [2, 3, 1, 4, 6, 5, 6, 5] (obtaining a
segment of length 1 has price 2, obtaining a segment of length 2 has price 3, obtaining a segment of
length 3 has price 1, etc), an optimal fragmentation is obtained by 2 fragments of length 3 and a
fragment of length 2.
a) Explain your aproach (the steps of your algorithm) and write the used recurrence relation/s.
b) Write the pseudocode for solving the problem.
Problem 2: Apply the memoization technique on the edit distance algorithm. (Write the pseudocode)
Problem 3: Let a1,a2,...,an be an array with real values. Determine a strictly increasing subarray having
the maximum sum of the elements.
Example: s = [3, 1, 6, 2, 8, 10] → solution: [3, 6, 8, 10]
a) Explain your aproach (the steps of your algorithm) and write the used recurrence relation/s.
b) Write the pseudocode for solving the problem.
Problem 4: TSP-Traveling Salesman Problem. Let us consider a set with n cities and a salesman who must
visit all of them, starting with the first city, visiting a city once and coming back to the forst city. Let us
consider the matrix D[1..n, 1..n] in which the element D[i, j] is 0 if there is no direct road between city i
and city j, and if there is a direct road between the cities, the element D[i, j] holds the length of the road.
(i) Generate all the circuits the saleman can cover starting with city 1;
(ii) Determine the shortest circuit.
For both points (i) and (ii), give an explanation of your algorithms.
Project 2: Dynamic Programming and Backtracking
Problem 1: Let us consider a rod that is to be sectioned into fragments of different lengths. Knowing that
each length has a different price, the problem is to determine a way of sectioning the rod with a
minimum price.
Example: For a rod of length 8 for which the fragments prices are p = [2, 3, 1, 4, 6, 5, 6, 5] (obtaining a
segment of length 1 has price 2, obtaining a segment of length 2 has price 3, obtaining a segment of
length 3 has price 1, etc), an optimal fragmentation is obtained by 2 fragments of length 3 and a
fragment of length 2.
a) Explain your aproach (the steps of your algorithm) and write the used recurrence relation/s.
b) Write the pseudocode for solving the problem.
Problem 2: Apply the memoization technique on the edit distance algorithm. (Write the pseudocode)
Problem 3: Let a1,a2,...,an be an array with real values. Determine a strictly increasing subarray having
the maximum sum of the elements.
Example: s = [3, 1, 6, 2, 8, 10] → solution: [3, 6, 8, 10]
a) Explain your aproach (the steps of your algorithm) and write the used recurrence relation/s.
b) Write the pseudocode for solving the problem.
Problem 4: TSP-Traveling Salesman Problem. Let us consider a set with n cities and a salesman who must
visit all of them, starting with the first city, visiting a city once and coming back to the forst city. Let us
consider the matrix D[1..n, 1..n] in which the element D[i, j] is 0 if there is no direct road between city i
and city j, and if there is a direct road between the cities, the element D[i, j] holds the length of the road.
(i) Generate all the circuits the saleman can cover starting with city 1;
(ii) Determine the shortest circuit.
For both points (i) and (ii), give an explanation of your algorithms.