Problem Set 1

Due before the start of lecture on February 17, 2026.
See below for a summary of the policies regarding late submissions.

Preliminaries

Homework is due prior to the start of lecture. If it is submitted more than 10 minutes after the start of lecture, it will be considered a full day late. There will be a 10% deduction for late submissions that are made by 11:59 p.m. Eastern time on the Sunday after the deadline, and a 20% deduction for submissions that are made after that Sunday and before the start of the next lecture. We will not accept any homework that is more than 7 days late. Plan your time carefully, and don’t wait until the last minute to begin an assignment. Starting early will give you ample time to ask questions and obtain assistance.

In your work on this assignment, make sure to abide by our policies on academic conduct.

If you haven’t already done so, you should complete Problem Set 0 before beginning this assignment.

If you have questions while working on this assignment, please come to office hours, post them on Ed Discussion, or email cscie22-staff@lists.fas.harvard.edu

Part I: Short-answer problems

40 points total

Creating the necessary folder

1. If you haven’t already created a folder named e22 for your work in this course, follow these instructions to do so.

2. Then create a subfolder called ps1 within your e22 folder, and put all of the files for this assignment in that folder.

Creating the necessary file

The problems from Part I will all be completed in a single PDF file. To create it, you should do the following:

1. Access the template that we have created by clicking on this link and signing into your Google account as needed.

2. When asked, click on the Make a copy button, which will save a copy of the template file to your Google Drive.

3. Select File->Rename, and change the name of the file to ps1_partI.

4. Add your work for the problems from Part I to this file.

5. Once you have completed all of these problems, choose File->Download->PDF document, and save the PDF file in your ps1 folder. The resulting PDF file (ps1_partI.pdf) is the one that you will submit. See the submission guidelines at the end of Part I.

Problem 1: Memory management and arrays

8 points

Consider the following lines of Java code:

int[] a = {5, 4, 3, 2, 1};
int[] b = {5, 4, 3, 2, 1};
int[] c = a;

for (int i = 0; i < b.length; i++) {
    c[i] = b[i];
}

b[3] += b.length;
a[3]--;

System.out.println(a[3] + " " + b[3] + " " + c[3]);

1. (6 points) In ps1_partI (see above), we have given you the beginnings of a memory diagram for these lines of code. It includes both the stack and the heap.

   On the stack, we have included a stack frame for the main method, which is where we are assume that the above lines are found. On the heap, we have included the array to which the variable a refers.

   Complete the provided memory diagram so that it shows the final result of the above lines of code.

   To do so, you should:

   • Click on the diagram and then click the Edit link that appears below the diagram.

   • Make whatever changes are needed to the diagram. Below the thick horizontal line, we have given you a set of extra components that you can use as needed by dragging them above the thick line and putting them in the correct position. You may not need all of the provided components.

   • You can also edit any of the values in an array by clicking on one of its cells and editing the text that is inside the cell.

   • Once you have made all of the necessary changes, click the Save & Close button.

2. (2 points) Indicate what will be printed by the final line of code shown above.

Problem 2: Array practice

10 points total; 5 points each part

In this problem, you will write static methods that operate on arrays. These methods do not need to use recursion, and they do not need to be implemented as part of a class. Simply include the methods with your answers for the other problems from Part I.

1. Write a method with the header

   public static boolean anyMult(int[] arr, int n)
   

   that takes a reference to an array of integers and returns true if at least one of the values in the array is a multiple of n, and false otherwise.

   Special cases:

   • If the method is passed a value of null, it should throw an IllegalArgumentException.

   • If the method is passed an array with a length of 0, it should return false.

   See below for a recommended approach to testing this method.

2. Write a method with the header

   public static void shiftRight(int[] arr)
   

   that takes a reference to an array of integers and shifts all of the array elements one position to the right, with the original last element wrapping around to become the new first element. For example, consider this array:

   int[] values = {0, 2, 4, 6, 8, 10};
   

   After calling shiftRight(values), the contents of the values array should be {10, 0, 2, 4, 6, 8}.

   Note that the method has a return type of void, which means that it should not return a value. It doesn’t need to do so, because it should be modifying the internals of the array arr, and thus those changes will still be there after the method returns.

   Special cases:

   • If the method is passed a value of null, it should throw an IllegalArgumentException.

   • If the method is passed an array with a length of 0 or 1, it should leave the array unchanged.

