Data Structures and Algorithms

Lab 1: Gitting Started with C++

Due on Wednesday, September 7th at 11:59 PM. This is an individual lab. You are to complete this lab on your own, although you may discuss the lab concepts with your classmates. Remember the Academic Integrity Policy: do not show your code to anyone outside of the course staff and do not look at anyone else’s code for this lab. If you need help, please post on the Courselore forum or reach out to the course staff. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

In this lab, you will:

  • Learn how to use Git, a popular version control system.

  • Write a C++ program using files and arrays.

This lab comes in two parts; please be sure to complete both. Please read this lab carefully as it prepares you for all of the labs you will be completing this semester and includes instructions for making sure that you have submitted your work properly!

Part I: Gitting Started

Throughout this course, we will be using a version control system known as Git. The purpose of a version control system is to track changes to software over time. Each week, you will use Git in this class to submit your homework.

We will learn about Git throughout the course of the semester. This part of the lab will teach you just what you need to know to complete the first few assignments.

About Git

Git Logo

A Git repository is a directory containing files that are managed by Git. This looks just like a normal directory under most circumstances, but it contains a hidden .git subdirectory (that you generally shouldn’t touch). By using the git command inside of a repository, you can manage the files in that directory.

Git is a distributed version control system: there can be multiple different copies of the same repository on different computers, some of which might contain different information than others. When developing software, we occasionally use the git tool to move information from one copy of a repository to another. Two operations you’ll be performing in this lab are cloning (which creates a copy of a repository) and pushing (which sends your changes back to the original repository).

About GitHub

GitHub Logo GitHub Logo

GitHub is a popular website that stores and manages Git repositories. Software developers can keep their repository on GitHub and then copy content to and from it from their own computers. We will not be using that website, although we will be using something very similar. Instead, we will use Swarthmore’s own GitHub site at https://github.swarthmore.edu.

In order to start using the Swarthmore GitHub website, you should follow the one-time setup instructions on Professor Newhall’s webpage. Note that these are one-time instructions; if you have already followed them for a different course (such as CS31), you don’t need to do so again.

Cloning a Repository

For the labs in this course, you will be using repositories that we have already created; this is similar to how students use the update21 script in CS21 to fetch the initial files for a given assignment. That repository — the directory of files we have created for you — exists on the Swarthmore GitHub site. To edit those files, you will have to clone the repository into your home directory on the CS lab machines. You can make the clone by running this command:

git clone git@github.swarthmore.edu:cs35-f22/lab01-<your-username>.git

Make sure to replace <your-username> with your Swarthmore username. For instance, you might write

git clone git@github.swarthmore.edu:cs35-f22/lab01-student1.git

if your Swarthmore username were student1. (It isn’t.)

Running the clone command will cause git to create a directory named e.g. lab01-student1 in your current directory. You should cd into that directory now.

Editing Files

Your newly-cloned repository contains several files; we will edit one named Questions.txt now. Use your favorite editor (e.g. emacs, vim, atom, etc) to open Questions.txt and answer the questions it contains.

Once you are finished, run 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:   Questions.txt

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

This indicates that changes have been made to the file named Questions.txt but that Git has not yet been told about those changes. In order to record the changes that we have made, we must commit them. Run the following commands:

git add Questions.txt
git status

You should now see something like this:

On branch master
Your branch is up-to-date with 'origin/master'.
Changes to be committed:
  (use "git reset HEAD <file>..." to unstage)

	modified:   Questions.txt

This indicates that Questions.txt has now been "staged"; that is, it will be part of the next set of changes we create. In a more complicated scenario, we might want to run git add several times or do something else more complicated to create a single "change". We use git add to add the changes for certain files to the staging area in order to create a new version of our directory.

In this case, the only file we’re changing is Questions.txt, so we’re ready to create our change. Run the following command:

git commit -m "Answered the questions."

This command will create and record the change. It will attach the comment (here, "Answered the questions.") to the new versions of our files. If we run git status now, we see something like this:

On branch master
Your branch is ahead of 'origin/master' by 1 commit.
  (use "git push" to publish your local commits)
nothing to commit, working directory clean

The message "working directory clean" indicates that our Git repository knows about all of the changes that we’ve made. You can even look at the history of the changes you have made by running git log. (If you do, you can exit the log viewer by pressing q.)

Pushing Your Changes

Remember: your directory on the CS network is only a copy of the "real" repository stored on the Swarthmore GitHub site! At this point, your copied repository is aware of your new changes, but the Swarthmore GitHub version is not. We can see this because the previous git status message included "Your branch is ahead of 'origin/master' by 1 commit.", which tells us that we have a commit that the GitHub does not. To send the commit that we have made to the Swarthmore GitHub, we can run git push.

