Forum

> > Off Topic > Computer Science Stuff
Forums overviewOff Topic overviewLog in to reply

English Computer Science Stuff

3 replies
To the start Previous 1 Next To the start

old Computer Science Stuff

Lee
Moderator Off Offline

Quote
It's been a while since I started college; I'm going to be honest, it's a very humbling experience and met none of my expectations. Nevertheless, it's been great so far and I realized how a lot of the theoretical shit is typically what scares people off from scripting or just problem solving in general. This is just a dump-bin for my thoughts and what not. I do some theoretical computer science, a lot of programming language theory, a lot of applied math.

--------------------------------------------------------

> Intuition behind Topological ordering of an acyclic directed graph.
More >


> A more powerful induction mechanism. ( ∗ New)
https://www.writelatex.com/126221rkjcfw
edited 1×, last 31.03.13 09:21:54 pm

old Re: Computer Science Stuff

fragezeichen
User Off Offline

Quote
This is a horrible post, because:
- you don't state whether E (=E^1?) is given
- you don't state whether G = (V, E) is acyclic
- you don't give a link between P and topological ordering (P_n will also converge if G is cyclic, in fact P_n will converge for any finite graph).
- there is no such thing as "total topological order" (at least according to google). Do you maybe mean total oder?, or topological ordering/sorting?

All I can conclude from this post is that P converges and P may have something to do with topological ordering in some way.

old Re: Computer Science Stuff

Lee
Moderator Off Offline

Quote
@user fragezeichen: A topological order by definition is a total order, the above construction only gives a partial order since only connected components are "comparable". It turns out that all partial orders can be "continuously" extended into total orders in the sense that least upper bounds (and hence limits) are preserved, so if we do the total order construction, the same argument still applies.

I think I specified in the title part that this only works for acyclic and directed graph. Also I gave the definition of such a graph as the pair ranging over vertices and edges, e.g. (V, E). But you're right, I should probably clean this up. I'm a bit spoiled by tex at this point and now I find it a bit weird to typeset anything in normal text.

-----------------------------------------

> A more powerful induction mechanism: Well-founded induction.
https://www.writelatex.com/126221rkjcfw
More >


> Amortized Linear Time Median (and in fact any index) Selection

https://dl.dropboxusercontent.com/u/25316665/median.pdf

I'm pretty sure that this isn't novel (and I glossed over the amortization proof), in fact it's quite easy to deamortize this fully in worst-case linear time (I believe a 6-split scheme will work here rather than the 2 presented).
edited 2×, last 18.04.13 05:54:27 am
To the start Previous 1 Next To the start
Log in to replyOff Topic overviewForums overview