3. Testing Your Methods in VS Code We encourage you to use VS Code to test your methods for parts 1 and 2 above. Here are the steps:

   1. If you haven’t already done so, create a folder named ps1 for your work on this assignment.

   2. Download the following file: Problem2Test.java

      Make sure to put the file in your ps1 folder. If your browser doesn’t allow you to specify where the file should be saved, try right-clicking on the link above and choosing Save as... or Save link as..., which should produce a dialog box that allows you to choose the correct folder for the file.

   3. In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open the folder that you created for this assignment. (Note: You must open the folder; it is not sufficient to simply open the file.)

      The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with the name of the Problem2Test.java file that you downloaded above.

   4. Click on the name Problem2Test.java, which will open an editor window for that file.

   5. Put your methods inside the provided class. We have given you some code in the main method for testing your methods, but we encourage you to add additional tests as well.

      Note: You may use the Arrays.toString() method for testing, since it allows to easily view the contents of an array. However, you should not be using this method or any other method from the Arrays class for any purpose other than testing.

   6. Run your program and make sure that the tests produce the expected results.

Once you are happy with your methods, put them in your ps1_partI file. Do not submit the Problem2Test.java file.

Problem 3: Recursion and the runtime stack

12 points

Consider the following recursive method:

public static int mystery(int a, int b) {
    if (a * b == 0) {
        return a;
    } else {
        int myst_rest = mystery(a - 1, b - 2);
        return b + myst_rest;
    }
}

1. (5 points) Trace the execution of mystery(5, 6). To do so, complete the template that we have provided in section 3-1 of ps1_partI. In particular, you should:

   • Include a separate “frame” for each call. We have filled in some of the components of the frames for the first two calls for you. You should replace each ... with the appropriate integer, and you should add frames for additional calls as needed, until you reach the base case.

   • Begin each frame with lines that explicitly state the values assigned to the parameters, as we have done for the first call.

   • Next, if the call is a base case, you can simply show the value that is returned (omitting the line for myst_rest). If the call is a recursive case, you should show the recursive call on the line for myst_rest.

   • Once you have reached the base case, you should work your way back through the frames for the previous calls. Add in both the results of the recursive call (i.e, the value assigned to myst_rest) and the value returned by the call itself.

2. (2 points) What is the value returned by mystery(5, 6)?

3. (2 points) During the execution of mystery(5, 6), method frames are added and then removed from the stack. How many method frames are on the stack when the base case is reached? You should assume that the initial call to mystery(5, 6) is made from within the main() method, and you should include the stack frame for main in your count.

4. (3 points) Give an example of values of a and b that would produce infinite recursion, and explain why it would occur.

Problem 4: Rewriting a method

10 points

Consider the following method, which uses iteration (a for loop) to search for an item in an array of integers. The method returns true if the item is found in the array, and false if it is not.

public static boolean search(int item, int[] arr) {
    for (int i = 0; i< arr.length; i++) {
        if (arr[i] == item) {
            return true;
        }
    }

    return false;
}

1. (4 points) Rewrite this method so that it searches for an item an array that can contain any type of object. Change the types of the parameters accordingly, and make whatever changes are needed to the body of the method.

2. (6 points) Rewrite your answer to part 1 so that it uses recursion instead of iteration. You will need to add a third parameter (call it start) that keeps track of where you are in the array. More precisely, start will specify the position in the array where the search for item should begin. For example, search("hello", arr, 0) should search for “hello” in the full array (beginning at position 0), whereas search("hello", arr, 2) should search for "hello" in the subarray that begins at position 2 and goes to the end of the array.

Submitting your work for Part I

Submit your ps1_partI.pdf file by taking the following steps:

1. If you still need to create a PDF file, open your file on Google Drive, choose File->Download->PDF document, and save the PDF file on your machine.

2. Click on the name of the assignment in the list of assignments on Gradescope. You should see a pop-up window labeled Submit Assignment. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

3. Choose the Submit PDF option, and then click the Select PDF button and find the PDF file that you created. Then click the Upload PDF button.

