S-22 Sample Problems

Overview

The following sample problems offer a sense of the level of programming proficiency that is required of students who are planning to take S-22 Data Structures. If you do not have the necessary level of proficiency, you may want to consider first taking Computer Science E-10b.

Problem 1 Array practice

Write a method with the header

public static void swapPairs(int[] arr)

that takes a reference to an array of integers arr and swaps adjacent pairs of elements: arr[0] with arr[1], arr[2] with arr[3], etc. For example, consider this array:

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

After calling swapPairs(values), the contents of the values array should be {2, 0, 6, 4, 10, 8}. In an odd-length array, the last element should not be moved. If the parameter is null, the method should throw an IllegalArgumentException.

Problem 2 Object-oriented programming

In this problem, you will implement two classes that could be used as building blocks for programs that manage someone’s appointments and contacts: a class called Date that serves as a blueprint for objects that represent a single date, and a class called Person that serves as a blueprint for objects that represent a single person. In addition, you will implement one method from a client program that uses these two blueprint classes. The sections below outline the steps that you should take.

  1. (0 points) Download Date.java and put this file in the folder/directory that you’re using for your work on this assignment. This file includes some starter code for the Date class the you will write, and we encourage you to read through this code before continuing. In particular, make sure that you understand each of the class constants that we have given you, reading the comments that accompany them.

  2. Implement two static helper methods
    In Date.java, we have given you the code for one “helper” method called dayOfWeekNumber. The method takes three parameters —a month number, a day number, and year —and it returns the number of the day of the week on which the corresponding date falls: 0 for Sunday, 1 for Monday, 2 for Tuesday, etc. For example, November 28, 2013 falls on a Thursday, and thus dayOfWeekNumber(11, 28, 2013) returns 4. (You do not need to understand the algorithm that this method uses.)

    You should implement two other static helper methods:

    • isLeapYear: it should take a year as a parameter, and it should return true if the year is a leap year and false if it is not. Most years that are divisible by 4 are leap years. The one exception is years that are divisible by 100 and not divisible by 400; they are not leap years. For example, 1900 was not a leap year because it is divisible by 100 and not divisible by 400. 2000 was a leap year because it is divisible by 400. (Hint: You can use the modulus operator (%) to determine if a year is divisible by 4, 100, or 400.)

    • numDaysInMonth: it should take a month number and year as parameters, and it should return the number of days in the specified month. This method should make use of the NUM_DAYS array that we have given you. When necessary, it should also take into account whether the specified year is a leap year. For example, numDaysInMonth(2, 2012) should return 29, because there were 29 days in February in 2012.

    You should implement these methods now before continuing, because you will use them in some of the other methods that you will write below.

    Note that these methods (unlike the other methods that you will write) are static, because they don’t access the fields inside an object. Rather, they only make use of the values passed in as parameters. Although these methods are helper methods, you should make both of them public, so that they can be called from outside the class.

  3. Define the fields for Date objects
    Below the starter code in Date.java, add field definitions that allow a Date object to capture the following information:

    • the number of the month (an integer: 1 for January, 2 for February, etc.)
    • the day of the month (an integer)
    • the year (an integer).

    For example, here is what a Date object representing November 28, 2013 (Thanksgiving!) would look like in memory:

    +----------------+
|       +------+ |
| month |   11 | |
|       +------+ |
|       +------+ |
|   day |   28 | |
|       +------+ |
|       +------+ |
|  year | 2013 | |
|       +------+ |
+----------------+

    Note that it has three fields, each of which is an int.

    For now, you only need to define the fields, making sure to protect them from direct access by client code. In the next section, you will write a constructor that assigns values to the fields and ensures that only valid values are allowed.

  4. Implement a Date constructor
    Next, write a constructor for Date objects that takes three integer parameters specifying (in this order) the month, day, and year. It should ensure that only valid values are assigned to the object’s fields, and it should throw an exception if the specified date is invalid. It should do the error-checking itself, because there will be no separate mutator methods for Date objects. In particular, it should ensure that:

    • the year is 1583 or later (a limitation stems from the fact that the Gregorian calendar was first used in October of 1582). We have given you a class constant called MIN_YEAR for this smallest year.
    • the month is between 1 and 12
    • the day is an integer between 1 and the number of days in that month. Take advantage of one of the helper methods that you wrote for part 2.

  5. Implement the basic Date accessor methods
    Once you have defined the fields and constructor, you should then write the following initial set of accessor methods:

    • getMonth, which returns the month component of a Date object as an integer. For the Date shown above, the method would return 11.

    • getDay, which returns the day component of a Date object as an integer. For the Date shown above, the method would return 28.

    • getYear, which returns the year component of a Date object as an integer. For the Date shown above, the method would return 2013.

    • monthName, which returns the name of a Date object’s month. For the Date shown above, the method would return the string "November". This method should make use of the array of month names that we have given you as a class constant. Hint: You should be able to write a single statement that returns the appropriate element of that array.

    • dayOfWeekName, which returns the name of the day of the week on which a Date falls. For the Date shown above, the method would return "Thursday". This method should make use of the array of day names that we have given you as a class constant, as well as the dayOfWeekNumber helper method (see part 2).

    • a toString method that returns a String representation of a Date object. The returned String should have the form “day_of_week, month_name day, year”. For the Date shown above, the method would return "Thursday, November 28, 2013". Like the toString() method that we discussed in lecture, this method should not do any printing; it should simply return the appropriate string.

    Note that all of these methods are accessor methods. Our Date objects are immutable — they cannot be changed after they are created — and thus they have no mutator methods.

    Make sure that your methods are non-static, because they need to access the fields in the calling object.

    You are now ready to use the first client program to test the code you have written thus far. See the section entitled Client programs below.

  6. Add methods for comparing two Date objects
    Define three non-static methods that allow a client to compare two Date objects:

    • an equals method that takes a Date object as a parameter and determines if it is equivalent to the calling object, returning true if it is equivalent and false if it is not equivalent. Two Date objects should only be considered equivalent if they have the same values for each of the components (month, day, and year). If a value of null is passed in for the parameter, the method should return false.

    • a method named isBefore that takes a Date object as a parameter and returns true if the calling Date object comes before the Date passed in as a parameter and false if it does not. For example, consider the following Date objects:

      Date d1 = new Date(12, 31, 2013);       // represents December 31, 2013
