Skip to Main Content

Introduction to Computer Science

Computer Science Department

Recursion – 80 course points

This assignment consists of two parts to exercise your ability to work with Strings and recursion.

Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.

Start your assignment early.

Programming

Write 2 programs and submit on Autolab.

We provide this ZIP FILE containing RecursiveAppend.java and RunLengthEncoding.java

Observe the following rules:

  1. DO NOT use System.exit().
  2. DO NOT add the project or package statements.
  3. DO NOT change the class name.
  4. DO NOT change the headers of ANY of the given methods.
  5. DO NOT add any new class fields.
  6. ONLY display the result as specified by the example for each problem.
  7. DO NOT print other messages, follow the examples for each problem.
  8. USE StdIn, StdOut, StdRandom, and StdDraw libraries.

1. Recursive Append (30 points). On RecursiveAppend.java write a recursive method appendNTimes that receives two arguments, a string and an integer. The method appendNTimes returns the original string appended to the original string n times.

Use the following method header: public static String appendNTimes (String original, int n)

Examples:

appendNTimes("cat", 0) returns “cat”

appendNTimes("cat", 1) returns “catcat”

appendNTimes("cat", 2) returns “catcatcat”

The following restrictions apply to method appendNTimes:

  • YOUR CODE MUST BE RECURSIVE
  • Do not use loops (while, do/while, or for).
  • Your code must return a string without extra space, comma or any other character that is not in the original string

You may write your own main method to test your appendNTimes method. Autolab will ignore your main method.

2. Run Length Encoding (50 points). This problem requires you to write a compression algorithm as described below.

Run-length encoding (RLE) is a simple “compression algorithm” (an algorithm which takes a block of data and reduces its size, producing a block that contains the same information in less space). It works by replacing repetitive sequences of identical data items with short “tokens” that represent entire sequences. Applying RLE to a string involves finding sequences in the string where the same character repeats. Each such sequence should be replaced by a “token” consisting of:

  1. the number of characters in the sequence
  2. the repeating character

If a character does not repeat, it appears as a single character in the compressed string with no number preceding it.

For example, consider the following string:

qwwwwwwwwweeeeerrtyyyyyqqqqwEErTTT

After applying the RLE algorithm, this string is converted into:

q9w5e2rt5y4qw2Er3T

In the compressed string, “9w” represents a sequence of 9 consecutive lowercase “w” characters. “5e” represents 5 consecutive lowercase “e” characters, etc.

The Assignment

  1. Write a method called encode that takes a string as input, compresses it using RLE, and returns the compressed string. Case matters – uppercase and lowercase characters are to be considered distinct. You may assume that there are no digit characters in the input string. There are no other restrictions on the input – it may contain spaces or punctuation. There is no need to treat non-letter characters any differently from letters.
  2. Write your code inside the encode method and use the main method to test your code. There is no need to delete the main method, the autograder will only grade encode.
  1. Write a method called decode that will decode text which has been encoded using the RLE algorithm defined above.
  2. For example, the following call to decode
  3. decode("q9w5e2rt5y4qw2Er3T")
  4. returns the string: “qwwwwwwwwweeeeerrtyyyyyqqqqwEErTTT”
  5. You may write your own main method to test your decode method. Autolab will ignore your main method.
  6. For this problem, you may assume that the character counts will be single-digit numbers (a character will not repeat more than 9 times consecutively).
  7.  
  8. **YOUR CODE MUST BE RECURSIVE**
  9. Do not use loops (while, do/while, or for).
  10. Do not declare any variables outside of a method. You may declare local variables inside a method.
  1. Hint #1: remember that characters are represented by numeric codes. You can decrement a character variable as follows:
     char c = '7';
 c--; // c will now hold the character '6'
  2. Hint #2: You probably will not need to use this hint for this problem. However, a fast way to convert a digit character into the numeric value of the digit is to subtract the character code for the digit zero:
     char c = '7'; // this has the character code 55, not 7
 int x = c - '0'; // this produces the number 7

Before submission

  • Collaboration policy. Read our collaboration policy here.
  • Update @author. Update the @author tag of the files with your name, email and netid.
  • Submitting the assignment. Submit RecursiveAppend.java and RunLengthEncoding.java separately via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza. Find instructors office hours by clicking the Staff  link from the course website. In addition to office hours we have the CAVE (Collaborative Academic Versatile Environment), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.