Computer Science 385
Design and Analysis of Algorithms

Spring 2019, Siena College

Home     Syllabus     Schedule

You will work with a partner and hand in a paper lab packet for most labs, but for this setup lab, you will need to complete the tasks individually and submit electronically.

Learning goals:

1. To set up an account and to gain a basic familiarilty with the git version control system and the GitHub hosting service.
2. To learn how to use the BlueJ interactive development environment with a git repository.
3. To review the use of some fundamental data structures from the Java API.

GitHub for Source Code Control

We will be using the git distributed version control system for nearly all of our work this semester.

If you are not familiar with the basic idea of version control, this brief video is a good place to start.

In particular, we will be using git repositories hosted on GitHub which are managed by GitHub Classroom.

If you do not already have an account at GitHub, please visit https://github.com/ and create one. Please use your college-issued email address when you create your account (or, be sure your college-issued email address is associated with your account if you already have one), since GitHub offers free unlimited private repositories for academic use. Also, a username that incorporates your real name is probably a good idea. Building up a portfolio of GitHub repositories that contain your work is a good way to impress future potential employers, so make it a username you won't be embarrassed to put on a resume.

Installing/Running Git

You will need to make sure you have Git installed on the computer you plan to use for your programming work this semester. Mac users will have Git at their Terminal window if the Developer Tools are installed. Windows users will need to install Git (which will also install Git Bash). A web search should yield all you need to get these installed.

Working with GitHub and BlueJ

Before you can do this task, you will need to have the GitHub classroom link (sent by email) to be able to create your repository for this lab's work.

You may use any development environment you wish, but these instructions assume you are using BlueJ.

If you are on a PC, launch the "Git Bash" program. If on a Mac, open the Terminal application. On a PC, once it launches, you should see a prompt that looks like this (or something similar in a Mac Terminal):

$ 

