VectorLinux
November 28, 2014, 05:07:20 am *
Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
News: Visit our home page for VL info. To search the old message board go to http://vectorlinux.com/forum1. The first VL forum is temporarily offline until we can find a host for it. Thanks for your patience.
 
Now powered by KnowledgeDex.
   Home   Help Search Login Register  
Please support VectorLinux!
Pages: [1]
  Print  
Author Topic: hay gice I startid ryting artikels on planetmath k wanna see?  (Read 3897 times)
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« on: May 27, 2008, 04:56:52 pm »

These are my first two. I'd like someone to review them.

http://planetmath.org/encyclopedia/LeslieModel.html

This one needs maybe a few more caveats about when it's acceptable to use, but it's otherwise done. I'm not going to write anything about stochastic Leslie models any time soon, because I'd need a specialist book on ecology and I'm probably not going to study ecology. Bioinformatics is mainly about microbiology.

http://planetmath.org/encyclopedia/DepthFirstSearch.html

This one I just started. The part I did complete is not raw at all though. For the time being, I just need someone to look at my description of the DFS algorithm for undirected graphs. I still need to do the 'pseudocode' definition AND the part about DFS for directed graphs, which will take even more time. Sheesh.

The four questions I'm mainly interested in are "Was it correct?", "Was it comprehensive?", "Was it clear?" and "Was it concise (i.e., no BS)?" Thanks for your consideration.

If these articles were good, I intend to write a more on my favorite subjects: graph theory, probability, modeling, algorithms, programming, abstract algebra and any places where they overlap. They might serve as a bit of a bargaining chip when I apply to Lehigh b/c the higher math curriculum at my current school is almost all calculus and I'm not a calculus wizard by any means.

Also, any recommendations about future topics? I'd love to shed light on something.
« Last Edit: May 27, 2008, 05:01:25 pm by Epic Fail Guy » Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
tomh38
Vectorian
****
Posts: 913



« Reply #1 on: May 28, 2008, 06:18:09 am »

« Last Edit: June 01, 2008, 06:09:05 am by tomh38 » Logged

"I'm doing a (free) operating system (just a hobby, won't be big and professional like gnu) for 386(486) AT clones." - Linus Torvalds, April 1991
overthere
Vectorian
****
Posts: 1281



« Reply #2 on: May 28, 2008, 01:36:29 pm »

Thanks for the interesting reading EFG..
.the DFS lead me to iterative deepening which lead to breadth-first search and then the idea of iterative lengthening search made my head explode..now I have to start all over again..
Logged

Everything Is Relative
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« Reply #3 on: May 28, 2008, 01:59:54 pm »

Thanks for the interesting reading EFG..
.the DFS lead me to iterative deepening which lead to breadth-first search and then the idea of iterative lengthening search made my head explode..now I have to start all over again..

http://aml.cs.byu.edu/~jlc/CS470/index.php/Lecture_13

"On page 79, we mentioned iterative lengthening search, an iterative analog of uniform cost search. The idea is to use increasing limits on path cost. If a node is generated whose path cost exceeds the current limit, it is immediately discarded. For each new iteration, the limit is set to the lowest path cost of any node discarded in the previous iteration"

I'm going to assume this is a variation on DFS (like iterative deepening). I can't find much on the Internets about this algorithm, but based on how it's described, it's probably something like this:

Alice: "Bob, look for a place to eat in town starting from here using a DFS. And don't turn onto a road longer than n miles!
[he comes back] Bob: "Haven't found one."
Alice: "What was the shortest road longer than n miles that you couldn't use?"
Bob: "n+2 miles."
Alice: "Alright, do another DFS, and this time you can take a road up to n+2 miles long."

And so forth. I think that's how it goes anyway. The description of the algorithm doesn't mention anything about relaxation of path length as with Dijkstra's algorithm, so I imagine it's actually pretty straightforward.

But in reality, they probably would have used Yahoo! Maps.
Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
overthere
Vectorian
****
Posts: 1281



« Reply #4 on: May 28, 2008, 02:22:25 pm »

Or a GPS path perhaps..
 apparently lengthing is less usefull as a search stratagy than deepening...I better get a coffee and read all this again..I am not so clever but it is really interesting..
