Jam 04 - Exercise 3

--- title: "Jam 04 - Exercise 3" tags: - 3 🧪 in testing - 4 🥳 done - jam04 - arrays - recursion ---   {%hackmd dJZ5TulxSDKme-3fSY4Lbw %} # Exercise 3 - Array Operations :::danger 🚨 **Prerequisites** Before starting this exercise, you MUST: 1. Complete the Arrays assignment in zyBooks (at minimum Section 6.1) 2. Understand the basic concepts of arrays in Java 3. Be comfortable with array syntax and operations Attempting this exercise without the prerequisite knowledge will make it significantly more challenging and time-consuming. ::: ## Overview - Exercise 3 - lowercase a arrays In this exercise, you'll implement fundamental array operations in Java. Arrays are the foundation of data structures and understanding how to manipulate them effectively is crucial for software development. You'll write methods to perform common array operations like concatenation, reversal, and searching, while practicing both iterative and recursive approaches. :::info 🔑 **Understanding Java Arrays vs Python Lists** If you're coming from Python, it's important to understand the key differences between Java arrays and Python lists: 1. **Type Restriction**: - Java arrays are homogeneous - all elements must be the same type - Python lists can mix different types freely 2. **Size**: - Java arrays have fixed size after creation - Python lists can grow and shrink dynamically 3. **Object Nature**: - Java arrays are objects that must be constructed using `new` - Python lists are dynamic and don't require explicit construction 4. **Memory Model**: - Java arrays use contiguous memory blocks - This makes them very efficient for direct access - But requires careful size planning ::: 🔑 **Array Fundamentals** **Definition**: An array is an ordered collection of items where: - Each item has the same type - Items are stored in contiguous memory - Each item can be accessed directly using an index - The size is fixed at creation time **Key Properties**: 1. Zero-based indexing (first element is at index 0) 2. Length is accessible via the `length` property 3. Must be constructed before use with the `new` operator 4. Can be single or multi-dimensional For more detailed explanations, refer to Chapter 5 of Schildt's *Java: A Beginner's Guide* on O'Reilly Learning: [Array Fundamentals](https://learning.oreilly.com/library/view/java-a-beginners/9781260463569/ch5.xhtml) :::info 🔑 **Key Concepts** - Arrays as fundamental data structures - Recursive vs iterative solutions - Array manipulation and traversal - Memory management with arrays - Algorithm efficiency considerations ::: ## The Problem - Exercise 3 You need to implement several array utility methods that will be used in a larger application. Each method must handle arrays of integers and perform specific operations while following certain constraints. First, let's get the starter code that contains the method signatures and test cases: ```bash # If working on your laptop (replace userid with your Bucknell username): scp "userid@linuxremote.bucknell.edu:/home/csci205/2025-spring/student/jam04/ArrayChallenge.java" "src/main/java/jam04/" # If working on linuxremote: cp "/home/csci205/2025-spring/student/jam04/ArrayChallenge.java" "src/main/java/jam04/" ``` :::warning 🚨 **Important**: - Make sure you're in your project root directory when running these commands - The file must be placed in the correct package directory (`src/main/java/jam04/`) - Don't forget to add your banner at the top of the file - Verify the file was copied correctly before proceeding ::: Copy a banner (the comment code at the top of the file) from the top of a previous file into the new ArrayChallenge.java file. This is important because it will help you keep track of your work and it will be required for this assignment. Normally IntelliJ creates this for you as a part of your template, but since you copied the file from linuxremote, you will need to add the banner manually. Take a moment to review the code you just received, particularly the `subArray` method which has been completed for you as an example. Notice: - How new arrays are created - How elements are copied between arrays - The style of parameter validation - The JavaDoc comment format Now let's look at each method you need to implement: **Problem**: This exercise involves six array utility methods. One (`subArray`) has been completed for you as an example, and you need to implement the remaining five: 1. `subArray`: Extract a portion of an array (already completed for you) 2. `concat`: Combine two arrays 3. `recReverse`: Recursively reverse an array 4. `altSum`: Calculate alternating sum 5. `isSorted`: Check if array is sorted 6. `hasDuplicateValues`: Detect duplicate elements ### Method Specifications 1. **subArray** (completed for you): ```java public static int[] subArray(int[] a, int iStart, int iEnd) ``` - Returns a new array containing elements from index `iStart` to `iEnd-1` - Example: `subArray([1,2,3,4,5], 1, 3)` returns `[2,3]` 2. **concat**: ```java public static int[] concat(int[] a1, int[] a2) ``` - Returns a new array containing all elements from `a1` followed by all elements from `a2` - Example: `concat([1,2], [3,4])` returns `[1,2,3,4]` 3. **recReverse**: ```java public static int[] recReverse(int[] a) ``` - Returns a new array with elements in reverse order - Must use recursion - Example: `recReverse([1,2,3])` returns `[3,2,1]` 4. **altSum**: ```java public static int altSum(int[] a) ``` - Returns alternating sum of elements (add first, subtract second, add third, etc.) - Example: `altSum([1,3,5,7])` returns `1-3+5-7 = -4` 5. **isSorted**: ```java public static boolean isSorted(int[] a) ``` - Returns true if array is in ascending order - Example: `isSorted([1,2,2,3])` returns `true` 6. **hasDuplicateValues**: ```java public static boolean hasDuplicateValues(int[] a) ``` - Returns true if any value appears more than once - Example: `hasDuplicateValues([1,2,2,3])` returns `true` ## Required Steps - Exercise 3 1. Review the provided `subArray` method to understand: - How to create new arrays - How to copy elements between arrays - Proper parameter validation - JavaDoc comment style 2. Implement the remaining methods following these guidelines: - Include parameter validation where appropriate - Follow the method signatures exactly - Do not use any methods from the Arrays class - Do NOT modify the main method or test cases - they are provided to help you verify your work - Test each method thoroughly before moving to the next :::warning 🚨 **Important Restrictions** 1. Do NOT use any methods from the Arrays class 2. The `recReverse` method MUST use recursion 3. Do NOT modify the main method or test cases 4. Each method must create new arrays rather than modifying inputs ::: :::info 🔧 **Implementation Tips** 1. For all methods: - Consider edge cases (empty arrays, single elements) - Think about memory efficiency when creating new arrays - Test with small examples first 2. When working with recursion: - Identify your base case(s) - Think about how to break down the problem into smaller subproblems - Draw out the call stack for a small example 3. For boolean methods: - Consider all conditions that could make the result true/false - Test with boundary conditions 4. General approach: - Start with a small example and work it out by hand - Look for patterns in how you solved it manually - Then translate your manual process into code ::: > 🔍 **Checkpoint** > > Before proceeding, verify that: > > - All methods are implemented with correct signatures > - Each method has proper JavaDoc comments > - Test cases pass for implemented methods > - No Arrays class methods are used > - recReverse uses recursion > - Parameter validation is implemented where needed > - New arrays are created rather than modifying inputs ## Save Your Work - Exercise 3 Verify what files are uncommitted: ```bash git status ``` Stage your changes: ```bash git add src/main/java/jam04/ArrayChallenge.java ``` Commit your work: ```bash git commit -m "jam04: Implement array utility methods" ``` Your working directory should now be clean. :::success 🔑 **Key Takeaways** - Arrays in Java are fixed-size objects that must be constructed - Recursive solutions can be elegant but may not always be most efficient - Creating new arrays vs modifying existing ones has different implications - Method decomposition helps manage complexity - Testing edge cases is crucial for robust code :::