CS 2110: Object-Oriented Programming and Data Structures

Assignment 1

A1 consists of a series of exercises to help you transition to procedural programming in the Java language. The problem-solving elements are at the level of lab exercises from CS 1110/1112. The assignment comes bundled with a thorough test suite, so you will know when you have implemented each method’s specifications correctly.

You must work on this assignment independently (no partners)—we want to ensure that every student can write, test, and submit Java code on their own. For this reason, we are also grading this assignment for mastery; if a grader identifies mistakes that you didn’t catch yourself, you may resubmit once to correct them without penalty.

Learning objectives

If you are worried that these exercises seem a bit dry and mathematical, that is a consequence of restricting ourselves to Java’s primitive types (which are mostly numbers). Once we get to object-oriented programming in A2, the problem domains will become richer.

Collaboration policy

This assignment is to be completed as an individual. You may talk with others to discuss Java syntax, debugging tips, or navigating the IntelliJ IDE, but you should refrain from discussing algorithms that might be used to solve the problems, and you must never show your in-progress or completed code to another student. Consulting hours are the best way to get individualized assistance at the source code level.

Frequently asked questions

There is a pinned post on Ed where we will post any clarifications for this assignment. Please review it before asking a new question in case your concern has already been addressed. You should also review the FAQ before submitting to see whether there are any new ideas that might help you to improve your solution.

I. Getting started

You already know at least one procedural language (e.g. Python) with which you should be able to solve the problems on this assignment. If that language is not Java, then the goal is for you to become comfortable with procedural Java syntax, as it compares with what you already know, by practicing it in targeted problems. Start by reading transition to Java on the course website, which provides a focused translation guide between Python, MATLAB, and Java.

Download the release code from the CMSX assignment page; it is a ZIP file named “a1-release.zip”. Decide where on your computer’s disk you want your project to be stored (we recommend a “CS2110” directory under your home or documents folder), then extract the contents of the ZIP file to that directory. Find the folder simply named “a1” (depending on your operating system, this may be under another folder named “a1-release”); its contents should look like this:

a1/
  src/
    cs2110/
      A1.java
  tests/
    cs2110/
      A1Test.java

We assume you have already followed the setup instructions for IntelliJ, possibly in your first discussion section. It is important that JDK 17 has been downloaded.

In IntelliJ, select File | Open, then browse to the location of this “a1” directory, highlight “a1”, and click OK. IntelliJ may ask whether you want to open the project in the same window or a new one; this is up to you, noting that if you choose the same window, whatever project you previously had open (e.g. a discussion activity or old assignment) will be closed.

Just two more steps before you can begin coding: you need to tell IntelliJ which version of Java to use for your project (even if you only have one), and you need to tell it what software to use to run the tests.

  1. From IDEA’s project browser, open “src/cs2110/A1.java”. You should see a banner at the top of your editor saying “Project JDK is not defined”; click the “Setup SDK” link in the upper-right corner, then select the version 17 JDK that you downloaded earlier.
  2. Open “tests/cs2110/A1Test.java”; expect lots of errors to be highlighted in red. At the top of the file will be one or more import statements related to JUnit (e.g. import org.junit.jupiter.api.Test;); you might need to expand the import block to see them. Hover your mouse over the word junit on one of those lines, wait a second for a context popup to appear, then click “More actions…” and choose “Add ‘JUnit 5.8.1’ to class path”. (Do not choose JUnit 4.) Finally, click OK in the resulting dialog.

The red highlights should go away, and you should be able to implement methods and run tests.

Please keep track of how much time you spend on this assignment. There is a comment at the top of “A1.java” for reporting this time, along with asserting authorship.

II. Working with the provided code

Specifications and preconditions

A recurring theme in this course is distinguishing between the roles of client and implementer. For methods, a client is someone who calls a method, and the implementer is someone who writes the method’s body. Although you might function both as client and implementer in a small project, ideally the two roles have no knowledge of one another, so you should keep track of which role you are currently in and “split your brain” accordingly. For most of this assignment you will be in the implementer role.

Each method is accompanied by a specification in a JavaDoc comment. As the implementer, your job is to write a method body that fulfills that specification. Specifications may include a precondition phrased as a “requires” clause. As the implementer, you can assume that the precondition is already satisfied. You do not have to attempt to check the precondition or to handle invalid arguments in any special way. It would be the responsibility of clients to ensure that they do not violate such conditions.

For example, if a specification contains the precondition “nTerms is non-negative”, then the client is never permitted to pass negative arguments to the function. If the client nonetheless does so, the specification promises nothing about the result. Specifically, the specification does not promise that the function will check for non-negativity, and the specification does not promise that any kind of error will be produced. That means the implementer has an easy job: they can simply ignore the possibility of negative arguments.

You might have been taught in previous programming classes that implementers must always check preconditions, or must always produce an error when a precondition is violated. Those are useful and important defensive programming techniques! (And we will see how to employ them in Java soon.) But the point we are making here is that they are not required by the specification. So in this assignment, you do not have to use such techniques, and it’s likely to be easier for you to omit them entirely.

