CS314 Assignment 1 CS 314 - Specification 1: Designing and Implementing Algorithms Assignment 1: Individual Assignment. You must complete this assignment on your own. You may not acquire from any source (e.g. another student or an internet site) a partial or complete solution to a problem or project that has been assigned. You may not show another student your solution to the assignment. You may not have another person (current student, former student, tutor, friend, anyone) “walk you through” how to solve an assignment. You may get help from the instructional staff. You may discuss general ideas and approaches with other students but you may not develop or debug code together. Review the class policy on collaboration from the syllabus. Placed online: Thursday, January 6 20 points, ~2% of final grade. Due: no later than 11 pm, Thursday, January 27 General Assignment Requirements The purposes of this assignment are: to learn the assignment guidelines to learn to use the required software tools for the course to review the basics of the Java language to create and implement non-trivial algorithms. NOTE: This is very important. You are NOT to search the web for algorithms or even ideas on how to solve these problems. I know you can use a search engine. What I don't know is if you can design and implement CS1 (first course in programming) level algorithms in Java. Certainly, if you need help, come see the instructional staff in help hours and we will give you suggestions. But, if you cannot design and implement the algorithms on this assignment yourself (with a bit of help from the instructional staff) you might be better suited for CS312. to learn to create basic test cases for the code you write Provided Files: CodeCamp.java contains 6 method shells. CodeCampTester.java contains a main method used for testing. CodeCamp.html is the documentation for the program. Assignment Restrictions: This assignment evaluates your ability to design and implement algorithms using Strings, arrays, and two dimensional arrays. I don't want to know how well you know the Java standard library or how well you can use search engine. Therefore the following restriction apply to this assignment: The only methods and classes from the Java standard library you may use in your final solutions are: methods from the Math class methods from the Random class on the mostVowels question you may use any methods from the String class you can use native arrays including the length field. (You may not use static methods from the Arrays class.) You may NOT use the clone method for arrays. Also, for this assignment, do not look up algorithms on the web or from textbooks. I want YOU to design and implement the algorithms for this assignment. I assume you know how to search the web. What I really need to know is if you can design and implement algorithms. Note: All the methods require that the parameter not be altered in any way. You can, of course, create local copies of the parameters and alter the copy. Getting Help: Start the assignment early in order to get help. Recall, you must complete this assignment on your own. You are not to copy code from other students in the class, current or previous, and you are not to copy code from the web. There are still ways to get help. The instructor and TA help hours The class discussion group on Piazza. You can post general questions. If you have a syntax error you may post the line of code that is given you a syntax error. Do not post more than 2 lines of actual code to Piazza. Use a search engine for syntax errors (not algorithms to solve the given problems). You can copy and paste in the Java syntax errors that you get and find the answers as opposed to emailing and waiting for the reply. Download CodeCamp.java and CodeCampTester.java from the class website. Assignments in CS314: If you took CS312, one difference in programming assignments is you will not always write complete programs. You will often, but not always, be given a partial program and have to complete it. You will do a lot of coding to "spec", that is coding to specification; the program will have already been designed and you must implement it, given the design. You will have to develop algorithms on your own, but the specification of methods are already complete. Many of the methods you write won't ask the user for input or do any output. The "input" to the methods will be via parameters and the "output " will be the return value. Of course you can add user input and output to the methods that call the specified methods to provide a way of interactively testing the methods you write. And you can add temporary output statements to the methods you are writing to assist in debugging issues. Complete the six methods in the program named hammingDistance, isPermutation, mostVowels, sharedBirthdays, queensAreSafe, and getValueOfMostValuablePlot. See the method descriptions below. Note, you are encouraged to add private "helper" methods to remove redundancy and / or provide structure to your solution. Complete the required experiments. Place your experiment code in CodeCamp.java. You may NOT share your experiment code with other students. Add at least 2 tests per method, 12 tests total to CodeCampTester. You may copy the structure of the provided tests, but change the data and expected results. You must write your own test cases to turn in, but you can share test cases on Piazza to help test each others programs. In the version of CodeCampTester.java that you turn in delete the original tests. Tests shall not violate the preconditions of the method. Ensure your two classes are part of the default package. No package statement in your Java classes for CS314.. Fill in the header for CodeCamp.java. Replace with your name. You are stating, on your honor, that you did the assignment on your own, as required and did not share your code with anyone else. If you copy code from someone else or give your code to someone else you will receive an F in the course. Fill in the header at the top of CodeCampTetser.java. Create a zip file name a1.zip [case sensitive! Do not name the file A1.zip!] with your CodeCamp.java and CodeCampTester.java files. The zip file must not contain any directory structure, just the two required files. Turn in a1.zip via your Canvas account to assignment 1. Ensure you are turning in the version of CodeCamp.java that has your completed methods and the version of CodeCampTester.java with your extra tests added and the original tests deleted. You may have more than one version of the files on your system. Do not turn in the .class file; turn in the Java source code. If you turn in the wrong file you will get a zero on the assignment. Ensure you have not imported any non standard java classes. If you have an import that starts with something besides java. or javax. your code will not compile when we test it and you will lose all correctness points. Ensure you files are named CodeCamp.java and CodeCampTester.java. Failure to do so will result in losing all correctness points. Ensure CodeCamp.java and CodeCampTester are part of the default package. Do not add a package statement to the either file. Ensure your zip has no internal directory structure. When the file is unzipped no directories (folders) are created. (Note the built in unzip feature of some versions of Windows and Apple OS X "helps" by adding a directory when you unzip with the same name as the file. The unzip we use on the CS Linux system does not do this. Neither do unzip programs such as 7zip.) Ensure you submit the assignment under Programming Assignment 1 in Canvas. You may turn in the file multiple times via Canvas. Canvas adds a "-1" to the file name. So if you turn in your program a second time before the due date the file name will be something like a1-1.zip. That is fine. Our grading scripts will adjust for the extra cruft Canvas adds to the file name If you want to test your code in that environment please see this handout for help on logging into those machines, moving, compiling, and running your Java programs. Note to SSH into the CS department machines from your own system you must set up an SSH key on your system and in your CS department account. See this page for help with Windows and this page for help with Linux and Macs. Checklist: Did you remember to: review and follow the general assignment requirements? work on the assignment by yourself and complete all the solution code on you own? fill in the headers in your file CodeCamp.java and CodeCampTester.java? (Eclipse and other IDES may compress the comment. Be sure to expand it and fill it in.) implement the six required methods? ensure your program does not suffer a compile error or runtime error? ensure you do not use any disallowed methods from the Java standard library? identify and correct any incorrect tests provided with the assignment? [Note, you delete these tests in the program you turn in, but your code must pass them..] ensure your program passes the tests in the main method of CodeCampTester.java? Note, passing all the provided tests does not mean your solution is correct. We will use other tests not published which test various edge / corner cases. add the required number of test cases to the main method of CodeCampTester.java and delete the original tests? include the result of the required experiments for the sharedBirthdays method? (See the required experiment in the method description below) Include the experiment code itself in CodeCamp.java? turn in your files in a zip named a1.zip with no internal directory structure? turn in your zip named a1.zip to Programming Assignment 1 via Canvas by 11 pm on Thursday, January 27? Method Descriptions: 1. Hamming Distance: "The Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different. Put another way, it measures the number of substitutions required to change one into the other, or the number of errors that transformed one string into the other." From the Wikipedia article on Hamming Distance. For this problem you will be working with arrays of ints instead of String objects. /* Determine the Hamming distance between two arrays of ints. pre: aData != null, bData != null, aData.length == bData.length post: return the Hamming Distance between the two arrays of ints. Neither the parameter aList or bList are altered as a result of this method. */ public static int hammingDistance(int[] aData, int[] bData){ For example given the array {1, 2, 3, 4, 5, 4, 3, 2, 1} and the array {1, 2, 8, 4, 5, 4, 3, 5, 1} the Hamming distance is 2. 2. isPermutation: This method determines if one int array is a permutation of another int array. "A permutation, also called an "arrangement number" or "order " is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself." [mathworld.wolfram.com] For example the list {1, 2} has the following permutations; {1, 2} and {2, 1}. Note the elements of listA and listB are lists, not sets, so duplicate items could appear. So for example given the list {1, 2, 2} the unique permutations are {1, 2, 2}, {2, 1, 2}, and {2, 2, 1}. {2, 1} is not a permutation of {1, 2, 2}., Another example of lists that are not permutations of each other: {2, 1, 1} is not a permutation of {2, 2, 1}. /* Determine if aData is a permutation of bData. pre: aData != null, bData != null post: return true if aData is a permutation of bData, false otherwise. Neither aData or bData are altered as a result of this method. */ public static boolean isPermutation(int[] aData, int[] bData) Hint: Do not try to solve the problem by taking one the arrays and generating all the permutations of that array and then check to see if the other array is one of those permutations. That is too inefficient except for arrays of a trivial length. One of the simplest solutions is to simply check the frequency of each element in the first array and verify the frequency of that value is the same in the second array. If not, return false right away. 3. mostVowels: On method mostVowels you can use any and all parts of the String class and native arrays. The mostVowels methods takes in an array of Strings as a parameter and determines which String has the most vowels. For this method vowels are the characters 'A', 'a', 'E', 'e', 'I', 'i', 'O', 'o', 'U', and 'u'. The method is not trying to determine which String has the largest number of distinct vowels. Thus "aaaaaa" has more vowels that "aeiou". The String "aaaaaa" has 6 vowels while the String "aeiou" only has 5 vowels. You can use whatever String methods you want when completing this method. /* Determine the index of the String that has the largest number of vowels. Vowels are defined as 'A', 'a', 'E', 'e', 'I', 'i', 'O', 'o', 'U', and 'u'. The parameter arrayOfStringsis not altered as a result of this method. pre: arrayOfStrings!= null, arrayOfStrings.length > 0, there is an least 1 non null element in arrayOfStrings post: return the index of the non-null element in arrayOfStringsthat has the largest number of characters that vowels. If there is a tie return the index closest to zero. The empty String, "", has zero vowels. It is possible for the maximum number of vowels to be 0. */ public static int mostVowels(String[] arrayOfStrings) 4. sharedBirthdays: The birthday problem is a question where most people's intuition is proved incorrect by mathematics. The problem is: Given a group of N people, how large must N be so that there is a 50% chance that at least 2 of the N people have the same birthday? Write a method with two parameters, the number of people in a group and the number of days in the year. The method will generate random birthdays for the number of people and then determine how many pairs of people have the same birthday. You don't have to generate actual days of the year for the birthdays. You can simply use ints. Here are two ways to generate random ints in Java. One uses an object of type Random and the other uses the random method from the Math class. // fist approach Random r = new Random(); int max = 10; int x = r.nextInt(max); // x will now hold a value between 0 and 9 inclusive. // The distribution of values in uniform. // second approach int max = 10; int x = (int) (Math.random() * max); // x will now hold a value between 0 and 9 inclusive. // The distribution of values in uniform. If three people (Olivia, Kelly, Isabelle) share the same birthday, that is 3 pairs of people: pair 1: Olivia and Kelly pair 2: Olivia and Isabelle pair 3: Kelly and Isabelle /* Perform an experiment simulating the birthday problem. Pick random birthdays for the given number of people. Return the number of pairs of people that share the same birthday. pre: numPeople > 0, numDaysInYear > 0 post: The number of pairs of people that share a birthday after randomly assigning birthdays. */ public static int sharedBirthdays(int numPeople, int numDaysInYear) { After completing the method run the following experiments: Perform 1,000,000 experiments with 365 days per year and 182 people per experiment . What is the average number of pairs of people with shared birthdays? (Write a method to automate this experiment and put the code in CodeCamp.java.). Include your answer in a comment at the top of your CodeCampTester.java program. How many people do you think it takes so there is a 50% chance that at least 2 of the people have a shared birthday in a 365 day year? Perform 50,000 experiments with 365 days per year and vary the number of people from 2 to 100. 50,000 runs with 365 days, and 2 people, 50,000 runs with 365 days and 3 people, ... 50,000 runs with 365 days and 100 people. Total of 4,950,000 runs, 50,000 runs per experiments * 99 experiments = 4,950,000 runs. For each of the given number of people determine the percentage of experiments where at least one pair of people shared a birthday. At what number of people (between 2 and 100) does the percentage first exceed 50%? Does the answer surprise you? How did it compare to your predicted answer? Include a table in a comment in your CodeCampTester.java program with the results of this experiment using the following format: Num people: 2, number of experiments with one or more shared birthday: 120, percentage: 0.24 ..... Num people: 100, number of experiments with one or more shared birthday: 50000, percentage: 100.00 At the top of the table state how many people it requires to have a 50% chance of there being at least 1 shared birthday, given a 365 day year. Note, in the version of the program you turn in, list your results in a comment, but do not include any code that calls your methods that perform these experiments. 5. queensAreSafe: The eight queens problem is a chess and programming problem with the goal is to place eight queens on a chess board so that none of them may attack any other queen. That is, no two queens are in the same row, column, or diagonal. In chess, a queen may move any number of spaces straight up, down, left, right, or along any of the 4 diagonals. In the method you are completing the board is square (same number of rows as columns) but is not necessarily 8 by 8. Consider the following board: A queen's position is designated with the Q. The red arrows show the squares that queen can attack. Thus if there were a queen in any of those squares this would be an unsafe board. So the following set up is unsafe. The following set up is safe, but the number of other safe squares is going down fast. .. Here is an example with 8 queens that are all safe: Complete the method that checks if a given board represents a safe placement of Queens. Note, the board size may be different that 8 by 8. /* Determine if the queens on the given board are safe. pre: board != null, board.length > 0, board is a square matrix. (In other words all rows in board have board.length columns.), all elements of board == 'q' or '.'. 'q's represent queens, '.'s represent open spaces. post: return true if the configuration of board is safe, that is no queen can attack any other queen on the board. Return false otherwise. The parameter board is not altered as a result of this method. */ public static boolean queensAreSafe(char[][] board) 6. getValueOfMostValuablePlot: Again, do NOT look up solutions or even approaches to this problem on the web. You are to figure out a solution yourself, with help from the instructional staff if needed. There is a video available on the course Canvas page explaining a brute force approach to this problem. For this problem a 2d array of ints represents the value of each block in a city. Each element in the array is a city block. The value of a block could be negative indicating the block is a liability to own. Complete a method that finds the value of the most valuable contiguous sub rectangle in the city represented by the 2d array. The sub rectangle must be at least 1 by 1. (If all the values are negative "the most valuable" rectangle would be the negative value closest to 0.) Note, for this method you may assume the given 2d array of ints will not cause your method to overflow or underflow the Java int data type. Consider the following example. The 2d array of ints has 6 rows and 5 columns per row, representing an area of the city. The cells with the white background represent the most valuable contiguous sub rectangle in the given array. (Value of 15.) 0 -2 -7 0 -1 9 2 -6 2 0 -4 1 -4 1 0 -1 8 0 -2 1 -10 1 1 -5 6 -15 -1 1 5 -4 Here is another example with the almost same 2D array with a single change. The value of the block at row 4, column 2 has been changed from 1 to 6. Given that configuration the most valuable contiguous sub rectangle in the given array has a value of 17 and is the cells with the white background. 0 -2 -7 0 -1 9 2 -6 2 0 -4 1 -4 1 0 -1 8 0 -2 1 -10 6 1 -5 6 -15 -1 1 5 -4 Another example. The whole 2d array is the most valuable sub plot: 3 2 13 7 9 2 0 6 14 1 5 4 Hint: Implement a brute force approach that examines each possible sub matrix independently. The brute force approach is typically O(N6) which is acceptable for this assignment. The brute force approach is still complicated, but use helper methods to break the problem down into smaller, more manageable pieces. /* Given a 2D array of ints return the value of the most valuable contiguous sub rectangle in the 2D array. The sub rectangle must be at lest 1 by 1. pre: mat != null, mat.length > 0, mat[0].length > 0, mat is a rectangular matrix. post: return the value of the most valuable contiguous sub rectangle in city. the 2d array city, is not altered as a result of this method call. */ public static int getValueOfMostValuablePlot(int[][] city){ Expected length of solutions: My solutions to the problems above added about 210 lines to CodeCamp.java. That includes many blank lines, lines with a single brace, and comments. About 140 actual lines of new code in my solution. This does no include the code for the shared birthdays experiments. Your solution can be larger or smaller than this. I only provide the number of lines of code as a guideline.
