CMPS 200 Homework Assignment 10, Fall 2011

Faculty of Arts & Sciences Department of Computer Science CMPS 200—Introduction to Programming Assignment 10 – Due Mon Dec 12, 2011 Notes and Announcements  Reading material: Section 7.5 Problem 1. Insertion Sort of integers Write an InsertionSort.java program that reads an array of integers from standard input and sorts the array in increasing order using an insertion sort method. Insertion sort works by repeatedly looping through the array: at iteration i, the method should insert the i-th element in a location such that everything to its left is smaller that it, and “pushing” all emenets between the target location and the i- th location to the right. See the Wikipedia entry http://en.wikipedia.org/wiki/Insertion_sort for an illustration. Insertion sort is a famous sorting algorithm that has the property that after k iterations, the first k+1 elements are in sorted order. When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort. Your program should contain the following methods: public static void insertionSort(int[] a) // insertion sort an array in place public static void printArray(int[] a) // prints an array to standard output and a main method that reads from standard input, creates an array of ints, and then calls insertionSort(), and printArray() as needed. (You may assume that the first entry in the input is the number of elements in the array and is followed by the values in the array.) In addition, you should write a method that doesn’t change its argument, but returns a new sorted array public static int[] insertionSort2(int[][] a) Hint: Use the insertionSort() method you wrote above to implement this method. Problem 2. Insertion Sort of Strings Write a program that takes two file names as command line arguments. The program should read the contents of the first file and write its strings in lexicographic order (the dictionary order) in the second file. All capitalized words should appear before the non-capitalized ones. The program has the read the input file twice: the first time to count how many strings it contains, and the second time to build an array of strings. Use the AUB Mission statement file as sample input to test your program. Problem 3. Day of the Year Write a program that reads in the name of a month (3 letter abbreviation) and the day of the month as command line arguments, and prints the number of that day in a non leap year (a number between 1 and 365). Use the following template. public static int dayOfYear (String month, int day) { String[] months = { "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec" }; int[] days = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; // insert code here } Introduction to Programming (CMPS 200) Fall 2011 2 of 3 Problem 4. Transpose Write a program Transpose.java that that reads a 2D array from a file and prints its transpose (rows and columns interchanged) to standard output. Your program should consist of the following methods: // Create and return a 2D array read from standard input public static int[][] readArray(String filename) // Print a 2D array to standard output public static void printArray(int[][] a) // Transposes a 2D array, argument unchanged, new array returned public static int[][] transpose(int[][] a) The input file that your program should read consist of two numbers representing the number of rows (n) and number of columns (m) in the array, followed by nxm integers that represent the entries. For example, consider the file matrix1.txt containing the following: 4 3 12 0 18 -1 2 3 7 8 0 -12 8 1 An invocation of the program using this input file might produce: > java Transpose matrix1.txt 12 -1 7 -12 0 2 8 8 18 3 0 1 Problem 5. Array Operations Write the following methods that operate on 2D arrays. // generate and return an array of doubles with n rows and m columns filled with random numbers from 0 to 1 public static double[][] generate2D(int n, int m) // generate and return an n by m array of doubles filled with random numbers between min and max public static double[][] generate2D(int n, int m, int min, int max) // returns the sum of all the entries of a 2D array public static double sum(double[][] a) // returns the sum of the entries that are in the lower part of the 2D array public static double sumLowerBlock(double[][] a) The lower block of an array consists of the entries whose row numbers are greater than or equal to their column numbers. Write a main() method that calls the methods above to test them. Problem 6. Grid Traversal Suppose you have a grid of NxN cells with one number per cell. Write a program GridTraversal.java that traverses the grid from outside to inside (as shown in Figure 1 below) and list the values of the traversed cells. The program takes the name of an input file as a command line argument and prints its output to standard output. Input Format The input has the following format: N v11, v12, …, v1N v21, v22, …, v2N … vN1, vN2, …, vNN N is the dimension of the grid, and vi,j corresponds to the value in the cell at i, j. Introduction to Programming (CMPS 200) Fall 2011 3 of 3 Output Format Display the values of the cells in their traversal order separated by blanks spaces on the screen. Sample Input file: 4 1, 2, 3, 4 12,13,14,5 11,16,15,6 10, 9, 8,7 Sample Output 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Figure 1. Tranversing a 5x5 grid from outside to inside. Problem 7. Mirror Write a program to read in a W-by-H picture and produce a 2W-by-H picture which concatenates the original W-by-H picture with its mirror image of the W-by-H picture. Use the peppers.jpg image (available on Moodle) to test your program. Problem 8. Pascal’s Triangle Write a program Pascal.java that builds and prints a two-dimensional jagged array a such that a[n][k] contains the coefficient of the k-th term in the binomial expansion of (x + y)n . These coefficients can be organized in a triangle, famously known as Pascal’s triangle. Every row in the triangle may be computed from the previous row by adding adjacent pairs of values together. Your textbook has a description of the algorithm on pages 499-503. Below is a sample invocation of the program. > java Pascal 7 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1