CMPT435 Assignment 5-Bellman-Ford dynamic programming algorithm Solved

Goals (1) to    implement    the    Bellman-Ford    dynamic    programming    algorithm    for    Single    Source    
Shortest    Path    (SSSP)    on    a    few    weighted,    directed    graphs;    
(2) to    implement    a    greedy    solution    to    an    intergalactic    instance    of    the    fractional    knapsack    
problem;    and    
(3) to    analyze    these    algorithms’    performance    in    asymptotic    terms.
Requirements    
and    Notes (1) Modify    your    graph    implementation    from    Assignment    Four    to    model    
directed    and    weighted    graphs.    The    Lile    graphs2.txt    contains    data    
describing    multiple    directed    and    weighted    graphs.    Read    it    and    create    a    
linked    object    representation    for    each    graph.    Then,    for    each    graph,    run    
SSSP    (with    vertex    #1    as    the    single    source)    and    output    the    results.    
Example    graph    
Example    output:    
1    ⇾    2    cost    is    2;    path    is    1    ⇾    4    ⇾    3    ⇾    2.    
1    ⇾    3    cost    is    4;    path    is    1    ⇾    4    ⇾    3.    
1    ⇾    4    cost    is    7;    path    is    1    ⇾    4.    
1    ⇾    5    cost    is    -2;    path:    1    ⇾    4    ⇾    3    ⇾    2    ⇾    5.    
(2) Imagine    you    are    traveling    to    Arrakis    for    a    spice    heist.    You    must    Lill    a    few    
knapsacks    with    as    much    of    the    most    valuable    spice    as    they    will    hold.    
The    Lile    spice.txt contains    the    details    of    available    spice    and    
knapsacks    you    can    use.    Implement    the    fractional    knapsack    algorithm    to    
maximize    your    take.    
Example    output:    
Knapsack    of    capacity    1    is    worth    9    and    contains    1    of    orange.    
Knapsack    of    capacity    6    is    worth    38    and    contains    2    of    orange,    4    of    blue.    
(3) In    your    LaTeX    analysis    document,    explain    the    asymptotic    running    
time    of    both    SSSP    and    fractional    knapsack    and    why    it    is    that    way.

As    ever,    your    code    must    …        
• separate    structure    from    presentation.    
• be    professionally    formatted    yet    uniquely    yours    (show    some    personality)    
• use    and    demonstrate    best    practices.    
• make    me    proud    to    be    your    teacher.
[−∞    if    not]
Resources • Dynamic    programming    is    described    in    our    text    in    section    15.    
• The    greedy    strategy    is    described    in    our    text    in    section    16.2.