Description

CSCI241 Lab 4 Solved

1 Overview

Thinking recursively is an important skill, and it does not come easily to most students. This
lab is intended to give you practice implementing various recursive methods. First, you will
work with some string and integer processing methods, filling in missing pieces at first and then
writing some in their entirety.

Finally, you’ll write some basic methods for a Binary Search
Tree class, which will be further developed in A2.

2 Git and submission for Lab 4

The Github Classroom link for Lab 4 is available in the Lab 4 assignment on Canvas. Clone
your repository as you did for Lab 2; be sure to clone it somewhere outside your other lab and
assignment repositories to avoid having nested local working copies of different repos.

As usual,
you will submit your code for this lab by committing and pushing the completed files to your
remote Lab 4 respository on GitHub before the deadline.

It is recommended that you git add and git commit regularly while developing your code; e.g.,
one or more times per method you implement. When you have something working, git push
your changes to GitHub.
1

3 Writing Recursive Methods

As discussed in lecture, the process of writing recursive methods is often mind-bendingly tricky,
because the method you are writing calls itself. The best way to think about recursive methods
as you’re writing them does not involve tracing the code through the recursive call—because you
haven’t finished implementing it yet!

Instead, you must rely on the specification of the method
to tell you what the recursive call will do—namely, correctly solve a smaller subproblem—when
the method is implemented. Then, assuming that the method implements the spec for the
subproblem call, you can write the method to implement the spec to solve the entire problem.

It’s easiest to break it down into a four-step procedure:

1. Write a precise method specification, including any applicable preconditions and details
of how the method behaves on all possible inputs.
2. Write code to handle any base cases—any inputs for which the problem can be solved
directly without using recursion.

3. For all other cases, define the solution to the larger problem in terms solutions to subproblems. This is usually the hardest step, as it involves coming up with a recursive definition
of your problem.
4. Implement the specification for the larger problem, using recursive calls to solve the
subproblems. When analyzing your code, do not trace your code into the recursive call,
but simply replace the recursive call with what the spec says it should do.

4 Recursion.java

The Lab 4 repository contains two files; the first one you’ll be working in is Recursion.java
under the directory src/main/java/lab4/. You will implement the following methods. In many
of these methods, some of the four steps have been done for you.

Testing The Recursion class’s methods will be tested using JUnit and Gradle just like Assignment 1 and Lab 2.
1. int len(String s): Compute the length of a string, without using the String’s length
method.

Steps 1 (spec), 3 (recursive definition), and 4 (implementation of the spec in the
recursive case) have been done for you: you simply need to fill in the condition for the
base case. Replace the true in the if statement’s condition with the correct base case
conditional expression.

2. countE(String s): Count the number of occurrences of the character ’e’ in the String
s. Steps 1 (spec) and 3 (recursive definition) have been done for you. Complete steps 2
and 4 to finish implementing the method.

3. int sumDigs(int n): Sum the digits in the decimal representation of an integer n. Steps
1 (spec), and 2 (base case) have been done for you. Complete steps 3 and 4 to finish
implementing the method.

4. String reverse(String s): Return the reverse of a string. Step 1 (spec) has been done
for you. Complete steps 2, 3, and 4 to implement the method recursively.
2
5. The remaining methods in Recursion.java (below the main method) are not required for
Lab 4. They are provided for additional practice/challenge to complete on your own time
if you wish.

5 BST.java

In A2 you’ll be implementing a Binary Search Tree. As a warmup, you’ll write some basic tree
processing methods.
Remember that when thinking about recursion in trees, it’s important to think of the left and
right children not as nodes, but as subtrees.

A typical recursive tree method will do some
processing on the root, one or more subtrees, and possibly some work to combine the results of
that processing into a solution to the larger problem.

BST.java, under the directory src/main/java/lab4/, contains class BST, which has two fields
root and traversal, of type Node and String respectively. Node is an inner class of BST,
which means it’s a class whose definition is nested within the BST class.

This simply means it’s
a helper class that is not intended for use outside the BST. The tree processing methods you’ll
write will be nonstatic members of the BST class.

Because we are writing our methods as public methods of BST but we’ll be operating recursively
on Nodes, many of the public methods will have associated private helper methods that take a
Node as an argument. Complete the following methods in BST.java.

Testing Test code for this part is written for you (you’re welcome!). BST.java has a special
constructor that takes an int and generates various test trees, and the main method tests the
methods below on each tree. Test your methods frequently and make sure your code passes all
the tests.

