CSCI 136 :: Fall 2020

Data Structures & Advanced Programming

Home | Schedule | Labs | Handouts | Links | CS@Williams

Lab Overview: The Genius of Dummies

The central purpose of this week's lab is to give you some hands-on experience writing code that manipulates a linked structure. Your task is to complete the Laboratory Assignment from Section 9.10 of your text, entitled Lists with Dummy Nodes (pages 215-217). You will start with already working code (a class called LinkedList that extends the structure5 class DoublyLinkedList). The goal is to simplify the code by adding two "dummy" nodes to your LinkedList in order to simplify the implementations of several of the class methods. The Laboratory Assignment in Section 9.10 walks you through this process—you will have the best experience if you follow the instructions in that description carefully!

Pre-lab: Step 0

Before lab, please do the following:

• Watch the lab video and read through the assignment
• Review any course materials on linked lists (particularly doubly linked lists) that were unclear, and bring your questions.

That's it for this week!

Lab Assignment

Complete Laboratory Assignment 9.10, which begins on page 215 of the course textbook. A starter file LinkedList.java will be included in your GitLab repository in addition to a starter file with some sample tests. The tests are not exhaustive, so please add additional tests as you consider the various edge cases.

In addition, answer the five Thought Questions on page 217 of your text. We have included (clarified versions of them) in the file called PROBLEMS.md. Please submit those answers with the rest of your code this week.

Lab Deliverables

For this lab, please submit the following:

• Your well-documented source code in LinkedList.java
• The sample testing file, TestLinkedList.java supplemented with additional tests as you feel appropriate. The sample file has some tests to get you started, but it does not test all edge cases.
• A PROBLEMS.md file that contains answers to the five warm-up/thought questions.

As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program appropriately: include pre/post conditions and assertions where appropriate. We will also be looking at how well you organize your code. Whenever you see yourself duplicating functionality, consider moving that code to a helper method. There are several opportunities in this lab to simplify your code by using helper methods. Think carefully!

checkstyle requirements:

This week, we are expanding checkstyle to encourage you to write modular and reusable code. Let’s first motivate that decision, and then describe the new checkstyle rule.

As a programmer, you should never type the same code over and over again. That would be a waste of your time. The ability to copy/paste useful code makes this tempting, but it is still very bad practice! When you copy code, you copy errors. If you ever fix those errors, you have to remember to fix them in every location. This “fixing” rarely happens. Trust us. We’ve been there.

So what should you do instead? You should write a helper method! Whenever you find yourself writing the same code more than once (it could be a common loop, searching a data structure, computing an equation) you should refactor that code into a method. Then you can call that method many times, but only ever have to fix bugs in one place.

Similarly, if you find yourselves writing a function that is very long, that is problematic. The long function can probably be broken into smaller parts that can then be composed to solve a larger problem. Bonus: you can now reuse those parts to solve other problems!

Breaking long functions into byte-size chunks also has the benefit of making your code easier to read and debug: by isolating functionality inside independent units, you can convince yourself that each of those units is correct in isolation, and then you can more easily convince yourself that the larger problem is correct.

Since we cannot easily check for copy/pasted code, we will use checkstyle to encourage concise methods.

The checkstyle tool will report an [ERROR] if your program has a method that is longer than 30 lines (excluding whitespace and single-line comments). This new rule is in addition to previous style requirements.

In total, checkstyle will enforce the following guidelines:

• All class variables that are not final must be declared private or protected (i.e., no public member variables unless they are constants).
• All public methods must include a “Javadoc” comment (starts with /** and ends with */; it should include descriptions of the function, the arguments, and any pre/post conditions).
• No methods should be longer than 40 lines (exluding whitespace and single-line comments).

To run checkstyle, you would type the following command at the terminal:

$ ./checkstyle

The ./ is peculiar to Unix: it tells the terminal to look for the checkstyle program in the current directory. This command will run checkstyle on every Java program in your directory. To run checkstyle on a specific Java file, type:

$ ./checkstyle SomeFile.java

javac requirements:

In addition to checkstyle, we will continue to enforce proper use of Java generics.

• Compiling your code with javac must not produce the following message:

  Note: YourProgram.java uses unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.
  

This message tells you how to get more information. Recompile your program as follows (replace with the appropriate file name):

$ javac -Xlint:unchecked YourProgram.java 

The output will give you details about the issue.

To fix this problem, make sure that you specify type parameters for every generic class, both when declaring the variable’s type and when instantiating an object. For example, to create a Vector that stores Integer objects, one would type:

    Vector<Integer> intVec = new Vector<Integer>();

Submitting Your Lab

As you complete portions of this lab, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please use the phrase "Lab Submission" as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

• Be sure to push your changes to GitLab.
• Verify your changes on GitLab. Navigate in your web browser to your repository on GitLab. It should be available at https://evolene.cs.williams.edu/cs136-f20/lab03-lists/USERNAME-lab03-lists. You should see all changes reflected in the files that you push. If not, go back and make sure you have both committed and pushed.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. We grade your lab programs anonymously to avoid bias. In your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement "I am the sole author of the work in this repository." in the comments at the top your Java files.