« first day (4025 days earlier)      last day (1292 days later) » 
00:00 - 21:0021:00 - 23:00

Ted Shifrin
Ted Shifrin
21:05
@geocalc33 You might review what it means for a group to act on a set. In particular, if $a\ne \pm 1$, does multiplication by $1/a$ map integers to integers?
robjohn
robjohn
@TedShifrin I had mentioned that earlier.
Avra
Avra
What is meant by $k$ successive calls to getSuccessor() method?
Does it mean we are calling the same procedure $k$ times on same or different inputs please?
robjohn
robjohn
yesterday, by robjohn
@geocalc33 if you divide, you probably won't stay in $\mathbb{Z}$
@Avra I would assume it is composing
getSuccessor(getSuccessor(getSuccessor(getSuccessor(x))))
Avra
Avra
21:23
@robjohn. Wow!
@robjohn. So, the innermost would return the leftmost of right subtree of $x$
Then the next call would go all the way up since the leftmost does not have a left or right nodes as its supposed to be a leaf?
robjohn
robjohn
@Avra If getSuccessor(x) returns $x+1$, what I wrote would return $x+4$
successor, not predecessor
Avra
Avra
0
Q: Prove that $k$ successive calls to binary tree successor take $O(k + h) $ time

AvraThis question has been around for while, but I still have a question please. I will discuss the following solution. Given tree successor algorithm below, that given an $x$, it will find it's left-most node of right-subtree of $x$. successor = getSuccessor (rightNode(x)) Fun getSuccessor(Node node...

elementary-number-theory discrete-mathematics algorithms computational-complexity trees
robjohn
robjohn
It should find a leaf, and since they are forcing leftNodes, it seems that is as they say
Avra
Avra
you agree that the solution is $O(k+h)$?
robjohn
robjohn
@Avra I don't see why it would be more
I guess it depends on how the tree is linked.
Avra
Avra
21:34
It's clear why there is $h$ (depth of a tree), but why it's not $k\times h$ please?
robjohn
robjohn
@Avra what is $h$?
Avra
Avra
Given that a tree has $n$ nodes, then $h = \log{n}$
If tree is unbalanced, $h = O(n)$
user image
I found the above solution
robjohn
robjohn
is $h$ then the depth of the tree? Oh, yes, I see it is.
Avra
Avra
@robjohn. Yes it's the depth of the tree
$h = O(n)$ in worst-case scenario
robjohn
robjohn
@Avra for a vine
geocalc33
geocalc33
21:45
@TedShifrin no, but the lattice is sitting in $\Bbb R^2_+$ and I'm not concerned about whether the transformation maps integers to integers
I'm just trying to focus on the flow of the lattice described by the continuous transformation
since the transformation is area preserving for all $a$
it forms a group that works the same as SL(2,R)
(stated as I understand it so far)
There's an argument on a website that explains this for a lattice in $\Bbb R^2$ as opposed to $\Bbb R^2_+$
Ted Shifrin
Ted Shifrin
22:05
I still say you’re wrong. Define the lattice.
geocalc33
geocalc33
while trying to follow the argument it's possible I've misunderstood
Ted Shifrin
Ted Shifrin
In the usual case, it’s $SL(2,\Bbb Z)$ that maps the lattice to itself.
geocalc33
geocalc33
so a lattice in $\Bbb R^2$ is isomorphic to the additive group of $\Bbb Z^2$ and which spans the vector space $\Bbb R$
however $(\Bbb Z^2,\times)$ is not a group
so I can't say that the lattice in $\Bbb R^2_+$ is isomorphic to that non-group
00:00 - 21:0021:00 - 23:00

« first day (4025 days earlier)      last day (1292 days later) »