4. You should see a question outline along with thumbnails of the pages from your uploaded PDF. For each question in the outline:

   • Click the title of the question.
   • Click the page(s) on which your work for that question can be found.

   As you do so, click on the magnifying glass icon for each page and doublecheck that the pages that you see contain the work that you want us to grade.

5. Once you have assigned pages to all of the problems in the question outline, click the Submit button in the lower-right corner of the window. You should see a box saying that your submission was successful.

Part II: Programming problems

60-70 points total

Problem 5: Adding methods to the ArrayBag class

25 points total

Getting started

1. If you haven’t already done so, create a folder named ps1 for your work on this assignment.

2. Download the following file:
   ArrayBag.java

   Make sure to put the file in your ps1 folder. If your browser doesn’t allow you to specify where the file should be saved, try right-clicking on the link above and choosing Save as... or Save link as..., which should produce a dialog box that allows you to choose the correct folder for the file.

3. In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open the folder that you created for this assignment. (Note: You must open the folder; it is not sufficient to simply open the file.)

   The name of the folder should appear in the Explorer pane on the left-hand side of the VS Code window, along with the name of the ArrayBag.java file that you downloaded above.

4. Click on the name ArrayBag.java, which will open an editor window for that file.

5. In ArrayBag.java, add the methods described below to the ArrayBag class, and then add code to the main() method to test these methods. You should not add any new fields to the class.

Here are the methods you should add:

1. public int capacity()
   This method should return the maximum number of items that the ArrayBag is able to hold. This value does not depend on the number of items that are currently in the ArrayBag — it is the same as the maximum size specified when the ArrayBag was created.

2. public boolean isFull()
   This method should return true if the called ArrayBag is full, and false otherwise.

3. public void increaseCapacity(int amount)
   This method should increase the maximum capacity of the called ArrayBag by the specified amount. For example, if b has a maximum capacity of 10, then b.increaseCapacity(5) should give b a maximum capacity of 15. As part of your implementation, you will need to create a new array with room to support the new maximum capacity, copy any existing items into that array, and replace the original array with the new one by storing its reference in the called object.

   Special cases:

   • If the parameter is 0, the method should just return without making any changes to the called object.

   • If the parameter is negative, the method should throw an IllegalArgumentException. See our second ArrayBag constructor for an example of throwing an exception.

4. public boolean removeItems(ArrayBag other)
   This method should attempt to remove from the called ArrayBag all occurrences of the items found in the parameter other. If the called object contains multiple copies of an item from otherBag, all of the copies should be removed. The method should return true if one or more items are removed and false otherwise.

   Hints:

   • Don’t forget that your removeItems method has direct access to the private fields of the ArrayBag passed in for other. See our containsAll method for another example of an ArrayBag method that takes another ArrayBag object as a parameter.

   • You can simplify your implementation of this method if you have it call one or more of the existing methods of the ArrayBag class. Here again, the existing containsAll method provides a relevant example.

   Special cases:

   • The method should return true if the bag represented by other is empty.
   • If the parameter is null, the method should throw an IllegalArgumentException. See our second ArrayBag constructor for an example of throwing an exception.

5. public ArrayBag unionWith(ArrayBag other)
   This method should create and return an ArrayBag containing one occurrence of any item that is found in either the called object or the parameter other. For full credit, the resulting bag should not include any duplicates. For example, if b1 represents the bag {2, 2, 3, 5, 7, 7, 7, 8} and b2 represents the bag {2, 3, 4, 5, 5, 6, 7}, then b1.unionWith(b2) should return an ArrayBag representing the bag {2, 3, 4, 5, 6, 7, 8}. Give the new ArrayBag a maximum size that is the sum of the two bag’s maximum sizes.

   The hints for the previous method also apply here.

   Special cases:

   • If one of the bags is empty, the method should return an ArrayBag containing one occurrence of each item in the non-empty bag.

   • If both of the bags are empty, the method should return an empty ArrayBag.

   • If the parameter is null, the method should throw an IllegalArgumentException.

Problem 6: Recursion and strings

10-20 points total; 5 points each part

Getting started

1. In VS Code, select the File->Open Folder or File->Open menu option, and use the resulting dialog box to find and open your ps1 folder. The name of the folder should appear in a new Explorer pane on the left-hand side of the VS Code window.