Logged

Everything Is Relative
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« Reply #5 on: May 28, 2008, 05:15:46 pm »

Or a GPS path perhaps..
 apparently lengthing is less usefull as a search stratagy than deepening...I better get a coffee and read all this again..I am not so clever but it is really interesting..

Yes, I've read the same thing.

And the secret, really, is to torture yourself with new information until it sinks in.
Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
mymarkers
Member
*
Posts: 29


« Reply #6 on: May 29, 2008, 01:06:52 pm »

I think the DFS article and definition are rather unclear. To somebody who doesn't already know what DFS is, it doesn't highlight the actual concept of a DFS especially well. It seems too focused on properties of the DFS that can be derived from the definition, as opposed to clearly defining a DFS. For example, the definition does not need any statement about the resulting tree-structure. That can be saved for a list of properties following the definition. Meanwhile, the steps themselves are rather clumsy and obscure the elegant simplicity of a Depth-First Search.

Here's how I'd be inclined to define a DFS:
Given a graph G = (V,E), an unvisited vertex v, and knowledge of which vertices have been visited:
     Mark v as visited.
     For each edge (v,w) (That is, an edge originative from v to w):
          If w has not been visited, then perform a DFS starting from w.
          If w has been visited, then we do nothing.

To DFS an entire graph, we mark all vertices as unvisited, choose the root vertex r, and DFS every unvisited vertex beginning with r.

Notice this definition is general enough to account for disconnected graphs and directed graphs. Also, it highlights the recursive nature of the algorithm. Working with this definition, it should be rather easy to show properties such as the tree structure it produces. It makes it very clear to see how to do more involved computations from a DFS. Every DFS-based algorithm is nothing more than deciding what the pre-visit and post-visit procedure should be at each vertex. Furthermore, it helps to analyze the asymptotic run time.

I haven't done much with the type of math for the other one, so I can't offer much insight there.

Logged
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« Reply #7 on: May 29, 2008, 01:34:56 pm »

I see the DFS primarily as a way of generating a spanning tree (or spanning forest in the case of a directed graph). But I want to use a recursive definition. Hmmm

EDIT: to clarify, in a computer program, I can imagine a depth-first search approach used in some kind of algorithm that might even terminate before it looks at every vertex, but theoretically I see the DFS as a way of generating a spanning forest, maybe containing only one tree. A recursive description of that process is difficult, at least in natural language, because parent vertices come into play. When you consider the audience, it seems better to use the 'true' definition.

AND WHY THE HELL DOESN'T FIREFOX THINK VERTICES IS A WORD?!?!
« Last Edit: May 30, 2008, 12:44:08 am by Epic Fail Guy » Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
tomh38
Vectorian
****
Posts: 913



« Reply #8 on: May 30, 2008, 08:27:26 am »

AND WHY THE HELL DOESN'T FIREFOX THINK VERTICES IS A WORD?!?!

Oooh!  I know the answer to this one:

"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Also, lately I've been seeing the word "indexes" a lot, and all this time I thought it was "indices."  This drives me almost as crazy as when people use the word "criteria" as singular, but not as much as when people use the word "definately."

Ah well, whaddaya gonna do?
Logged

"I'm doing a (free) operating system (just a hobby, won't be big and professional like gnu) for 386(486) AT clones." - Linus Torvalds, April 1991
mymarkers
Member
*
Posts: 29


« Reply #9 on: May 30, 2008, 12:30:39 pm »

I agree that it's important that a DFS produces a spanning tree (or forest) of the graph, and that it's one of the main ideas of DFS. But it's not part of the definition. It's a direct consequence. Distinguishing the two makes it both more clear what DFS does, how it can be used in practice, and theoretical consequences such as generating the tree.

