Assignment I: Principles of Algorithm Analysis Objectives The purpose of this assignment is to evaluate your understanding of algorithm analysis. You will be required to compare algorithms empirically (experimentally) as well as theoretically. Prerequisites 1. Each group must consist of 2 individuals (as two different computers are required for experiments) 2. Each group must submit ONE report. 3. Each group must submit ONE cohesive program (one source file or project file). 4. Any programming language can be used but choose only ONE (Java, Python, C++). 5. You can use codes from online sources, but they must be cited. Instructions 1. Identify or write two algorithms that are at least of order (one of each): a. O(n) must have at least two for loops b. O(n) 2. These algorithms must have a purpose or solves a simple problem (not just printing out hello world). 3. Provide a brief introduction to both algorithms aided by pseudocodes. 4. You will require two computers or laptops to run experiments, preferably with different computing capabilities (one weak and one powerful, specify in report). 5. You are required to perform two experiments, the first will compare both algorithms based on runtime whereas the second will compare both algorithms based on the number of primitive operations. (Details in the following page) 6. You are required to discuss the results of each experiment, taking note of the following: a. The different growth rates of each algorithm. b. Effect of different hardware on the analyses. c. Time complexity, f(n) in terms of the number of inputs n. 7. Finally, perform a comparison of Experiment 1 and Experiment 2. Experiment 1: 1. Measure the runtime (in seconds) of both algorithms for n = {1,10,100,1000,10000,100000,1000000} on two different computers. 2. Compare and discuss the results aided by graphs. Experiment 2: 1. Insert counters at appropriate locations in the program to count the primitive operations. These operations include: a. Variable assignment b. Function calls c. Arithmetic operations (addition, subtraction, multiplication) d. Variable comparison e. Indexing into an array (reading an array) f. Return calls from a function 2. Run both algorithms for n = {1,10,100,1000,10000,100000,1000000} on two different computers. 3. Compare and discuss the results aided by graphs. 4. Analyse the time complexity of both algorithms. *Note that if your algorithms take too long to run on n = 100000 or larger, you may choose other sizes of n. But please justify your choices. Report Specifications There is no specific format for the report but it MUST contain the following information: a. Font: Times New Roman (10), Single-Spacing (1.0) b. Cover Page indicating division of tasks c. Pseudocodes of both algorithms, not source code. d. Results: a. Screenshots b. Graphs c. Discussions e. Maximum number of pages: 15 pages excluding front page, references and appendices (You will be penalized 1% for each additional page) Rubric (100%) - L02/PO2 Category Weak Average Good Algorithm Selection The algorithms that were Correctly identified at least Correctly identified selected did not fulfil one algorithm of order algorithms of order O(n) neither O(n) nor O(n). 0(n) or O(n) and O(n) (0-2%) (3-5%) (6-10%) Algorithm Description Pseudocode and description The basic idea of the Pseudocode is easy to indicate a lack of algorithms are apparent in understand and in-depth understanding of the the pseudocode and description available algorithms description (6-10%) (0-2%) (3-5% Experiment 1 Program produces wrong Program is functioning. Program is functioning. (Implementation) results or has errors. (6-10%) producing accurate results. (0-5%) (11-15% Experiment 1 (Discussion) Discussion indicates a lack Discussion indicates a basic Discussion provides of understanding of the of understanding of the valuable insights based on experimental results. experimental results. the experimental results. (0-5%) (6-10%) (11-15% Experiment 2 Program produces wrong Program is functioning. Program is functioning. (Implementation) results or has errors. (6-10%) producing accurate results. (0-5%) (11-15% Experiment 2 (Discussion) Discussion indicates a lack Discussion indicates a basic Discussion provides of understanding of the of understanding of the valuable insights based on experimental results. experimental results. the experimental results. (0-5%) (6-10%) (11-15%) Comparison of Discussion indicates a lack Discussion indicates a basic Discussion provides Experimental Methods of understanding of the of understanding of the valuable insights based on experiments. experiments the experiments. (0-2%) (3-5%) (6-10%) Overall Report (Group) Badly written and Reasonable language and Well-written and structured structured structure (-10%) (0-2%) (3-5%)