2. Select File->New Text File, which will open up an empty window known as an editor window for your new program. It will initially have a name that is something like Untitled-1.

3. Select File->Save, and give the file the following name:

   StringRecursion.java
   

   Important: When naming a Java file, the case of the letters matters. Make sure to use the exact combination of upper-case and lower-case letters that we have specified.

4. In your StringRecursion.java file, create a class named StringRecursion, implement the methods described below within that class, and then create a main() method to test these methods.

Here are the methods:

1. public static void printLetters(String str)
   This method should use recursion to print the individual characters in the string str, separated by commas. All characters in the string should be printed, not just the letters. For example, printLetters("Rabbit") should print

   R, a, b, b, i, t
   

   and printLetters("I like to recurse!") should print

   I,  , l, i, k, e,  , t, o,  , r, e, c, u, r, s, e, !
   

   Note that there is a single space between each comma and the subsequent character. The method should not do any printing if the empty string ("") or the value null is passed in as the parameter; it should simply return.

2. public static String replace(String str, char oldChar, char newChar)
   This method should use recursion to return a String that is formed by replacing all occurrences of the character oldChar in the string str with the character newChar. For example:

   • replace("base case", 'e', 'y') should return "basy casy"
   • replace("base case", 'r', 'y') should return "base case"

   This method should not do any printing; it should simply return the resulting string.

   Special cases:

   • If the first parameter is null, the method should return null.

   • If the first parameter is the empty string (""), the method should return the empty string.

3. (required for grad-credit students; “partial” extra credit for others)

   public static int indexOf(char ch, String str)
   This method should use recursion to find and return the index of the first occurrence of the character ch in the string str, or -1 if ch does not occur in str. For example:

   • indexOf('b', "Rabbit") should return 2
   • indexOf('P', "Rabbit") should return -1

   The method should return -1 if the empty string ("") or the value null is passed in as the second parameter. The String class comes with a built-in indexOf() method; you may not use that method in your solution!

4. (required for grad-credit students; “partial” extra credit for others)

   public static String trim(String str)
   This method should take a string str and use recursion to return a string in which any leading and/or trailing spaces in the original string are removed. For example:

   • trim(" hello world ") should return the string "hello world"
   • trim("recursion ") should return the string "recursion"

   The String class comes with a built-in trim() method that does the same thing as the method that we’re asking you to write; you may not use that method in your solution!

   Special cases:

   • If the parameter is null, the method should return null.

   • If the parameter is the empty string, the method should return the empty string.

Problem 7: A Sudoku solver

25 points

In this problem, you will write a program that solves Sudoku puzzles using recursive backtracking.

Overview

A Sudoku puzzle consists of a 9x9 grid in which some of the cells have been filled with integers from the range 1-9. To solve the puzzle, you fill in the remaining cells with integers from the same range, such that each number appears exactly once in each row, column, and 3x3 subgrid.

Here is an example of an initial puzzle:

and here is its solution:

Getting started

Begin by downloading the following zip file: problem7.zip

Unzip this archive, and you should find a folder named problem7 that contains all of the files that you need for this problem. You should not move any of the files out of the problem7 folder.

Keep all of the files in the problem7 folder, and open that folder in VS Code using the File->Open Folder or File->Open menu option.

Most of the functionality of your program should go in a class called Puzzle, which you will use to represent an individual Sudoku puzzle. We have provided you with skeleton code for this class in the file Puzzle.java. The provided code includes:

• a field called values that refers to a two-dimensional array of integers. This array is used to store the current contents of the cells of the puzzle, such that values[r][c] stores the current value in the cell at row r, column c of the puzzle. A value of 0 is used to indicate a blank cell.

• a field called valIsFixed that refers to a two-dimensional array of booleans. It is used to record whether the value in a given cell is fixed (i.e., part of the original puzzle). valIsFixed[r][c] is true if the value in the cell at row r, column c is fixed, and valIsFixed[r][c] is false if the value in that cell is not fixed. For example, in the original puzzle above, there is a fixed 4 in the cell at row 0, column 1 (the second cell in the top row), and thus valIsFixed[0][1] would be true for that puzzle.

