Issue 13066044: Inv
DescriptionInv
Patch Set 1 #
Total comments: 6
Patch Set 2 : Line break #Patch Set 3 : Reply to the three inline comments #
Total comments: 45
Patch Set 4 : Responding to comments #
Total comments: 24
MessagesTotal messages: 6
Polam prosze linijki z tekstem, izby latwiej sie bylo odnosic do czegos innego niz caly akapit. https://codereview.appspot.com/13066044/diff/1/per.tex File per.tex (right): https://codereview.appspot.com/13066044/diff/1/per.tex#newcode68 per.tex:68: To simplify the notation, we will write $a \in b$ to denote $a \in [0, b-1]$. Typowa notacja: [b] na [0, b-1]. https://codereview.appspot.com/13066044/diff/1/per.tex#newcode72 per.tex:72: A sequence of pairwise different vertices $(a_0, a_1, ..., a_{m})$ will be said to form a "path" if $t[a_i]=a_{i+1}$ for $i \in m-1$. "pairwise different" -> "distinct" ? "will be said to form" -> "forms" ? "if" -> "iff" ? https://codereview.appspot.com/13066044/diff/1/per.tex#newcode76 per.tex:76: A sequence of pairwise different vertices $\sequencen{a}{m}$ will be said to form a "cycle" if $t[a_i]=a_{(i+1) \bmod m}$ for $i \in m$. See above.
Sign in to reply to this message.
https://codereview.appspot.com/13066044/diff/1/per.tex File per.tex (right): https://codereview.appspot.com/13066044/diff/1/per.tex#newcode68 per.tex:68: To simplify the notation, we will write $a \in b$ to denote $a \in [0, b-1]$. On 2013/08/24 09:56:33, robryk wrote: > Typowa notacja: [b] na [0, b-1]. Done. https://codereview.appspot.com/13066044/diff/1/per.tex#newcode72 per.tex:72: A sequence of pairwise different vertices $(a_0, a_1, ..., a_{m})$ will be said to form a "path" if $t[a_i]=a_{i+1}$ for $i \in m-1$. On 2013/08/24 09:56:33, robryk wrote: > "pairwise different" -> "distinct" ? > "will be said to form" -> "forms" ? > "if" -> "iff" ? Done. https://codereview.appspot.com/13066044/diff/1/per.tex#newcode76 per.tex:76: A sequence of pairwise different vertices $\sequencen{a}{m}$ will be said to form a "cycle" if $t[a_i]=a_{(i+1) \bmod m}$ for $i \in m$. On 2013/08/24 09:56:33, robryk wrote: > See above. Done.
Sign in to reply to this message.
No comments to code yet. https://codereview.appspot.com/13066044/diff/7001/per.tex File per.tex (right): https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode54 per.tex:54: Limiting the numbers that can be stored in our array to the range of the permutation still allows a simple $O(n^2)$ solution. No mention of constant (actually log) space. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode54 per.tex:54: Limiting the numbers that can be stored in our array to the range of the permutation still allows a simple $O(n^2)$ solution. range of the permutation unclear. Maybe "to [n]"? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode60 per.tex:60: Let us say that the permutation is stored in global variables $t$ and $n$ where $t$ is an array and $n$ denotes the size of the permutation. let us say -> assume/... https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode61 per.tex:61: The numbers in the array have to fit in the range $[0,n-1]$ and the array indices are 0-based. fit in is weird here. $t$ is an array on $n$ integers from $[n]$? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode63 per.tex:63: Then the function $invertPermutation$ is called and we will prove that after it returns, $t$ contains the inverse of the permutation given, the function's running time is $O(n^{3/2})$ and, excluding the $t$ array, only a constant number of $\log{n}$-bit words is used. Function names don't seem to belong in the problem stmt. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode65 per.tex:65: \subsection*{Pseudocode} This is like calling a driver's textbook `How to rotate the steering wheel'. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode65 per.tex:65: \subsection*{Pseudocode} A generic overview would be very useful here: someting that tells you that you iterate over all [n] numbers and do _something_ for every one. This naturally segues into small/large cycle distinction. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode67 per.tex:67: Until further notice, consider a simpler but incomplete version of the pseudocode received by removing the lines annotated with "(1)" or "(2)". It's not incomplete. It works, but isn't constant memory. This is very helpful when trying to understand this part. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode72 per.tex:72: Let us call cycles of length at most $4k+1$ the "small" cycles and all the others the "large" ones. Why? You can afford to walk the small ones once for each of their vtxes. This is important at this point of the paper. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode72 per.tex:72: Let us call cycles of length at most $4k+1$ the "small" cycles and all the others the "large" ones. Cycles are defined later. Also, you should say explicitely that you'll treat this as a graph. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode78 per.tex:78: \subsection*{Paths} These things don't seem to be worthy of a subsection each. Maybe have a `preliminary definitions' subsection with all this inside? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode88 per.tex:88: We will say that the sequence of vertices $\sequencen{a}{m}$ forms a segment when $m \in [k+1, 2k+1]$, $t[a_i]=a_{i+1}$ for $i \in [m - 1]$ and $t[a_{m-1}] = a_i$ for some $i \in [k]$. nitpick: s/when/iff/ https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode90 per.tex:90: Please note that there are $k^2$ unlabeled segments with at most $2k$ vertices. There are this many where? In the whole universe? Are there at most this many, at least, or exactly? Is 2k the total number of the vertices or the number of vertices in one segment? Does this describe the case initially or at some point (specify when) of the algorithm? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode94 per.tex:94: Segments of size $2k+1$ will have a special meaning that will be described later. See above. This is eally confusing when you've just said that segments have at most 2k vertices. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode98 per.tex:98: The function $invertLargeCycles$ does one pass over the array $t$ and converts each large cycle to an intermediary structure. Say that you want to avoid doing it twice for any cycle (obvious, but reassuring). https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode99 per.tex:99: The structure is basically the inverse of the cycle with some modifications that allow us both to recognize that this cycle was visited and to repair the cycle later. s/basically// ? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode101 per.tex:101: After this is done, the only thing required is to do a third pass over the array to inverse the small cycles, which is done in $invertSmallCycles$. s/inverse/invert/ https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode105 per.tex:105: Functions $invertPath$, $invertCycle$ and $iterate$ are self-explanatory. This paragraph is pointless. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode109 per.tex:109: Function $isLeader$ takes a vertex on a cycle and returns $true$ if and only if its index is the smallest on the cycle. Time complexity? Actually, consider writing this for every function here. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode115 per.tex:115: If not, a pair of two zeroes is. Lack of verb grates here. What is a pair of three zeroes? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode116 per.tex:116: The function can be implemented in $O(depth)$ running time and using $O(1)$ $\log{n}$-bit words of memory with Floyd's cycle-finding algorithm. Ref to Floyd's algorithm. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode120 per.tex:120: Functions $isALargeCycle$ and $isASegment$ are also self-explanatory. Ditto as for invertPath. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode124 per.tex:124: If $u \in [n]$ and $p$ is the start of the path $(a_{m-1}, a_{m-2}, ..., a_0)$ ending at $i$ where $m > 2k+1$, after the function $makeSegment$ returns, the vertex sequence $(a_{m-l}, a_{m-l+1}, ..., a_{m-1})$ for some $l < m$ forms a segment that encodes $u$ and no other array value is modified except the $l$ values mentioned. Split the sentence. Preconditions, postconditions separately. (See createIntermediaryStructures) "ending at $i$"? I don't understand. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode128 per.tex:128: The functions $prolongSegment$ and $setSegmentCycleLength$ are self-explanatory, too. Ditto. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode132 per.tex:132: Assume that $(a_{m-1}, a_{m-2}, ..., a_0)$ forms a large cycle at the start of the function and $a_0 = i$ is the smallest vertex number. smallest among the vertices of the cycle? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode135 per.tex:135: \item let $b_0, ..., b_k$ be integers such that $0 \leq b_0 < b_1 < b_2 < ... "let"? Do you mean "there exist" or "for every such"? https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode143 per.tex:143: The function $createIntermediaryStructure$ is called exactly once for each large cycle, always with $i$ being the smallest vertex on the cycle. Time complexity?
Sign in to reply to this message.
https://codereview.appspot.com/13066044/diff/7001/per.tex File per.tex (right): https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode54 per.tex:54: Limiting the numbers that can be stored in our array to the range of the permutation still allows a simple $O(n^2)$ solution. On 2013/08/24 10:39:54, robryk wrote: > No mention of constant (actually log) space. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode60 per.tex:60: Let us say that the permutation is stored in global variables $t$ and $n$ where $t$ is an array and $n$ denotes the size of the permutation. On 2013/08/24 10:39:54, robryk wrote: > let us say -> assume/... Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode61 per.tex:61: The numbers in the array have to fit in the range $[0,n-1]$ and the array indices are 0-based. On 2013/08/24 10:39:54, robryk wrote: > fit in is weird here. $t$ is an array on $n$ integers from $[n]$? Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode63 per.tex:63: Then the function $invertPermutation$ is called and we will prove that after it returns, $t$ contains the inverse of the permutation given, the function's running time is $O(n^{3/2})$ and, excluding the $t$ array, only a constant number of $\log{n}$-bit words is used. On 2013/08/24 10:39:54, robryk wrote: > Function names don't seem to belong in the problem stmt. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode65 per.tex:65: \subsection*{Pseudocode} On 2013/08/24 10:39:54, robryk wrote: > This is like calling a driver's textbook `How to rotate the steering wheel'. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode65 per.tex:65: \subsection*{Pseudocode} On 2013/08/24 10:39:54, robryk wrote: > A generic overview would be very useful here: someting that tells you that you > iterate over all [n] numbers and do _something_ for every one. This naturally > segues into small/large cycle distinction. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode98 per.tex:98: The function $invertLargeCycles$ does one pass over the array $t$ and converts each large cycle to an intermediary structure. On 2013/08/24 10:39:54, robryk wrote: > Say that you want to avoid doing it twice for any cycle (obvious, but > reassuring). Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode99 per.tex:99: The structure is basically the inverse of the cycle with some modifications that allow us both to recognize that this cycle was visited and to repair the cycle later. On 2013/08/24 10:39:54, robryk wrote: > s/basically// ? Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode101 per.tex:101: After this is done, the only thing required is to do a third pass over the array to inverse the small cycles, which is done in $invertSmallCycles$. On 2013/08/24 10:39:54, robryk wrote: > s/inverse/invert/ Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode105 per.tex:105: Functions $invertPath$, $invertCycle$ and $iterate$ are self-explanatory. On 2013/08/24 10:39:54, robryk wrote: > This paragraph is pointless. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode115 per.tex:115: If not, a pair of two zeroes is. On 2013/08/24 10:39:54, robryk wrote: > Lack of verb grates here. What is a pair of three zeroes? Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode116 per.tex:116: The function can be implemented in $O(depth)$ running time and using $O(1)$ $\log{n}$-bit words of memory with Floyd's cycle-finding algorithm. On 2013/08/24 10:39:54, robryk wrote: > Ref to Floyd's algorithm. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode120 per.tex:120: Functions $isALargeCycle$ and $isASegment$ are also self-explanatory. On 2013/08/24 10:39:54, robryk wrote: > Ditto as for invertPath. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode128 per.tex:128: The functions $prolongSegment$ and $setSegmentCycleLength$ are self-explanatory, too. On 2013/08/24 10:39:54, robryk wrote: > Ditto. Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode132 per.tex:132: Assume that $(a_{m-1}, a_{m-2}, ..., a_0)$ forms a large cycle at the start of the function and $a_0 = i$ is the smallest vertex number. On 2013/08/24 10:39:54, robryk wrote: > smallest among the vertices of the cycle? Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode135 per.tex:135: \item let $b_0, ..., b_k$ be integers such that $0 \leq b_0 < b_1 < b_2 < ... On 2013/08/24 10:39:54, robryk wrote: > "let"? Do you mean "there exist" or "for every such"? Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode135 per.tex:135: \item let $b_0, ..., b_k$ be integers such that $0 \leq b_0 < b_1 < b_2 < ... On 2013/08/24 10:39:54, robryk wrote: > "let"? Do you mean "there exist" or "for every such"? Done. https://codereview.appspot.com/13066044/diff/7001/per.tex#newcode143 per.tex:143: The function $createIntermediaryStructure$ is called exactly once for each large cycle, always with $i$ being the smallest vertex on the cycle. On 2013/08/24 10:39:54, robryk wrote: > Time complexity? Done.
Sign in to reply to this message.
Still no code comments, I've just looked quickly through it. https://codereview.appspot.com/13066044/diff/10001/per.tex File per.tex (right): https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode52 per.tex:52: We assume the permutation is given by an array in which the i-th element denotes the value at i. I'd rephrase: Let's consider a permutation given by an array... https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode53 per.tex:53: Finding its inverse can be achieved in linear time and constant memory with a simple cycle leader [TODO: citation] algorithm. 1. Seems untrue (the cycle leader stuff had exp runtime of nlgn and didn't use overly large array elements, right?). 2. We care about constant additional memory. 3. Explain what kind of constant additional memory you mean (constant number of log-sized words is a good way to say that) and what kind of additional memory (array constrained to hold values from [n], but _not_ constrained to hold permutations). https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode62 per.tex:62: Also: a path is defined as a sequence of distinct vertices $(a_0, a_1, ..., a_{m})$ such that $t[a_i]=a_{i+1}$ for $i \in [m-1]$, Introduce definitons. Extraneous also. https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode70 per.tex:70: \item excluding the $t$ array, this is a constant memory algorithm. .. uses a constant number of additional log-sized words? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode73 per.tex:73: The algorithm has three phases - each is an iteration over the vertices in order of increasing indices and doing something for every one. `doing something' extraneous Prop: each iterates... https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode74 per.tex:74: As we aim at an $O(n^{\frac{3}{2}})$ algorithm, we can afford to walk each cycle of size $O(\sqrt{n})$ for each of their vertices. nitpick: its vertices https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode75 per.tex:75: For larger cycles, we do something to them at first visit so that they are processed only once. s/do something/modify/? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode76 per.tex:76: So let $k = \lceil \sqrt{n} \rceil$ and $4k+1$ be the length of the largest cycle that we will walk multiple times. ... Let's call all cycles of length <=4k+1 small cycles and the rest large cycles. Each small cycle we will walk every time we encounter one of its vertices. For large cycles.... ? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode80 per.tex:80: assume a trivial linear memory implementation of functions $storeSegmentSize$ and $retrieveSegmentSize$. Write it out explicitely in the pseudocode? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode81 per.tex:81: After proving the correctness and the time boundary, we will present their constant memory implementations in the annotated lines. ...and prove that using those implementations preserves the correctness and time complexity? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode83 per.tex:83: In order to mark a large cycle as visited, we will divide it into "segments" by redirecting some edges. What it the point of marking as visited? This is the first time `marking as visited' is mentioned. Sugg: rephrase the statement about avoidance of multiple walks over large cycles. https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode85 per.tex:85: We are doing this for two reasons. Doesn't flow. Define a segment earlier, when defining path, and provide a figure with a sample path, cycle and segment? Segment size limits missing, following sentences assume reader knows segments are O(sqrt(n)) in size. https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode88 per.tex:88: So please assume the following definition: a sequence of vertices $\sequencen{a}{m}$ forms a segment iff ``So please assume'' weird phrasing https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode93 per.tex:93: Now consider segments of size $2k$. at most? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode94 per.tex:94: Please note that there are at most $k^2$ such segments up to isomorphism. at most? it's obviously O(k^2), but seems to be k(2k-1) rather than k^2. https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode95 per.tex:95: Thanks to the choice of $k$ this means that segments can encode vertex numbers. a segment (maybe: segment's shape?) can encode a vertex number https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode96 per.tex:96: This encoding and its inverse are implemented in functions $encode$ and $decode$, respectively. are implemented, respectively, in ... https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode103 per.tex:103: The structure is the inverse of the cycle with some modifications that allow us both to recognize that this cycle was visited and to repair the cycle later. s/repair/reconstruct/? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode104 per.tex:104: The second pass over the array happens in the function $repairLargeCycles$, in which the intermediary structure is removed, leaving the large cycles inverted. converted into the inverted original large cycle? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode113 per.tex:113: If yes, the number of vertices in the segment and the length of the segment's cycle are returned. nitpick: If so? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode121 per.tex:121: The function's running time is linear in the segment size. It follows from the definition of a segment that this is equivalent to $O(\sqrt{n})$. nitpick: not equivalent https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode128 per.tex:128: \item $0 \leq b_0 < b_1 < b_2 < ... < b_{k-1} < b_k = m$, 0 \leq b_0 and not 0 = b_0? Else what happens with t[a[0]], t[a[1]], ..., t[a[b_0-1]]? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode156 per.tex:156: Function $repairCycle$ is called exactly once for each large cycle from the input, always with $i$ set to the smallest vertex on the cycle. input isn't the functions input. Maybe name the intermediate structure somehow and use its name a.o. here? https://codereview.appspot.com/13066044/diff/10001/per.tex#newcode163 per.tex:163: The function inverts every small cycle and does nothing more. weird phrasing: `does nothing more'
Sign in to reply to this message.
|
