CS 112 Fall, 2017{ Homework Four
Due October 25th at 11:59pm using gSubmit
No late assignments will be accepted.
0 PartA
For each function f from the following list of functions, determine which g makes f(n) is O(g(n)) true1 The point of representing a function in this form is to create the simplest possible function g(n), e.g., do not include a coe cient in g(n), since it does not matter. Represent your answer as an equality (e.g., p(n) = O(n2)). To be clear, the correct answer to the rst function is shown. Write your solutions in a text le hw4.txt.
1. (a) a(n) = 8n + 3 = O(n)
(b) b(n) = 12n + n2 + 64
(c) c(n) = 2log(n) + n
(d) d(n) = log(n) + 2 p
(e) e(n) = 2n
2. Using O(::::) notation, determine the number of times the count() function is called when the following code fragment runs, in terms of the variable n.
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
for (int k = 0; k < j; k++) count();
Include a short explanation of your answer by explaining how many times each loop iterates.
3. Using O(::::) notation, determine the number of times the count() function is called when the following code fragment runs, in terms of the variable n.
for (int i = n; i > 0; i /= 2) for (int j = 0; j < n; j++)
for (int k = 0; k < 1000; k++) count();
Include a short explanation of your answer by explaining how many times each loop iterates.
In lecture using Wolfram Alpha, we saw that f(n) is O(g(n)) when:
f(n) C g(n) k > n
where C and k are some constants.
1
4. Perform this code for insertion sort on the following input array, showing the array after every swap. public static void insertion(int[] arr) {
for (int i = 1; i < arr.length; i++) { for (int j = i; j > 0; j–) {
if (arr[j] < arr[j – 1]) swap(arr, j, j – 1); // show array here
}
}
}
Execute the algorithm on the following input:
+——————-+ | 3 | 5 | 8 | 2 | 1 | +——————-+
5. Perform selection sort on the following input array, showing the array after each swap.
public static void selection(int[] arr) { int k;
for (int i = 0; i < arr.length; i++) { k = i;
for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[k])
k = j;
}
swap(arr, i, k); // show array here
}
}
Execute the algorithm on the following input:
+——————-+ | 9 | 6 | 4 | 2 | 3 | +——————-+
6. Now perform merge sort on the following input array, showing each subarray after it is merged with another subarray (you will sort all sublists of size 1, then of size 2, and nally of size 4).
+——————————-+ | 9 | 5 | 3 | 2 | 1 | 8 | 7 | 4 | +——————————-+
0 PartB
We have provided you on Blackboard the following Java les for PartB of this assignment:
FindSpacing.java
FindSpacingDriver.java
WordGame.java
WordGameDriver.java
You are required to write code only in FindSpacing.java, HW4IO.java and WordGame.java. The le HW4IO.java is used by Word Game and Find Spacing. Inside your Eclipse, you must have the following arrangement of les inside your hw4 package before writing any code:
Figure 1: Arrangement of hw4 les inside hw4 package
2.1 Word Game
We provide you with code for implementing the following game: given a rectangle of letters, nd all dictionary words that consist of consecutive letters on the board (up-down, down-up, left-right, or right-left). We provide a dictionary le (999 most common American English words) and a sample input, as dictionary.txt and board.txt les. We also provide a correct output for this input as example-output.txt le. Implement the code according to instructions. Don't neglect to answer one question in the comments of the code. Your submitted code should not have any new or modi ed print statements (they are useful for debugging, but remove them once you are done). You can change WordGameDriver however you want (including adding print statements); we won't grade it.
If you are feeling ambitious, you can download other dictionaries { for example, the huge (178,690 words) https://www.wordgamedictionary.com/twl06/download/twl06.txt used for Scrabble. That way your program will nd more words. However, please don't submit huge dictionaries with your assignment.
Note: We have provided you with lots of comments in the code to help you get started. All methods that have a TODO as part of comments, are methods that you MUST complete. Do not change the method signature or the name of the class in any way. This will break our tests and will result in you getting 0 for this question.
2.2 Find Spacing
Many writing systems do not put a space between words (which makes translating ancient texts|such as the Bible|even more challenging). Your job is to implement a method that takes a string of letters and breaks it up into dictionary words in all possible ways. We will reuse the dictionary le of 999 most common American English words. Again, if you are feeling ambitious, you can download other dictionaries { for example, the huge (178,690 words) https://www.wordgamedictionary.com/twl06/download/twl06.txt used for Scrabble, which will make playing with your program more fun.
Note: We have provided you with lots of comments in the code to help you get started. All methods that have a TODO as part of comments, are methods that you MUST complete. Do not change the method signature or the name of the class in any way. This will break our tests and will result in you getting 0 for this question.
0 Submission Checklist2
Similar to your previous assignments, you will create a new package hw4 in Eclipse. Inside this package, all your Java les will reside. You will only submit the package hw4 to us. This package must contain the following les only.
hw4.txt
FindSpacing.java HW4IO.java
WordGame.java
The rst line in every Java le must be package hw4;
Be sure to do the following:
You have read the Java Style Guide for CS112 (linked on BlackBoard), and followed all guidelines regarding format, layout, spaces, blank lines, and comments;
You have removed or changed all comments inherited from my templates which do not relate to your solution;
You have veri ed that your program satisfy all the performance tests in the templates.
You can con rm that your assignment has been correctly3 submitted by typing this out: gsubmit cs112 -ls
You can add as many helper methods (these must all be private), however, YOU CANNOT CHANGE
THE METHOD NAMES OR CHANGE THE SIGNATURE OF THE REQUIRED METHODS IN THIS
ASSIGNMENT. THIS WILL BREAK OUR TESTS AND YOU WILL RECEIVE ZERO.
2If you deviate from these instructions, we will penalize you 30% on the entire assignment. No late work will be accepted. If you are still not familiar with gSubmit, please stop by our o ce hours and we can help you with this.
3You can read more about the gsubmit command by typing man gsubmit on the linux machines at BU
