Splay trees may allow us to do the splay operation when inserting and to be find
nono
(by the way, my advisor has apparently proven years ago that rotatins in AVL tree can not amortise properly; he was happy that the result finally found an application :D)
morning @DaveClarke! I tried to use the tools I linked to on some music with a similar scenario as yours, but all they did was spew out numbers (I expected nice pictures, naive me). Without reading their papers it is probably hard to extract something useful.
@DaveClarke I only have few Eagles songs. It was Sentenced, a now discontinued metal band. I have a live recording of their last concert where a former vocalist performed some songs. So I figured that that would be a good scenario try and detect the change of a band member.
Would have loved to include some results in the answer, but well -- only numbers.
We're not in public beta yet, so there's only about 30 people that visit the site right now, and I think most of the questions we can think of have already been asked
There's only so much seeding we can do - most of our users are answerers, not questioners
Hm, I would like to put a bounty on this question of mine once we go public. However, if nobody proposes a good answer during the periode, Jeffe automatically is awared half of it, despite him not answering the question. Wicked system.
@AlextenBrink Hm, I guess we can maintain a median pointer if we have double-linked threading. We know wether we insert/delete to the left or right and we can also count how many nodes are left or right from the current median. Once the counts are 2 apart, move the pointer by one.
Search in worst-case O(log n) time, which returns a pointer to the tree, and in O(1) it can return a pointer to the minimum, maximum and O(1) other order statistics (such as the mean)
And given a pointer it can do this:
Remove in O(1) time, return successor and predecessor pointers in O(1) time
@AlextenBrink sounds almost too good to be true. So you have to ensure some kind of height-balancing; I am curious how you maintain that during deletiong in (wc?) O(1) time.
I just submitted a few suggested edits to tag wikis on Computer Science, (137–146). All of them were newly created excerpts or wikis. They have been rejected silently: there is no indication of who did the rejection, not even Community. None of the users in the CS chat saw the edits, though one r...
On insertion, you check the depth of the path you take, and if it's too deep, you go back up the tree, figure out where the unbalance is, and then you reform that subtree into a perfectly balanced tree
Deletion is even simpler: you delete the node... and do nothing! Unless you have deleted too many nodes since the last rebalance, at which point you rebalance the entire tree
So that's an O(n) operation every O(n) deletions, and hence O(1)
If you use a threaded tree, or as I did it, store predecessor and successor pointers in every node, you get everything I mentioned above
I ended up at Scapegoat trees as I realized you didn't have time to update any kind of information stored in nodes
If you have predecessor and successor pointers, you can actually do the rebalancing (a constant factor) faster than the method described in the paper (which involves a lot of rotations)
Maybe you can support insertion of elements that are larger/smaller than anything in the tree in O(1) time amortized, using a similar trick to deletion
That is, you save them up in a 'linked list' by just not balancing, and if you perform some other operation, you balance them all at once
Hmm, what if you just forget about balancing at all, and only balance if you search? Only allow insertions given a pointer, and let search return the pointer closest to the key you searched on...
That would make everything O(1), except searching
And arbitrary insertions (which need a search first)
Most of us learned programming using "textual" programming languages like Basic, C/C++, and Java. I believe it is more natural and efficient for humans to think visually. Visual Programming allows developers to write programs by manipulating graphical elements. I guess using Visual Programming sh...
A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing thesis:
Any reasonable model of computation can be efficiently simulated on Turing machines
How...
I like to quote the tooltips of the UP- and DOWN-vote buttons here:
UP: “This question shows research effort; ...”
DOWN: “This question doesn not show any research effort; ...”
I interpret “research effort” not in terms of science, but simply that the person who is asking should state what he ...
Given a labelled transition system $(S,\Lambda,\to)$, where $S$ is a set of states, $\Lambda$ is a set of labels, and $\to\subseteq S\times\Lambda\times S$ is a ternary relation. As usual, write $p \stackrel\alpha\rightarrow q$ for $(p,\alpha,q)\in\to$. The labelled transition $p\stackrel\alpha\t...
A day or two ago, I was able to see upvote- and downvote-counts here on meta. That Feature is gone now.
Was it a bug that it was available or is it a bug that it is missing now?
This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar?
cstheory.SE and math.SE have a link cite in the link popin that offers BibTeX and amsrefs for proper citing of questions and answers.
Can we please get that, too?
Is there a formal/academic connection between an imperative program and algebra, and if so where would I learn about it?
The example I'm thinking of is:
if(C1) { A1(); A2(); }
if(C2) { A1(); A2(); }
Represented as a sum of terms:
(C1)(A1) + (C1)(A2) + (C2)(A1) + (C2)(A2) = (C1+C2)(A1+A2)
...
I am having trouble understanding the definition of primitive recursion. I would like to have clarification of the definition with simple applications of the definition with examples.
The definition of Primitive Recursion is: h(x,0)=f(x), h(x,s(y))=g(x,y,h(x,y)).
The short hand is h=Pr[f,g]. ...
This is a follow-up to some comments at this question
If the new cs-theory-lite site is created (it is still in pre-beta), a tricky issue is which questions here might be migrated there. I want to ask the moderators to show restraint, especially at first, in migrating questions.
One area where...
There are three questions on TCS that have been closed for being of rather low level in the past few ours, might it be worth pointing them in our direction? Not sure which of them would be suitable
OK, so I am trying to prove that the following language is undecidable. The language is
$EQ_{CFG} = \{M_{1}$ and $M_{2}$ are context free grammars and $L(M_{1})$ = $L(M_{2})$
The book the "Theory of Computation" by Michael Sipser provides the following proof for showing that the similar la...
Say I have a string $a \in \Sigma^+$ and some CFG $G$ such that $x a y \in \mathcal{L}(G)$ where $x,y\in \Sigma^*$.
Given the CFG, I'd like to determine a set of characters $C = \{ b \mid xaby \in \mathcal{L}(G)\}$.
For my application, the string $a$ is not much longer than the right hand side ...
I like to quote the tooltips of the UP- and DOWN-vote buttons here:
UP: “This question shows research effort; ...”
DOWN: “This question doesn not show any research effort; ...”
I interpret “research effort” not in terms of science, but simply that the person who is asking should state what he ...
Are we really this inactive, or are the stats broken (again)? On other sites, the stats seem to work fine...
0 visitors per Day?
This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar?
cstheory.SE and math.SE have a link cite in the link popin that offers BibTeX and amsrefs for proper citing of questions and answers.
Can we please get that, too?
Is there a formal/academic connection between an imperative program and algebra, and if so where would I learn about it?
The example I'm thinking of is:
if(C1) { A1(); A2(); }
if(C2) { A1(); A2(); }
Represented as a sum of terms:
(C1)(A1) + (C1)(A2) + (C2)(A1) + (C2)(A2) = (C1+C2)(A1+A2)
...
I am having trouble understanding the definition of primitive recursion. I would like to have clarification of the definition with simple applications of the definition with examples.
The definition of Primitive Recursion is: h(x,0)=f(x), h(x,s(y))=g(x,y,h(x,y)).
The short hand is h=Pr[f,g]. ...
This is a follow-up to some comments at this question
If the new cs-theory-lite site is created (it is still in pre-beta), a tricky issue is which questions here might be migrated there. I want to ask the moderators to show restraint, especially at first, in migrating questions.
One area where...
OK, so I am trying to prove that the following language is undecidable. The language is
$EQ_{CFG} = \{M_{1}$ and $M_{2}$ are context free grammars and $L(M_{1})$ = $L(M_{2})$
The book the "Theory of Computation" by Michael Sipser provides the following proof for showing that the similar la...
Say I have a string $a \in \Sigma^+$ and some CFG $G$ such that $x a y \in \mathcal{L}(G)$ where $x,y\in \Sigma^*$.
Given the CFG, I'd like to determine a set of characters $C = \{ b \mid xaby \in \mathcal{L}(G)\}$.
For my application, the string $a$ is not much longer than the right hand side ...
