## Description

# 1 Submission Instructions

Note that for each homework assignment, only some of the exercises will be graded. A list of the exercises that will be graded can be found in the Homework Assignment 3 submission link in Blackboard (BB). This does not mean that the ungraded exercise are unimportant or that you will not be tested on the material in the exercise. They are, and you will. There are two primary reasons we grade only some of the exercises: first, this course has a large enrollment so there are many assignments to be graded; second, in the accelerated time frame for online courses, we want to return graded homework exercises as quickly as we can. Despite not grading some exercises, if you wish to perform as well as you can in this course, we strongly recommend that you complete all of the exercises.

Some of your solutions will be typed in a PDF document (the penalty for submitting a document in any format other than PDF will be 10% or -2.5 pts if the grader can open it; if the file cannot be opened, scores of 0 will be assigned to the solutions that are to be included in the PDF).

To start, create a document using your favorite word processor and type your exercise solutions—except for those exercises where you are asked to submit your solution in a separate file. At the top of the document please include your name, your ASURITE ID (the username you use to login to MyASU and BB), your email address, and the homework assignment number, e.g. Homework 3.

For the **short-answer **and **description **exercises (e.g., see Exs. 4.3, 5.1, 5.5, 6.4), please neatly type your solution in your document.

If an exercise asks you to write Java code **but does not request you submit your solution** in a separate Java source code file, then copy-and-paste your code from your IDE or text editor into your word processing document. Make sure to neatly format your code, i.e., properly indent your code and use consistent indentation.

For an exercise which asks you to write a Java method, please see §1.1 below for instructions on what to submit. We will employ an automated grading script to grade these exercises, so it is extremely important that you follow the exercise instructions—especially in regard to naming of things such as filenames, classnames, etc.—so your submission will not cause the script to fail resulting in point deductions.

When you are done, convert the word processing document into **Adobe PDF format** and name the PDF file *asuriteidh03.pdf* where *asuriteid *is your ASURITE user id (for example, if your ASURITE user id is *jsmith6 *then your file would be named *jsmith6-h03.pdf*).

Next, create an empty folder named *asuriteid-h03* where *asuriteid* is your ASURITE user id and and copy *asuriteidh03.pdf* to that folder. Copy any requested Java source code files to the *asuriteid-h03* folder. You do not need to submit any other files, e.g., do not submit *.class *files or data files.

Finally, compress the *asuriteid-h03 *folder creating a **zip archive** file named *asuriteid-h03.zip*. Upload *asuriteid-h03.zip* to the Homework Assignment 3 submission link by the assignment deadline. Please see the *Course Schedule* section in BB or in the Syllabus for the deadline. Consult the Syllabus for the late and academic integrity policies.

**1.1**_{ }**Submitting Java Source Code Files Containing Methods. **Several exercises ask you to submit a Java file containing just methods that solves the problem (not a complete runnable program containing a *main*() method). We want you to write the requested method within a class declaration (i.e., in a *.java* file) named as requested in the exercise. Remember that Java is case-sensitive so your filenames, method names, variable names, etc. must be named exactly as requested in the homework document. Failure to do this may cause you to lose points on an exercise. For example, here is what we want you to submit for Ex. 3.1, where you will write the method *int sum1toN*(*int n*) to solve the problem:

// CLASS: H03_31

// AUTHOR: your name, your ASURITE username, your email address // Import any required classes…

public class **H03_31** { // Remember that class name and filename have to be the same. Case matters.

public **H03_31**() { // Provide a default constructor. Some exercises may require other ctors.

}

// This is the method you are asked to write for Ex. 3.1. Name it exactly as requested so our testing driver

// can call it.

int **sum1toN**(int n) {

// Check for the base case of ** n** = 1 and return 1 when it is detected (the sum of 1 to 1 is 1).

// Otherwise, call the method recursively to calculate ** sum1toN**(

**– 1).**

*n*// Add ** n** to the return value from

**(**

*sum1toN***– 1) and return the sum.**

*n*} }

