/nDeadline: Friday 10 November 2023 Part 1 Part 2 Total / 60 / 40 / 100 GUIDELINES 1. Your document must be written in LATEX, using the provided LATEX, sources, including the completed cover page. You should submit all your documents in an archive named assign- ment2.zip via Moodle. This archive should contain : — The PDF version of your assignment. - The LATEX, sources required to generate the PDF version of your assignment. — The code for your programs with the appropriate file extensions. 2. Every response must be accompanied by a justification. If this is not the case, a score of 0 will be assigned, regardless of the correctness of the response. 3. Late Submission Policy : Penalty of 2 points out of 100, where m is the number of minutes of delay (equivalent to 10 points for 24 hours). PART 1 - We have a square matrix M, n x n, n ≥ 1, with rows and columns indexed from 0 to n - 1, containing integer values. We want to determine the maximum length of a path that starts at position [0, 0] and reaches either a cell in column n - 1 or a cell in row n - 1. The length of a path is the sum of the encountered elements. The rules are as follows : - The starting point must be the cell [0, 0]. - The next step chooses a neighboring element in the same row, the same column, or diagonally if it exists. For example, if you are at cell [2,3], the next element can be either cell [2,4], [3, 4], or [3,3], assuming that n > 4. - The path ends when either the last row or the last column is reached. The length of the path is the sum of the numbers encountered during the journey. — Here's an example : 1 4 3 -6 5 0 4 2 -3 3 -1 1 The maximum length of a course is 40. Here, there are four courses that give 40 : [0, 0][1, 0][2, 0][3, 0][4, 0][4, 1][4, 2][4, 3][4, 4][5, 5] -1 3 1 9 4 -3 11 2 -10 11 0 -17 9 8 0 1 2 4 [0, 0][1, 0][2, 0][3, 0][4, 0][4, 1][4, 2][5, 2] [0,0][1, 0][2, 0][3, 0][4, 0][4, 1][5, 1] -2 8 8 4 2 5 [0, 0][1, 0][2, 0][3, 0][4, 0][4, 1][5, 2] The naive algorithm involves generating all possible paths, calculating the length of each one, and determining the maximum. It can be shown that the number of possible paths is given by : 2 k=0 (" Fn-1 (n-1) (n-1+k). Here are some values for different values of n to give you an idea of the growth rate. n 5 6 7 321 1683 8989 48639 8 9 1462563 10 11 8097453 45046719 12 (a) (5 points) List all the paths, with their lengths, for the matrix 4 2 -1 0 2 7 -1 5 3 Answer : DO NOT DELETE THIS LINE AND REPLACE THIS PHRASE WITH YOUR ANSWER (b) (15 points) Let ci,j be the maximum length of a path starting from the cell [0, 0]. Establish a recursive scheme for the computation of Ci,j, 0 ≤ i, j < n. Do not forget the base cases and the boundary conditions. Answer : (c) (2 points) Establish the solution (the maximum length of a route) according to the ci,j. Answer : (d) (8 points) Provide the pseudo-code (not code !) of the recursive algorithm that determines the maximum length of a path starting from the cell (0,0) and gives one of the paths of maximum length. Answer : (e) (3 points) Estimate the complexity of your recursive algorithm. You may use the §2 notation but try to have a bound not too far from reality. (An answer like §2(1), Q(logn), or even $2(nk) is not acceptable as it is not close enough). Page 2 Numb 1 3 13 1 2 3 4 63 265729 Answer : (f) (10 points) From the recursive scheme, provide the pseudo-code (not code !) of an algorithm that uses dynamic programming. Answer : (g) (3 points) Give the complexity of your algorithm using dynamic programming. Answer : (h) (8 points) Describe in pseudo-code (not code!) a greedy algorithm to solve the same problem. Explain why it is a greedy algorithm. Answer : (i) (3 points) Give the complexity of your gluttonous algorithm. Answer : (j) (5 points) Does your algorithm always produce a solution ? When it determines a solution, is it optimal ? Answer : PART 2 - You will need to program your three algorithms (recursive, dynamic programming, greedy). You will compare the results obtained with each of the three algorithms and conduct an empirical study of their performance. (a) (20 points) Design a program that will read the matrix M from a file. The first line of the file will contain the value of n ≥ 1. The following lines will contain the rows of the matrix, with elements separated by at least one space. The program must execute your three algorithms with the matrix and provide the maximum length and one of the paths of this maximum length. You must submit a few executions. (b) (20 points) Design a second program that will compare the execution times of your three algorithms for n =1,2,3, 4, .... Here, the answer returned by your algorithms is not impor- tant but the execution time is (the content of the matrices is not important and they will be filled in the program (see later for an example)). Determine what is the value of n from which the execution time is too long (I leave it to you to judge what that means!) for each of your three algorithms. Make graphs for the execution time, as a function of n for each of the three algorithms. Make a link between these graphs and the complexity of each of your algorithms. Discuss the results obtained. Page 3 Your programs should be written in Java, C++, or Python. You must specify the compiler with which your program was compiled and on which platform. You should provide me with the source code. In case of any issues, it is your responsibility to convince me that your code works, and not my responsibility to convince you that your code does not work, if applicable. Voici le code LaTeX pour votre texte en anglais, en respectant l'indentation : "latex Examples of Code 1 1.1 Execution Time Calculation Java long beforeTime; long afterTime; double elapsedTime; beforeTime = System. currentTimeMillis(); / / calculation ... afterTime = System. currentTimeMillis () ; elapsedTime = afterTime - beforeTime; You can also use System. nanoTime () instead of System. currentTimeMillis (). A nanosecond is equal to 10-9 seconds. C++ #include <ctime> #include <iostream> using namespace std; clock_t beforeTime; // time before calculation clock_t afterTime; / / time after calculation double elapsedTime; // time required for calculation beforeTime = clock(); // calculation . . . afterTime = clock() ; elapsedTime = (double) (afterTime - beforeTime) / (double) CLOCKS_PER_SEC; Python from time import time Page 4 beforeTime = time(); // time in milliseconds // calculation ... afterTime = time () ; 1.2 To generate matrices with random content in Java private static Random generator = new Random ( 0 ); // in java.util Returns a random number uniformly distributed between a and b inclusively. * precondition: a <= b (otherwise, the generated numbers will no longer be uniform) * @param a minimum value * @param b maximum value */ private static int random ( int a, int b ) { return (int) Math. floor ( ( b - a + 1 ) * generator.nextDouble () ) + a; } / / random / ** * Generates an n X n square matrix of random integers between inf and sup incl. * @param n: dimension of the matrix * @param inf minimum value of generated numbers * @param sup maximum value of generated numbers */ public static int [] [] randomMatrix ( int n, int inf, int sup ) { int [] [] answer = new int [n] [n] ; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { answer [i] [j] = random ( inf, sup ) ; } } return answer; } 1.3 Example of Speed Tests in Java public static void speedTest ( int n ) { int [] [] matrix = randomMatrix ( n, 0, 9 ); long beforeRec = System.nanoTime () ; // call the method using the recursive algorithm long afterRec = System.nanoTime () ; long beforeDynProg = System.nanoTime () ; // call the method using the dynamic programming algorithm long afterDynProg = System.nanoTime(); Page 5 long beforeGreedy = System.nanoTime () ; // call the method using the greedy algorithm long afterGreedy = System. nanoTime () ; System. out. println ( "n = " + n , + " + (afterRec - beforeRec) /1000.0 (afterDynProg - beforeDynProg) /1000.0 + + " , " + ", " + (afterGreedy - beforeGreedy) /1000.0 ) ; } Page 6