Date d2 = new Date(1, 1, 2014);         // represents January 1, 2014

      d1.isBefore(d2) should return true, whereas d2.isBefore(d1), d1.isBefore(d1), and d2.isBefore(d2) should all return false. If a value of null is passed in for the parameter, the method should return false.

    • a method named isAfter that takes a Date object as a parameter and returns true if the calling Date object comes after the Date passed in as a parameter and false if it does not. Note: If you take advantage of other methods that you are writing, this method should be very simple! If a value of null is passed in for the parameter, the method should return false.

    You are now ready to use the second client program to test the code you have written for part 6. See the section entitled Client programs below.

  7. Define the fields for Person objects
    Create a new file Person.java, in which you will create a blueprint class for Person objects. After specifying the class header, add field definitions that allow a Person object to capture the following information:

    • the person’s name (a String object)
    • the person’s date of birth (a Date object)

    Note that the Person class makes use of the Date class that you defined above. For now, you only need to define the fields, making sure to protect them from direct access by client code.

  8. Implement a Person constructor
    Next, add a constructor for Person objects that takes two parameters: a String for the person’s name and a Date for the person’s date of birth (in that order). It should ensure that neither parameter is null, and that the string specifying the name is not empty, and it should throw an exception as needed. It should do the error-checking itself, because there will be no separate mutator methods for Person objects.

    Here is one example of how the constructor will be used:

    Person kate = new Person("Kate Winslet", new Date(10, 5, 1975));

    The variable kate now represents the actress Kate Winslet, who was born on October 5, 1975.

  9. Implement the Person accessor methods
    Once you have defined the fields and constructor, you should then write the following set of accessor methods:

    • getName, which returns the Person‘s name as a String.

    • getDOB, which returns the Person‘s date of birth as a Date.

    • getBirthdayIn, which takes an integer parameter representing a year, and creates and returns a Date object representing the date on which the person’s birthday falls in that year. In other words, it should construct and return a Date object with the same month and day as the person’s date of birth, but with the specified year instead of the year in which the person was born. For example, given the Person object kate defined above, kate.getBirthdayIn(2013) should return a Date object representing 10/5/2013, which was the date of Kate Winslet’s birthday this year. The specified year can be before the year in which the person was born. The only problematic parameter values are years that are smaller than the minimum year for Date objects, but the Date constructor will already check for those, so this method won’t need to perform any error-checking of its own.

      • You will need to use the Date constructor to construct the new Date object that the method will return.

      • To obtain the necessary month and day, you will need to make method calls using the Date object that represents the person’s date of birth — i.e., the Date object that is stored inside the Person object. Note that your code cannot access the fields of the Date object directly, because those fields are private members of another class. That’s why you will need to call the appropriate accessor methods in the Date object.

    • getAgeOn, which takes a parameter of type Date and returns an integer representing the person’s age in years on that date.

      • If the specified Date is before the person’s date of birth, the method should throw an exception.

      • The method should take into account all components (month, day and year) of the Person‘s date of birth and the specified Date parameter when determining the person’s age on that date. For example, consider the following Date objects:

        Date july4 = new Date(7, 4, 2013);