Next, create a directory (that's our grown up computer scientist Unix word for what Microsoft and Apple want you to call a "folder") for your work for this course. If you want to name it "algorithms", use the command:

mkdir algorithms

Then change your working directory to that new directory:

cd algorithms

Now, create your GitHub repository for this lab. To do so, open a browser window at https://github.com and sign in. In the same browser, visit the link you received in your email. This should bring you do a page where you can "Accept the setup-lab assignment". Do so. If that worked, the next page will have a link to a GitHub URL which is your copy of this lab's repository. Follow it.

You are now on the main page for your repository. You should see a screen that looks like this:

Let's add your name and your Siena userid to the README.md file in the repository on GitHub. This will help me match up your GitHub userid with your real name and your Siena userid (login name, not your "901" number) in cases where they do not match. To edit README.md, click on its name, then in the window that comes up, click on the little pencil icon near the "Raw", "Blame", and "History" buttons to bring up GitHub's simple editor.

You'll be editing in a simple markup language called Markdown (please click here and read about it). Add your name to the file, then scroll down to the bottom and "Commit changes". You can leave the radio buttons above that set to "Commit directly to the master branch." Once you've commited your changes, you should now see the file displayed with your additions.

To get back to the main view of your repository, click on the "<> Code" tab.

Next, click on the green "Clone or Download" and copy the URL that pops up. Go back to your git bash window and type

git clone ...

replacing ... with the URL you copied from the web page.

When prompted, log in with your GitHub credentials. You should then see some messages, and a new directory will be created. Change into that directory with the cd command, then list the contents with ls. You should see two files: README.md and Hello385.java, which are the same two files that were in the repository on the GitHub site.

Before going further, we have a bit of configuration to do for your git setup in the git bash window. Issue these commands (replacing with your own GitHub username and your email, of course) at the terminal prompt:

git config --global user.name "jcool"
git config --global user.email "jcool@teresco.org"

It's also probably a Good Idea to change your default git editor from vim to the more user-friendly nano. You can issue this command to so do:

git config --global core.editor "nano"

One of the files in your repository is a Java program, so let's bring it up in BlueJ to compile and run it.

First, we need to let BlueJ know that the directory contains a BlueJ project. This is indicated by the presence of a file package.bluej. This file was not included in the starter repository to prevent it from being under Git source code control. You do need it if you're using BlueJ, but it should not be added to Git's control for any of your projects, since it would be likely to lead to merge conflicts, and those are just annoying. To create this file, change into the directory that was created when you cloned the repository:

cd setup-lab-yourgithubname

then use the Unix touch command to create the file:

touch package.bluej

You will need to repeat the creation of the package.bluej file for each repository you clone throughout the semester, if you are using BlueJ.

Now, if you navigate to the directory where you cloned the repository, you should see a "package" icon that will launch BlueJ and open this project. Once it opens, click on the Hello385 class to open the editor. It's a pretty simple Java program. Run it by right-clicking on the class in the object workbench window and choosing the "void main(String args[])" entry.

If all goes well, you should see the "Hello, CSIS 385 world!" printout in the BlueJ Terminal Window.

Now, make a couple changes to the Java program. Put your name in the comment at the top, and add at least one more println statement to print additional messages.

Recompile and re-run your program to make sure it works.

Next, create a new Java class within the same BlueJ project (use the "New Class..." button on the object workbench window). Name the class DataStructures, which will create a file DataStructures.java.

• In your program's main method, declare and construct five data structures from the standard Java API, each of which will contain Integer objects.
  1. An ArrayList
  2. A LinkedList
  3. A stack (which you should construct as an ArrayDeque and declare as a Deque)
  4. A queue (which you should construct as a LinkedList and declare as a Queue)
  5. A PriorityQueue
• Generate a series of 20 random int values ranging from 1 to 100, and add each to all 5 structures. Use the single-parameter add method for all except the stack, where you should use the push method.
• Print the contents of your ArrayList and LinkedList using their toString methods.
• For each other structure, remove and print each integer until the structure is empty. For the stack, use the pop method. For the other two, use the zero-parameter remove method.

A sample output from my version of the program follows. Of course your random numbers will be different.

ArrayList contents: 
[96, 64, 85, 60, 5, 26, 30, 21, 21, 80, 33, 31, 39, 1, 51, 93, 83, 80, 100, 28]
LinkedList contents: 
[96, 64, 85, 60, 5, 26, 30, 21, 21, 80, 33, 31, 39, 1, 51, 93, 83, 80, 100, 28]
Pops from stack: 
28 100 80 83 93 51 1 39 31 33 80 21 21 30 26 5 60 85 64 96 
Dequeues from queue: 
96 64 85 60 5 26 30 21 21 80 33 31 39 1 51 93 83 80 100 28 
Removes from PQ: 
1 5 21 21 26 28 30 31 33 39 51 60 64 80 80 83 85 93 96 100 

So you now have two copies of the repository, one on the GitHub server (the "origin" repository) and one in your account on your own computer or on a lab PC (a "clone"). Later in the semester, you might have multiple clones in various places (maybe your own computer, or in your lab partner's account) and will want to be able to keep them in sync. Your clone has changes (1 new file, and one modified file) that are not in the origin on GitHub.

git knows what's changed, so let's ask it, in the git bash window:

git status

You should see something like this:

On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
  (use "git add <file>..." to update what will be committed)
  (use "git checkout -- <file>..." to discard changes in working directory)

	modified:   Hello385.java

Untracked files:
  (use "git add <file>..." to include in what will be committed)

	DataStructures.java

no changes added to commit (use "git add" and/or "git commit -a")

This means there is one file that git "knows about" that has changed: Hello385.java, and there is a file that git doesn't know about listed under the "Untracked files" header.

Notice that the two .class files (compiled versions of your Java classes that gets generated from the Java files), the package.bluej file, and the .ctxt files also generated by BlueJ are not listed. We don't want to store those in our repository. The stater repository included a file .gitignore that tells git that we don't care about certain types of files. All that said, the DataStructures.java file is one we want to put in the repository (only because it's part of the grading). We can tell git to start tracking it with

git add DataStructures.java

You might get a (hopefully harmless) warning here about line feeds. You can ignore it.

If you rerun the git status command, it should now be listed as a new file.

Once we're happy with a change or set of changes to files in our repository, we need to commit those changes to the repository. In this case, we will issue a command for each file, with an appropriate message in each:

git commit -m "Added name and extra printout." Hello385.java
git commit -m "Practice program." DataStructures.java

Now a git status command should show something like this:

On branch master
Your branch is ahead of 'origin/master' by 2 commits.
  (use "git push" to publish your local commits)

Your changes have been committed to the clone, but they are not yet back up on the origin repository on GitHub. To do that, you will use

git push

This is short for "git push origin master", which says push the changes from this repository to the origin on the master branch. So far, we have not created any branches, so everything is on the master.

If your push command is successful, you should now see your changes reflected on GitHub (in the web page).

One last step: let's make a change right in the GitHub repository and then pull it down to our clone on the PC. Edit the README.md file again to include a bulleted list of the git commands you used in this lab. Use Markdown to make it look pretty. When you are done, include a meaningful commit message and use the green button to commit your changes.

Now the repository on GitHub has changes that aren't in your clone. Back in git bash, we want to "pull down" the changes:

git pull

Now, your README.md local clone should include the changes you made on GitHub.

There are several error messages and other situations that arise commonly when using our Git and GitHub workflow. A document describing common situations and their solutions can be found here. Please refer to this when you encounter problems, and make corrections, suggestions, or requests for solutions to additional problems by submitting Issues and/or Pull Requests to that file's repository.

Grading

This assignment is worth 25 points, which are distributed as follows: