need help with this assignment
Published Version: 3/14/2023 12:10 PM 1 CS 2223 D23 Term. Homework 1 (100 pts.) Homework Instructions • This homework is to be completed individually. If you have any questions as to what constitutes improper behavior, review the examples I have posted online http://web.cs.wpi.edu/~heineman/html/teaching_/cs2223/d23/#policies • The due date for this assignment can be found in Canvas. Late submissions received after the deadline are penalized 25% and can be submitted for up to 48 hours. • Submit your assignments electronically using the canvas site for CS2223. You must submit a single ZIP file that contains all of your code as well as the written answers to the assignment. • All of your Java classes must be defined in a package USERID.hw1 where USERID is your WPI user name (the letters before the @wpi.edu in your email address). You will lose FIVE POINTS (or 5% of your assignment) if you don’t do this. Pay Attention!!! First Steps Your first task is to copy all necessary files from the git repository that you will modify for homework 1. First, make sure you have created a Java Project within your workspace (something like MyCS2223). Be sure to modify the build path so this project will have access to the shared code I provide in the git repository. To do this, select your project and right-click on it to bring up the Properties for the project. Choose the option Java Build Path on the left and click the Projects tab. Now Add… the Algorithms D2023 project to your build path. http://web.cs.wpi.edu/~heineman/html/teaching_/cs2223/d23/#policies Published Version: 3/14/2023 12:10 PM 2 Once done, create the package USERID.hw1 inside this project, which is where you will complete your work. You likely will have packages for each of the homework assignments. Start by copying the following file into your USERID.hw1 package. • hw1.WrittenQuestions.txt → USERID.hw1.WrittenQuestions.txt • Other files will be copied over, as described in each question In this way, I can provide sample code for you to easily modify and submit for your assignment. I will provide a video explanation that goes over this assignment and will post to Canvas. This homework has a total of 100 points. You can earn additional bonus points, but sometimes the extra bonus questions require some extensive work so be sure to complete regular homework first. This homework assesses the following skills: • How to use debugger to inspect information as a program executes • How to implement a stack in a fixed size array (stacks can grow to the right or grow to the left) • How to implement a queue in a fixed size array (queues can grow to the right or grow to the left) • How to use a stack as part of an algorithm • How to work with two-dimensional arrays • How to use Binary Array Search in a number of ways: (a) determine whether an ordered array contains a value; (b) When an ordered array contains duplicate values, determine the location of a (possibly duplicated) value with the lowest index; and determine the location of a (possibly duplicated) value with the highest index This assignment has a total of 100 points (with four potential bonus points) • Q1 has 20 points • Q2 has 30 points and 1 bonus point question • Q3 has 15 points and 1 bonus point question • Q4 has 25 points and 1 bonus point question • Q5 has 10 points and 1 bonus point question All told, you will copy the following files into your USERID.hw1 package: • ComputeRectangle.java • DigitRepresentation.java • EmpiricalEvaluation.java • Evaluate.java • SolveSearch.java • StackConverter.java • Staque.java • Strassen.java • WrittenQuestions.txt Published Version: 3/14/2023 12:10 PM 3 Q1. Stack Experiments (20 pts.) On page 129 of the book there is an implementation of a calculator algorithm using two stacks to evaluate an expression, invented by Dijkstra (one of the most famous designers of algorithms). I have created the algs.hw1.Evaluate class which you should copy into your USERID.hw1 package. Note that all input (as described in the book) must have spaces that cleanly separate all operators and values. Note: If, to an empty stack, you push the value “1”, “2” and then “3”, the state of this stack is represented as [“1”, “2”, “3”] where the top of the stack contains the value “3” on the right, and the bottommost element of the stack, the value “1”, is on the left. An empty stack is represented as []. 1.1. (2 pts.) Run Evaluate on input "( ( 4 + 1 ) / ( ( 8 * 2) / ( 3 - 7 ) ) )" and state the observed output 1.2. (4 pts.) Modify Evaluate to support two new operations: a. Add a new binary operation “n mod m” that computes n % m, where % is the modulo operator. For example, “5 mod 2” is equal to 1 b. Add a new binary operation “n choose k” which computes the binomial coefficient C(n, k). For example, “5 choose 2” is equal to 5!/(3!*2!) = 10. Note that the arguments to choose are first converted to integers before being processed. Thus 5.2912 choose 2.18 first becomes 5 choose 2. 1.3. (2 pts.) Run your modified Evaluate on input "( ( 9 choose 4 ) % 13 )" and state the observed output The following inputs are all improperly formatted, but aren’t you curious what will be output? For each of these questions below, be sure to (a) state the observed output; (b) describe the state of the ops stack when the program completes; (c) describe the state of the vals stack when the program completes. If you set a breakpoint at line 57 in Evaluate you can use the debugger to find the values. 1.4. (3 pts.) Run Evaluate on input "( 2 3 * / 5 )" 1.5. (3 pts.) Run Evaluate on input "( 6 + + 1 )" (there is a space between the plus signs) 1.6. (3 pts.) Run Evaluate on input "- 34" (there is a space between the minus sign and the 76) 1.7. (3 pts.) Run Evaluate on input "( 4 * ( 5 + ( 8 + 9" Write the answers to these questions in the WrittenQuestions.txt text file. For question 1.2, modify your copy of the Evaluate class and be sure to include this revised class in your submission. https://en.wikipedia.org/wiki/Edsger_W._Dijkstra https://en.wikipedia.org/wiki/Binomial_coefficient https://en.wikipedia.org/wiki/Binomial_coefficient Published Version: 3/14/2023 12:10 PM 4 Q2. Searching Programming Exercise (30 pts.) Many algorithms are concerned with searching for values within a given data structure, and this homework assignment is no exception. For this assignment you will be working with 2D arrays of integer values. I have created a helper class TwoDimensionalStorage which you will use to get the value at a given row and column or set a value in a particular row and column. I have done this because it also records the total number of times any value was read. The purpose of this question is to have you design efficient algorithms that try to minimize the number of array entries that are read. Q2.1 Searching Values [15 pts] Consider a Permutation Array, a specially constructed two-dimensional array of integers with R rows and C columns that contains each of the R x C integers from 1 to R x C in a permuted arrangement such that the values in each row appear in ascending order. The following is a sample array: int[][] sample = new int[][] { { 1, 2, 4, 10, 11}, { 6, 7, 12, 13, 15}, { 3, 5, 8, 9, 14}, } Copy the algs.hw1.SolveSearch into your USERID.hw1 package where you will complete the implementation of the following two functions: • int[] less(TwoDimensionalStorage storage, int target) returns the number of integers in each row of the array that are strictly smaller than target. For example, less(sample, 5) produces the one-dimensional array of int[] { 3, 0, 1 } • int contains(TwoDimensionalStorage storage, int value) returns the row that contains value. For example, contains(sample, 5) returns 2 Once you have a working SolveSearch, execute it to confirm that it works on this simple example and a smaller trial of ten (if it fails any of these trials then an error is reported.) Task 2.1 (15 points): Complete implementation of SolveSearch and execute it to reproduce the following table of runs on specific random 8 x 8 arrays (which appears in the output) [2, 3, 8, 4, 7, 7, 8, 6] for 46 [3, 5, 5, 8, 8, 8, 7, 8] for 53 [1, 1, 2, 3, 4, 1, 1, 1] for 15 [7, 6, 4, 4, 4, 4, 0, 8] for 38 [5, 7, 8, 3, 7, 4, 4, 1] for 40 [1, 3, 0, 1, 2, 3, 2, 6] for 19 [5, 5, 3, 2, 4, 6, 3, 6] for 35 [0, 0, 2, 1, 2, 1, 0, 0] for 7 [8, 8, 3, 6, 2, 5, 3, 2] for 38 [5, 8, 5, 2, 8, 7, 7, 7] for 50 It will also produce a leaderboard computation. To get full credit, you need fewer than 1,082,400,000 total inspections. DM to alert me if you outperform the leaderboard champion. Published Version: 3/14/2023 12:10 PM 5 Q2.2 Searching for Rectangles [15 pts] Consider an Embedded Rectangle, a specially constructed two-dimensional array of integers with R rows and C columns where: • Both R and C are odd values • The only values stored in the array are 0 and 1 values • The 1 values form a contiguous r x c rectangle, where r > R/2 and c > C/2; note that r and c may be odd or even • All other values in the array are 0 The following R=5 row, C=7 column array is an example with r=4 and c=5 whose upper-left corner is (startr=1, startc=2): int[][] sample = new int[][] { { 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 1 }, } Copy the algs.hw1.ComputeRectangle class into your USERID.hw1 package and complete the implementation of the search(TwoDimensionalStorage) method. The goal is to devise an algorithm that computes (startr, startc, numRows, numCols) given a specially constructed two-dimensional arrays with an Embedded Rectangle. I have provided the implementation of algs.hw1.fixed.er.SweepFindRectangle, which is a naïve solution you can execute. Your goal is to write code that outperforms this naïve implementation. Task 2.2 [15 points]: Complete implementation of ComputeRectangle and execute it to reproduce the following table of runs on specific random 7 x 15 arrays (which appears in the output): start=(0,0) with 5 rows and 14 columns in 11 start=(1,2) with 4 rows and 9 columns in 10 start=(0,0) with 6 rows and 14 columns in 12 start=(0,1) with 6 rows and 11 columns in 11 start=(1,0) with 5 rows and 9 columns in 11 start=(1,1) with 5 rows and 12 columns in 11 start=(2,0) with 4 rows and 12 columns in 11 start=(1,3) with 5 rows and 10 columns in 11 start=(0,1) with 6 rows and 11 columns in 11 start=(1,2) with 4 rows and 11 columns in 10 It will produce a computation for the leaderboard. I have provided a simple SweepFindRectangle algorithm which requires 2,639,301,797 array inspections. To receive half credit for this assignment, your final leaderboard computed number of inspections must be smaller than 326,000,000. To receive full credit, your total number of inspections must be smaller than 56,000,000. Published Version: 3/14/2023 12:10 PM 6 Q2.2.1 BONUS Searching for Knight’s Path [1