Algorithms and Data
Spring 2012

Due date: Wednesday, March 21, 2012.
At beginning of lecture

Homework 8

Reading:
Textbook: Read about shortest path algorithms in the
Greedy Algorithm Chapter as well as in the 
Dynamic Programming Chapter.
It is intentional that you read ahead in the book:
in the future you will learn about many more algorithms
by reading books and papers.

Next read about a resource from Berkeley:
Read about the branch and bound pattern:
http://parlab.eecs.berkeley.edu/wiki/patterns/backtrack_branch_and_bound

Read the introduction first:
http://parlab.eecs.berkeley.edu/wiki/patterns/patterns

This is also helpful:
http://parlab.eecs.berkeley.edu/wiki/patterns/graph_algorithms

Learn about connections between longest paths and shortest paths:
http://en.wikipedia.org/wiki/Longest_path_problem

Although the Berkeley Pattern Language is for Parallel 
Programming, we focus on a sequential implementation
of the algorithms, ignoring parallelization opportunities.
end Reading

Claims are of the form:
ShortestPath(Proposer,Niche,f(n,m),t) meaning that
Proposer has an f(n,m) algorithm that
for all directed graphs G =(V,E,L) with integer-valued weights
on the edges in E (represented by L) and in subset 
of directed graphs called Niche,
and for all pairs of nodes v1 and v2 in V
finds the shortest, simple path from v1 to v2 in
f(n,m) time, i.e. in at most time f(n,m) for
all n>t and m>t where n is the number of nodes
and m is the number of edges in G.
A path is called simple if it does not have any 
repeated vertices. 
f(n,m) is a function of two integer arguments which returns
an integer. Express f(n,m) in common mathematical notation
like:
3*m*log(n),
m*n,
5*(2^n)*m, etc.

We assume that the edge weights fit into one memory word
and we don't account for the size of the weights.

We also consider the longest path problem where
shortest is replaced by longest:
LongestPath(Proposer,Niche,f(n,m),t).

Consider the following niches:
ShortestPath(Proposer,AllGraphs,f(n,m),t) 
ShortestPath(Proposer,PositiveWeights,f(n,m),t) 
CHANGE: ShortestPath(Proposer,NoNegativeWeightCycles,f(n,m),t) 
LongestPath(Proposer,AllGraphs,f(n,m),t) 
LongestPath(Proposer,DAG,f(n,m),t) 

For some of those claims there exist polynomial-time algorithms
while for others only exponential-time algorithms are known.

AllGraphs is the set of directed 
graphs with both positive and negative integer-valued weights.

PositiveWeights is the subset of graphs where all
integer-valued weights are positive (> 0).

CHANGE:
NoNegativeWeightCycles is the subset of graphs where
there don't exist negative cycles but negative weights
on edges are allowed.

DAG is the subset of directed graphs that are acyclic.

We use the same set-up as in hw 7 regarding reporting 
running times. The honor code applies again.
A claim is refuted if a shorter (or longer path) exists
or if the running time is longer than claimed.

Note that during the refutation protocol an instance is
a labeled graph G and two nodes v1 and v2.
A solution is a path which must be of minimum or maximum length
and it must be computed within the claimed resource bound.

Also note that your constants will depend on the
programming language and the computer you use.

This homework requires that you do some research 
on the shortest and longest path problem
using your text book and the web.

What to turn in:
The code for the two algorithms that you claim.
One algorithm is for a problem that is polynomial and the
other for a problem that is NP-hard.
If you believe a polynomial algorithm does not exists
give a justification by pointing to a reduction.
In other words, give an argument why you
implemented an exponential or super polynomial algorithm.

On Piazza:
Make 2 claims (for different niches) on Piazza and oppose 2 
claims. 
Choose graphs of appropriate size that your algorithm can easily handle
and that will not be too big for Piazza.
If you want to give a graph that is too big for Piazza,
just put a link to the graph on Piazza.

JSON:
We adapt the graph notation we have used earlier:
http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/sp12/JSON/graphs-in-JSON

We add a third component to each edge which is the edge weight:

{"nodeCount": 6, 
 "edges" : [[0,1,125],[0,5,4567],[3,4,9876]]
}

A path we represent as an array:
[0,6,7,8,9,15,5,1]
Depending on the claim, it represents a shortest or longest path.