Assignment 3- kwoc3

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.