$30
Software Engineering 265
Software Development Methods
Assignment 3
Programming environment
For this assignment please ensure your work executes correctly on the Linux
machines in ELW B238. You are welcome to use your own laptops and desktops for
much of your programming; if you do this, give yourself a few days before the due
date to iron out any bugs in the C program you have uploaded to the BSEng
machines. (Bugs in this kind of programming tend to be platform specific, and
something that works perfectly at home may end up crashing on a different
hardware configuration.)
Objectives of this assignment
• Revisit the C programming language, this time using dynamic memory.
• Use Git to manage changes in your source code and annotate the evolution of
your solution with messages provided during commits.
• Test your code against the 20 provided test cases from assignment #2.
• Use valgrind to determine how effective your solution is in its management
of dynamic memory.
kwoc3.c: Using C’s heap memory for KWOC
In assignment 2 you used Python to implement an extended version of the KWOC
scheme (i.e., words with identical spelling but different lettercase were considered
the same keyword). For this assignment you are to write an implementation called
kwoc3 to provide the same functionality, but this time using C and using dynamic
memory.
We will, however, re-introduce two restrictions on input in order to help you with
your problem solving for your solution. That is:
• You may assume that keywords will be at most 40 characters long, and you
may use a compile-time constant to represent this.
• You may assume the length of any input line will be at most 100 characters,
and you may use a compile-time constant to represent this.
Note that there is no restriction or upper limit on the number of distinct keywords or
exceptions words, nor is there any restriction on the number of lines of input. (This
is similar to assignment #2.) That is, you are not permitted to use any compile-time
constants for these. Put differently, you are not permitted to statically declare
arrays large enough to hold all the keywords, exception words, and input
lines.
Therefore in order to store keywords, exception words, and input lines, you must to
use either linked-lists or dynamically-sized arrays or both.
In addition to these requirements for your implementation, the program itself now
consists of several files, some of which are C source code, and one of which is for
build management.
• kwoc3.c: The majority of your solution will most likely appear in this file.
Some demo code (protected with an #ifdef DEBUG conditional-compilation
directive) shows how a simple list consisting of words can be constructed,
traversed, and destroyed.
Page 3 of 5
• emalloc.[ch]: Code for safe calls to malloc(), as is described in lectures, is
available here.
• linky.[ch]: Type definitions, prototypes, and code for the singly-linked list
implementation described in lectures. You are permitted to modify these
routines or add to these routines in order to suit your solution. Regardless of
whether or not you do so, however, you are fully responsible for any
segmentation faults that occur as the result of this code’s operation.
• makefile: This automates many of the steps required to build the kwoc3
executable, regardless of what files (.c or .h) are modified. The Unix make
utility will be described in lectures.
Starter versions of these files are in the /home/zastre/seng265/a3 directory.
You must ensure all of these files are in the a3/ directory of your repo, and
must also ensure that all of these files are properly added, committed, and
pushed.
A call to kwoc3 will use identical arguments to that from the first assignment. In the
examples below, the output of kwoc3 is also being compared with what is expected:
./kwoc3 in14.txt -e english-2.txt | diff out14.txt -
./kwoc3 -e latin-2.txt in18.txt | diff out18.txt -
A few more observations:
• All allocated heap memory is automatically returned to the operating system
upon the termination of a Unix process or program (such as kwoc3). This is
true regardless of whether the programmer uses free() to deallocate
memory in the program or not. However, it is always a good practice to write
our code such that we deallocate memory via free() – that is, one never
knows when their code may be re-used in the future, and having to rewrite
existing code to properly deal with the deallocation of memory can be
difficult. A program where all memory is properly deallocated by the
programmer will produce a report from valgrind stating that all heap
blocks were free and that the heap memory in use at exit is “0 bytes in 0
blocks”. valgrind will be discussed during the during labs.
• You must not use program-scope or file-scope variables.
Page 4 of 5
• You must make good use of functional decomposition. Phrased another
way, your submitted work must not contain one or two giant functions
where all of your program logic is concentrated.
Exercises for this assignment
• Within your git repo ensure there is an a3/ subdirectory. (For testing please
use the files provided for assignment #2.) All files described earlier in this
document must be in that subdirectory. Note that starter versions of all these
files are available for you in the /home/zastre/seng265/a3 directory.
• Write your program. Amongst other tasks you will need to:
• read text input from a file, line by line.
• implement required methods for the solution, along with any other
methods you believe are necessary.
• extract substrings from lines produced when reading a file
• write, test, and debug linked-list routines
• write, test, and debug routines for dynamically-sized arrays.
• Use the test files and listed test cases to guide your implementation effort.
Refrain from writing the program all at once, and budget time to anticipate
when “things go wrong”.
• For this assignment you can assume all test inputs will be well-formed (i.e.,
our teaching assistant will not test your submission for handling of input or
for arguments containing errors). I had wanted to throw some error handling
at you, but I think you have your hands full enough with wrangling C into
behaving well with dynamic memory.
What you must submit
• The seven files listed earlier in this assignment description (kwoc3.c,
emalloc.c, emalloc.h, listy.c, listy.h, , makefile).
• Any additional source-code files that you introduce for your solution. You
must take responsibility for ensuring such files are in your git project. If
these files are missing, then the teaching team will be unable to build and test
your solution for A#3.
Page 5 of 5
Evaluation
Our grading scheme is relatively simple.
• “A” grade: A submission completing the requirements of the assignment
which is well-structured and very clearly written. All tests pass and therefore
no extraneous output is produced. valgrind produces a report stating that
no heap blocks or heap memory is in use at the termination of kwoc3.
• “B” grade: A submission completing the requirements of the assignment.
kwoc3 can be used without any problems; that is, all tests pass and therefore
no extraneous output is produced. valgrind states that some heap memory
is still in use.
• “C” grade: A submission completing most of the requirements of the
assignment. kwoc3 runs with some problems.
• “D” grade: A serious attempt at completing requirements for the assignment.
kwoc3 runs with quite a few problems; some non-trivial tests pass.
• “F” grade: Either no submission given, or submission represents very little
work, or no tests pass.