DUE: 11:59 pm on Monday, December 8. No late days may be used!

  1. DUE: 11:59 pm on Monday, December 8. No late days may be used!
  2. Goals of This Assignment
    1. Tools for Completing This Assignment
      1. Git
      2. Collaboration Policy
      3. Style & Design Policy
  3. Specification
    1. Easier Problems
      1. countSubstrings
      2. convertIntToString
      3. digitMatch
      4. sumReciprocalsBetween
      5. writeBinary
      6. multiplyOdds
    2. More Difficult Problems
      1. findSecondLargest
      2. collatz
      3. permutation
      4. recamans
    3. Most Difficult Problems
      1. subsetsOfSize
      2. maxSum
      3. waysToClimb
  4. Testing
  5. Submission

Goals of This Assignment

In this assignment, you’ll practice thinking recursively through writing six recursive functions across a range of difficulties.

Tools for Completing This Assignment

  • Recursive programming and backtracking
  • Working with Data Structures
  • Unit Testing

Git

You should keep track of your code for this assignment using git. Review the instructions for setting up a git repository here. There are not specific checkpoints at which you should make a commit. Instead, you should commit and push your changes each time you make substantial progress. A good rule of thumb is to make a commit each time you finish one of the required functions.

You will submit as part of your solution a screenshot of your commit history. The image should show at minimum 5 commits to receive the full 5 points. You are welcome to make more.

Collaboration Policy

You cannot collaborate with anyone on this assignment. All code you write must be your own, and you may not discuss the assignment with other students. Please refer to the Collaboration & Academic Misconduct portion of the syllabus for further details.

Style & Design Policy

There is no style and design portion of the grade for this assignment, but you should still aim to follow the best practices you’ve learned thus far.

Specification

For this assignment, you will have some flexibility in terms of which problems to complete. Below you will find three categories of problems:

  1. Easier (6 total options)
  2. More difficult (4 total options)
  3. Most difficult (3 total options)

Each problem asks you to write a recursive function. The function signature should exactly match the function signature given in the problem. This may mean you need to write some recursive helper functions in order to complete a problem. Helper functions should be private static and add the word Helper to the function name. All of these functions should be written in a file called RecursivePractice.java.

You will complete 6 recursive functions for this assignment. You may choose which problems to complete, following these requirements:

  • 3 of the problems should be from the “Easier” category
  • 2 of the problems should be from the “More difficult” category
  • 1 of the problems should be from the “Most difficult” category

Note Solutions using any kind of iteration will be given no credit.

Easier Problems

countSubstrings

Function Signature: public static int countSubstrings(String word, String substring)

Problem Description: Given a word and a substring, count how many times the substring appears in the word.

For example, in the word “banana”, the substring “na” appears two times, with “banana” and “banana”, so countSubstrings would return 2.

Similarly, the substring “ana” also appears twice in “banana”, with “banana” and “banana”. Note that this means we can have overlaps between the starts of our substrings (don’t worry, this actually makes the problem easier).

You may assume that both word and substring are not null and have positive lengths. You may also assume that both strings are all lowercase.

convertIntToString

Function Signature: public static String convertIntToString(int x)

Problem Description: Given an integer x, convert it into a String representation.

To do this recursively, you should process x digit by digit. You will find the ASCII table of values useful for converting int to char and you may use the method Character.toString() to convert from char to String.

If x is negative, you should maintain this in the String representation.

digitMatch

Function signature: public static int digitMatch(int x, int y)

Problem Description: Given two integers x and y, count the number of digits they have in common.

Two digits match if they are equal in 1) value and 2) position (relative to the end of the number). In other words, the function should compare the last digits of each number, followed by the second-to-last digits, then the third-to-last digits, and so forth, counting how many pairs match.

For example, digitMatch(1072503891, 62530841) would return 4.

1 0 7 2 5 0 3 8 9 1
    | | | | | | | |
    6 2 5 3 0 8 4 1

You may assume that x and y are non-negative numbers with no leading zeroes.

sumReciprocalsBetween

Function Signature: public static double sumReciprocalsBetween(int lower, int upper)

Problem Description: Given two integers lower and upper, sum the reciprocals between the two. In math, we would write this problem as \(\sum_{i=lower}^{upper}\frac{1}{i}\).

For example, sumReciprocalsBetween(1,3) returns 1.8333... because 1 + 1/2 + 1/3 = 1.8333....

If either bound is less than or equal to 0, or if the upper bound is less than the lower bound throw an IllegalArgumentException.

writeBinary

Function Signature: public static void writeBinary(int x)

Problem Description: Given an integer x, write its binary (base-2) representation to the console.

For example, the binary representation of 44 is 101100.

If x is less than 0, throw an IllegalArgumentException.

multiplyOdds

Function Signature: public static int multiplyOdds(int n)

Problem Description: Given an integer n, return the product of the first n odd integers.

For example, multiplyOdds(1) returns 1 and multiplyOdds(4) returns 105 because 1 * 3 * 5 * 7 = 105.

If n is less than or equal to 0, throw an IllegalArgumentException.

More Difficult Problems

findSecondLargest

Function Signature: public static int findSecondLargest(int[] arr)

Problem Description: Given an array of integers, find the second largest number in the array.

Note that if the largest number appears multiple times, the second largest is considered to be the same as the largest number. For example, the second largest number of [7, 1, 7] is 7.