• a field called subgridHasValue that refers to a three-dimensional array of booleans. This array allow us to determine if a given 3x3 subgrid of the puzzle already contains a given value. For example, subgridHasValue[0][0][4] will be true if the 3x3 subgrid in the upper left-hand corner of the board (a subgrid that we are identifying using the indices [0][0]) already has a 4 in one of its cells. See the comments accompanying this field for more information about the numbering of the subgrids.

• partial implementations of methods called placeValue() and removeValue() that place a value in a given cell and remove a value from a given cell by updating the fields mentioned above. You will need to add code to these methods to update the other fields that you add.

• a full implementation of a method called readFrom() that takes a Scanner as its only parameter and reads in a specification of a puzzle from that Scanner. This method assumes that a puzzle specification consists of nine lines of text — one for each row of the puzzle — and that each line contains nine digits separated by whitespace. Here again, 0 is used to indicate a blank cell. For example, the specification of the initial puzzle above would begin:

  0 4 0 0 0 3 7 0 0
  0 8 9 7 0 0 1 0 0
  ...
  

  The method reads in the puzzle specification and makes the corresponding changes to the fields mentioned above. You should not need to change this method, because it calls placeValue(), and you are already modifying that method as needed. However, we do recommend that you read this method over.

• the full implementation of a method called display() that prints out the current state of the Puzzle object on which it is invoked.

• the skeleton of a private method called solveRB() that you will implement. This is the recursive-backtracking method, and it should return true if a solution to the puzzle is found and false if no solution has been found (i.e., if the method is backtracking). If the initial call to this method returns false, that means that no solution can be found — i.e., that the initial puzzle is not valid. If there is more than one solution (which can happen if the initial puzzle does not have enough numbers specified), your code should stop after finding one of them.

  Each invocation of the solveRB() method is responsible for finding the value of a single cell of the puzzle. The method takes a parameter n, which is the number of the cell that the current invocation of this method is responsible for. We recommend that you consider the cells one row at a time, from top to bottom and left to right, which means that they would be numbered as follows:

  0  1  2  3  4  5  6  7  8
  9 10 11 12 13 14 15 16 17
  ...
  

• the full implementation of a public “wrapper” method called solve() that makes the initial call to solveRB(), and that returns the same value that solveRB() returns.

• a partial implementation of a constructor. You will need to add code to initialize the fields that you add.

We are also providing:

• a separate Sudoku class in the file Sudoku.java. It contains the main() method for your Sudoku solver. You shouldn’t need to change this method (or any other code in this file), but we encourage you to review its use of the methods of the Puzzle class. In particular, note that it displays the puzzle after the solution is found, and thus your recursive-backtracking method should not display it.

• a collection of four sample puzzle files:

  • two puzzles with only one solution (puzzle1.txt and puzzle2.txt)
  • no_solution.txt, which has no solution
  • multi_sol.txt, which has multiple solutions.

Your task

Complete the Puzzle class in the ways described above so that it can be used to solve Sudoku puzzles using recursive backtracking.

In addition to completing the methods mentioned above, you should also add to the Puzzle class whatever additional fields or methods that are needed to efficiently maintain the state of a Sudoku puzzle and to solve it using recursive backtracking. In particular, we recommend adding two fields:

• one to keep track of whether a given row already contains a given value

• one to keep track of whether a given column already contains a given value.

For full credit, you must use your additional fields and methods to avoid iterating over the Sudoku board unnecessarily.

Additional hints and suggestions

• Take advantage of the first template in the notes for recursive backtracking — the one in which only one solution is found.

• As mentioned above, the recursive solveRB() method takes a single parameter n that represents the number of the cell that the current invocation is responsible for. You should use n to compute the row and column indices of the current cell as follows:

  int row = n / DIM;
  int col = n % DIM;
  

  where DIM is the class constant that we’ve provided for the dimension of the puzzle.

• We highly recommend that you add a non-static method that you can use to check the constraints of the puzzle before you attempt to assign a value to a given cell. This method will be similar to the isSafe method from the n-Queens code that we discussed in lecture.

