Due: Monday 8 March 2010, 11:45pm
This assignment should be completed in a team of exactly two students. Instead of forcing anyone to work in a team, however, we will give 1 point of extra credit to all those who complete the assignment in a team (i.e., no extra credit for those who work by themselves). Note that BOTH partners must participate in completing the assignment. This participation should be reflected in the svn commit operations of team members.
In this assignment, you will gain experience with basic software engineering techniques and tools. In particular, you will practice:
This assignment is a lot more open-ended than previous assignments. There is no single good solution. Many solutions are possible.
There are no additional files for this assignment.
Before you can begin your project, you need to setup a repository for your team, and import a new project into the repository. Only one person needs to setup the repository and import the project. You should do it together to learn how it is done.
Once you import the project, each team member will be able to checkout a local copy of the project.
To setup a new svn repository, please follow the steps below:
Before importing a project into svn, it is a good idea to determine the directory structure for your project. We suggest that you use the following structure.
To import your project into svn, please follow the steps below:
mkdir hw6
mkdir hw6/substrings/
mkdir hw6/substrings/src/
mkdir hw6/substrings/test/
svn import hw6 file:///projects/instr/10wi/cse303/teamAA/svn/hw6
Each member of your team now needs to check-out their own copy of the project in their own home directory.
svn co file:///projects/instr/10wi/cse303/teamAA/svn/hw6
After executing this command, you should see the following new directory structure in your home directory
hw6/
hw6/substrings/
hw6/substrings/src/
hw6/substrings/test/
Every time you create a new file in your project, you need to add it to svn. To see the changes that your partner makes, you need to update your local copy of the project. In this question, you will add a file to svn
One team member should create an empty file called hw6/substrings/src/substrings.h and add it to svn with the following commands:
cd hw6/substrings/src/
svn add substrings.h
svn commit -m "Added empty file for our specifications" .
The other team member, should now update his or her local copy of the project with the following command:
cd hw6/
svn update
For practice, the second team member should try to modify the file and commit the changes with the "svn commit" command. The first team member should update her or his local copy of the project to see the new changes. Try it.
You can also commit your changes without the -m option, simply by typing: svn ci In that case, svn will open an editor window. You can type your commit message in that window, save, and quit. You need to set the editor by setting the environment variable SVN_EDITOR. For example, use the following command to change the default editor to emacs: export SVN_EDITOR=emacs. You should add this export commands to your ~/.bashrc to make sure the environment variable is set properly every time you login.
Please see the lecture 11 notes for more information about svn and revision control.
Together with your partner, you will develop the specification for a simple module that computes common substrings. Once you agree on the specification, in Problem 3, one of you will implement the module and prepare white-box tests, while the other one will prepare black-box tests and a framework for automatically testing your module. Later in the assignment, you will reverse your roles.
Here is a vague specification for the module. You should refine the specification with your partner.
We will grade the overall quality and exhaustiveness of your specifications. For example, if you abuse preconditions to avoid worrying about all sorts of corner cases or bad inputs, then we will consider your specifications as not being very good. Same thing if you simply ignore many corner cases. We only ask you to write the specifications for two functions so that you can spend time thinking about what makes a good specification.
Write your specification directly in the file substrings.h. For each one of the two functions, your specification should take the same form as the following example:
/** * Brief one line description of the function. * * Detailed description of the function including... * * Precondition: list any assumptions that your function makes * about the state of the world in which it can be called: i.e., the * conditions that must hold when the function is called. * * Postcondition: * (a) Describe the output of the function for different inputs * The output includes the value that is returned and any arguments * that are modified * * (b) List any other side effects: any data members or global variables that * are modified, under what conditions they are modified, and how they are modified * Do NOT give the details about the implementation. Just list the conditions that * will hold when the function returns. For example, for a function that * sorts a list of integers, the specification could say: "sorts the list * given as argument in ascending order" but NOT "uses quicksort to sort.." * * (b) Describe what the function does when given invalid * inputs (throws an exception, returns NULL, returns an error code, etc.) * * @throws if you are using C++, list any exceptions that you * function throws and describe the conditions under which it throws them. * @param a short description of the first input parameter. * @param b short description of the second input parameter. * @return short description of the value that is returned. */ int example_function(int* a, int b);
Remember that your specification should clearly state what happens for various corner cases.
Your specification should not say anything about the implementation! You will lose points if it does.
In this assignment, you can use either C or C++. If you chose to use C, you only need to specify the two functions described above. If you chose to use C++, you should create a class called Substrings and the functions common_substring and longest_common_substring should be member functions of your class. You should add a specification for your class as a whole. The specification should describe the purpose of the class. It should give any restrictions about how the class can be used. It should indicate if the class is mutable or immutable (i.e., can the data members be changed or not). It should describe the data members of the class (if there are any). All these comments should appear before the name of the class.
/**
* Description of the class.
* Description of any limitations on the use of this class.
* Description of the data members (if there are any).
* Is the class mutable or immutable.
*/
class Substrings {
...
}
For this problem, you and your partner should work separately. One of you should complete problem 3A and the other one should work on 3B.
Make sure to add all your files to svn. Before you commit any changes, make sure the code compiles.
If you are working by yourself, pretend that you are two different people: Alice and Bob. Checkout two different copies of your code. First, pretend that your are either Alice or Bob and complete problem 3.A. Commit your changes periodically as you make progress. Then change personality and complete problem 3.B. Again, commit your code as you make progress on it. It is important that you complete problem 3.A before 3.B (from a pedagogical perspective).
Note: we will examine the svn log messages that you produced. We will grade your svn activity as either: insufficient, minimal, or good. We will also grade the quality of your svn log messages as either: useless or useful, so make sure to write useful messages every time your commit your work. Each message should briefly describe the nature of your changes. For example, after writing the specifications, a commit message could say: "First draft of specifications for module substrings". A later commit message could read: "Added specification for corner case where input string is NULL ". Note that svn will allow us to see the exact time when you committed different changes and the details of the changes between versions of the source code. You will lose points if we see that you created a fake commit history minutes before submitting the assignment. So please make sure to use svn throughout the assignment.
In the directory test, you will develop a framework for testing the substrings module. The framework will perform unit tests on common_substring and longest_common_substring, the two functions that are part of the module specification. You do not need to test any other utility functions that your partner may have implemented. You should not need to look at the module implementation. You should prepare your test cases based on the specification alone. Your tests should thus be black-box tests.
There exist tools that help such unit-testing. These tools exist for many languages: CUnit for C, CPPUnit for C++, JUnit for Java, and more. We encourage you to learn more about these tools. In this assignment, however, you will develop a simple framework manually.
Prepare a file of test-cases for each function. The test suite should cover each equivalence class of inputs. Each file should contain at least 20 tests. Each test should specify a set of inputs and the expected output. Test files for testing common_substring should be of the form
String1 String2 Length ExpectedOutput
Here is an example of the format for test file for test_common_substring:
aaaaccaaaa dddccddd 2 cc
aaaaccaaaa ddd 2 [empty_string]
aacc ccaa 2 aa
aacc NULL 2 [error_code 1]
...
Note that [empty_string] is a predefined token indicating that the output of the function should be the empty string. Please use the same standard in your tests. In our automatic tests, we will be looking for that exact token. Note that we will never use a string that contains this token as an input.
For invalid inputs, you can use any standard to represent the output of the function. The output will depend on your specifications.
The test file for testing longest_common_substring should be of the form:
String1 String2 ExpectedOutput
Then write the following two programs that will test the functions on the battery of tests you prepared in each file:
Each program should take two command-line arguments: 1) the name of a file with test cases and 2) the name of a file where to write the test results. The program should perform all the tests in the file. For each test, the program should write the following information in the output file:
For test_common_substring, the output for each test case should be formatted as follows:
Result String1 String2 Length ExpectedOutput ActualOutput
And as follows for test_longest_common_substring
Result String1 String2 ExpectedOutput ActualOutput
Write a Makefile with targets test_common_substring and test_longest_common_substring to build each of these programs. Add all your files to svn.
In a file called substrings.c, implement the two functions specified in substrings.h.
You must implement each one of these functions yourself. You may not use an existing library that computes these functions directly for you. However, you can use functions from string.h. In particular, you may find the strstr function useful. Do not worry about the efficiency of your implementation!
Use defensive programming. For instance, your functions must check that all parameters meet the specified preconditions. When possible, do not trust the caller to pass correct arguments. One approach for testing preconditions in C is through the use of the macro "assert" (from assert.h). We showed an example of using assert in Lecture 15. You can find the relevant example here. You do not have to use assert. If you are writing in C++, you can use exceptions instead.
We suggest that you start with the function common_substring. The function longest_common_substring should use common_substring.
We will grade the readability and overall quality of your code. We will not grade the performance of your algorithm, so it is better to do something simple and readable than try to find the optimal technique.
Golden rule: Always write as little code as possible and test what you wrote right away!
Even though you are not responsible for writing the black-box tests, as the module implementor, you should perform the appropriate white-box tests on the module. In a file called main.c, you should write a function main containing a sufficient number of white-box tests to ensure that each statement in your functions is executed at least once.
Make sure to create a Makefile to build main. Call this target white_box_tests, and have it build an executable called white_box_tests
All the white-box tests should work before you can move on to the next problem.
Run all your black-box tests on your module. As you perform the tests, you will find errors. As you discover these problems:
Now switch roles with your partner and repeat all the steps in problems 2 through 4 on a different software module. This module simply computes various statistics on a file of homework grades. The module should contain a single function whose vague specification is as follows
Devise the specifications, black-box tests, implementation, and white-box tests for this module. Commit all relevant files to svn under hw6/averages/
In this problem, you have a lot of freedom in choosing the module specifications and how to implement and test your module. We will accept all reasonable solutions. We will grade the overall quality of your specifications, implementation, and tests. Feel free to add comments to your test modules if you want to make sure the TA understands your testing strategy.
In this assignment, extra credit is given to students who work in a group of two.
For this assignment, you only need to commit all your files to svn. We will pick them up from there right after the deadline. If you are going to hand-in this assignment late, please email your TA.
When you commit your assignment, pay close attention to the svn messages, especially lines that contain the character ?. This character indicates that svn does not know anything about a file. This is a sign that the file is not under svn control. If it is a file that you need to submit with your assignment, ? indicates that you still need to add the file to svn.
To test that you committed all the files properly, in your home directory, create a subdirectory called "temp". Checkout a fresh copy of you assignment in that directory. Make sure all the files are there.