You can use the simple recursive definition to show that the process generates the spanning tree or forest. Then let G = (V,E) be a graph, fix a vertex r as the root of the search. Perform the DFS algorithm on G starting from r with all vertices unmarked. Then the DFS generates a spanning forest of G. (And whatever other properties you're concerned about). Then you prove it. Your current definition is more or less an outline of this proof. Since we're dealing with a recursive process, an inductive proof will be very natural. I think this would clarify how and where the tree comes from.

Also, DFS is inherently a recursive process. It's just a matter of how it's described. Defining it in terms of itself is one way. Your description relying on keeping track of parent vertices implies a stack, which is the signature of a recursive computation.
Logged
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« Reply #10 on: May 30, 2008, 06:07:31 pm »

I agree that it's important that a DFS produces a spanning tree (or forest) of the graph, and that it's one of the main ideas of DFS. But it's not part of the definition.

But I've seen it defined as such in a very good book.
Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
mymarkers
Member
*
Posts: 29


« Reply #11 on: June 02, 2008, 08:36:03 pm »

I've had a chance to think this over, and I've come up with a few ideas that may be relevant.

First, your definition is hinting at an iterative approach to a depth-first search (as opposed to recursive). The need for a stack is circumvented by solving the slightly different problem of identifying a parent vertex for each vertex in the graph. Especially in practice, this is a clever approach to solving the problem, but the algorithm is somewhat more complicated to describe.

I think your definition is valid but poorly phrased, which makes me nervous about details. First, I don't think as it is phrased it actually works. In step 2, you say that if all adjacent vertices have been visited to proceed to step 3, only exploring the parent of the current vertex. Step 3 assumes that there is an unvisited adjacent vertex to v. There are no instructions for what to do when there are none. It should fix it to just repeat step 2 instead of going immediately to step 3. Second, it doesn't seem clear that the algorithm is intended to scan every edge of a vertex to search for unvisited vertices. Termination depends on all vertices being visited, so we better be sure to visit all of them. Arguably, this is implied, but precision is essential for a definition. The interjections about tree edges in (3) and about the spanning tree in (1) distract from the actual definition. Finally, it's just generally disorganized and awkward.

Anyway, there are a number of equivalent definitions. It's reasonable to start with any of them and show they're all logically equivalent. It's a matter of taste and purpose. For the initial definition, I like the recursive one because it's very concise; it doesn't require attention to many technicalities and highlights the recursive nature of the algorithm. Your definition has advantages, too. In practice, iteration would certainly be preferred and it does highlight the tree generated by DFS.

I'm tired and I want to go to bed now. If I have time, I'll try to come up with an iterative definition that's convincing to me and then prove that it is equivalent to the recursive definition. I've also thought of another way to describe the recursive algorithm directly using a stack, but I have a few more details to iron out.
Logged
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« Reply #12 on: June 03, 2008, 02:10:58 am »

I think your definition is valid but poorly phrased, which makes me nervous about details. First, I don't think as it is phrased it actually works. In step 2, you say that if all adjacent vertices have been visited to proceed to step 3, only exploring the parent of the current vertex. Step 3 assumes that there is an unvisited adjacent vertex to v. There are no instructions for what to do when there are none.

Well that was the straw that broke the camel's back. I'm using the recursive definition. Thank you for being so persistent, I might not have noticed that fault otherwise.

btw, all of my objects are and will be world-writable so you can edit them if you have an account
Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« Reply #13 on: June 03, 2008, 12:57:49 pm »

I wrote one on Dijkstra's algorithm and I'm confident it's more readable than my (original) DFS article.

http://planetmath.org/encyclopedia/DijkstrasAlgorithm.html

Maybe I should add illustrations for them. Generally speaking you can see which objects I've added here:

http://planetmath.org/?op=userobjs;id=20292

Since I'm a hardcore cheapskate, I'm going to be uploading a lot of online books as well.
Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
Triarius Fidelis
Vecteloper
Vectorian
****
Posts: 2399


Domine, exaudi vocem meam


WWW
« Reply #14 on: June 05, 2008, 06:13:24 pm »

More on Dijkstra added. Plus two group theory proofs. My proof-writing style is still sophomoric and someone stepped in and changed the style of the identity one. Damned if I don't improve though.
Logged

"Leatherface, you BITCH! Ho Chi Minh, hah hah hah!"

Formerly known as "Epic Fail Guy" and "Döden" in recent months
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2013, Simple Machines Valid XHTML 1.0! Valid CSS!