You may assume that the array is not null and has at least 2 different elements in it.

collatz

Function Signature: public static boolean collatz(int n)

Problem Description: Given an integer n, determine whether or not the number will ever reach 1 by following the steps of the Collatz Conjecture.

The Collatz Conjecture is an unsolved problem in mathematics which states that every positive integer can be transformed into 1 by doing the following:

  1. If n is even, the next term will be n / 2
  2. If n is odd, the next term will be 3 * n + 1
  3. Repeat until the term becomes 1

If a value of n is ever repeated in this process, then there is a cycle and it is impossible to reach the value 1. If such a case is detected, the function returns false. Otherwise, if the value reaches 1, return true.

For example, collatz(10) returns true and the sequence of computations which leads to this is as follows:

10 -> 10 / 2 -> 5
5  -> 5 * 3 + 1 -> 16
16 -> 16 / 2 -> 8
8  -> 8 / 2 -> 4
4  -> 4 / 2 -> 2
2  -> 2 / 2 -> 1
1  -> return true

Hint Think about what data type you could add as a parameter to a helper function to help you track previously seen elements.

Exception This problem is exempt from the 100% line coverage requirement for testing!

permutation

Function Signature: public static double permutation(int n, int r)

Problem Description: Given two integers n and r, compute the number of unique permutations of r items from a group of n items.

For given values of n and r, this value P(n, r) can be computed as follows: \(P(n, r) = \frac{n!}{(n - r)!}\)

For example, permutation(7, 4) should return 840.0.

If n is less than r, or either value is less than 0, throw an IllegalArgumentException.

Hint Think about how the call permutation(7, 4) relates to the call permuttaion(6, 3).

recamans

Function Signature: public static int recamans(int n)

Problem Description: Given an integer n, compute the nth term in Recamán’s sequence.

If n is less than 0, throw an IllegalArgumentException.

Recamán’s sequence is defined as follows:

\[a_{n} = \begin{cases} 0 & \text{if } n = 0 \\ a_{n-1} - n & \text{if } a_{n-1} - n > 0 \text{ and is not already in the sequence} \\ a_{n-1} + n & \text{ otherwise} \end{cases}\]

Hint Think about what data type you could add as a parameter to a helper function to help you track previously seen elements.

Most Difficult Problems

subsetsOfSize

Function Signature: public static void subsetsOfSize(ArrayList<String> list, int size)

Problem Description: Given a list of strings and a size, print out every sub-list of that size that could be created from elements of the given list.

For example, given the list [Banana, Mango, Pineapple, Strawberry] and a size 2, the output would be:

[Banana, Mango]
[Banana, Pineapple]
[Banana, Strawberry]
[Mango, Pineapple]
[Mango, Strawberry]
[Pineapple, Strawberry]

The order in which you show the sub-lists does not matter, and the order of the elements of each sub-list also does not matter. The key thing is that the function should produce the correct overall set of sub-lists as its output.

You may assume that the list is not null, that the list contains no duplicates, and that the size is at least 1 and no larger than the size of the list.

maxSum

Function Signature: public static int maxSum(ArrayList<Integer> list, int limit)

Problem Description: Given a list of integers and a limit, find the maximum sum that can be computed by adding elements of the list without exceeding the limit.

For example, given the list [7, 30, 8, 22, 6, 1, 14] and the limit of 19, the maximum sum that can be generated that does not exceed the limit is 16. This is achieved by adding 7, 8, and 1.

If the list is empty, or if the limit is not a positive integer, or all of the lists values exceed the limit, return 0.

Each index’s element in the list can be added to the sum only once, but the same number value might occur more than once in a list, in which case each occurrence might be added to the sum. For example, if the list is [6, 2, 1] you may us up to one 6 in the sum, but if the list is [6, 2, 1, 6] you may use up to two sixes.

You may assume that all values in the list are nonnegative. Your method may alter the contents of the list as it executes, but it should be restored to its original state before your method returns. Do not use any loops.

waysToClimb

Function Signature: public static int waysToClimb(int n)

Problem Description: Given an integer n representing an amount of stairs to climb, calculate the number of ways to climb the stairs taking either 1 or 2 steps at a time.

If n is less than or equal to 0, throw an IllegalArgumentException.

For example, if there are four stairs, it returns 5 as there are the following options:

1, 1, 1, 1
1, 1, 2
1, 2, 1
2, 1, 1
2, 2

Hint You may find it helpful to write out the possibilities by hand for several small examples. Look for patterns you can take advantage of.

Testing

We expect you to write unit tests using JUnit for every recursive function in RecursivePractice.java in a file called RecursiveTesting.java. We will run your tests in addition to our own to verify your code works. To earn full points on testing, you must:

  • Write at least 3 tests for each function you implement
  • Achieve 100% line-based code coverage for each function you implement (including private helper functions which are tested implicitly)

Submission

Submit the files RecursivePractice.java and RecursiveTesting.java which should contain all your recursively implemented functions and their associated tests, respectively. Finally, submit a screenshot of your git log history.

Ensure that your files do not have a package header! Specifically, the first lines of your file should not read package xyz or similar.

Please find these files locally on your file system. You should select each of the files and upload them as files (not as a directory, and preferably not as a .zip either). If you need help, please reach out on Ed or in Office Hours.