The CLASS: and AUTHOR: comment lines must be included. All other comment lines are optional but we strongly encourage you to comment your code. In some situations, well-written comments may help us assign partial credit. Note that your instructor indents using 4 spaces. It does not matter to us how many spaces you indent but please configure your editor to insert spaces and not hard tabs when you hit the Tab key. Be sure for each exercise that you import any required classes so that your class will build. It is preferable to import just the one class that may be needed from a package, e.g., import java.util.ArrayList; rather than writing import java.util.*; Given your class, we will write a driver routine that instantiates an object of your class and then calls *sum1toN*() on that object to test your solution. Do not provide a *main*() method or driver routine in your class: for testing on your end, write your own *main*() method and drivers in a class separate from *H03_31*. For these exercises, you do not need to copy-and-paste your code into the word processing document but **the .java files must be included in your zip archive **or otherwise we will be unable to compile your code and you may be assigned a score of zero.

# 2 Learning Objectives

- To apply recursion solutions to solve problems.
- To use the linear search and binary search algorithms to search a list for a key.
- To analyze an algorithm to determine the asymptotic time complexity.
- To determine the order of growth of a function and express it in Big O notation.
- To implement sorting algorithms to sort a list of elements.
- To analyze the time complexity of sorting algorithms.

# 3 Recursion

**3.1 **Learning Objective: To write a recursive method.

Instructions: See the instructions in §1.1 for what to submit for grading. This is not a complete program. Name your class *H03_31* and save it in a file named *H03_31.java*. When you are done, copy *H03_31.java* to your *asuriteid-h03 *folder, i.e., to the same folder as the PDF.

Problem: The sum of the first *n* positive integers, *n* 1, is:≥

*n*

*sum*(*n*) = ∑ *i*

*i*=1

and can easily be computed using a for loop:

public int sum1toN(int n) { // You may assume ** n** 1≥ int sum = 0;

for (int i = 1; i <= n; ++i) { sum += i;

}

return sum;

}

It is also possible to recursively compute the sum by recognizing that *sum*(*n*) = *n* + *sum*(*n* – 1). For this exercise, write a recursive version of int sum1toN(int n).

Testing: We will be testing your method using our driver routine. For testing on your end, write your own driver routine in a class different than *H03_31*.

**3.2 **Learning Objective: To write a recursive method.

Instructions: See the instructions in §1.1 for what to submit for grading. This is not a complete program. Name your class *H03_32* and save it in a file named *H03_32.java*. When you are done, copy *H03_32.java* to your *asuriteid-h03 *folder, i.e., to the same folder as the PDF.

Problem: Write a recursive method double power(double x, int n) that computes and returns *x** ^{n}* where

*n*≥ 0. Hint: remember from algebra that

*x*

*=*

^{n}*x*·

*x*

^{n}^{-1}, and

*x*

^{0}= 1.

Testing: We will be testing your method using our driver routine. For testing on your end, write your own driver routine in a class different than *H03_32*. We will not call your method with a negative value for *n*.

**3.3 **Learning Objective: To write a recursive method.

Instructions: Name your class *H03_33* and save it in a file named *H03_33.java*. This question is not graded so write your own driver routine in *H03_33.java *(e.g., in the *main*() method) which calls and tests your method for *x *= 1, 2, 3 and for each value of *x*, *n* = 0, 1, 2, …, 10. You do not need to submit *H03_33.java*.

Problem: Write a recursive method double powerFaster(double x, int n) that computes and returns *x** ^{n}*. In this method, when

*n*is odd, use the same technique you used in Ex. 3.2 to compute

*x*

*. However, when*

^{n}*n*is even, have the method return (

*x*

^{n}^{/2})

^{2}.

**3.4 **Learning Objective: To compare the time for *power*() and *powerFaster*() to calculate *x** ^{n}.* To determine why in some cases

*powerFaster*() is faster than

