Welcome to the AlgorithmsProject350 wiki!

Sorry if this is a bit much, but I love project planning so deal with it...

I'll try and keep track of emails and stuff here as well as discussion we have in person.

Timeline:

Test Plan: 2-25 (CS 350 Hw 3 due 2-19) (CS 321 Hw 3 due 2-23)

Calculate & hypothesize:2-27

Code & Execute:3-2

(CS 350 Hw 4 due 3-5) Analysis & what we learned:3-6

(CS 321 Hw 4 due 3-9 Est.) Diagrams and write-up:3-10

Project Due: 3-12

Proposal

David Cobbley, Andrew Qin, and I are proposing to work on a comparison of shortest path algorithms. To keep the project in manageable scope, we will compare the runtime of two different algorithms to see which is more efficient. In terms of shortest path, we would like to look specifically at shortest route (e.g. in a city). So we'll be looking at directed/undirected, weights of edges, etc, and how these effect the algorithm's efficiency. The two algorithms we were thinking about comparing are Dijkstra's modified algorithm and Bellman-Ford.

Emails:

2/12/15

David: Yea, learning about all the metrics for testing and possible software to do it would be great. If there is anything other than time that we want to look at i.e. space complexity. Looking at parallelization might be too complex for us, or out of scope, I don't know.

So we are comparing Dijkstra's modified algorithm and Bellman-Ford. Can we nail down the specific Dijkstas we're going to use? Should we also compare more than one Dijkstra?

2/12/15

katie: I think maybe we pick one characteristic to compare them with, at least for starters. We could start with time, unless that sounds too boring. I figure they'll be the most info about that. If we do multiple dijktra's, we could compare data structures. (Priority queue, min priority queue).

I do wonder how many algorithms we have to compare to be sufficient for the assignment. If two is enough we might want to stick with that.

2/12/15

Andrew: I think we can use the vanilla dijkstra until we understand it better. I'm going to watch the MIT opencourseware lectures on that and they have a lecture on speeding it up. I'm thinking the Bellman-Ford and Dijkstra variation algorithms are probably well documented with plenty of literature. Let's look up some articles on those algorithms in terms of shortest path.

##2/25/15 Group Meeting: Still to do

• Modify data set(no negatives)
• Get our Dijkstra's to take same source input as our Bellman.
• More on Metrics in Python, but we have a good start.
• Add global incrementers to a copy of the source code to count metrics ourselves & check Pythons metrics.

Got a ton done today. Settled on Python, got a basis for metrics and a Bellman-Ford algorithm to use.

3/6/15

Think we finally settled on Dijkstra code, need to write a wrapper. We will be inserting the B-F source input function into the Dij code, adding a wrapper that will take that data structure (List of lists of dictionary) into a graph that Dij can use.

3/10/15

Andrew

• Pseudocode
• datastructure with expanation

Katie

• correctness proof (notes & internet)
• termination proff
• Big O
• stuff

David

• Bibliography
• Results & what we learned
• testing