1. First, implement boolean isLeaf(Node n) method. This does not require recursion.
Notice that there is not a precondition specifying that n can’t be null.
2. The public int size() method of BST takes no arguments, but simply calls a private
helper method int size(Node n) that calculates the size of a tree rooted at the given
node.

Getting the size of the whole tree is as simple as calling size(root). Implement
the private size(Node n) helper method. Steps 1 (spec) and 3 (recursive definition)
have been done for you.

3. Implement the three canonical recursive tree traversals: inOrder, preOrder, and postOrder.
For these traversals, we will not be printing each node value but instead accumulating
the nodes values in the string traversal. As before, the implementation for each is done
in the helper method that takes a Node n as its argument. Step 1 (spec) has been done
for you.

4. Implement the int height(Node n) helper method to calculate the height of the tree
rooted at n. Notice that the specification defines a special case in the definition of height:
an empty tree (that is, a tree with no nodes) is defined to have a height of -1. Step 1
(spec) has been done for you.

CSCI241 Lab 5 Solved

1 Overview

In this lab, you’ll implement AList, an ArrayList-like dynamic array class that automatically
expands its underlying storage array as needed. Because this is a useful data structure for
storing all manner of data types, you’ll be making the AList generic, so that it can contain any
single type of object.

 

2 Git and submission for Lab 5

The Github Classroom link for Lab 5 is available in the Lab 5 assignment on Canvas. Clone
your repository as usual; be sure to clone it somewhere outside your other lab and assignment
repositories to avoid having nested local working copies of different repos.

As usual, you will
submit your code for this lab by committing and pushing the completed files to your remote
Lab 5 repository on GitHub before the deadline.

It is recommended that you git add and git commit regularly while developing your code;
e.g., one or more times per method you implement. When you have something working,
git push your changes to GitHub.

3 AList Overview

The AList class is modeled after Java’s ArrayList class. The functionality you will implement is
fairly simple: the AList uses an array to store its contents, keeps track of its own size, and has
various accessor and mutator methods. Notice that the size field is the number of elements in
the list, which is not necessarily the same as the length field of the underlying storage array
(which we’ll refer to as the capacity).

The type of the underlying storage array is a generic type placeholder, T. You’ll find that you
never need to worry about what type T actually refers to, because the AList behavior doesn’t
depend on the type of the objects being stored.

The only time this comes into play is methods
that set or return values; instead of a fixed type (e.g., int), we simply use the T placeholder to
refer to whatever type is being stored.

4 Your Tasks

You have four tasks. When you finish implementing each TODO, run the tests using gradle
test and make sure you’re passing the corresponding tests; if not, debug the issue until the
test passes.
1

1. One constructor is provided, which creates an AList with a default underlying storage
array size of 8. Implement the one-argument constructor that allows the user to specify
the initial capacity of the storage array. Run the tests and make sure you pass the
test00Constructors test, i.e., you’re failing only 4 of the 5 tests.

2. If the size of the AList grows beyond the underlying array’s capacity, we need to allocate
a new, bigger array. Implement growIfNeeded and resize according to their specifications. Use the provided createArray method to perform the allocation in
growIfNeeded; then, resize can change the size of the list and call growIfNeeded to
expand the capacity as necessary.

Your code should now also pass test10Resize.
3. Implement put and get to provide array-like indexing into the AList. Your code should
now pass test20PutGet and test21PutGet.

4. Implement append and pop to provide easy methods for adding to and removing from the
end of the list. Keep in mind that adding to the end of the list may cause size to exceed
capacity. Your code should now pass all five tests.

 

 

CSCI241 Lab 8 Solved

1 Overview

In this lab, you will write a program to read an undirected, unweighted graph from a text file
into an adjacency matrix and output the number of connected components in the graph.

2 Git and submission for Lab 8

The Github Classroom link for Lab 8 is available in the Lab 8 assignment on Canvas. There
is no skeleton code, so your repository will start out empty. You will begin by initializing a
gradle project in your repo, then you will implement a program to count connected components.

Whether or not you finish during lab, make sure to commit and push whatever code you have
at the end of the lab period to receive credit for attending lab.

3 Creating a Gradle project from scratch

In past assignments and labs, we’ve given you a skeleton repository with gradle all set up to
run and test the code. In this lab, you’ll set up a gradle project from scratch.
1. Start by cloning your (empty) repository.
2. Change into the repo directory and run gradle init. You will be prompted to answer
some questions about the project you’d like to create:
• Select application for project type. This will make a project with a run task that
executes some class’s main method.

 

• Select Java for implementation language. This tells Gradle that this is a Java project.
• Select groovy for DSL; specifies that the configuration file build.gradle will be
written in the Groovy language, which is the default and what we’ve been using this
quarter.

