CS 112
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.
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
HW4IO.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.
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.
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.
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.