Problem statement:
You are given an array of integers ‘arr’ of length n. Your task is to find the length of the longest increasing subsequence (LIS) of arr. A subsequence of an array is obtained by deleting some (or none) of the elements from the array, without changing the order of the remaining elements. For example, [1, 3, 5] is a subsequence of [1, 5, 2, 3, 4, 6, 5]. An increasing subsequence of an array is a subsequence in which the elements are in strictly increasing order. For example, [1, 3, 5] is an increasing subsequence of [1, 5, 2, 5, 3, 4, 5, 5], but [5, 3] and [5, 5] are not. Your task is to write a Python program that uses divide and conquer and dynamic programming to solve this problem.
Assignment tasks:
Write a function lis_rec(arr) that outputs the length of the longest increasing sequence and the actual longest increasing sequence. This function should use divide and conquer strategy to the solve the problem, by using an auxiliary function that is recursive. For example, one possibility is to define a recursive function, lis_rec(arr, i, prev), that takes the array arr, an index i, and the previous element index prev of LIS (which is part of the array arr before index i), and returns the length of the LIS that can be obtained by considering the subarray arr[i:]. Write a dynamic programming version of the function, lis_dp(arr), that outputs the length of the longest increasing sequence and the actual longest increasing sequence by using a table to store the results of subproblems in a bottom-up manner. Test the performance of the two functions on arrays of length n = 100, 500, 1000, 5000, 10000. Compare the running times and memory usage of the two functions.
Brief Report Writing:
Methodology: Describe the algorithms used to solve the problem and the experimental setup used to test their performance. Results: Present the running times and memory usage of the algorithms for different array lengths. Use tables and graphs to visualize the results. Discuss the performance of the algorithms.
INPUT: Your program is to read input from in.txt. The first line contains one integer N: the size of the array. The following line is the array of numbers. For example, one possible input can be:
7
1 5 2 3 4 6 5
OUTPUT: Your program is to write length of the longest increasing sequence in the first line, followed by the actual sequence to out.txt. For example, for the above input, the output must be:
5
1 2 3 4 5
You must use Python 3 or higher to implement your algorithms. Explicitly document the recurrence you use (the basis for recursive definition of a function), the corresponding iterative pseudocode (using dynamic programming strategy), and the asymptotic time complexity of the two algorithms as comments.
You must name the input file, the output file, and the well-documented Python script as follows: in.txt, out.txt, and assignment3.py respectively. You must execute your application through the terminal using the following syntax:
• python3 assignment3.py in.txt.
Make sure that your Python program receives only one argument, the input file, from the command line and generates the output file in the current working directory. Note: our grading script, will look inside of only your current working directory for the appropriate output file and not any subdirectories. Below is one way you can handle your input and output files in your application.
import sys
with open(sys.argv[1], "r") as file:
//Do Something
with open("out.txt", "w") as file:
//Do Something
Caution:
Points will be deducted if you do not follow these naming conventions, file extensions, or if your program does not run in the terminal/command line. Use/monitor discord to seek clarifications and for updates. If there are several small changes due to these discussions, I may email an updated assignment consolidating all the changes.
Visualizing Analysis: Run your algorithms on datasets of different sizes and graph the average time required to execute your code as a function of N, to shed light on the asymptotic time complexity. Name the files:
graphRecur.pdf and graphDP.pdf. Clearly label the x-axis and the y-axis and
what they stand for. You are to design and implement a strategy for this analysis
so that we can contrast the two algorithms.
For further Please Contact at: +91-995 314 1035
Solution Includes: Plagiarism and AI report with 100% Accuracy.
Comments