Date birthday = new Date(10, 5, 2013);
Date thanksgiving = new Date(11, 28, 2013);

        If kate is still the Person object mentioned above, kate.getAgeOn(july4) should return 37 — because 7/4/2013 was before Kate Winslet’s birthday in 2013, when she turned 38 — whereas kate.getAgeOn(birthday) and kate.getAgeOn(thanksgiving) should return 38, because the dates specified in those method calls are on or after her birthday in 2013.

    • a toString method that returns a String representation of a Person object. The returned String should have the form “name (born on dob)”, where dob is the String representation of the person’s dob. For the Person object kate defined above, the method would return "Kate Winslet (born on Sunday, October 5, 1975)". Take advantage of the Date toString() method, which will produce the necessary string for the date of birth. Here again, this method should not do any printing; it should simply return the appropriate string.

    All of these methods are accessor methods. Our Person objects are immutable — they cannot be changed after they are created — and thus they have no mutator methods. In addition, we have chosen not to implement our own equals method for this class, which means that clients of the class will use the default equals method when they need to check if two Person objects are equal.

    Make sure that your methods are non-static, because they need to access the fields in the calling object.

    You are now ready to use the third client program. See the section entitled Client programs below.

  10. Complete the BirthdayCalculator client program
    Finally, you will write the code needed to complete the final client program, which reads information from the console about one or more people, and then outputs their birthdays and ages in two different years —the current year, and a year entered by the user. Each age should be the age that the person will turn on their birthday in the corresponding year.

    We’ve written most of this client program for you in a file named BirthdayCalculator.java. Save this file in the folder/directory that you’re using for your work on this assignment. We recommend that you begin by reading through the code that we’ve given you. You can also run the program in its current form, but you will see that it doesn’t currently print the names, birthdays and ages.

    To complete this program, you need to write the body of the method called printBirthdays. We have given you the header that you should use, and the body of the method currently consists of a temporary println statement that indicates that the method is not yet implemented. You should replace that println with your implementation.

    The method takes an array of Person objects and a year as parameters, and it should print the names of the people in the array, along with their birthdays and ages in the specified year. See the sample runs for what this method’s output should look like. For full credit, this method should not do unnecessary work. Rather, it should take full advantage of the methods that you implemented for the Person class to obtain the information that it needs to print.

Client programs
To help you in testing your classes, we have created several sample client programs:

  • DateClient1.java

    • should compile after completion of parts 1–5. Do not open it before then!
    • tests the methods from parts 2, 4 and 5
    • if it doesn’t compile, check your method headers
    • expected output is given here

  • DateClient2.java

    • should compile after completion of parts 1–6. Do not open it before then!
    • tests the methods from part 6
    • if it doesn’t compile, check your method headers
    • expected output is given here

  • PersonClient.java

    • don’t open it until the Person class is completed
    • if it doesn’t compile, check your Person method headers
    • expected output is here

  • the BirthdayCalculator.java program. See part 10 for more detail.

Save these files in the same folder/directory as your Date.java and Person.java files.

Make sure that your constructors and methods are compatible with these client programs. Once you have implemented your classes, the client programs should compile and run without any modification. You may also want to add code to these programs to allow yourself to test your classes more thoroughly.

Implementation guidelines

  • Make sure that your classes provide appropriate encapsulation.

  • Avoid redundant code. Don’t forget that one instance method can call another instance method. Taking advantage of this fact will help you to avoid code duplication and to simplify your code.

  • Employ good programming style. Use appropriate indentation, select descriptive variable names, insert blank lines between logical parts of your program, and add comments as necessary to explain what your code does. In particular, you should add comments to the start of the file and before each method that you write.

Problem 3 Recursion and strings

Note

Prior exposure to recursion is not strictly required, but it is recommended. If you have had little or no prior experience with recursion, you may want to consider taking Computer Science E-10b before you take S-22 Data Structures.

In a file named StringRecursion.java, implement the methods described below, and then create a main() method to test these methods. Your methods must be recursive; no credit will be given for methods that employ iteration. In addition, global variables (variables declared outside of the method) are not allowed. You may find it helpful to employ the substring, charAt, and length methods of the String class as part of your solutions.

  1. public static void printWithSpaces(String str)

    This method should use recursion to print the individual characters in the string str, separated by spaces. For example, printWithSpaces("space") should print

    s p a c e

    where there is a single space after the e. The method should not return a value.

    Special cases: If the value null or the empty string ("") are passed in as the parameter, the method should just print a newline (by executing the statement System.out.println();) and return.

  2. public static String weave(String str1, String str2)

    This method should use recursion to return the string that is formed by “weaving” together the characters in the strings str1 and str2 to create a single string. For example:

    • weave("aaaa", "bbbb") should return the string "abababab"

    • weave("hello", "world") should return the string "hweolrllod"

    If one of the strings is longer than the other, its “extra” characters — the ones with no counterparts in the shorter string — should appear immediately after the “woven” characters (if any) in the returned string. For example, weave("recurse", "NOW") should return the string "rNeOcWurse", in which the extra characters from the first string — the characters in "urse" — come after the characters that have been woven together.

    This method should not do any printing; it should simply return the resulting string. If null is passed in for either parameter, the method should throw an IllegalArgumentException. If the empty string ("") is passed in for either string, the method should return the other string. For example, weave("hello", "") should return "hello" and weave("", "") should return "".