Replacing method “stubs”

The body of each method initially looks like this:

    // TODO: Implement this method according to its specifications.
    throw new IllegalArgumentException();

This is a placeholder—it allows the method to compile even though it doesn’t return a value yet, but it will cause any tests of the method to fail. You should delete these lines as the first step when implementing each method. (We’ll discuss the meaning of these lines later in the course when we cover exceptions, objects, and so forth.)

Use the TODO comments to guide you to work that still needs to be done. As you complete each task, remove the comment line with the TODO since it doesn’t need doing anymore! Temporary comment prefixes like TODO and FIXME are a convenient way to keep track of your progress when writing and debugging code.

Finally, some method bodies contain comments with “implementation constraints.” These are not part of the specification, as they do not affect potential clients. Instead, they are requirements of the assignment to ensure that you get practice with the necessary skills. Violating these constraints will not cause unit tests to fail, but points will be deducted by your grader, so make sure you obey them.

Testing

Test cases for each method are in “tests/cs2110/A1Test.java”. You are encouraged to read the test cases to see what corner cases are considered, but you do not need to add any tests of your own for this assignment.

To run a test case, click the green arrow to the left of the method name, then select “Run”; the results will be shown at the bottom of the screen. To run all test cases, use the arrow to the left of the class name (A1Test). If a test fails with a yellow “X”, that means it returned the wrong result. By reading the messages in the output window, you should be able to determine which case failed and what your implementation computed instead. If it fails with a red “!”, that means it encountered an error (or you forgot to delete the placeholder throw line).

III. Assignment walkthrough

Implement the methods one at a time. As soon as you implement one, run the corresponding test case to verify your work. Do not modify any method signatures (or return types or throws clauses)—not only would that change the class type we provided, but it would make it impossible for our autograder to interoperate with your code. And do not leave print statements in your final submission unless the method specification mentions printing output as a side effect.

Each of the numbered exercises below references a section of the Supplement 1 chapter of the primary course textbook, Data Structures and Abstraction with Java, 5th edition, to which you should have access in Canvas through the “Course Materials” link. That supplement is designed to help students who know how to program, but are new to Java. It is a great resource for making the transition to Java.

1. Regular polygons

[Textbook: S1.29: The Class Math]

The area of a regular polygon with n sides of length s is given by the formula:

$$A = \frac{1}{4} s^2 \frac{n}{\tan(\pi/n)}$$

Implement this formula. You will need one or more math functions and/or constants from Java’s standard library. Read the JavaDoc page for the static methods in the Math class to learn which functions are available. Remember that a Math. prefix is required when calling them (so to compute the absolute value of -5, you would write Math.abs(-5)).

Take some time to explore these functions and get a feel for how Java’s standard library is documented. The functions you are most likely to use later in the course include: abs(), min(), max(), sqrt(), pow(), and the trigonometric functions.

Note: methods dealing with dimensionful quantities (like length and area) should always say something about what units (e.g. meters, acres) those quantities are measured in. In this case, the formula makes no assumptions about units, so the specification simply tells the client that the units of the output are compatible with the units of the input.

2. Collatz sequence

[Textbook: S1.59: The while Statement]

The Collatz conjecture is a fun piece of mathematical trivia: by repeatedly performing one of two simple operations on a positive integer (depending on whether it is even or odd), you always seem to get back to 1. The rules for determining the next number in the sequence are:

Our objective is to sum all of the terms in the sequence starting from a given “seed” number until we get to 1. This involves indefinite iteration, and you should use a while loop for this.

This is also a chance to practice problem decomposition and defining new methods. Declare and implement a method named nextCollatz() that takes one int argument and returns an int value according to the given specification. When you have done this, remove the TODO and uncomment the relevant test case in A1Test (it was commented out because the test case will not compile unless that method is at least declared, preventing you from running tests for other methods in the suite). Tip: there is an IntelliJ keyboard shortcut for commenting and uncommenting whole selections of code; can you find it?

3. Median of three

[Textbook: S1.38: The if-else Statement]

The median value of a collection of numbers is the value that would be in the middle if the collection were sorted. A special case is median-of-three voting, which is used in fault-tolerant systems to decide how to proceed when not all components agree. This small function is actually one of the most commonly-run procedures in SpaceX’s flight software, helping it determine which sensors and commands to trust dozens of times per second.

You need to develop an algorithm for determining which of three numbers is the middle value. The numbers could be in any order, and there could be duplicates. Use a chain of conditional statements (if/else), possibly nested, to find the middle value.

4. Interval overlaps

[Textbook: S1.41: Boolean Expressions]

Intervals are a useful abstraction when working with schedules. For example, if class meeting times are represented as intervals over the seconds of a day, then an overlap would imply that two classes conflict.

This exercise is designed to help you avoid a common “anti-pattern” among new programmers:

if (expr) {
    return true;
} else {
    return false;
}

(here, expr is a Boolean expression, like x > 0). Remember that the conditions used in if statements are expressions that yield a boolean value and can be used anywhere a boolean value like true or false could be used. Therefore, the above code can (and should) be rewritten as:

return expr;

Keeping this in mind, implement intervalsOverlap() using a single return statement.

5. Estimating pi

[Textbook: S1.61: The for Statement]

The Madhava-Leibniz series is an infinite sum of numbers that is related to π:

$$\frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \ldots$$

Observe that the denominators of the terms are the sequence of odd integers and that the sign alternates between plus and minus.

By truncating this series after a finite number of terms, we get an approximation for π (though this particular formula requires many terms for even modest accuracy). Use a for-loop to evaluate this approximation for a specified number of terms (this is an example of definite iteration). Recall that integer division in Java rounds down to another integer, so you may need to cast some numbers to a floating-point type when evaluating the fractions.

As a corner case, note that the sum of zero terms is 0.

6. Palindromes

[Textbook: S1.67: The Class String]

With control structures and primitive types out of the way, it’s time to get some experience with our first aggregate type: String (an aggregate type is one that groups together multiple values, like how a String contains multiple chars). Strings get some special treatment in Java; while they are objects, they are immutable (their contents can’t be changed), which means they behave much like primitive values. And unlike other objects, they have their own literals and even an operator (+ for concatenation). But as a sequence of characters they are like arrays, giving you some early practice with algorithms that iterate over data.

A palindrome has the same sequence of characters when written backwards as when written normally. To examine the ith character in string s, use s.charAt(i). The total number of characters in s is given by s.length(). In Java, the index of the first character is 0, and the index of the last character is s.length() - 1. The specifications for these methods are in the API documentation for String; by calling them, you are now in the client role with respect to the String class.

7. Formatting messages

[Textbook: S1.70: Concatenation of Strings]

A common task in computing systems is to format information to be read by humans. The system may need to support translations in multiple languages, and sometimes words will change depending on the data being explained (e.g. singular vs. plural nouns, “a” vs. “an” depending on the following word, etc.). To manage this potential complexity, it is a good idea to move formatting logic into its own function (Java actually provides a sophisticated infrastructure for managing this in large applications, but that is beyond the scope of this course).

This exercise requires you to concatenate strings and to format numerical data as a string. There are several approaches you can take; the + operator is probably most convenient, but if you have used a format or printf feature in another language, you might be interested in String’s format() method. This is also a good opportunity to get practice with Java’s ternary operator ?:, an awkward-to-read but extremely useful bit of syntax; use this to decide between the singular and plural forms of “item” without using an if-statement.

8. Making a program

Now it’s time to step into the client role. Add a main() method so that the A1 class can be run as a program. Find a way to use at least four of the methods in A1 in combination, then print the final result. Is is okay to be silly here! Ideas include:

You can be creative here and provide arbitrary inputs as necessary, but all four methods must contribute somehow to the final result.

Your program’s printed output should be a complete sentence written in English. It should describe what final operation was performed, what its inputs were, and what the result was (the inputs and outputs should not be baked into the text; they should be the values of program variables or expressions). For example, “The area of a polygon with 4 sides of length 0.5 m is 0.25 m^2.” When you run your program, make sure this is the only output (i.e. that there are no “debugging prints” in the other methods you are calling).

IV. Scoring

This assignment is evaluated in the following categories:

You can maximize the “fulfilling specifications” portion of your score by passing all of the included unit tests (don’t forget to uncomment the ones for nextCollatz()). The smoketester will also run these tests for you when you submit so you can be sure that your code works as well for us as it does for you.

Formatting is a subset of style. To be on the safe side, ensure that our style scheme is installed and that you activate “Reformat Code” before submitting. Graders will deduct for obvious violations that detract from readability, including improper indentation and misaligned braces.

But beyond formatting, choose meaningful local variable names, follow Java’s capitalization conventions (camelCase), and look for ways to simplify your logic. If the logic is subtle or the intent of a statement is not obvious, clarify with an implementation comment.

V. Submission

Double-check that you have provided the information requested in the header comment in “A1.java” (name, NetID, hours worked).

Upload your “A1.java” file to CMSX before the deadline. If you forgot where your project is saved on your computer, you can right-click on “A1.java” in IntelliJ’s project browser and select “Open In”, then your file explorer (e.g. “Explorer” for Windows, “Finder” for Mac). Be careful to only submit “.java” files, not files with other extensions (e.g. “.class”).

After you submit, CMSX will automatically send your submission to a smoketester, which is a separate system that runs your solution against the same tests that we provided to you in the release code. The purpose of the smoketester is to give you confidence that you submitted correctly. You should receive an email from the smoketester shortly after submitting. Read it carefully, and if it doesn’t match your expectations, confirm that you uploaded the intended version of your file (it will be attached to the smoketester feedback). Be aware that these emails occasionally get misclassified as spam, so check your spam folder. It is also possible that the smoketester may fall behind when lots of students are submitting at once. Remember that the smoketester is just running the same tests that you are running in IntelliJ yourself, so don’t panic if its report gets lost—we will grade all work that is submitted to CMSX, whether or not you receive the email.