• Make sure that you take advantage of the subgridHasValue field — along with the fields that you will add to keep track of the values in a given row and a given column of the puzzle — when deciding whether a particular value can be assigned to a particular cell. You should not scan through the puzzle to determine if a given value is valid. See the notes for n-Queens for another example of efficient constraint checking.

• Make sure that you use the addValue() and removeValue() methods when updating the state of the puzzle, and that you add code to these methods as needed to update the fields that you add to the Puzzle class.

• Make sure that you don’t attempt to assign a new number to cells that are filled in the original puzzle — i.e., cells whose values are fixed. Your solveRB() method will need to skip over these cells somehow.

Testing your code

Use the provided sample puzzles to test your code.

For example, here’s what you should see if you use the program to solve the puzzle found in puzzle1.txt:

Please enter the name of puzzle file: puzzle1.txt

Here is the initial puzzle:
-------------------------------------
|   | 4 |   |   |   | 3 | 7 |   |   |
-------------------------------------
|   | 8 | 9 | 7 |   |   | 1 |   |   |
-------------------------------------
|   |   |   |   |   | 4 | 2 |   |   |
-------------------------------------
|   |   |   |   |   |   |   |   | 1 |
-------------------------------------
| 6 |   |   | 5 | 1 | 8 |   |   | 9 |
-------------------------------------
| 2 |   |   |   |   |   |   |   |   |
-------------------------------------
|   |   | 5 | 3 |   |   |   |   |   |
-------------------------------------
|   |   | 6 |   |   | 1 | 9 | 4 |   |
-------------------------------------
|   |   | 1 | 2 |   |   |   | 6 |   |
-------------------------------------

Here is the solution:
-------------------------------------
| 1 | 4 | 2 | 9 | 8 | 3 | 7 | 5 | 6 |
-------------------------------------
| 5 | 8 | 9 | 7 | 2 | 6 | 1 | 3 | 4 |
-------------------------------------
| 7 | 6 | 3 | 1 | 5 | 4 | 2 | 9 | 8 |
-------------------------------------
| 9 | 5 | 8 | 4 | 3 | 2 | 6 | 7 | 1 |
-------------------------------------
| 6 | 3 | 7 | 5 | 1 | 8 | 4 | 2 | 9 |
-------------------------------------
| 2 | 1 | 4 | 6 | 9 | 7 | 5 | 8 | 3 |
-------------------------------------
| 4 | 7 | 5 | 3 | 6 | 9 | 8 | 1 | 2 |
-------------------------------------
| 3 | 2 | 6 | 8 | 7 | 1 | 9 | 4 | 5 |
-------------------------------------
| 8 | 9 | 1 | 2 | 4 | 5 | 3 | 6 | 7 |
-------------------------------------

If your code isn’t working, see the PS 1 FAQ for suggestions of steps you can take to debug it.

Submitting your work for Part II

You should submit the following files:

• ArrayBag.java
• StringRecursion.java
• Puzzle.java

Here are the steps:

1. Click on the name of the assignment in the list of assignments. You should see a pop-up window with a box labeled DRAG & DROP. (If you don’t see it, click the Submit or Resubmit button at the bottom of the page.)

2. Add all three files to the box labeled DRAG & DROP. You can either drag and drop the files from their folder into the box, or you can click on the box itself and browse for the files.

3. Click the Upload button.

4. You should see a box saying that your submission was successful. Click the (x) button to close that box.

5. The Autograder will perform some tests on your file. Once it is done, check the results to ensure that the tests were passed. If one or more of the tests did not pass, the name of that test will be in red, and there should be a message describing the failure. Based on those messages, make any necessary changes. Feel free to ask a staff member for help.

   Note: You will not see a complete Autograder score when you submit. That is because additional tests will be run later, after the final deadline for the submission has passed. For such problems, it is important to realize that passing all of the initial tests does not necessarily mean that you will ultimately get full credit on the problem. You should always run your own tests to convince yourself that the logic of your solutions is correct.

6. If needed, use the Resubmit button at the bottom of the page to resubmit your work. Important: Every time that you make a submission, you should submit all of the files for that Gradescope assignment, even if some of them have not changed since your last submission.

7. Near the top of the page, click on the box labeled Code. Then click on the name of each file to view its contents. Check to make sure that you see the code that you want us to grade.

Last updated on February 10, 2026.