*power*(). To understand that the time complexity of a solution to a problem can vary depending on the algorithm that is employed.

Instructions: Modify *H03_33.java* by copying the *power*() method from *H03_32* to the *H03_33* class. This question is not graded so you do not need to submit *H03_33.java*.

Problem: Within the *H03_33 *class, declare two private int instance variables named *calls* and *callsFaster*. Modify the driver routine your wrote for Ex. 3.3 to call both *power*() and *powerFaster*() to calculate *x** ^{n}* for

*x*= 1, 2, 3, and for each value of

*x*,

*n*= 0, 1, 2, …, 10. Next, within

*power*(), write a statement as the first statement in the method which increments

*calls*, before you check the base case. Within

*powerFaster*(), write a statement as the first statement in the method which increments

*callsFaster*, before you check the base case. After each method returns the computed power

*x*

*back to the driver routine, print the values of*

^{n}*calls*and

*callsFaster*(I hope you have figured out that

*calls*and

*callsFaster*are counting the number of times each method is called during the computation of

*x*

*).*

^{n}Explain why the number of calls to *powerFaster*() is fewer than the number of calls to *power*() in some cases.

**3.5 **Learning Objective: To write a recursive method.

Instructions: See the instructions in §1.1 for what to submit for grading. This is not a complete program. Name your class *H03_35* and save it in a file named *H03_35.java*. When you are done, copy *H03_35.java* to your *asuriteid-h03 *folder, i.e., to the same folder as the PDF.

Problem: Write a recursive method String reverse(String s) that returns the reverse of *s*. For example, if *s* is “Hello world” then the method shall return “dlrow olleH”. Hint: The base case occurs when the length of your string is 1. Otherwise, remove the first character *c* at index 0 of *s* forming a substring *t* which consists of the characters of *s *at indices 1, 2, 3, …, *s*.*length*() – 1. Then, concatenate the reverse of *t* and *c* and return this new string. Note that the reverse of the empty string “” is the empty string.

Testing: We will be testing your method using our driver routine. For testing on your end, write your own driver routine in a class different than *H03_35*.

# 4 Linear and Binary Search

**4.1 **Learning Objective: To write a recursive method which searches a list for a key element.

Instructions: See the instructions in §1.1 for what to submit for grading. This is not a complete program. Name your class *H03_41* and save it in a file named *H03_41.java*. When you are done, copy *H03_41.java* to your *asuriteid-h03 *folder, i.e., to the same folder as the PDF.

Problem: We discussed in the lectures how to write a linear search algorithm using a for loop which iterates over each element of a list. Linear search can also be implemented recursively. For this exercise, write a recursive method int recLinearSearch(ArrayList<String> pList, String pKey, int pBeginIdx, int pEndIdx) that searches *pList *elements *pBeginIdx* up to and including *pEndIdx* for *pKey *and returns the index of *pKey* in *pList* if found or -1 if not found.

Hint: The base case is reached when *pBeginIdx* is greater than *pEndIdx* (what does this mean?). Otherwise, check to see if the element at *pBeginIdx* is equal to *pKey*. If it is, then return *pBeginIdx. *If it is not, then make a recursive method call which will search *pList* at elements *pBeginIdx* + 1 to *pEndIdx*.

Testing: We will be testing your method using our driver routine. For testing on your end, write your own driver routine in a class different than *Hw4_41*. For testing, your method will be called in this manner to search the entire list:

ArrayList<String> list = new ArrayList<>(); // we will populate list with several Strings…

int idx = recLinearSearch(list, “the key”, 0, list.size() – 1); Note that if *list* is empty, the method should return -1.

**4.2 **Learning Objective: For the student to demonstrate that he or she understands how the recursive binary search algorithm works.

Instructions: This question is not graded, but if you wish, you may include your solution in your word processing document.

Problem: Suppose *list* is an *ArrayList *of *Integer*s and contains these elements (note that *list* is sorted in ascending order); ** list** = { 2, 3, 5, 10, 16, 24, 32, 48, 96, 120, 240, 360, 800, 1600 }

