The Question is attached in the order files.
The final project submission due on April 24, 2021 and it must be submitted on Canvas. It consists of: · The project report, see below. · The source code. The project report must be typed and it must contain the following sections: Project Title. Student Name. 1. Problem definition: Clearly state your problem, what is given and what the objective is. Define the input size. Identify real-world application(s) of your problem. 2. Algorithms and RT analysis: Write the pseudocode for each algorithm and show the RT analysis. Clearly state the RT for each algorithm. 3. Experimental Results: Specify the programming language used to implement the algorithms. Planning of the experiments: what values did you take for the input size?; how many runs for each input size?; what data structures did you use?; how did you generate the input? Write the results of your experiments. Include graph(s) showing the running time and explain how your empirical results relate to theoretical complexity analysis. Explain/describe your graphs. The graphs/tables cannot be drawn by hand. Use Microsoft Excel, MATLAB, or another tool. 4. Conclusions: What conclusions can you draw from your experiments? Are the theoretical and empirical results consistent? 5. References: Clearly write the references used, such as books, web page links (URL), class notes, etc. Grading · The maximum total is 100 points, consisting of: · Project report: 60 points. · Code: 40 points. Please check the Grading Rubric posted on Canvas. · A penalty of 10 points is applied if the project proposal is not received by the deadline. Topic Selection You can select one of the problems listed below or propose a different problem. · Finding the fake coin (BF, D&C). If you work on this problem, you need to specify in the proposal how you will implement the weighting of two piles of coins in constant time. · Matrix-chain multiplication (CLRS, ch 15) · Majority Element problem (BF, D&C, solution in linear time). All 3 solutions must be implemented for this topic. · Selection problem (CLRS, ch 9) · An activity selection problem (CLRS, ch 16) · Sequence Alignment Problem (KT, ch 6.6, DP and BF) · Weighted Interval Schedule (KT ch 6.1, DP and BF) · Single Source Shortest Paths (CLRS, ch 24) 4/21/2021 Programming Project -- Final Report and Source Code https://canvas.fau.edu/courses/95497/assignments/989478 2/4 Criteria Ratings Pts 5 pts 10 pts 5 pts 5 pts 10 pts Problem Definition 5 pts Excellent The problem definition is clear and concise. It contains all the requirements that are needed to understand what needs to be solved. 3 pts Satisfactory The problem definition is written however it isn't fully clear and concise. Missing certain parts, etc... 0 pts Unsatisfactory Problem Definition is missing from the document. Pseudocode 10 pts Excellent Pseudocode (for all solutions) is written out fully and clearly and easy to understand the solution(s). 7 pts Good Pseudocode is written, however one of the solutions pseudocode is not fully clear. 4 pts Satisfactory Pseudocode is written, however two or more of the solutions pseudocode is not fully clear. 0 pts Unsatisfactory Pseudocode is missing from the document. RT Analysis 5 pts Excellent RT Analysis is clear and concise for all solutions. 3 pts Satisfactory RT Analysis is included in the document, however it isn't clear and/or concise, or may be incorrect. 0 pts Unsatisfactory RT Analysis is missing from the document. Experiment Description 5 pts Excellent The experiment description is clear and concise and contains all the necessary information. Information included such as data structure(s) used, number of runs per trial, input size, etc... 3 pts Satisfactory The experiment description is included, however certain information is missing or isn't clear and/or concise. 0 pts Unsatisfactory The experiment description is not included in the document. Tables for computing C 10 pts Excellent Tables for computing C are included and they contain the correct information. Constant C is computed correctly for all algorithms. 7 pts Good Tables for computing C are included, however they contain incorrect information, or constant C is computed incorrectly. 5 pts Fair One table for computing constant C is missing. 0 pts Unsatisfactory Tables for computing constant C are not included in the document. 4/21/2021 Programming Project -- Final Report and Source Code https://canvas.fau.edu/courses/95497/assignments/989478 3/4 Criteria Ratings Pts 20 pts 5 pts 20 pts 5 pts 5 pts 5 pts RT graphs 20 pts Excellent All required RT graphs are included the final document. They are clear and concise. 15 pts Good A graph is missing or there are errors and inconsistencies. 7 pts Fair Two graphs are missing or there are major errors and inconsistencies. 0 pts Unsatisfactory The graphs are not included in the document. Conclusion and References 5 pts Excellent Conclusion and references are clear and concise. 3 pts Satisfactory Conclusion and references aren't clear and/or concise. Conclusion or References is missing. 0 pts Unsatisfactory Conclusion and References aren't provided in the document. Pseudocode implemented correctly 20 pts Excellent Pseudocode implemented for all algorithms is correct and matches fully. 15 pts Good Implementation has small errors that doesn't match the pseudocode for one algorithm. 10 pts Satisfactory Implementation has errors that doesn't match the pseudocode, or one algorithm not implemented. 5 pts Emerging One algorithm missing and the remaining algorithm has implementation error(s). 0 pts Unsatisfactory Pseudocode was not implemented correctly. Does not match at all or no code was provided to compare. Values Selected 5 pts Excellent Values selected in report match in implementation 3 pts Satisfactory One of the values selected in report doesn't match in implementation 0 pts Unsatisfactory Both values selected in report don't match in implementation. Or no code was submitted. Running Trials 5 pts Excellent Each algorithm does m runs for each input value. 3 pts Satisfactory One algorithm does not do m runs for all input values. 0 pts Unsatisfactory No algorithm does m runs on each input value, or does different number of runs on each input value, or no code was submitted. Compute RT Average 5 pts Excellent Compute the Average RT properly. 3 pts Satisfactory Errors in computing the Average RT. 0 pts Unsatisfactory Average RT was not computed or no code was submitted. 4/21/2021 Programming Project -- Final Report and Source Code https://canvas.fau.edu/courses/95497/assignments/989478 4/4 Total Points: 100 Criteria Ratings Pts 5 pts Implement all Algorithms with exactly same input 5 pts Excellent All algorithms were run on exactly the same input. 0 pts Unsatisfactory Algorithms were run on different input values, or no code was submitted.