• Select JUnit 4 for test framework. Although you won’t be required to write any
tests, this sets up a test task that compiles and runs JUnit tests stored in the test
source directory.
• Name your project lab8

• Use lab8 also for the source package; this means your code lives in the lab8 package
(i.e., has a package lab8; declaration at the top of each code file.
Take a look around your project directory – the init task has created a bunch of stuff
that should look familiar by now. To finish setting up your project like past labs and
assignments we need to do a few more things.
1

3. For Java Application projects, gradle defaults to creating a class called App, stored in
src/main/java/lab8/App.java. Rename this file to be called Components.java. Edit the
file and replace the App class name with Components (and change the main method to
create an instance of Components instead of App).

4. Likewise, Gradle auto-generates an JUnit test class called src/test/java/lab8/AppTest.java.
We won’t be asking you to write any JUnit tests here, so you can delete this file if you’d
like. If you wanted to write some unit tests, you’d want to rename the file to ComponentsTest.java and write test cases in there.

5. The last thing we need to get something running is to tell Gradle that the name of the
class whose main method we want to run with the run task is Components instead of
App. Edit the last line of build.gradle to set mainClassName to lab8.Components.
6. At this point, try the gradle run task. You should see Hello world printed under the
:run task.

7. When running programs with command-line input or output, it’s often annoying to have
gradle’s progress bars and output get in the way. To make some of this go away, create a
file called gradle.properties and include the following line:
org.gradle.console=plain

8. You can also control the amount of output (the log level) using command-line flags, such
as -q for quiet (no output), -i for info (lots of output), and -d for debug (more output
than you know what to do with).

9. Now seems like a great time to commit your changes to git! Because the repo started out
empty, we need to add all the files to our repository. Be sure you git add the following
to your repo:
• build.gradle
• gradle.properties
• settings.gradle

• .gitignore (this file tells git that you don’t want to add the build directory and
the hidden .gradle directory where gradle caches local state)
• src/main/java/lab8/Components.java

Gradle init also generated a wrapper, which allows your gradle tasks to be run on systems
that don’t have gradle installed. On linux, you use the gradlew script and on Windows
you’d use gradlew.bat.

These scripts make use of the .jar file in the gradle directory to
run tasks without help from a local gradle installation. It’s standard practice to include
the necessary wrapper files in your git repository, so also git add the following:
• gradlew
• gradlew.bat
• gradle/wrapper/gradle-wrapper.jar
• gradle/wrapper/gradle-wrapper.properties
2

10. Here are a couple of other noteworthy changes that we’ve used in build.gradle for past
assignments that are not relevant to this lab, but you may find helpful to know about:
• If you want your program to accept user input from the command line, you need to
tell gradle about this by adding something like the following to build.gradle:
run {
standardInput = System.in
}

• If you want to print stuff in JUnit test cases and have it actually show up on the
console, you need to specify:
test {
testLogging {
showStandardStreams = true;
}
}

• A great deal of additional customization is possible by specifying your preferences
in build.gradle. You can learn more from the gradle documentation at http:
//docs.gradle.org.

4 Problem Specification

Implement your program in the Components class. The program takes a single command line
argument specifying a filename. The given file adheres to the format specified below. The
program should: read the file and create an adjacency matrix representation of the graph, then
compute and print the number of connected components in the graph.

You are not required to implement error checking, e.g., for malformed input files or bad
command line arguments.

4.1 Input File Specification

Nodes in this undirected graph are numbered sequentially from 0..|V |. The first line of the
file contains a single integer, specifying the number of |V |, and each remaining line in the file
contains two integers indicating that an edge exists between the two nodes.

4.2 Example

Here’s an example of the program’s behavior. The graph drawing is only for illustrative purposes
– your program does not need to parse or produce drawings.
Graph drawing: input.txt: Sample invocation:
0 4 5 $ gradle run -q –args “input.txt”
| | 0 1 2
1 – 2 3 3 4 $
1 2

Note that “$” denotes the shell prompt, indicating that the program has printed “2” followed
by a newline and then terminated.
3

4.3 Implementation Hints and Guidelines

In this lab, you are given no skeleton code and less specific guidance than usual. First focus
on parsing input correctly; then get a correct implementation of the core algorithm; then use
the algorithm to find connected components.

Leave efficiency considerations until last: 8/10
points are based on correctness. Please comment your code well: if we cannot understand your
implementation, we can’t give full credit for it.

5 Submission

Be sure that all the requisite files listed in Section 3 are included in your repository. Then,
simply commit your final changes and push to GitHub as usual.