CSCI 136 :: Spring 2021
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:
That's it for this week!
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.
For this lab, please submit the following:
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!
This week, we are expanding
checkstyle to encourage you to write modular
and reusable code. Let’s first motivate that decision, and then describe
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 bite-sized 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.
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:
finalmust be declared
publicmember variables unless they are constants).
publicmethods must include a “Javadoc” comment (starts with
/**and ends with
*/; it should include descriptions of the function, the arguments, and any pre/post conditions).
checkstyle, you would type the following command at the terminal:
./ 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.
checkstyle on a specific Java file, type:
$ ./checkstyle SomeFile.java
In addition to
checkstyle, we will continue to enforce
proper use of Java generics.
javacmust 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
commit your changes and
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
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
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
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.
Remember that if‐for any reason‐you will be submitting your lab beyond submission deadline, you'll need to fill out the Late Lab Form. That form contains a description of the late lab submission policy for the course