and we call the recursive binary search method, discussed in the lecture notes:

int index = recursiveBinarySearch(list, 10, 0, list.size() – 1);

where 10 is the key, 0 is the index of the first element in the range of *list* that we are searching (this becomes *pLow*), and *list.size*() – 1 is the index of the last element in the range of *list* that we are searching (this becomes *pHigh*).

Trace the method by hand and show the following: (1) The values of *pLow* and *pHigh* on entry to each method call;

(2) The value of *pMiddle* that is computed; (3) State which clause of the if-elseif-elseif statement will be executed,

i.e., specify if return middle; will be executed, or if return recursiveBinarySearch(pList, pKey, pLow, middle – 1); will be executed, or if return recursiveBinarySearch(pList, pKey, middle + 1, pHigh); will be executed; (4) After the method returns, specify the value assigned to *index* and the total number of times that *recursiveBinarySearch*() was called, including the original call shown above.

**4.3 **Repeat Exercise 4.2 but this time let *pKey* be 150. This exercise is graded, so include your trace in the word processing document.

# 5 Analysis of Algorithms and Big O Notation

**5.1 **Learning Objective: To demonstrate that the student understands the definition of Big *O*. To demonstrate that the student knows how to use the definition of Big *O *to formally determine the asymptotic time complexity of a specific function.

Instructions: This exercise is graded, so include your solution in your word processing document.

Problem: Using the formal definition of Big *O*, prove mathematically that *f*(*n*) = 2.5*n *+ 4 is *O*(*n*). Hint: you must choose values for *C* and *n*_{0} and a function *g*(*n*), such that the criteria in definition are satisfied.

**5.2 **Learning Objective: To demonstrate that the student understands the definition of Big *O*. To demonstrate that the student knows how to use the definition of Big *O *to formally determine the asymptotic time complexity of a specific function. To demonstrate that the student understands that when *f*(*n*) is a constant, no matter how large, the time complexity is *O*(1).

Instructions: This exercise is not graded, so you do not need to include your solution in your word processing document.

Problem: Using the formal definition of Big O, prove mathematically that *f*(*n*) = -4 × 10^{600,000} is O(1). Hint: you must determine values for *C* and *n*_{0} and a function *g*(*n*), such that the criteria in definition are satisfied.

**5.3 **Learning Objective: To demonstrate that the student understands the definition of Big O. To demonstrate that the student understands that if a function *f*(*n*) is *O*(*log*_{a}* n*) then that same function is also *O*(*log*_{b}* n*), where *a* and *b* are constants. That is, different bases for the logarithm function do not change the time complexity.

Instructions: This exercise is not graded, so you do not need to include your solution in your word processing document.

Problem: An important concept to know regarding Big *O *notation is that for logarithmic complexity, the base is irrelevant. In other words, if *f*(*n*) is a function that counts the number of times the key operation is performed as a function of *n* and *f*(*n*) is *O*(*log*_{a}* n*) then it it also true that *f*(*n*) is *O*(*log*_{b}* n*). For example, binary search—which is usually stated as being *O*(*lg n*)—is also *O*(*ln n*), *O*(*log*_{10}* n*), and *O*(*log*_{3.14159265}* n*). Using the formal definition of Big *O*, prove mathematically that if *f*(*n*) is *O*(*log*_{a}* n*) then *f*(*n*) is also *O*(*log*_{b}* n*).

Hint: First, show that *log*_{a} *n* = (*log*_{a} b)(*log*_{b}* n*). Note that (*log*_{a} b) is a constant. Next, since we are trying to show that *f*(*n*) = *log*_{a} *n* is *log*_{b} *n*, note that you already showed that *log*_{a} *n* = (*log*_{a} b)(*log*_{b}* n*).

**5.4 **Learning Objective: To demonstrate the student can identify the key operation when finding the asymptotic time complexity of an algorithm.

