PART A: Programming Exercises for Part A (Java Reviews) - COSC-2436

Class, to complete any of these exercises/projects/LABs, you will download/install/use any free Pythons IDE (integrated development environment/Editor/shell), such as:

General Editors and IDEs with JAVA Support

JAVA-Specific Editors and IDEs

GNU Debugger (https://www.onlinegdb.com/) this is what I use in the classroom No Installation required for this,

IntelliJ IDEA. With more than 33 percent of the market share, IntelliJ IDEA is the most used Java IDE in 2022

Eclipse. Eclipse is a well-liked Java IDE that accounts for about 48 percent of the market share

NetBeans

JDeveloper

JCreator or DrJava or any other

General Rules:

You MUST add comments in the body of your program to explain each block of text properly (please see the attached program sample document: SampleJavaProgramDocumentation.docx attached here). Points will be deducted if comments are NOT provided for block of codes that you submit.

Programming Exercise 5 ():

Recursion is the technique of making a function call itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.

Recursion may be a challenge. The best way to figure out how it works is to experiment with it. The most important skill needed is patience. In this exercise, you will need that.

Assume in the example below, that a mergeSort function is called with the input array {10, 6, 8, 5, 7, 3, 4} and its length (7) as the parameters input array is passed to a and 7 is passed to n. The recursive function needs the base and the recursive conditions [and recursion].

- Base Condition - The base condition checks if the array length is 1 and it will just return. For the rest of the cases, the recursive call will be executed.

- Recursive Condition - For the recursive case, we get the middle index and create two temporary arrays l[] and r[]. The mergeSort function is then called recursively for both the sub-arrays.

Here is the Java Code for this program segment:

public static void mergeSort(int[] a, int n) {

// Interpret this as is simply the dividing portion.

if (n < 2) {

return;

}

int mid = n / 2;

int[] l = new int[mid];

int[] r = new int[n - mid];

for (int i = 0; i < mid; i++) {

l[i] = a[i];

}

for (int i = mid; i < n; i++) {

r[i - mid] = a[i];

}

mergeSort(l, mid);

mergeSort(r, n - mid);

merge(a, l, r, mid, n - mid); // this is merging the arrays (conquering)

}

Using any drawing program (or MS Word or PowerPoint), trace/draw what happens for each step. Just indicate the merge function call with its arguments.

Here is a sample to help you get started:

Start file for Tracing the Recursion in mergeSort function:

Start file for Tracing the Recursion in Merge Sort Algorithm

main() method

actual[] = {10, 6, 8, 5, 7, 3, 4}

actual.length = 7

-------------------------------------------------------------------------------------

Call mergeSort({10, 6, 8, 5, 7, 3, 4}, 7) (1) Initial call of mergeSort from main method

Line when call returns

2. mergeSort({10, 6, 8, 5, 7, 3, 4}, 7)

Array a = {10, 6, 8, 5, 7, 3, 4}

n = 7

----------------------------------------------------

mid = 7/2 = 3

l[3] = array of size 3 created

r[4] = array of size 4 created

l[3] = {10,6,8}

r[4] = {5,7,3,4}

Call mergeSort({10,6,8}, 3) (2)

Call mergeSort({5,7,3,4}, 4) (9)

Call merge( ) ()

3. mergeSort({10, 6, 8}, 3)

Array a = {10, 6, 8} and n = 3

----------------------------------------------

mid = 3/2 = 1

l[1] = array of size 1 created

r[2] = array of size 2 created

l[1] = {10}

r[2] = {6,8}

Call mergeSort({10}, 1)(3)

Call mergeSort({6,8}, 2) (4)

Call merge({10, 6, 8},{10},{6.8}, 1, 2) (8) return to (1) - Line when call returns

Complete the Rest for a grade and submit