Counting objects: 3, done.
Writing objects: 100% (3/3), 209 bytes | 0 bytes/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To git@github.swarthmore.edu:cs35-f22/lab01-student1.git
 * [new branch]      master -> master

Now, git status looks like this:

On branch master
Your branch is up-to-date with 'origin/master'.
nothing to commit, working directory clean

The git push command attempts to send every new commit we have made back to the original place from which we cloned our repository.

Double-Checking Your Push

To be certain that the Swarthmore GitHub website has your changes, visit your repository on that webpage. The URL will be https://github.swarthmore.edu/cs35-f22/lab01-<your-username> (again replacing <your-username> appropriately). If everything worked out, you should be able to view the GitHub copy of Questions.txt by clicking on the like-named link on that page. Make sure that the contents of that file match what you expect.

Summary

In order to use Git to update your lab repository, you should perform the following steps:

  1. Clone the repository (only necessary once per lab!)

  2. Make changes to your files

  3. git add each file you changed

  4. git commit -m "message" to create a commit (include a brief message that explains the changes you made)

  5. git push to send your changes to the Swarthmore GitHub

  6. Repeat steps 2-5 as necessary until you are satisfied with your repository

Part II: Number Summaries

Next, you will create a C++ program to read a list of numbers from a file and produce some summary information from it. You will submit your work by pushing it to the Swarthmore GitHub repository. Remember: we will only grade what appears in the GitHub repository, so make sure to git push!

The Task

Your task is to create a program which performs the following tasks:

  • Prompts the user for the name of a file.

  • Reads the contents of that file — a sequence of numbers — into an array.

  • Prints out a series of summaries regarding that sequence.

The files you will read all have the same format. The first number appearing in the file indicates how many numbers the file contains. The rest of the numbers in the file are the numbers to summarize. For instance, if a file contains

4
5 10 18 3

then the sequence we want to read contains the four numbers 5, 10, 18, and 3. You are guaranteed that all of the numbers in the file are non-negative; you are also guaranteed that there are at least two numbers.

Once you have read all of the numbers in the file, you should print the following summaries:

  • The last number in the sequence (here, 3).

  • The largest number in the sequence (here, 18).

  • The number of items in the sequence that are less than 10 (here, 2).

  • The average of all of the numbers in the sequence using a float (here, 9.0).

You are required to write at least three functions other than main to complete this task. Those functions should not print any values; they should return information for main to print.

You should compile your program using the following command:

clang++ -std=c++11 -o numberSummary numberSummary.cpp

Then, you can run your program with this command:

./numberSummary

Example

Here are two example runs of the above program:

  • Please enter the name of your file: test_data/numbers1.txt
    The last number is 2.
    The largest number is 9.
    There are 4 numbers less than 10 in the sequence.
    The average is 6.
  • Please enter the name of your file: test_data/numbers3.txt
    The last number is 57.
    The largest number is 99.
    There are 5 numbers less than 10 in the sequence.
    The average is 45.8.

Your output doesn’t have to look exactly like this, but it should produce the same results.

Approaching the Task

It’s always good to plan out what you intend to write before you write it. What functions will you need? How will you read and store your data?

In this assignment, we have the following suggestions:

  • Start by opening the file and reading the first number, which tells you how many elements are in the sequence. Then, you must dynamically allocate an array large enough to hold them all. (Do not use static allocation for the array. Refer to the lecture notes if you are unsure of the difference.)

  • Don’t try to do everything at once. For example, you might start by reading all of the numbers into an array and then simply printing them all back out again. You don’t have to keep the code that prints the numbers out, but this will help you be sure that you read them in properly before you do anything more complex with them.

  • Use the Top-Down Design (TDD) skills you learned in CS21. Decide what functions you want to write. What inputs should they take? What should they return? What is the purpose of each function? Answer these questions before implementing the functions.

  • Every time you get something useful written, then git add, git commit and git push! You can push as many times as you want and each push is a copy of your work. If you later find that you’ve made changes you regret, you can always go back to an old version that GitHub will keep for you.

Comment Your Code

As you implement your lab, provide comments describing what each piece of code does.

/* don't forget includes here */
#include <iostream>

using namespace std;

/* sayHello
 * a simple function that prints a greeting
 *   @param name: the name of the person we're greeting
 *   @return: nothing
 */
void sayHello(string name) {
  cout << "Hello " << name << endl;
}

...

Remember to Add, Commit and Push

Once you are finished writing the above programs, remember to add, commit and push them! You can double-check your submission by looking at the GitHub website. We will grade what is shown there by the due date, of course!

Questionnaire

Once you have submitted your lab, please make sure to complete its corresponding questionnaire. The questionnaire will typically take less than a minute and helps us to understand how much work the labs are so we can adjust appropriately. Completing the questionnaire is part of your participation grade, so don’t forget to fill it out!