Dev Stack Source

Answer : See this page. It contains instructions for each production that needs to be converted: From EBNF to BNF For building parsers (especially bottom-up) a BNF grammar is often better, than EBNF. But it's easy to convert an EBNF Grammar to BNF: Convert every repetition { E } to a fresh non-terminal X and add X = ε | X E. Convert every option [ E ] to a fresh non-terminal X and add X = ε | E. (We can convert X = A [ E ] B. to X = A E B | A B. ) Convert every group ( E ) to a fresh non-terminal X and add X = E. We can even do away with alternatives by having several productions with the same non-terminal. X = E | E'. becomes X = E. X = E'.

Answer : Let's assume that width of the array is bigger than height, otherwise we will split in another direction. Split the array into three parts: central column, left side and right side. Go through the central column and two neighbour columns and look for maximum. If it's in the central column - this is our peak If it's in the left side, run this algorithm on subarray left_side + central_column If it's in the right side, run this algorithm on subarray right_side + central_column Why this works: For cases where the maximum element is in the central column - obvious. If it's not, we can step from that maximum to increasing elements and will definitely not cross the central row, so a peak will definitely exist in the corresponding half. Why this is O(n): step #3 takes less than or equal to max_dimension iterations and max_dimension at least halves on every two algorithm steps. This gives n+n/2+n/4+... which is O(n) . Important detail: we split...

Answer : Whether a particular character is categorized as a whitespace character or not should depend on the character set being used. That said, it is not impossible that a programming language can make its own definition of what constitutes whitespace. Most modern languages use the Unicode Character set, which does have a definition for space separator characters . Any character in the Zs category is a space separator . You can see the complete list here. In addition you can grep for ;Zs; in the official Unicode Character Database to see those characters. Note that the number of characters in this category may grow as new Unicode versions come into existence, so I will not say how many such characters exist, nor even attempt to list them. In addition to the Zs Unicode category , Unicode also defines character properties . Among the properties defined by Unicode is a Whitespace property. As of Unicode 7.0, characters with this property include all of the characters wi...

Answer : Implementation 1 returns the magnitude of the vector that would result from a regular 3D cross product of the input vectors, taking their Z values implicitly as 0 (i.e. treating the 2D space as a plane in the 3D space). The 3D cross product will be perpendicular to that plane, and thus have 0 X & Y components (thus the scalar returned is the Z value of the 3D cross product vector). Note that the magnitude of the vector resulting from 3D cross product is also equal to the area of the parallelogram between the two vectors, which gives Implementation 1 another purpose. In addition, this area is signed and can be used to determine whether rotating from V1 to V2 moves in an counter clockwise or clockwise direction. It should also be noted that implementation 1 is the determinant of the 2x2 matrix built from these two vectors. Implementation 2 returns a vector perpendicular to the input vector still in the same 2D plane. Not a cross product in the classical sense but c...

Answer : Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k): function choose(n, k) if k == 0 return 1 return (n * choose(n - 1, k - 1)) / k I wrote it recursively because it's so simple and pretty, but you could transform it to an iterative solution if you like. You could use the Multiplicative formula for this: http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula Probably the easiest way to compute binomial coefficients (n choose k) without overflowing is to use Pascal's triangle. No fractions or multiplications are necessary. (n choose k) . The nth row and kth entry of Pascal's triangle gives the value. Take a look at this page. This is an O(n^2) operation with only addition, which you can solve with dynamic programming. It's going to be lightning fast for any number that can fit in a 64-bit integer.