Instructions: This exercise is not graded, so you do not need to include your solution in your word processing document.

Problem: Consider this *split*() method where: *pList* is an *ArrayList* of *Integer*s containing zero or more elements; *pEvenList* is an empty *ArrayList *of *Integer*s; and *pOddList* is an empty *ArrayList *of *Integer*s. On return, *pEvenList *will contain the even *Integer*s of *pList* and *pOddList* will contain the odd *Integer*s.

void split(ArrayList<Integer> pList, ArrayList<Integer> pEvenList, ArrayList<Integer> pOddList) { for (int n : pList) { if (n % 2 == 0) pEvenList.add(n); else pOddList.add(n);

}

}

To analyze the worst case time complexity of an algorithm we first identify the “key operation” and then derive a function which counts how many times the key operation is performed as a function of the size of the input. What is the key operation in this algorithm? Explain.

Hint: One way to determine the key operation is to identify the operation which will be performed the most number of times during the execution of algorithm. Also, the key operation is generally an operation that is at the heart of the algorithm. For example, in the iterative linear search algorithm, the key operation is the comparison of *pKey* to the element in *pList* that is currently being examined because in order to find *pKey* we compare each element in *pList* to *pKey*. That comparison will be performed the most number of times during the execution of the algorithm and the entire point of the algorithm is to find the key, so comparing the current element to *pKey* is at the heart of the algorithm.

**5.5 **Learning Objective: To demonstrate that the student understands the definition of Big *O*. To demonstrate that the student understands how to derive the function *f*(*n*) which computes how many times the key operation of an algorithm is performed as a function of the size of the problem.

Instructions: This exercise is graded, so include your solution in your word processing document.

Problem: Continuing with the previous exercise, derive a function *f*(*n*) which equates to the number of times the key operation is performed as a function of *n,* where *n* is the size of *pList*. State the worst case time complexity of *split*() in Big *O *notation. You do not need to formally prove it but explain your answer.

**5.6 **Learning Objective: To demonstrate that the student understands the definition of Big *O*. To demonstrate the student can analyze the time complexity of an algorithm.

Problem: Would the time complexity of *split*() change if the elements of *pList* were sorted into ascending order? Explain.

**5.7 **Learning Objective: To demonstrate that the student understands how the binary search algorithm works and to implement an algorithm that is similar to binary search.

Instructions: See the instructions in §1.1 for what to submit for grading. This is not a complete program. Name your class *H03_57* and save it in a file named *H03_57.java*. When you are done, copy *H03_57.java* to your *asuriteid-h03 *folder, i.e., to the same folder as the PDF.

Problem: Binary search is such an efficient searching algorithm because during each pass of the loop (in the iterative version) or in each method call (in the recursive version) the size of the list is essentially halved. An algorithm which repeatedly divides the problem size by two each time will have *O*(*lg* *n*) performance. If reducing the size of the list to be searched by two is so efficient, it may seem that dividing the problem size by three each time would be even faster. To that end, consider this iterative ternary (ternary is base three) search method. Rewrite it is as a recursive ternary search method named int recTernarySearch(ArrayList<Integer> pList, Integer pKey, int pLow, int pHigh).

int ternarySearch(ArrayList<Integer> pList, Integer pKey) { int low = 0, high = pList.size() – 1; while (low <= high) { int range = high – low;

int oneThirdIdx = (int)Math.round(low + range / 3.0);

int twoThirdIdx = (int)Math.round(low + range / 1.3333333333333333); if (pKey.equals(pList.get(oneThirdIdx))) { return oneThirdIdx;

} else if (pKey.equals(pList.get(twoThirdIdx))) { return twoThirdIdx;

} else if (pKey < pList.get(oneThirdIdx)) { high = oneThirdIdx – 1;

} else if (pKey > pList.get(twoThirdIdx)) { low = twoThirdIdx + 1;

} else { low = oneThirdIdx + 1; high = twoThirdIdx – 1;

}

}

return -1; }

