CS575: Programming Assignment 4

CS575: Programming Assignment 4

1. [90%] Randomly create an undirected complete graph as follows:
• Create n vertices where n is randomly selected between 5 and 10. Display the
selected n value.
• Create an n x n adjacency matrix A. Randomly assign a weight to each edge (i,j)
where 1 ≤ i, j ≤ n. Specifically, make A[i,j] = 0 if i = j. If i ≠ j, assign an integer randomly
selected between 1 and 10 to A[i,j]. Ensure that A[i,j] = A[j,i] since you need to
create an undirected graph. Display the generated adjacency matrix.
For the created undirected complete graph, do the following:
1) [45%] Implement Prim’s minimum spanning tree algorithm by programing priority
queue either as array or heap data structure (Chapter 9). Print all the edges in the
generated minimum spanning tree.
2) [45%] Implement Kruskal’s minimum spanning tree algorithm using the find3() and
union3() functions in the lecture notes (Chapter 10). Print all the edges in the
generated minimum spanning tree.
• Note 1: Please let a user select one of the above two algorithms. Return an error
message, if the selected algorithm is other than the above two algorithms.
• Note 2: You are supposed to implement the algorithms correctly for random
undirected graphs as described above. If your program produces correct results for
some graphs but doesn’t for other graphs, you will get zero.
• Note 3: For grading purposes, don’t pass any parameter to your main() function. You
will lose 10% if you violate this requirement. If everybody follows this rule, grading
may finish earlier.
2. [10%] 10% of the grade will be based on good coding style and meaningful comments.
All    programming    must    be    done    using    C    or    C++    in    Linux where    your    code    will    be    tested.        
Create    a    tar    file    that    includes    (1)    source    code    files,    (2)    a    Makefile    to    produce    an    executable,    
and    (3)    a    readme    file    that    clearly    describes    how    to    run    your    code.    Submit    only    the    tar    file
through    the    Blackboard.        The    name    of    the    tar    file    should    be    yourlastname_yourfirstname
_proj4.tar        (Do    not    use    special    characters    like    #,    @,    or    &,    because    they    have    caused    
Blackboard    problems    in    the    past.)    Suppose    that    your    assignment    files    are    under    the    
directory    of    /your_userid/yourlastname_yourfirstname_proj4/    and    you    are    under    that    
directory    right    now.    To    create    a    tar    file    under    /your_userid    directory,    do    the    following    in    
Linux    command    line:
>cd    ..
>tar    cvf        yourlastname_yourfirstname_proj4.tar        yourlastname_yourfirstname_proj4
To    view    the    content    of    the    created    tar    file,    do    the    following    in Linux    command    line:
>tar    tvf        yourlastname_yourfirstname_proj4.tar
Finally,    read    the    following    policies    carefully:
• All    work    must    represent    each    individual    student’s    own    effort.    If    you    show    your    code    or    any    
other    part    of    your    work    to    somebody    else    or    copy    or    adapt    somebody    else’s    work    found    
online    or    offline,    you    will    get    zero    and    be    penalized    per    the    Watson    School    Academic    
Honesty    Code    (http://www.binghamton.edu/watson/about/honesty-policy.pdf).        
• To    detect    software    plagiarism,    everybody’s    code    will    be    cross-checked    using    an    automated    
tool.
• Your    code    will    be    compiled    and    executed.    If    your    code    does    not    compile    or    produce    any    
runtime    errors    such    as    segmentation    faults    or    bus    errors,    you    will    get    zero.
• The    instructor    and    TA    will    not    read    or    debug    your    code.        The    instructor    and    TA    will    not    
take    a    look    at    an    emailed    code.    If    you    need    general    directions,    show    your    code    to    a    TA    
during    her office    hours.        The    TA    will    not    do    programming    or    debugging    for    you    though.        
The    TA    will    only    help    you    understand    algorithms    to    be    implemented    and    answer    basic    
questions    related    to    implementation.