algorithm papers

[le yu]

Hello, everyone

There you go:

lecture_apsp gives a overview of the solution to this problem. I guess floyd-warshall algorithm is the one we want to convert it to D&C version.

http://www.seas.gwu.edu/~ayoussef/cs212/dynamicprog.html

(this one is a good warm-up )

Another warm-up material (attached, named APSPwarmup2) provides example of floyd-warshall algorithm

Lecture_Parallelism_DC is a short review about parallel programming and divide-and-conquer. Ans this link: http://www.webcitation.org/5wfSkP1Ia    is a book talks about parallel programming thoroughly.  

R-Kleene_DivideConquer_APSP and Minimizing_communication_in_all_pairs_shortest_paths are two papers improve the the D&C algo of APSP problem.

For the improvement, the above two papers mention the blocked algo (somewhere), I think we don't need to care about that. FYI, it is a way to optimize the data locality and reduce the message passing between processors. Personally I felt there are bunch of unknown there while reading. I am still in learning phase. I feel the papers I read have a gap. The gap between the basic APSP algorithm (like floyd-warshall algorithm) to a D&C algorithm. Please let us know if you find one. Also, some paper above mentions the relationship between the matrix multiplication and the D&C APSP algorithm. I have not look into this field.

In the end , there are some videos online after you search "all pairs shortest path divide and conquer". I did not have chance to look into them. Just let you know in case. 

Good nigh and good morning. 

Le

[Po-Chun Chang]

Let me do a short summary:

In all, you could think Dynamic Programming as Divide-and-Conquer with
cache so as to save the redundant work.
But there is actually no such clear distinct for these algorithm.

In APSPwarmup2, you can see the APSP could be modeled as:
1. Dijkstra from all the point, which is a great waste.
2. Construct APSP with maximum one hop, then two, ... till |V|-1
hops (D^0, D^1, ... D^n-1 in the slide)
3. As 2, but one hop, two hop, four hop, 8... and so on. Think of as
an exponential grow because the operation is associative.
4. Construct APSP by allowing through vertices #1, #2... and so on
till all vertices. You could think as add each vertices one at time
and this one is actually floyd-warshall algorithm.

lecture_apsp is almost the same as APSPwarmup2, except its
presentation and notation are different. Some more thing about
re-weighting is mentioned, but I guess we will not use this here.

R-Kleene_DivideConquer_APSP and
Minimizing_communication_in_all_pairs_shortest_paths are
optimizations, which I only ski through the latter for DC-APSP. Still,
I feel this is a little bit too far as our project.

Lecture_Parallelism_DC: seriously we don't have to worry about this at all.

==

I guess maybe a discussion would be a help to synchronize our
understanding. How about after class, say 4, as Dong dong has
follow-up class from 2:30. Or the rest of us could discuss just after
the class. I now are investigating the GAE platform for two keys:
map-reduce and storage.

Thanks
-Chang

> --
>
>