Testing: We will be testing your method using our driver routine. For testing on your end, write your own driver routine in a class different than *H03_57*. Note that if *pList* is empty, the method should return -1.

**5.8 **Learning Objective: To demonstrate the student understands the definition of Big O. To informally prove the time complexity of an algorithm.

Problem: For *recTernarySearch*() the key operations are the four comparisons of *pKey* to the the elements of *pList*. Treat these four comparisons as one comparison and provide an informal proof of the worst case time complexity of ternary search (doing so will not change the time complexity of the algorithm because it only multiplies *g*(*n*) by the constant 4). To simplify the analysis, assume that the size of the list on entry to *recTernarySearch*() is always a power of 3, e.g., on the first call assume the size of the list is 3* ^{p}*, on the second call the size of the list is 3

^{p}^{-1}, on the third call 3

^{p}^{-2}, and so on.

# 6 Sorting

**6.1 **Learning Objective: To demonstrate that the student can implement the *java.lang.Comparable*<*T*> interface.

Instructions: For this exercise you will be modifying the *Point* class declaration which was discussed in the Week 1 lecture notes in *Objects and Classes** :** Section 1* (in *burger-cse205-note-objs-classes-01.pdf*). The *Point*.*java* source code file can be found in the *Week 1 Source Code *zip archive). Include *Point.java* in your assignment zip archive.

Problem: Consider the *Point* class mentioned in the Instructions. Modify this class so it implements the *java.lang. Comparable*<*Point*> interface. We define *Point* *p1* to be less than *Point p2* if the distance from the origin to *p1* is less than the distance from the origin to *p2*; *p1* is greater than *p2* if the distance from the origin to *p1* is greater than the distance from the origin to *p2*; otherwise, if the distances are equal then *p1* is equal to *p2*.

Testing: We will be testing your method using our driver routine. For testing on your end, write your own driver routine in a class different than *Point*.

**6.2** Learning Objective: To demonstrate an understanding of how the insertion sort algorithm works.

Problem: Consider this *ArrayList *of *Integer*s, which is to be sorted into ascending order:

** list **= { 13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15 }.

Trace the *insertionSort*() method and show the contents of *list*: (1) on entry to *insertionSort*(); (2) after the for *j *loop terminates each time but before the for *i* loop is repeated; and (3) after the for *i* loop terminates.

**6.3 **Learning Objective: To demonstrate that the student can estimate the actual time an algorithm will take to execute. For the student to understand that even on a spectacularly fast computer system, a *O*(*n*^{2}) algorithm is still too slow for large problem sizes.

Problem: Your after-hours research finally pays off: you discover a way to build a computer system that is one billion (10^{9}) times faster than the fastest system currently in existence, where we are assuming that the fastest system in existence is the one we discussed in the Week 5 notes *Sorting Algorithms** :** Section 6 *(the file is named *burger-cse205note-sort-06.pdf*) which performs a comparison in 25 nanoseconds.

On your new computer system, each comparison in *findMinIndex*() and *findMaxIndex*() of selection sort requires only 25 × 10^{–[1]8} seconds, which is 25 attoseconds^{1}. Create a table similar to the one in the lecture notes showing how long selection sort will take to sort lists of sizes 10* ^{p}*, for

*p*= 2, 3, 4, …, 10 (Excel is an ideal tool for doing this).

**6.4 **Learning Objective: To demonstrate that the student can use mathematics to solve a time-complexity related problem.

Instructions: This exercise is graded, so write your solution in your word processing document.

Problem: If we require *insertionSort*() to sort a list of 10-billion elements in no more than one minute, how many times faster would your new computer system need to be than the fastest system currently in existence, i.e., the one that performs a comparison in 25 ns?

[1] That’s fast. The smallest amount of time ever measured is on the order of zeptoseconds, 10^{-21} seconds which is only 1,000 times shorter than an atto-second.