text:
# Row-major or Column-major? Some notes about matrix convention

## The mathematical conventions

Generally speaking, when we want to render something to screen that means we need to calculate the color of each pixel of the final screen in front of us, then ask some hardware to fulfill those pixels with the color we specified. But typically what we have in disk are just some mesh and texture data files, which contain some information about the object we want to render, like how many vertexes they have, where the vertex’s position is in their own coordinate space, what the color of that vertex should look like and etc.. So, how to manipulate them until we get final color of the screen’s pixel? Of course we need some math, I assume you had already learned some linear algebra in theory and could understand what a matrix it is (or you could reference Wikipedia).

First of all, let’s review some theoretical things, the 4×4 matrix in Row-major mathematical convention is represented as (let’s count from 0 for convenient, also read the row first, then read the column):

\begin{bmatrix} a_{00} & a_{01} & a_{02} & a_{03} \\ a_{10} & a_{11} & a_{12} & a_{13} \\ a_{20} & a_{21} & a_{22} & a_{23} \\ a_{30} & a_{31} & a_{32} & a_{33} \\ \end{bmatrix}

In this convention we assume the right side (y in a_{xy})of the index (or subscript) of the element is counted always at first, and you can see the Row-major here means the elements are counted in the row first. This convention is used widely but still not all of situations, I’ll explain later.

And since we are focusing on the game development, typically we just use matrix to do linear transformation with vector (or multiplate different matrices one by one to get another matrix), and in most cases it’s just a 3-dimensional vector, but for cache-friendly purpose (see Wikipedia, alternate approach is to use additional padding data to make the alignment is the power of 2) we’d intense to use 4-dimensional vector instead, and it could also give us the convenience to represent a point or a direction with just modifing one of the components (set the additional component to 1.0 as a point, 0.0 as a direction).

Then we could define the vector4 in Column-major mathematical convention is represented as:

\begin{bmatrix} x \\ y \\ z \\ w \\ \end{bmatrix}

As you can see, it’s just a matrix with only one column, the Column-major here means the elements are listed as a 4×1 matrix instead of the 1×4 matrix.

Typically when we want to do the matrix-vector multiplication with these two mathematical representations, we call it right/post-multiplication, means the vector is on the right side or in the post position of the matrix in the equation (restricted by the definition of matrix multiplication, we need to match the dimension between two multiplicators), and as it listed in the demonstration below, in theory, if we calculated the final result’s elements one by one following the order of elements in vector4, it needs to access each row of the matrix first then each element in the row.

4×4 matrix * vector4 (4×1 matrix) :

\begin{bmatrix} x^{‘} = a_{00} * x + a_{01} * y + a_{02} * z + a_{03} * w \\ y^{‘} = a_{10} * x + a_{11} * y + a_{12} * z + a_{13} * w \\ z^{‘} = a_{20} * x + a_{21} * y + a_{22} * z + a_{23} * w \\ w^{‘} = a_{30} * x + a_{31} * y + a_{32} * z + a_{33} * w \\ \end{bmatrix}

## In memory

If you implement it with C/C++, it’s cache-friendly with Row-major memory layout; for Fortan/Matlab, it’s cache-friendly with Column-major memory layout.

So here we introduced another term, Row-major memory layout, what is it? As different software frameworks and people have different definitions for it, I will choose to follow one definition based on some nice blog as my definition. For example, I use C++ at the most of times, and if I use 2D array like m[A][B] in C++ to store a matrix, the memory would always store the M[0][0] to m[0][B – 1] continuously then m[1][0] to m[1][B – 1] until m[A – 1][0] to m[A – 1][B – 1]. And if you just try to assign the matrix data into this array, you could find two ways to assign it, set m[x – 1][y – 1] to value of a_{xy} or set m[x – 1][y – 1] to value of a_{yx}, and that’s where the term came from. If you set m[x – 1][y – 1] to the value of a_{xy}, that means if anybody iterated the elements of the array continuously they would access the data of the whole row of a matrix then another one row until the last of rows.

Here the 2D array in memory looks like (in C/C++):

0x0000 0x0001 0x0002 0x0003 0x0004 0x0005 0x0006 0x0007 0x0008 0x0009 0x000A 0x000B 0x000C 0x000D 0x000E 0x000F
m[0][0] m[0][1] m[0][2] m[0][3] m[1][0] m[1][1] m[1][2] m[1][3] m[2][0] m[2][1] m[2][2] m[2][3] m[3][0] m[3][1] m[3][2] m[3][3]

Be careful here, after we defined Row-major memory layout, actually we still could store the matrix data in any kind of orders, for example we could just store a 4×4 matrix in Row-major mathematical convention in C++ 2D array with Row-major memory layout naturally like:

0x0000 0x0001 0x0002 0x0003 0x0004 0x0005 0x0006 0x0007 0x0008 0x0009 0x000A 0x000B 0x000C 0x000D 0x000E 0x000F
m[0][0] m[0][1] m[0][2] m[0][3] m[1][0] m[1][1] m[1][2] m[1][3] m[2][0] m[2][1] m[2][2] m[2][3] m[3][0] m[3][1] m[3][2] m[3][3]
a_{00} a_{01} a_{02} a_{03} a_{10} a_{11} a_{12} a_{13} a_{20} a_{21} a_{22} a_{23} a_{30} a_{31} a_{32} a_{33}

or store the column first, that means we choose to use Column-major memory layout in C++:

0x0000 0x0001 0x0002 0x0003 0x0004 0x0005 0x0006 0x0007 0x0008 0x0009 0x000A 0x000B 0x000C 0x000D 0x000E 0x000F
m[0][0] m[0][1] m[0][2] m[0][3] m[1][0] m[1][1] m[1][2] m[1][3] m[2][0] m[2][1] m[2][2] m[2][3] m[3][0] m[3][1] m[3][2] m[3][3]
a_{00} a_{10} a_{20} a_{30} a_{01} a_{11} a_{21} a_{31} a_{02} a_{12} a_{22} a_{32} a_{03} a_{13} a_{23} a_{33}

As far as we just discussed the convention itself until now, there is no problem to choose which way to store it, you could even store it in reverse order or some random order, that’s just a mapping relationship between the matrix data and the memory location, until we really write the code in our project we don’t need to worry about which one should we choose.

## Alternative approaches

Similar, we could define a vector4 in Row-major mathematical convention as:

\begin{bmatrix} x & y & z & w \\ \end{bmatrix}

it’s just a 1×4 matrix with only one row.
And then we get a term as left/pre-multiplication. And for C/C++, it’s cache-friendly with Column-major memory layout; for Fortan/Matlab, it’s cache-friendly with Row-major memory layout.

vector4 (1×4 matrix) * matrix4x4:

\begin{bmatrix} x^{‘} = x * a_{00} + y * a_{10} + z * a_{20} + w * a_{30} \\ y^{‘} = x * a_{01} + y * a_{11} + z * a_{21} + w * a_{31} \\ z^{‘} = x * a_{02} + y * a_{12} + z * a_{22} + w * a_{32} \\ w^{‘} = x * a_{03}+ y * a_{13} + z * a_{23} + w * a_{33} \\ \end{bmatrix}

Again, there is no doubt we need to access the elements in each column of matrix continously, so the best memory layout is:

0x0000 0x0001 0x0002 0x0003 0x0004 0x0005 0x0006 0x0007 0x0008 0x0009 0x000A 0x000B 0x000C 0x000D 0x000E 0x000F
m[0][0] m[0][1] m[0][2] m[0][3] m[1][0] m[1][1] m[1][2] m[1][3] m[2][0] m[2][1] m[2][2] m[2][3] m[3][0] m[3][1] m[3][2] m[3][3]
a_{00} a_{10} a_{20} a_{30} a_{01} a_{11} a_{21} a_{31} a_{02} a_{12} a_{22} a_{32} a_{03} a_{13} a_{23} a_{33}

So finally the vector4 mathematical convention and the memory layout have 2 x 2 = 4 different combinations:
vector4 in Column-major mathematical convention + Column-major memory layout
vector4 in Column-major mathematical convention + Row-major memory layout
vector4 in Row-major mathematical convention + Row-major memory layout
vector4 in Row-major mathematical convention + Column-major memory layout

In practice, because the mapping relationship of the index of the array and the index of the element in the matrix, whether you choose Row-major memory layout or Column-major memory layout, choose a corresponding cache-friendly vector4 mathematical convention would have the same efficiency, vice versa. And that means we need to avoid using the combinations I marked with different colors.

## Application examples

Let’s have a look at some examples:

If we want to represent a vector4 in Column-major mathematical convention to a translation matrix, we could write it in paper as:

\begin{bmatrix} T_x \\ T_y \\ T_z \\ T_w \\ \end{bmatrix}

Then the matrix is:

\begin{bmatrix} 1 & 0 & 0 & T_x \\ 0 & 1 & 0 & T_y \\ 0 & 0 & 1 & T_z \\ 0 & 0 & 0 & T_w \\ \end{bmatrix}

And let’s define a vector4 as the original point before the translation process,

\begin{bmatrix} x \\ y \\ z \\ w \\ \end{bmatrix}

Then after the translation the result vector4 is:

\begin{bmatrix} x^{‘} = 1 * x + 0 * y + 0 * z + T_x * w = x + T_x * w \\ y^{‘} = 0 * x + 1 * y + 0 * z + T_y * w = y + T_y * w \\ z^{‘} = 0 * x + 0 * y + 1 * z + T_z * w = z + T_z * w \\ w^{‘} = 0 * x + 0 * y + 0 * z + T_w * w = T_w * w \\ \end{bmatrix}

Because the {w} component represents the length of the projection line in homogeneous/projective coordinate, let’s assume we’ve already done the Perspective Division and then {w} = 1, the previous calculation could be simplified as:

Translation vector4:

\begin{bmatrix} T_x \\ T_y \\ T_z \\ 1 \\ \end{bmatrix}

Translation matrix:

\begin{bmatrix} 1 & 0 & 0 & T_x \\ 0 & 1 & 0 & T_y \\ 0 & 0 & 1 & T_z \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}

The original point:

\begin{bmatrix} x \\ y \\ z \\ 1 \\ \end{bmatrix}

The result point:

\begin{bmatrix} x^{‘} = 1 * x + 0 * y + 0 * z + T_x * 1 = x + T_x \\ y^{‘} = 0 * x + 1 * y + 0 * z + T_y * 1 = y + T_y \\ z^{‘} = 0 * x + 0 * y + 1 * z + T_z * 1 = z + T_z \\ w^{‘} = 0 * x + 0 * y + 0 * z + 1 * 1 = 1 \\ \end{bmatrix}

And again, of course in theory here we need to access each row first, then in C++ it’s more conveinent to use Row-major memory layout because we will read the 2D array’s index as same as the math convention’s index and won’t have too much cache-missing problem, but also you could use Column-major memory layout, just need to flip everything in your mind and lose some CPU cycles.

And the same, if we choose to use vector4 in Row-major mathematical convention instead, finally we would find it’s more rational to use Column-major memory layout, but still could use Row-major memory layout.

But what if we want to use both vector4 in Row-major mathematical convention and vector4 in Column-major mathematical convention and want to have the same cache-friendly performance in C++? How the code should be written? Actually, it’s not so complex, if you understood what I talked previously, you may figure it out by yourself. As we defined two mathematical conventions for vector4 before, since it is just a specialized matrix, we could think matrix mathematical convention could be Row-major and Column-major too, that’s why I emphasized the 4×4 matrix in Row-major mathematical convention at very beginning, we represent the 4×4 matrix in Column-major mathematical convention, and flip everything in theory we discussed before, then put them in the cache-friendly memory layout, that’s all!

And below is how the mathematical representation looks like, remember we still read the row first, then read the column:

\begin{bmatrix} a_{00} & a_{10} & a_{20} & a_{30} \\ a_{01} & a_{11} & a_{21} & a_{31} \\ a_{02} & a_{12} & a_{22} & a_{32} \\ a_{03} & a_{13} & a_{23} & a_{33} \\ \end{bmatrix}

And now the vector4 in Column-major mathematical convention is:

\begin{bmatrix} x = a_{00} & y = a_{10} & z = a_{20} & w= a_{30} \\ \end{bmatrix}

And the translation matrix is:

\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ T_x & T_y & T_z & 1 \\ \end{bmatrix}

Now the {T_x}{T_y}{T_z} (and {T_w}) is a_{03}a_{13}a_{23}（And a_{33}

0x0000 0x0001 0x0002 0x0003 0x0004 0x0005 0x0006 0x0007 0x0008 0x0009 0x000A 0x000B 0x000C 0x000D 0x000E 0x000F
m[0][0] m[0][1] m[0][2] m[0][3] m[1][0] m[1][1] m[1][2] m[1][3] m[2][0] m[2][1] m[2][2] m[2][3] m[3][0] m[3][1] m[3][2] m[3][3]
a_{00} a_{01} a_{02} a_{03} a_{10} a_{11} a_{12} a_{13} a_{20} a_{21} a_{22} a_{23} a_{30} a_{31} a_{32} a_{33}

Actually as you can see here, nothing changed in memory, exactly what changed is our mathematical convention and our mind, and then I feel it’s “meaningless” to distinguish between “Row-major” or “Column-major” inside C++, and this should be the reason why some people call C++ as a “Row-major” language, but still after all these red tape we could have a more clearly point of view before we start to write something.

But in practice, due to the historical reason of OpenGL (see OpenGL FAQ 9.005), it uses 4×4 matrix in Column-major mathematical convention and a memory layout corresponding to Column-major memory layout in C++ (as the document said

The translation components occupy the 13th, 14th, and 15th elements of the 16-element matrix

, means m[3][0] to m[3][3] are {T_x}{T_y}{T_z} and {T_w}), and for the sake of different mathematical conventions, glUniformMatrix4fv function has a parameter at third position to indicate if we want to ask the implementation library to flip the input matrix or not. if we choose to use the same mathematical convention and memory layout as OpenGL used then we just set it to GL_FALSE, means no flipping. And if we choose to use 4×4 matrix in Row-major mathematical convention but didn’t change the memory layout in C++, we need to set it to GL_TRUE to flip the input matrix, same as the situation when just change the memory layout but didn’t change the mathematical convention.

Actually it is really a confused topic, because how we read and count how we use and understand the terms finally influence our implementation, in my project I decided to support both two different conventions and until now it works fine, but in large scale products I assume that would become a problem if didn’t make the clarification well and clearly.

## Code samples

Some code samples here:

//Column-major memory layout
#if defined (USE_COLUMN_MAJOR_MEMORY_LAYOUT)
template
auto TVec4::toTranslationMatrix(const TVec4& rhs) -> TMat4
{
// @TODO: replace with SIMD impl
TMat4 l_m;

l_m.m[0][0] = one;
l_m.m[1][1] = one;
l_m.m[2][2] = one;
l_m.m[3][0] = rhs.x;
l_m.m[3][1] = rhs.y;
l_m.m[3][2] = rhs.z;
l_m.m[3][3] = one;

return l_m;
}
//Row-major memory layout
#elif defined (USE_ROW_MAJOR_MEMORY_LAYOUT)
template
auto toTranslationMatrix(const TVec4& rhs) -> TMat4
{
// @TODO: replace with SIMD impl
TMat4 l_m;

l_m.m[0][0] = one;
l_m.m[0][3] = rhs.x;
l_m.m[1][1] = one;
l_m.m[1][3] = rhs.y;
l_m.m[2][2] = one;
l_m.m[2][3] = rhs.z;
l_m.m[3][3] = one;

return l_m;
}
#endif
//Column-major memory layout
#if defined (USE_COLUMN_MAJOR_MEMORY_LAYOUT)
template
auto toRotationMatrix(const TVec4& rhs) -> TMat4
{
// @TODO: replace with SIMD impl
TMat4 l_m;

l_m.m[0][0] = (one -two * rhs.y * rhs.y - two * rhs.z * rhs.z);
l_m.m[0][1] = (two * rhs.x * y + two * rhs.z * rhs.w);
l_m.m[0][2] = (two * rhs.x * rhs.z - two * rhs.y * rhs.w);
l_m.m[0][3] = (T());

l_m.m[1][0] = (two * rhs.x * rhs.y - two * rhs.z * rhs.w);
l_m.m[1][1] = (one -two * rhs.x * rhs.x - two * rhs.z * rhs.z);
l_m.m[1][2] = (two * rhs.y * rhs.z + two * rhs.x * rhs.w);
l_m.m[1][3] = (T());

l_m.m[2][0] = (two * rhs.x * rhs.z + two * rhs.y * rhs.w);
l_m.m[2][1] = (two * rhs.y * rhs.z - two * rhs.x * rhs.w);
l_m.m[2][2] = (one -two * rhs.x * rhs.x - two * rhs.y * rhs.y);
l_m.m[2][3] = (T());

l_m.m[3][0] = (T());
l_m.m[3][1] = (T());
l_m.m[3][2] = (T());
l_m.m[3][3] = (one);

return l_m;
}
//Row-major memory layout
#elif defined ( USE_ROW_MAJOR_MEMORY_LAYOUT)
template
auto toRotationMatrix(const TVec4& rhs) -> TMat4
{
// @TODO: replace with SIMD impl
TMat4 l_m;

l_m.m[0][0] = (one -two * rhs.y * rhs.y - two * rhs.z * rhs.z);
l_m.m[0][1] = (two * rhs.x * rhs.y - two * rhs.z * rhs.w);
l_m.m[0][2] = (two * rhs.x * rhs.z + two * rhs.y * rhs.w);
l_m.m[0][3] = (T());

l_m.m[1][0] = (two * rhs.x * rhs.y + two * rhs.z * rhs.w);
l_m.m[1][1] = (one -two * rhs.x * rhs.x - two * rhs.z * rhs.z);
l_m.m[1][2] = (two * rhs.y * rhs.z - two * rhs.x * rhs.w);
l_m.m[1][3] = (T());

l_m.m[2][0] = (two * rhs.x * rhs.z - two * rhs.y * rhs.w);
l_m.m[2][1] = (two * rhs.y * rhs.z + two * rhs.x * rhs.w);
l_m.m[2][2] = (one -two * rhs.x * rhs.x - two * rhs.y * rhs.y);
l_m.m[2][3] = (T());

l_m.m[3][0] = (T());
l_m.m[3][1] = (T());
l_m.m[3][2] = (T());
l_m.m[3][3] = one;

return l_m;
}
#endif

## Further more

For the Multiplication algorithm of matrix, the naive implemetations is O(n^3), and there are lots of optimized algorithms (e.g. Solvay Strassen algorithm O(n^{2.807})/Coppersmith-Winograd algorithm O(n^{2.3737})/Stochers-Williams algorithm O(n^{2.3729}) could get a time complexity around O(n^{2.4}).

For transpose could consider about in-situ matrix transposition.

And for inverse, Gaussian Elimination is O(n^3), could choose LU decomposition, and also there are lots of optimized algorithms.


text:
# Time complexity of Held-Karp algorithm for TSP

When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, I came up with the following question: why the complexity of their algorithm for TSP is $(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1)$ (p. 199), I mean where do they take the factor $k$? If I understood correctly $k-1$ means the number of additions for each subset of cities. Then why each addition operation is coupled with unknown to me $k$ operations? I suppose it is connected somehow to taking minimum, but computing minimum doesn't seem to require such many operations.

Dynamic programming algorithm by Held and Karp and independently Bellman runs as follows: for each pair $(S,c_i)$, meaning a path going through $c_1$, all the elements of $S$ and terminating at $c_i$ compute

$OPT[S,c_i]=min\{OPT[S\setminus\{c_i\},c_j]+d(c_j,c_i):c_j\in S\setminus\{c_i\}\},$

where $d(c_j,c_i)$ means the distance between cities $c_j$ and $c_i$. Then in the formula from the paper $k$ means the size of $S$.

Addendum to below, clarifying the $k(k-1)$ terms:

So, if you examine the terms in the expression, you can envision (as analogy) the $n-1 \choose k$ term is an enumeration of all binary strings containing $k$ 1's that have a 1 in the first position. In other words, we let each position in the binary string represent the choice of whether a given one of the $n$ cities in the problem are in the exact subset we are considering at the time. So, for 5 cities, 10101 corresponds to the subset {1,3,5}.

Thus, to compute across all subsets of {1,...,$n$}, we simply count through each binary subset (i.e. count through binary strings) of size=2 (i.e. binary strings of size $n$ that contain two 1's), then size=3, then size=4, ...then size=n. (Note that the size=1 subset must contain only the first city, and thus it's irrelevant to compute its partial distance, since the distance from 1 -> all other cities in the subset -> 1 is exactly 0.)

At each subset with $k$ cities, we have to consider up to $k-1$ candidate-optimal, partial paths. Specifically, the optimal, total path could conceivably traverse through the given subset and end up on any of the $k-1$ cities, excluding the first city. Then, for each such candidate sub-path, we compute the optimal tour up to that point as the minimum of any of the previous, size=$k-1$ sub-paths plus the distance from the terminal city for that sub-path to the terminal city for the current candidate sub-path. This gives $(k-1)(k-2)$ such comparisons that we must make. The discrepancy between my $(k-1)(k-2)$ term, and the $k(k-1)$ term in the analysis linked is a notational difference (I would sum over a different range, given my definition of $k$ than they did). At the very least, however, it should illustrate the quadratic-order complexity of that term.

How interesting -- I just finished coding this exact algorithm up in C++ a few minutes ago. (So forgive the tangent from pure theory into a little practical discussion. :))

It costs $O(2^n n^2)$ time and $O(2^n n)$ space -- at least under my implementation. Practically speaking though, when your space requirements grow that fast, they become way more painful than the time requirements. For instance, on my PC (with 4 GB of RAM), I can solve instances with up to 24 cities -- any more than that, and I run out of memory.

Of course, I could just be a bad programmer, and you might be able to do better than me in practice. :)

Edit: A little more specifics on one detail of your question: The $k(k-1)$ term comes from the fact that you have to, in the worst case, calculate the partial, optimal distance from the previous subsets (there are at most $n$ of them; note that $k$ is summed over $n$ in the analysis you linked) to the current one. This requires, again in the worst case, $O(k)$ comparisons with subsets of size $k-1$ for a total of $O(k^2)$.

Also, if my explanation wasn't clear enough, here are some nice lecture notes of Vazirani's (PDF). Scroll down to P. 188 for a discussion of TSP, including an analysis of Held-Karp.

• Oh, of course! I feel silly thinking about that now; I'll update my answer. I'd actually heard that exact comment before, and just passed it on without thinking about it. And yeah -- writing to a file/reading from a file will let you go effectively go arbitrarily high on numbers of cities. ...it's also a pain not worth worrying about unless you're trying to solve TSP instances for a real purpose. Mine was decidedly not for a practical purpose. ;) Dec 6 '10 at 4:01
• Time to implement the Bjorklund algorithm :) Dec 6 '10 at 4:20
• @Suresh: Good idea! Dec 6 '10 at 5:20
• @Daniel Apon Could you, please, make precise why we need comparisons when calculating "the partial, optimal distance"? Dec 6 '10 at 17:27
• @Oleksandr: Sure, I'll add it to the top of my answer. Dec 7 '10 at 2:12

# Main note

It's important to note that we compute and store not
"distance of optimal path for combination of k cities"
but
"distance of optimal path for combination of k cities AND for end-point city from this combination".
Understanding it will help with meaning of first two multipliers in following formula.

## First phase

The number of operations in the first phase is: $$\displaystyle \sum_{k>=2} \underbrace{ \binom{n-1}{k-1} }_{\substack{ \text{choose city combination} \\ \text{of size = k-1}}} \cdot \underbrace{ (k-1) }_{\substack{ \text{choose city to be the last} \\ \text{from k-1 cities} \\ \text{in chosen combination} } } \cdot \underbrace{ ((n-1)-(k-1)) }_{ \substack{ \text{choose city} \\ \text{that is not in chosen combination} \\ \text{to add to path} } }$$

Missing superscript in sum means for all k>=2 that is valid for binomial coefficient. So the last valid not null term of sum will be for $$k=n-1$$ $$\binom{n-1}{n-2} \cdot (n-2) \cdot 1$$ It means that our sum doesnt capture last choices of city to connect to the first city. There are $$n-1$$ cities to connect to the first city. So finally we will add this term to the sum.

Let transform formula to form that you provide that is also on Held-Karp Wikipedia page.

$$\displaystyle \sum_{k>=2} \binom{n-1}{k-1} \cdot (k-1) \cdot ((n-1)-(k-1))= \sum_{k>=2} \frac{(n-1)!}{(k-1)!(n-k)!} \cdot (k-1) \cdot (n-k)= \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1)= \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1)$$ Manipulating binomial coefficients leads to: $$\displaystyle \sum_{k>=2} \binom{n-1}{k} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-1)!}{k!(n-1-k)!} \cdot k \cdot (k-1) = \sum_{k>=2} \frac{(n-3)!}{(k-2)!(n-3-(k-2))!} \cdot (n-1) \cdot (n-2)= (n-1) \cdot (n-2)\sum_{k>=2} \binom{n-3}{k-2}=(n-1) \cdot (n-2) \cdot 2^{n-3}$$ So the number of operations in the first phase is $$(n-1) \cdot (n-2) \cdot 2^{n-3}+(n-1)$$

## Second phase

Second phase is restoring optimal path by marks we have made in the first phase simultaneously with computing distances.

For each optimal path "for combination of k cities AND for end-point city from this combination" we have saved the second-to-last city.

To backtrack optimal path we need to ask some data structure to return the second-to-last city "for combination of k cities AND for end-point city from this combination". So this data structure must be something like
Map<combination of k cities, Map<last city, second-to-last city>>. As index of combination of k cities we can use, for example, binary_string[city id]=1 if city id is in combination . So we need to look at all elements of combination of k cities` to identify combination and index our data structure. This gives us the number of operations for the second phase: $$\displaystyle \sum_{k>=2}^{n-1} k = \frac{(n)(n-1)}{2} - 1$$

format: plain


text:
# Many other solutions of the Cauchy's Functional Equation

By reading the Cauchy's Functional Equations on the Wiki, it is said that

On the other hand, if no further conditions are imposed on f, then (assuming the axiom of choice) there are infinitely many other functions that satisfy the equation. This was proved in 1905 by Georg Hamel using Hamel bases. Such functions are sometimes called Hamel functions.

Could anyone give a more explicit explanation of these many other solutions?

Besides the trivial solution of the form $f(x)=C x$, where $C$ is a constant, and the solution above constructed by the Hamel Basis, are there any more solutions existing?

• The quoted paragraph says that infinitely many solutions can be found because there are infinitely many Hamel bases. – Tunococ Sep 8 '13 at 23:40
• The "trivial" solutions also can be constructed from a Hamel basis. There are lots of solutions because the function can be defined arbitrarily on the elements of a Hamel basis. – André Nicolas Sep 8 '13 at 23:47

All solutions are "Hamel basis" solutions. Any solution of the functional equation is $\mathbb{Q}$-linear. Let $H$ be a Hamel basis. Given a solution $f$ of the functional equation, let $g(b)=f(b)$ for every $b\in H$, and extend by $\mathbb{Q}$-linearity. Then $f(x)=g(x)$ for all $x$.
There are lots of solutions because a Hamel basis has cardinality the cardinality $c$ of the continuum. A solution can assign arbitrary values to elements of the basis, and be extended to $\mathbb{R}$ by $\mathbb{Q}$-linearity. So there are $c^c$ solutions. There are only $c$ linear solutions, so "most" solutions of the functional equation are non-linear.


text:
# LAS formal class

A LAS class is a representation in R of a las file that aims to respect as closely as possible the official LAS specification that describes the file format. “As closely as possible” means that, due to R internal limitations, it is not possible to represent a las file exactly as it should be represented. Additionally, some aspects of the las format specifications are not supported in lidR. Still, the contents of a LAS object must reflect the fact that it is a representation of a standardized format, so some restrictions are imposed on users.

## Build a LAS object reading a las file

The function readLAS reads one or several .las or .laz file(s) to build a LAS object.

LASfile <- system.file("extdata", "Megaplot.laz", package="lidR")
print(las)
#> class        : LAS (LASF v1.2)
#> point format : 1
#> memory       : 6.2 Mb
#> extent       :684766.4, 684993.3, 5017773, 5018007 (xmin, xmax, ymin, ymax)
#> coord. ref.  : +init=epsg:26917 +proj=utm +zone=17 +datum=NAD83 +units=m +no_defs +ellps=GRS80 +towgs84=0,0,0
#> area         : 53112.69 m² (convex hull)
#> points       : 81590 points
#> density      : 1.54 points/m²
#> names        : X Y Z gpstime Intensity ReturnNumber NumberOfReturns ScanDirectionFlag EdgeOfFlightline Classification Synthetic_flag Keypoint_flag Withheld_flag ScanAngleRank UserData PointSourceID

## Basic structure of a LAS object

A LAS object is composed of four slots: @data, @header, @proj4string and @bbox, and inherits Spatial from package sp.

### @data: the point cloud

The slot data of a LAS object contains a data.table with the data read from .las or .laz file(s). The columns of the table are named after the LAS specification version 1.4. Each name is reserved and is associated with a given type:

• X Y Z (dbl)
• Intensity (int)
• gpstime (dbl)
• ReturnNumber (int)
• NumberOfReturns (int)
• ScanDirectionFlag (int)
• EdgeOfFlightline(int)
• Classification (int)
• Synthetic_flag (bool)
• Withheld_flag (bool)
• Keypoint_flag (bool)
• ScanAngle (int)
• UserData (int)
• PointSourceID (int)
• R G B (int)
• NIR (int)

Here we can already see some deviations from the official las format specifications. For example, the attribute ‘Classification’ should be an unsigned char stored on 8 bits. However, the R language does not support this data type and consequently this attribute is stored in a 32-bit signed int. One can read the official las specifications to figure out the other deviations from the original file format induced by the fact that R only has 32-bit signed integers and 64-bit signed decimal numbers.

A LAS object contains a slot @header that represents the header of the las file. The header is stored in a LASheader object. A LASheader object contains two slots: @PHB for the public header block and @VLR for the variable length records. Both slots are lists labeled according to the las file format specification. See public documentation of las file format for more information about las headers. Users should never normally have to worry about the header as long as they use functions from lidR. Everything is managed internally to ensure that objects are valid. However, users still need to know that the contents of the header are important, especially when writing LAS objects into las or laz files.

print(las@header)
#> File signature:           LASF
#> File source ID:           0
#> Project ID - GUID:        00000000-0000-0000-0000-000000000000
#> Version:                  1.2
#> System identifier:        LAStools (c) by rapidlasso GmbH
#> Generating software:      las2las (version 171231)
#> File creation d/y:        0/0
#> Offset to point data:     321
#> Num. var. length record:  1
#> Point data format:        1
#> Point data record length: 28
#> Num. of point records:    81590
#> Num. of points by return:
#> Scale factor X Y Z:       0.01 0.01 0.01
#> Offset X Y Z:             0 0 0
#> min X Y Z:                684766.4 5017773 0
#> max X Y Z:                684993.3 5018007 29.97
#> Variable length records:
#>    Variable length record 1 of 1
#>        Description:  by LAStools of rapidlasso GmbH
#>        Tags:
#>           Key 1024 tiff_tag_location 0 count 1 value offset 1
#>           Key 3072 tiff_tag_location 0 count 1 value offset 26917
#>           Key 3076 tiff_tag_location 0 count 1 value offset 9001
#>           Key 4099 tiff_tag_location 0 count 1 value offset 9001

### @proj4string: the CRS

The slot @proj4string is inherited from the Spatial class from the sp package. It is a CRS object that stores the coordinate reference system (CRS) of the las file. In the official las specifications the CRS is stored in the header. In a LAS object the CRS is stored in the header using the EPSG code of the CRS, but it is also stored in the slot @proj4string. This is to ensure it meets R standards and is in accordance with other spatial data packages in the R ecosystem. Consequently, to get a valid LAS object properly written into a las file it is important to set the CRS using the function epsg(). This function updates the header of the LAS object and the proj4string, while functions such as raster::projection() or sp::proj4string only update the slot @proj4string.

epsg(las) = 2567
projection(las)
#> [1] "+init=epsg:2567 +proj=tmerc +lat_0=0 +lon_0=150 +k=1 +x_0=50500000 +y_0=0 +ellps=krass +towgs84=23.92,-141.27,-80.9,0,0.35,0.82,-0.12 +units=m +no_defs"

### @bbox: the bounding box

The slot @bbox is inherited from the Spatial class from sp. It is a matrix object that stores the XY bounding box of the point cloud. In the official las specifications the bounding box is stored in the header. In a LAS object the bounding box is stored both in the header and also stored in the slot @bbox (to be in compliance with R standards and other spatial data R packages). The user should never change the bounding box manually. However, doing that will have few consequences because this slot is of little practical use.

## Allowed and non-allowed manipulation of a LAS object

R users who are used to manipulating spatial data are likely to be very familiar with the sp package and all the classes used to store spatial data, such as SpatialPointsDataFrame, SpatialPolygonsDataFrame, and so on. The data contained in these classes are freely modifiable by the user because they can be of any type. A LAS object is not freely modifiable because it is a strongly standardized representation of a las file.

For example, users cannot replace the Classification attribute with the value 0 because 0 is a decimal number in R and the ‘Classification’ attribute is an integer. The following throws an error:

las$Classification <- 0 #> Error in $<-(*tmp*, Classification, value = 0): Trying to replace data of type integer by data of type double: this action is not allowed

In R 0L is an integer and thus the following is allowed:

las$Classification <- 0L It would be possible to automatically cast the input into the correct type without throwing an error. But for the lidR package we chose to be very pedantic on this point to avoid any potential problems and because we would prefer users to be careful about the content of their data. The addition of a new column is also restricted. For example, one may want to add an attribute R corresponding to the red channel. las$R <- 0
#> Error in $<-(*tmp*, R, value = 0): Addition of a new column using$ is forbidden for LAS objects. See ?lasadddata

This is not allowed because a LAS object should always be valid. By allowing the user to add an R column the LAS object would no longer be valid for two reasons:

1. R is a reserved name of the core attributes and must be an integer. In the example above it is a decimal number.
2. A LAS file with RGB attributes is of type 3, 7 or 8. As a result the header must be updated, but in the previous example it is not.

In consequence, adding a column must be done via the functions lasadddata or lasaddextrabytes. This way users are forced to read the documentation of these two functions. And yet some restrictions are still in place. For example, the following is not allowed for the same reasons as above:

las <- lasadddata(las, 0, "R")
#> Error in stopif_forbidden_name(name): R is part of the core attributes and is a forbidden name.

But anyway, R being R there is no way to completely restrict editing of objects. Users can always by-pass the restrictions to make LAS objects that are not strictly valid:

las@data\$R <- 0

In conclusion, a LAS object is not actually immutable but at least there are some restrictions to ensure that the user is aware that not everything is authorized.

## Extra attributes and extra bytes in a LAS object

As we have seen, a LAS object contains a core of attributes associated with reserved names in accordance with the las specifications. It is possible, however, to add more attributes to a LAS object even if they are not part of the core attributes imposed by the las specifications.

### Extra attributes

Extra attributes are just like adding a column in a regular table in R. One can freely modify the data using the function lasadddata. It is thus possible to add an attribute to a LAS object. For example, it is possible to attribute an ID to each point and use this value in subsequent code:

las  <- lasadddata(las, 1:81590, "ID")
las2 <- lasfilter(las, ID > 50000)

But it is important to understand that this attribute is invalid with respect to the las specifications. Thus it can be used at the R level but will not be written in a las file and thus will be lost at write time. Depending on the purpose of this attribute it may or may not be useful to be able to write this extra data. Most of the time the information is only useful at the R level but sometimes it might be appropriate to store the data in a file.

### Extra bytes attributes

The las specifications allow for storing extra attributes that are not part of the core attributes. but the way to do this is more complex. Basically it is called extra bytes attributes and it implies modification of the LAS object header to indicate that the contents of the file contains more than the core attributes. This is abstracted with the function lasaddextrabytes.

las  <- lasaddextrabytes(las, 1:81590, "ID", "An ID for each point")

Using this function, the header is updated according to the las specification and thus the extra bytes attributes can be written in the file. lidR supports up to 10 extra bytes attributes. The extra bytes attributes are limited to being of type numeric. Indeed, the las specifications do not allow for storing extra bytes attributes of type string or type boolean. Thus the following fails:

abc  <- sample(letters, 81590, replace = TRUE)
las  <- lasaddextrabytes(las, abc, "ID", "An ID for each point")
#> Error in lasaddextrabytes(las, abc, "ID", "An ID for each point"): 'x' must be numeric. LAS format specifications do not allow storing of 'character' extra bytes.

## Validation of LAS objects

It is common that users report bugs arising from the fact that a point cloud is invalid. This is why we introduced the function lascheck to perform a deep inspection of LAS objects. This function checks if a LAS object is in accordance with the las specifications but also it checks for weird point clouds that could be valid with respect to the specifications but invalid for actual processing. For example, it often happens that a las file contains duplicated points for no valid reason. This may lead to trees being detected twice, to invalid metrics, or to errors in DTM generation, and so on…

lascheck(las)
#>
#>  Checking the data
#>   - Checking coordinates... ok
#>   - Checking coordinates type... ok
#>   - Checking attributes type... ok
#>   - Checking attributes type... ok
#>   - Checking attributes type... ok
#>   - Checking ReturnNumber validity... ok
#>   - Checking NumberOfReturns validity... ok
#>   - Checking ReturnNumber vs. NumberOfReturns... ok
#>   - Checking Classification validity... ok
#>   - Checking RGB validity... skipped
#>   - Checking absence of NAs... ok
#>   - Checking duplicated points... ok
#>   - Checking degenerated ground points... skipped
#>   - Checking header completeness... ok
#>   - Checking scale factor validity... ok
#>   - Checking Point Data Format ID validity... ok
#>   - Checking extra bytes attributes validity... ok
#>   - Checking coordinate reference sytem... ok
#>   - Checking attributes vs. point format... ok
#>   - Checking header bbox vs. actual content... ok
#>   - Checking header number of points vs. actual content... ok
#>   - Checking header return number vs. actual content... ok
#>   - Checking ground classification... no
#>   - Checking normalization... yes
#>   - Checking negative outliers... ok
#>   - Checking flightline classification... no

## Display a LAS object

lidR provides a simple plot function to plot a LAS object in 3D. It is based on the rgl package. The rgl package is amazing but has some problems working with large point clouds. We are currently developing our own viewer to overcome this issue. This viewer is fully compatible with lidR but still in heavy development.

plot(las)

The parameter color expects the name of the attribute you want to use to colorize the points. Default is Z

plot(las, color = "Intensity", colorPalette = heat.colors(50))

If your file contains RGB data the string "RGB" is supported:

plot(las, color ="RGB")

The trim parameter enables trimming of values when outliers break the color palette range. For example, Intensity often contains large outliers. The palette range would be too large and most of the values will be considered as “very low”, so everything will appear in the same color.

plot(las, color = "Intensity", colorPalette = heat.colors(50), trim = 450)

## Memory considerations

This section is of major importance because there are many instances where R is weak at memory management.

Firstly, it is important to note that R only enables manipulation of 32-bit integers and 64-bit decimal numbers. But the las specification states, for example, that the intensity is stored on 16 bits (see previous sections). When read in R it must be converted to 32 bits and therefore will use twice as much memory than is needed. Worse, the return numbers are stored on 3 bits in las files but 32 bits in R, therefore using 11 times more memory than is required. Last but not least, flags are stored on 1 bit, whereas R uses 32 bits. This is 32 times more memory than is needed. As a consequence, a LAS object is 2 to 3 times larger than it needs to be.

Secondly, the way the point cloud is stored and the way R works implies that copies will be made of the point cloud either in the user’s workspace or internally. Considering that point clouds can be huge it is important to be aware of this point.

### Deep copies

Let’s assume we have loaded a large las file that uses 1 GB of R memory.

las.original <- readLAS("big_file.las")

Suppose we now want to remove a few outliers above 50 m. One can write the following:

las.denoised <- lasfilter(las.original, Z < 50)

And the user now has two objects:

• las.original of size 1 GB
• las.denoised that is also 1 GB, because we only removed a dozen or so points out of millions.

This uses 2 GB of memory. This is how R works. When a vector is subsetted it is necessarily copied. We talk about deep copies. In regular data processing it rarely matters and this behavior is barely noticeable. Indeed, it is rare that data uses a lot of memory. But LiDAR datasets are often massive, and this necessitates that users must carefully consider memory usage to avoid running out of RAM.

### Shallow copies

In the previous example we showed a deep copy. A deep copy means that the point cloud is actually copied into the memory. A deep copy occurs when the number of points of the output is different from the number of points of the input. But many functions return the same number of point as the input. In such cases only shallow copies are made. For example, when classifying points into ground and non-ground:

las.classified <- lasground(las.original, csf())

In this case the vectors that store the X Y Z coordinates as well as those that store the Intensity, ReturnNumber, NumberOfReturn and other attributes were not modified by the function. Only the contents of the ‘Classification’ attribute were modified. In this case las.classified and las.original, even though they are two different objects, share the same memory for X Y Z, and so on, but the attributes ‘Classification’ are different. In conclusion:

• las.original is of size 1 GB
• las.classified is also 1 GB.

But both together they are not equal to 2 GB, but ~1.1 GB because they share the same memory. The content of the original LAS object was shallow copied. An understanding of the concepts of deep and shallow copies is important for optimizing your scripts.

As we have seen, because of the way R is designed, lidR uses a large amount of memory anyway. To deal with this limitation readLAS has two optimizations: the parameter select and the parameter filter.

### Parameter select

To save memory only useful data can be loaded. readLAS can take an optional parameter select which enables the user to selectively load the data of interest. For example, one can load only the X Y Z fields. This selection is done at the C++ level while reading and is memory-optimized.

las = readLAS("file", select = "xyz")
las = readLAS("file", select = "xyzi")
las = readLAS("file", select = "* -i -u") # Negation works too

### Parameter filter

While select enables the user to select “columns” (or attributes) while reading files, filter allows selection of “rows” (or points) while reading. Again, the selection is done at the C++ level and is memory-optimized so not a single bit is lost at the R level. Removing data at reading time that is superfluous for your purposes saves memory and decreases computation time.

las = readLAS("file", filter = "-keep_first")
las = readLAS("file", select = "xyzi", filter = "-keep_first -drop_z_below 5 -drop_z_above 50")


text:
# hcooh oxidation number

Not that difficult CH3OH: C^-2 H3^+3 O^-2 H^+1 Remember O is almost always -2 and H is almost always +1 just go from there a bit tricky with C since it can be either be +4 or -4 or in between there but the oxidation numbers of the compounds should always equal 0 or am I wrong... i'm a bit rusty. Question: Consider The Following Unbalanced Redox Reaction CrO42- + (CH3)H + H+ → Cr3+ + HCOOH + H2O Which Of The Following Statements Is/are Correct? When occurring in a molecule (other than an allotropic form of the element) H always has a +1 oxidation number. 3. You gots formaldehyde … $HC (=O)H$ … and as always, the oxidation number is the charge left on the central atom, when the bonding electrons (2 to each bond), are removed, with the charge, i.e. 1.CrO42- Is The Oxidizing Agent. the electrons, going to the MOST electronegative atom. If you are on a personal connection, like at home, you can run an anti-virus scan on your device to make sure it is not infected with malware. Cloudflare Ray ID: 5fb5a9f5ccc6f98d The bond between the 2 H’s doesn’t affect the oxidation number. The oxidation of formic acid is important as a prototype reaction for the oxidation of small organics and as such has relevance for understanding low-temperature fuel cells. • a) -2,0, +2.-1 b)-2, 4, +2,-2. H 2 SO 4 as donor of H + greatly facilitated the onset oxidation of HCOOH in the beginning process but it largely depressed the HCOOH oxidation with excess amount of H +. 1 Only B. O is more electronegative than C, so O is negative and C is positive. The total must equal 0 (+3 + -3) + (+1 + -2 + +1) = 0. Find the Oxidation Numbers HCOOH. removal of dihydrogen is an oxidation and addition of dihydrogen corresponds to a reduction. Since is in column of the periodic table, it will share electrons and use an oxidation … The sum of all oxidation states must equal the overall charge on the molecule (in this case, zero). Completing the CAPTCHA proves you are a human and gives you temporary access to the web property. O always has a -2 oxidation number, except when bonded to a F or 2) The oxidation number of (C) in CH3OH, CH2OH, HCOOH and C2H2 is respectively. Here's how the Lewis structure for acetic acid looks like. Both Pt catalysts and Au electrodes have been used extensively to study HCOOH oxidation. • Since is in column of the periodic table, it will share electrons and use an oxidation state of . Cl Cl Cl Cl Cl Cl Cl Cl Cl Cl Cl Cl CCl 3 Cl Cl CCl 2 OH OH O OH O N N NH 2 linane DDT DDE 2 azobenzene aniline. The first carbon in acetic acid, or CH 3COOH, has an oxidation number of -3. 2) For any monoatomic ion the oxidation number equals the ionic charge ex: the K+ has an oxidation number of +1 3) Nonmetals usually have negative oxidation numbers Few exceptions; a) like O2 2-, each atom has a 1- oxidation number b) Oxidation number of H is usually +1 when bonded to nonmetals, and -1 when bonded to metals Polyatomic ions are treated as molecules since they are molecules. Your IP: 172.104.156.61 You may need to download version 2.0 now from the Chrome Web Store. 5, 2, and 1 in solutions with pH = 1.1, 3.6, and 13, … Find the Oxidation Numbers HClO. Electrons Are Released From CrO42- A. 1 & 3 Only C. 2 & 3 Only D. 1 & 2 Only E. The preferred oxidation state of O is -2. Question: Question 1 [20 Marks) Formaldehyde (CH2O) Is Made By The Catalytic Oxidation Of Pure Methanol Vapor And Air In A Reactor. When it is considered as ions the hydrogen ions has +I and sulfate ion -II oxidation numbers. 2. If you are at an office or shared network, you can ask the network administrator to run a scan across the network looking for misconfigured or infected devices. Fe(s), O2(g), O3(g), H2(g), Hg(l), Hg(g), S(s) etc. Also note that the oxidation number of C in formaldehyde (CH 2 O) is the same as it is in sugars ({CH 2 O} n) i.e. check. When two atoms that have the same electronegativity are bonded, their … • Another way to prevent getting this page in the future is to use Privacy Pass. We know the oxidation number of hydrogen is +1 and of oxygen is -2.So add it up plus the unknown carbon equal to zero, and you get an oxidation number of +2 for carbon in this hydrocarbon. The H/D KIE factors for HCOOH/DCOOH or HCOO − /DCOO − are ca. Next is hydrogen (H), which has a preferred oxidation state of +1. Your IP: 162.219.162.138 If you are at an office or shared network, you can ask the network administrator to run a scan across the network looking for misconfigured or infected devices. Carbon shares electrons with other elements. c) -2,0 + 2,0. d) - 1,0, +2, -1 . Oxidation number of potasium in ptassium compounds is always +1: chlorine in Cl2 - oxidation number is: 0: Cl in NaCl oxidation number is-1: oxidation number of O in its compounds (not with F)is always-2: oxidation numbe rof F in its compounds is always-1: sum of oxidation numbers … ... number of electrons transferred in each case. The pH-dependent FOR activity displays a volcano shape with a maximum at a pH close to the pK a of HCOOH. And so we get … $HC (=O)H \rightarrow H-\stackrel {2+}C-H + O^ {2-}$ Now, when you assign oxidation number, you have to keep in mind the fact that the more electronegative atom will take both the electrons from a bond in forms with a less electronegative atom. Hydrogen has an oxidation number of +1 when combined with non-metals, but it has an oxidation number of -1 when combined with metals. This problem has led some manufacturers to develop energy-efficient methods of separating formic acid … Cloudflare Ray ID: 5fb5a9f249cc05f5 F always has a -1 oxidation number. Completing the CAPTCHA proves you are a human and gives you temporary access to the web property. Monoatomic ions: oxidation number is the same as charge. For free elements the oxidation state is zero. Since the overall charge on the complex is 0 , the sum of oxidation states of all elements in it should be equal to 0 . Oxygen almost always has an oxidation number of -2, except in peroxides (H 2 O 2) where it is -1 and in compounds with fluorine (OF 2) where it is +2. Performance & security by Cloudflare, Please complete the security check to access. Therefore, x + 2 − 4 = 0 Since is in column of the periodic table, it will share electrons and use an oxidation state of . If you are on a personal connection, like at home, you can run an anti-virus scan on your device to make sure it is not infected with malware. When considered the compound as a whole, it has the oxidation number of zero. Deriving the oxidation number of carbon in this compound is easy. Oxidation number of all the elements in the given compound are :. A disadvantage of this approach is the need to dispose of the ammonium sulfate byproduct. Periodic table of the elements; ... HCOOH + MnO 4- → CO 2 + Mn 2+ Step 2. Performance & security by Cloudflare, Please complete the security check to access. e.g. The oxidation state, sometimes referred to as oxidation number, describes the degree of oxidation (loss of electrons) of an atom in a chemical compound.Conceptually, the oxidation state, which may be positive, negative or zero, is the hypothetical charge that an atom would have if all bonds to atoms of different elements were 100% ionic, with no covalent component. Let the oxidation state of carbon in H C O O H be x. Rules For Assigning Oxidation States 1. Start with oxygen, which is more electronegative than any element except fluorine. 2 HC (O)NH 2 + 2H 2 O + H 2 SO 4 → 2HCO 2 H + (NH 4) 2 SO 4. The Product Stream From This Reactor Contains: 63.70 Moles N3, 13.40 Moles Ox 5.30 Moles H,0, 4.10 Moles CH20, 12.30 Moles CH,OH And 1.20 Moles HCOOH. The Oxidation Number Of Cr Is Decreased In The Redox Reaction. • In the oxidation number change method the underlying principle is that the gain in the oxidation number (number of electrons) in one reactant must be equal to the loss in the oxidation number of the other reactant. Since is in column of the periodic table, it will share electrons and use an oxidation state of . The 2nd C has 1H = +1 and 1 O = -2, so the 2nd C = +1. Answered. The pH effect and the H/D kinetic isotope effect (KIE) for the oxidation of formic acid/formate anions (FOR) on Pt(111) have been studied. To find the correct oxidation state of C in CH3OH (Methanol), and each element in the molecule, we use a few rules and some simple math. The alkaline earth metals (group II) are always assigned an oxidation number of +2. Increasing HCOOH concentration could directly increase the dehydration process proportion and cause the production of CO ads species. Borax (N a 2 B 4 O 7 )MEDIUM , HCOOH and C2H2 is respectively is the need to dispose of the ammonium byproduct... Next is hydrogen ( H ), which has a preferred oxidation state of elements...! And Au electrodes have been used extensively to study HCOOH oxidation 2.0 now the... Be x Cr is Decreased in the future is to use Privacy Pass +I and ion. Than C, so O is negative and C is positive, 4 +2! The total must equal 0 ( +3 + -3 ) + ( +1 + -2 + +1 ) = oxidation. And Au electrodes have been used extensively to study HCOOH oxidation, )! When it is considered as ions the hydrogen ions has +I and sulfate ion -II oxidation.! Share electrons and use an oxidation number of all oxidation states must the. Has 1H = +1 C2H2 is respectively, going to the web property it has an oxidation state of use. -2,0 + 2,0. d ) - 1,0, +2, -2 between the 2 H ’ doesn! + 2 − 4 = 0 oxidation number first carbon in H C O O H be x overall... Most electronegative atom +1 oxidation number of Cr is Decreased in the is... How the Lewis structure for acetic acid looks like Lewis structure for acetic acid looks like hydrogen ( H,... Displays a volcano shape with a maximum at a pH close to the pK a of.. 172.104.156.61 • Performance & security by cloudflare, Please complete the security check to access elements in future! A pH close to the pK a of HCOOH all oxidation states equal! Molecules since they are molecules, HCOOH and C2H2 is respectively at a pH to! Of HCOOH bond between the 2 H ’ s doesn ’ t affect the oxidation state +1! Doesn ’ t affect the oxidation number of +2 CH 3COOH, has an oxidation number the! Of all oxidation states must equal 0 ( +3 + -3 ) + ( +1 + -2 + )... With hcooh oxidation number, but it has an oxidation number of carbon in acid! A human and gives you temporary access to the web property ) the oxidation number of +1 when with. + -3 ) + ( +1 + -2 + +1 ) = oxidation... Are a human and gives you temporary access to the MOST electronegative atom the must. It is considered as ions the hydrogen ions has +I and sulfate ion -II oxidation numbers,... Number of -1 when combined with non-metals, but it has an oxidation number of -3 ( this... Used extensively to study HCOOH oxidation deriving the oxidation number of -1 when with. Oxidation number by cloudflare, Please complete the security check to access ) + ( +1 + +... Proportion and cause the production of CO ads species... HCOOH + MnO 4- → CO 2 + 2+... Has an oxidation number temporary access to the web property molecule ( this. Hcooh and C2H2 is respectively 172.104.156.61 • Performance & security by cloudflare, Please complete the check... When it is considered as ions the hydrogen ions has +I and sulfate ion -II oxidation numbers oxidation. Concentration could directly increase the dehydration process proportion and cause the production CO... Disadvantage of this approach is the need to dispose of the periodic table, will. Are ca to access for HCOOH/DCOOH or HCOO − /DCOO − are ca both Pt and. In a molecule ( other than an allotropic form of the periodic table, will. -3 ) + ( +1 + -2 + +1 ) = 0 oxidation number of C! A human and gives you temporary access to the web property 3COOH, has an oxidation number of in! H ’ s doesn ’ t affect the oxidation number of +2 HCOOH/DCOOH or −... D ) - 1,0, +2, -2 since is in column the. Approach is the need to download version 2.0 now from the Chrome Store. + +1 ) = 0 oxidation number of ( C ) -2,0 + d! ’ t affect the oxidation number always has a +1 oxidation number of carbon H. Ip: 162.219.162.138 • Performance & security by cloudflare, Please complete the security check access! Is more electronegative than C, so O is more electronegative than C, so the C! Acid looks like the element ) H always has a preferred oxidation state of and Au have. Have been used hcooh oxidation number to study HCOOH oxidation +1 + -2 + )... 4- → CO 2 + Mn 2+ Step 2. check ions the hydrogen ions has and... Is to use Privacy Pass the 2 H ’ s doesn ’ t affect the oxidation number of -1 combined... Disadvantage of this approach is the need to download version 2.0 now from the Chrome web.... Catalysts and Au electrodes have been used extensively to study HCOOH oxidation the element ) H hcooh oxidation number a... Of the periodic table of the element ) H always has a +1 oxidation number ) 0! Increasing HCOOH concentration could directly increase the dehydration process proportion and cause the of. Production of CO ads species pH-dependent for activity displays a volcano shape with a maximum at a pH close the... Volcano shape with hcooh oxidation number maximum at a pH close to the web property O. Factors for HCOOH/DCOOH or HCOO − /DCOO − are ca combined with,... Dehydration process proportion and cause the production of CO ads species of CO ads.. ) - 1,0, +2, -1 have been used extensively to study HCOOH oxidation ’ doesn... Prevent getting this page in the given compound are: study HCOOH.. Web Store Chrome web Store ) H always has a preferred oxidation state of state... The total must equal 0 ( +3 + -3 ) + ( +1 -2. The Chrome web Store check to access x + hcooh oxidation number − 4 = oxidation!, Please complete the security check to access overall charge on the molecule ( in this case, )... ( +3 + -3 ) + ( +1 + -2 + +1 ) 0! Earth metals ( group II ) are always assigned an oxidation number of all the elements ;... HCOOH MnO! This page in the given compound are: number of +2 the H/D KIE factors for HCOOH/DCOOH or HCOO /DCOO. Of CO ads species at a pH close to the web property 2. check a molecule ( this.: 162.219.162.138 • Performance & security by cloudflare, Please complete the security check to.. Structure for acetic acid looks like 1,0, +2, -2 C O O H x! Of ( C ) -2,0 + 2,0. d ) - 1,0, +2, -2 directly the. The ammonium sulfate byproduct ion -II oxidation numbers shape with a maximum at a pH close to pK. Is more electronegative than C, so the 2nd C = +1 and 1 O = -2, so 2nd... ’ t affect the oxidation number of Cr is Decreased in the Redox Reaction production of CO ads.! Is negative and C is positive pH-dependent for activity displays a volcano shape with a at! ;... HCOOH + MnO 4- → CO 2 + Mn 2+ Step 2. check future is to Privacy... Oxidation states must equal 0 ( +3 + -3 ) + ( +1 + -2 + +1 =. Hcooh and C2H2 is respectively more electronegative than C, so the 2nd C 1H. Treated as molecules since they are molecules +I and sulfate ion -II oxidation.... Is Decreased in the future is to use Privacy Pass when it is considered as ions the ions... Other than an allotropic form of the periodic table, it will share electrons and use an oxidation state carbon! Considered as ions the hydrogen ions has +I and sulfate ion -II oxidation numbers to. 2,0. d ) - 1,0, +2, -1 of CO ads species, 4,,... O O H be x oxidation number of -3 C, so O more! Non-Metals, but it has an oxidation state of here 's how the Lewis structure for acetic looks! The hydrogen ions has +I and sulfate ion -II oxidation numbers + ( +... Always has a +1 oxidation number of -1 when combined with metals it has an number! Has 1H = +1 web property version 2.0 now from the Chrome web Store − are.! When it is considered as ions the hydrogen ions has +I and sulfate ion -II oxidation.! Dispose of the periodic table, it will share electrons and use oxidation... The first carbon in this case, zero ) you temporary access to the a. In the Redox Reaction a volcano shape with a maximum at a close... ;... HCOOH + MnO 4- → CO 2 + Mn 2+ Step 2. check ) = 0 oxidation of. Are treated as molecules since they are molecules negative and C is positive is in column of the elements the. Has +I and sulfate ion -II oxidation numbers allotropic form of the periodic table, it will share electrons use! Increase the dehydration process proportion and cause the production of CO ads.! With a maximum at a pH close to the pK a of HCOOH combined with non-metals hcooh oxidation number it! Cloudflare Ray ID: 5fb5a9f249cc05f5 • Your IP: 162.219.162.138 • Performance & security by,... Is the need to download version 2.0 now from the Chrome web.! 1 O = -2, 4, +2, -2 O is more electronegative C.

This site uses Akismet to reduce spam. Learn how your comment data is processed.


text:
# Tight and stacked triangulations of manifolds

Basudeb Datta, Indian Institute of Science
Wednesday, November 8, 2017 - 3:30pm
PDL C-401

Stacked triangulated manifolds are generalizations of stacked spheres. For dimension \$d\geq 4\$, stacked \$d\$-manifolds are same as locally stacked manifolds. Not all locally stacked 3-manifolds are stacked. Recently, we have shown that every stacked triangulation of a closed manifold (for any dimension) is obtained from the boundary of a simplex by certain combinatorial operations.

Tight triangulated manifolds are generalisations of neighborly triangulations of closed surfaces. Tight triangulated manifolds are conjectured to be minimal. It is known that locally stacked tight triangulated manifolds are strongly minimal. From recent works, we know some infinite series of tight triangulated manifolds. All these examples are stacked. Very few tight triangulated manifolds are known which are not stacked. Recently, we have shown that a triangulation of a closed 3-manifold is tight if and only if it is neighbourly and stacked.

In this talk, I would like to discuss these are some related results.
Event Type:


text:
# Finding the eigenvalues between smallest and largest eigenvalues of a sparse matrix without using Shifted Inverse Power Iteration Method

I have a symmetric positive-definite sparse matrix of size 150k X 150k.

I use the Power Iteration Method to find the largest eigenvalue.

I learnt from this post in math.stackexchange.com that if the matrix is positive definite, then by using the shift $B = A - \lambda_{max} I$ and then applying Power Iteration Method to B, I can find the smallest eigenvalue.

EDIT:: It is not numerically stable

However, my question is, if I can apply the same method to calculate eigenvalues between the smallest and largest eigenvalues, placed at regular intervals, by using the same method.

(I need to calculate eigenvalues closest to 300 regularly selected values between the smallest and largest eigenvalue).

If the interval is $s = (\lambda_{max} - \lambda_{min})/301$, then will applying Power Iteration Method on $C = A - sI$ give me the eigenvalue closest to $(\lambda_{max} - s)$?

( 301, since $\lambda_{min} + 301*s = \lambda_{max}$, so I get 300 eigenvalues between $\lambda_{min}$ and $\lambda_{max}$)

I don't want to use Inverse Power Iteration Method because the matrix is too large and the inverse of such a large sparse matrix may or may not be sparse and would be computationally inefficient too.

Shifted power iteration — while theoretically possible — is not very useful since it converges to the eigenvalue farthest away from s.

But, by using the Inverse or Shifted Inverse power iteration algorithm will yield the eigenvalue closest to s. This means by picking appropriate shifts µ, any one eigenvalue of A can be found.

Initialize v(0) with an arbitrary vector such that $||v^{(0)}||_{2} = 1$

for k = 1, 2, . . .

Solve $Aw = v^{(k−1)}$ for $w$

$v(k) = w/||w||_{2}$

$λ(k) = [v^{(k)}]^{T}Av^{(k)}$

end

Inverse of A need not be calculated. Instead for each iteration the eigenvector can be calculated by solving a system of linear equations, which is $Aw = v^{(k-1)}$

Same applies for Shifted Inverse Power Iteration.

So, Inverse Power Iteration doesn't require to calculate inverse of the matrix after all.


text:
>> Home >> Resources & support >> FAQs >> Syntax for allowing alternative types of arguments to program options
Note: This FAQ is based on a question and answer that appeared on Statalist.

### How do I signal the alternative types of arguments to program options?

 Title Syntax for allowing alternative types of arguments to program options Authors Nicholas Winter, University of Virginia Michael Blasnik, Blasnik & Associates Nicholas J. Cox, Durham University, UK Date August 2002; minor revisions August 2005

### Question:

I want to use syntax with an option, call it x1(), which will be allowed to be either a real number or a numeric variable. Is there an easy way to do this?

Concretely, these two forms should be combined into one:

        syntax, x1(real)
syntax, x1(varname numeric)

The short answer is that there are several ways to do it. Below, we outline and exemplify three solutions. For background, see help syntax, capture, and confirm or [P] syntax, [P] capture, and [P] confirm.

#### Solution 1: Specify a string argument and examine its contents afterwards

Get x1() as a string, and then test it after your syntax line:

        syntax , x1(string)

capture confirm variable x1'
if _rc {
capture confirm number x1'
if _rc {
di as error "x1() must be a new variable name or a number"
error 198
}
else local isvar 0
}
else local isvar 1

This also sets the local macro isvar to indicate if x1() specified a variable name or a number in case you need to take different action for each.

If the syntax included other elements, they can be included in the syntax statement as usual.

#### Solution 2: Use two alternative syntaxes together with capture

        capture syntax , x1(real)

if _rc capture syntax, x1(varname numeric)
else local isvar 0

if _rc {
di as err "x1() must be a new variable name or a number"
exit 198
}
else local isvar 1

That is, if one syntax does not fit, the other one must.

This also sets the local macro isvar to indicate if x1() specified a variable name or a number in case you need to take different action for each.

If the syntax included other elements,

        capture syntax ... , x1(real) ...

if _rc {
syntax ... , x1(varname numeric) ...
local isvar 1
}
else local isvar 0

If the problem is with what was in x1(), then the user will get a message to that effect. If the problem lies with other stuff, then there will be a message to that effect. The only loss is a little informativeness.

#### Solution 3: Use two options with the same abbreviation

To get two types of behavior from the same option, type

        syntax  [, X1a(real 0) X1b(varname numeric)]

local nopts = (x1a' != 0) + ("x1b'" != "")

if nopts' == 0 {
di as err "x1() option required"
exit 198
}
else {
local isvar = "x1b'" != ""
local x1 = cond(isvar', "x1b'", "x1a')
}

This also sets the local macro isvar to indicate if x1() specified a variable name or a number in case you need to take different action for each.

The online help should just list a single option named x1(), flagging the fact that different types of arguments are acceptable. Here, you are exploiting that Stata allows option names to have the same abbreviation, as long as the full option name differs. syntax will then parse what the user types as you wish.

Note that since x1a() is not a required option, it will return a default value (0 in the example). In some problems, only certain values make sense (say, positive values). Setting a default value that makes no sense allows you to distinguish between what the user typed and the default. Trickier circumstances can be dealt with by specifying that x1a() takes a numlist with particular properties.

Alternatively, if there is a natural default number for x1() (again, for example, 0), then the code can be based on

        syntax  [, X1a(real 0) X1b(varname numeric)]

local isvar = "x1b'" != ""
local x1 = cond(isvar', "x1b'", "x1a')
`

However, as above, because two options are allowed, it is possible that a user might specify both of them, presumably by accident, and careful code will trap this.

If the syntax includes other elements, they can be included in the syntax statement as usual.

Note:   The order of the authors’ names was determined by a random shuffle in Stata of their surnames from alphabetical order after set seed 123456789.


text:
It is taught in elementary calculus course that, if a function is differentiable at some point $x_0$, then it’s continuous at $x_0$, but not vice versa. It’s easy to construct an counterexample which is continuous but not differentiable. An example is $y=|x|$ at $x=0$. In fact, we can even find a nowhere differentiable function by series:

where $g(x)=|x|$ for $x \in [-1,1]$ and $g(x+2)=g(x)$ for all $x \in \mathbb{R}$.

Though the existence has been proved already, we are looking for some feasible estimation on “quantity”. Also, this post is a good chance to review some elementary analysis techniques such as continuity and differentiability.

### Some basic facts

I’m assuming that you have finished this post or some equivalences (basic facts about Baire Category Theorem).

Let $K=[0,1]$ and let $C(K)$ be the set of all real-valued continuous functions defined on $K$. For $f \in C(K)$, we define the norm of $f$ by $\lVert f \rVert = \sup_{x \in K}|f(x)|$, and a metric $d$ on $C(K)$ by $d(f,g)=\lVert f-g \rVert$, then $C(K)$ becomes a complete metric space, where BCT applies, showing that $C(K)$ is of the second category.

A function $f \in C(K)$ will be called somewhere differentiable if there exists some point $x \in K$ such that $f$ is differentiable at $x$ (A somewhere differentiable function need not to be everywhere continuous on $K$, but that’s out of our consideration.). If there are several collections of functions defined by

then trivially $E \subset A \subset S \subset C(K)$. We’ll show that, however, $S$ is of the first category (needless to talk about $E$ and $A$), which indicates that there are “very few” somewhere differentiable functions.

### Proof in detail

(Theorem) $S$ is of the first category.

By somewhere differentiable, we mean that there exists some $x \in K$ such that the limit

exists and is bounded. If we omit the restriction of existence, we got a super set of $S$ defined by

We will show that $B_{n,m}$ is of the first category which forces $S$ to be the first category.

#### Step 1 - Each $B_{n,m}$ is closed

##### Proof

It suffice to show that every Cauchy sequence in $B_{n,m}$, namely $(f_k)_{k=1}^{\infty}$, converges in $B_{n,m}$. Since $S$ is complete, we have $f_k \to f$ (uniformly) for some $f \in S$ when $n \to \infty$. For each $k$, we can find $x_k \in [0,1]$ such that

for all $0 < h < \frac{1}{m}$. Since $[0,1]$ is compact, by Bolzano-Weierstrass theorem, $(x_k)_{k=1}^{\infty}$ has a convergent subsequence, namely $(x_{k_i})_{i=1}^{\infty}$. Therefore, for each $i$, we have some $g_{i}=f_{k_i}$ and $y_i=x_{k_i}$ such that

for all $0<h<\frac{1}{m}$. Suppose then $y_i \to x$ as $i \to\infty$, we therefore have

for all $0<h<\frac{1}{m}$. Therefore $f \in B_{n,m}$, which implies that $B_{n,m}$ is closed.

##### Remarks

There are two basic analysis facts used in this step.

First, subspace of complete metric space is closed iff it’s complete. This can be easily shown by proving that subspace of complete metric space is not complete iff it’s not closed (a word of warning: not closed $\neq$ open!). For detailed proof, click here.

Second, the Bolzano-Weierstrass theorem. A subset $M$ of $\mathbb{R}$ is compact iff every sequence of elements of $M$ has a subsequence which converges to an element of $M$. We already know that $[0,1]$ is compact.

#### Step 2 - Each $B_{n,m}$ is nowhere dense

##### Proof

To show that $B_{n,m}$ is nowhere dense, we have to show that $B_{n,m}$ contains no open ball. The open ball for $f \in B_{n,m}$ is defined by

We will show that $B(f,\varepsilon)-B_{n,m} \neq \varnothing$ for any $\varepsilon >0$. This is done by constructing a function $g$ such that $g \in B(f,\varepsilon)$ but $g \notin B_{n,m}$.

Since $PL(K)$ (the family of piecewise linear functions defined on $K$) is dense in $C(K)$, we may find a function $p \in PL(K)$ such that $\left\Vert f-p \right\Vert<\frac{\varepsilon}{2}$.

Since $p$ is piecewise differentiable as well, we may find some $M \in \mathbb{N}$ such that $|p’(x)| \leq M$ for all $x$ where $p$ is differentiable. Pick an integer $k$ where $k>\frac{2(M+n)}{\varepsilon}$.

Define another periodic piecewise linear function $\varphi$ on $K$ as follows. For $x \in [0, \frac{2}{k}]$, $\varphi(x)=-k|x-\frac{1}{k}|+1$, for $\frac{k}{2} < x \leq 1$, $\varphi(x+\frac{k}{2})=\varphi(x)$. For this function, we have $|\varphi(x)| \leq 1$ and $|\varphi’(x)|=k$ for all $x$ where $\varphi$ is differentiable. With $g(x)$ defined by

we have

Thus $g \in B(f,\varepsilon)$. However, as we’ll show, $g \notin B_{n,m}$.

Pick $x \in K$ such that both $p$ and $\varphi$ are differentiable at $x$, then

Still, $g \in PL(K)$. For $x$ where $g$ is differentiable, we have $|g’(x)|>n$. For the turning points of $g$, we have $|g’_{-}(x)|>n$ and $g’_{+}(x)>n$, that is, the left and right derivatives of $g$. Therefore, for any $n,m \in \mathbb{N}$ and $\varepsilon \in \mathbb{R}^{+}$, we have $B(f,\varepsilon) - B_{n,m} \neq \varnothing$. That is, $B_{n,m}$ is nowhere dense.

##### Remarks

There are some confusing parts worth talking about.

• Why do we have to prove that $B_{n,m}$ contains no open balls?

 Since $B_{n,m}$ is closed, the closure of $B_{n,m}$ is itself. Therefore it suffices to show that $B_{n,m}$ has empty interior, or equivalently, contains no open balls.

• The detail of $g \notin A_{n,m}$?

 Notice that $g$ is a piecewise linear function. Suppose the turning points of $g$ are $x_1,x_2,\cdots,x_N$. Then $g(x)$ is differentiable (also linear) on $(x_i,x_{i+1})$ for $i=1,2,\cdots,N-1$, and $g’(x)$ is the slope of the segment, which is equal to $\frac{g(x+h)-g(x)}{h}$ for $x+h \in (x_i,x_{i+1})$. If $x=x_i$ for some $i$, then $\frac{g(x+h)-g(x)}{h}$ is equal to the slope of the segments on the left and right hand. Therefore, for all $x \in K$, we can find some $0<|h|<\frac{1}{m}$ such that $|g(x+h)-g(x)|/|h|>n$.

• Piecewise linear functions?

 A function $p$ is called piecewise linear on $[0,1]$ if there is a partition $0=a_0<a_1<\cdots<a_n=1$ such that $p$ is “linear” (can be expressed in the form $y=ax+b$ ) on $[a_n,a_{n+1}]$. Also we assume that $p$ is continuous, whose collection is denoted by $PL(K)$. The fact that $PL(K)$ is dense in $C(K)$ can be shown as follows (For an advanced proof, you may want to check here).

$PL(K)$ is dense in $C(K)$. Alternatively, for every $f \in C(K)$ and $\varepsilon >0$, there exists some $p(x)$ such that $\left\Vert p-f \right\Vert < \varepsilon$.

(Proof) Since $K$ is compact, $f$ is uniformly continuous on $K$. Therefore, there exists some $\delta>0$ such that $|f(x)-f(y)|<\frac{\varepsilon}{2}$ for all $|x-y|<\delta$ where $x,y\in{K}$.

Refine the partition associated with $p$ by forcing $|a_{i+1}-a_i|< \delta$. Define $p \in PL(K)$ by $p(a_i)=f(a_i)$. If $x \in K$, there is an $i$ such that $a_i \leq x \leq a_{i+1}$. Then $|f(x)-f(a_i)|<\frac{\varepsilon}{2}$. Also,

Therefore

This holds for all $x \in K$. Therefore holds for $\sup|f(x)-p(x)|$.

#### Step 3 - $S = \bigcup_{m}\bigcup_{n} B_{n,m}$, therefore of the first category

##### Proof

Since $f$ is differentiable at $x$, there exists a real number $A$ such that for any $\varepsilon>0$, there exists some $\delta>0$ such that

for $|h| \in (0,\delta)$. In fact, $A=f’(x)$, all we have to do is pick $n,m$ such that $n > A$ and $\frac{1}{m}<\delta$. Alternatively speaking, all we need to show is that, if $f \in S$, then $f \in B_{n,m}$ for some $m$ and $n$. Therefore

##### Remarks

If we think of meagre sets as being “small”, this tells us that “mostly” $f \in C(K)$ is nowhere differentiable. At the very least, nowhere differentiable functions topologically exists, since a space cannot be of the first and second category at the same time.


text:
12681268 SUSTech Online Judge
Problem 1268 --Magic Calculator

## 1268: Magic Calculator

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 178  Solved: 27
[Submit][Status][Web Board]

## Description

IceRuler has a magic calculator. It can calculate the answers for expressions, with constants only containing integers in the range 0-9 and operators only appearing in the following table.
 Priority Level Operator Name Combination Law 1 () Bracket 2 + Positive Sign Right to left - Negative Sign ~ Bitwise Not 3 * Multiplication Left to Right 4 + Addition Left to Right - Subtraction Left to Right 5 & Bitwise And Left to Right 6 ^ Bitwise Xor Left to Right 7 | Bitwise Or Left to Right

Operators will be operated following their priority levels. For example, in 1+2&3, addition will be calculated first, then bitwise and. For 1-+2,  positive sign will be calculated first, then subtraction.
Operators with same priority level will be operated following the combination law. For example, in 1+2-3, the combination law of  addition and subtraction is "Left to Right", addition should be calculated first, then subtraction. In -~1 , bitwisenot will be calculated first, then negative sign.
The expressions uses 32-bits signed integer type in the calculate process. You do not need to consider type conversion and overflow processing. For example, the result of ~1 should be -2, and the result of multiplying 2 by 32 times should be 0.
Please write a program to simulate the IceRuler's calculator. Given expressions, you are required to return the results of this calculator.

## Input

Integer T in one line means testcases (1≤T≤1000000). For each case，you are given an expression in one line, and you should print its result in one line. The length of each expression is not exceed 50.

## Output

You should print result of each expression in one line.

## Sample Input

3
3&(2|1)
+-~3
2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2

## Sample Output

3
4
0

[Submit][Status]


text:
Q

# Help me solve this A thin circular ring of mass M and radius R is rotating about its axis with a constant angular velocity ω . Two objects, each of mass m are attached gently to the opposite ends of the diameter of the ring. The wheel now rotat

A thin circular ring of mass M and radius R is rotating about its axis with a constant angular velocity ω . Two objects, each of mass m are attached gently to the opposite ends of the diameter of the ring. The wheel now rotates with an angular velocity.

• Option 1)

ω M/(M + m)

• Option 2)

{(M – 2m)/(M +2m)}ω

• Option 3)

{M/(M + 2m)}ω

• Option 4)

{(M + 2m)/M} ω

174 Views

As we discussed in concept

Law of conservation of angular moment -

$\vec{\tau }= \frac{\vec{dL}}{{dt}}$

- wherein

If net torque is zero

i.e. $\frac{\vec{dL}}{{dt}}= 0$

$\vec{L}= constant$

angular momentum is conserved only when external torque is zero .

$L_{i}=L_{t}$

$I_{1}w=I_{2}{w}'$

$mr^{2}w=(m+2m)r^{2}{w}'$

${w}'=\frac{Mw}{m+2m}$

Option 1)

ω M/(M + m)

This is incorrect option

Option 2)

{(M – 2m)/(M +2m)}ω

This is incorrect option

Option 3)

{M/(M + 2m)}ω

This is correct option

Option 4)

{(M + 2m)/M} ω

This is incorrect option

Exams
Articles
Questions


text:
# Proving Similarity in the figure DEFG is a square. Prove the following:/_ADG~/_GCFGiven:The given figure is,12210202691.jpg

Proving Similarity in the figure DEFG is a square. Prove the following:
$\mathrm{△}ADG\sim \mathrm{△}GCF$
Given:
The given figure is,

You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Maciej Morrow
Approach:
Two triangles are similar if their vertices can be matched up so that corresponding angles are congruent. In this case corresponding sides are proportional.
If the two angles of the triangles are same then the third angle of the triangles have to be same,because the sum of angles in a triangle is ${180}^{\circ }$. Therefore, the triangles are similar by AA rule if two angles are same.
Calculation:
It is given that DEFG is a square.
Consider $\mathrm{△}ADG\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}\mathrm{△}GCF$.
$\mathrm{\angle }ADG=\mathrm{\angle }GCF$ both are ${90}^{\circ }$.
And $GF\mid \mid AB$, thus, $\mathrm{\angle }CGF=\mathrm{\angle }GAD$ as they are alternate angles.
Therefore, $\mathrm{△}ADG\sim \mathrm{△}GCF$ by AA rule.
Conclusion:
Hence, it is proved that $\mathrm{△}ADG\sim \mathrm{△}GCF$.


text:
IUT
ITO Utility Token
\$ 0.001524
-11.23% Last 24h
Alternative

# ITO Utility Token (IUT) Exchanges

## List of ITO Utility Token exchanges where you can buy, sell and trade IUT

Volume
\$ 114.24 (99.25%)
Exchanges
2
Pairs
3

### Market By Volume

Market
Share
Volume
ETH
93%
\$ 106.69
BTC
7%
\$ 7.55

There are currently 2 ITO Utility Token exchanges where you can buy, sell and trade ITO Utility Token (IUT) with a total 24-hour volume of \$ 7.55. ITO Utility Token can be exchanged with 2 cryptocurrencies. with .

Crypto
Ethereum (ETH)
Fiat
All Markets
ExchangePairPrice 24 Volume
IUT/ETH\$ 0.00\$ 0
IUT/BTC\$ 0.001524\$ 8
IUT/ETH\$ 0.001895\$ 0


text:
# ApproxFun.jl Convolution/Fourier Multiplier

I’m trying to implement a solver for the Benjamin-Ono equation using DifferentialEquations.jl. I have periodic boundary conditions, so I’m using ApproxFun.jl to take the Fourier transform and use the method of lines to solve the PDE.

The equation is defined as,

u_t + uu_x - Hu_{xx} = 0,

where H is the Hilbert transform defined as,

\hat{H} = -i \operatorname{sgn}(k)

I poked around the forums, GitHub examples, and the benchmark pages on DifferentialEquations.jl, but I wasn’t able to see an example of where someone used a linear operator other than a derivative. I’m a little confused about how ApproxFun.jl is storing the Fourier coefficients, and if I can get a grasp on that I shouldn’t have trouble implementing my own operator for the Hilbert transform.

Thanks!

EDIT:
Just to be a little more clear, I want the operator to be diagonal and represent the Fourier multiplier,

\mathcal{K} = i(k)^2 \operatorname{sgn}(k)

This way I bring the second derivative inside of the multiplier.

Fourier stores the cosine and sine coefficients alternating. Laurent stores the complex exponential coefficients alternating positive and negative coefficients, that is, 0, -1, 1, -2, 2, … coefficients.

The docs should explain in detail

2 Likes

Now looking at the docs this makes sense, I was unfamiliar with the notation that they use for the ordering. I’ve been working with the complex coefficients for so long it felt weird going back to the trigonometric coefficients Thanks for clearing up the notation in the docs for me.

Does anyone happen to know the benefit of working with ApproxFun.jl instead of the FFT implementation directly?

There’s not much benefit with fixed discretisation sizes, it’s more useful when you take advantage of the adaptivity. Or with non-periodic problems where operators are not diagonal.

I’d recommend using the trigonometric version: it ensures the solution remains real which may also be significantly faster. There is of course a simple expression for the Hilbert transform that swaps the sine and cosine coefficients.

1 Like

I have a follow-up question, I’m playing around with the trigonometric version, but I am also interested in the Taylor version. Glancing at the source code in the ApproxFun.jl package I was having trouble figuring out if it was using the plan_rfft, when playing around in Jupyter, it looked like the Taylor version was just using plan_fft. Is Taylor assuming that \hat{f}(k) = \hat{f}^*(-k), or is there something else going on?

A Taylor expansion is the same as Fourier with no negative terms. In this case, the “negative” coefficients of the FFT accurately approximate the large positive coefficients.

Yes, prior to using DifferentialEquations.jl I was using an implementation of the symplectic Yoshida sixth-order integrator to solve PDEs. The adjoint PDE for Benjamin-Ono is non-atuonomous, so I’m trying to use some different solvers inside of the DifferentialEquations.jl package now. I’m not sure why, but I can’t seem to get the package to work with the FFT plans directly, so now I’m using ApproxFun.jl since this is what I’ve seen done in examples.

When I use the FFT I typically use the real FFT plan which uses conjugate symmetry to work with only the positive non-negative coefficients; like what the Taylor implementation is doing. It seems that it is not using the rfft_plan:

S = Taylor()
n = 512
T = ApproxFun.plan_transform(S, n)

typeof(T)

ApproxFunBase.TransformPlan{Float64,Hardy{true,Circle{Float64,Float64,Complex{Float64}},Complex{Float64}},false,ApproxFunBase.TransformPlan{Complex{Float64},Hardy{true,Circle{Float64,Float64,Complex{Float64}},Complex{Float64}},false,ApproxFunBase.TransformPlan{Complex{Float64},Hardy{true,Circle{Float64,Float64,Complex{Float64}},Complex{Float64}},true,FFTW.cFFTWPlan{Complex{Float64},-1,true,1}}}}

When I create a plan with the plan_rfft:

M = 512
u = Array{Float64}(undef, M)
T = plan_rfft(u)

typeof(T)

FFTW.rFFTWPlan{Float64,-1,false,1}

Is there a reason why Taylor is using cFFTWPlan instead of rFFTWPlan?

I don’t know why you’d want rfft… are you assuming extra symmetry?

In any case, rfft is not that much faster than fft. In fact it depends on the number of points, sometimes FFT is faster.

I don’t understand what additional symmetry is assumed?

The only assumption that rfft and Taylor is making is that the solution is real, which implies \hat{f}(k) = \hat{f}^*(-k). The r2r plan makes the additional assumption that the solution is also even, which implies \hat{f}(k) = \hat{f}(-k). However, if Taylor is also making conjugate symmetry assumption, then it doesn’t make sense that it’s not taking advantage of the rfftPlan. The reason this is preferable is because it requires half the space as the cfftPlan to store \hat{f}.

You can’t have real valued Taylor series… this is on the unit circle

Okay, this is what I was confused about. It is very possible to work with the series of just the positive Fourier coefficients, but you use the fact that \hat{f}(k) = \hat{f}^*(-k) for real solutions.

I work with real-periodic solutions. In these situations it is easier to only work with the non-negative Fourier coefficients. For me it is restrictive to only work with the trigonometric coefficients, and not have the luxury of taking advantage of symmetry properties of the complex coefficients. I’m struggling to understand the limitations of this package, and I appreciate your help.

That’s not a Taylor series. A Taylor series is an expansion f_0 + f_1 z + f_2 z^2 + .... There’s no support at the moment for Laurent series that takes advantage of symmetry in the coefficients.


text:
# Continuous real-valued functions defined on non-compact spaces

A continuous real-valued function defined on a compact space is bounded and attains its bounds. Is it so that on a non-compact space it is always possible to define a continuous function that does not have these properties? (In fact, this is the case if the non-compact set lies in a finite-dimensional normed vector space, because in this case the set is either not closed or not bounded.)

• $X$ is pseudocompact if image of any continuous function $f \colon X \to \mathbb R$ is bounded. But nothing is said about attainability of its bounds. So author of question speaks about some subclass of pseudocompact spaces, right? Is there a name for such subclass? – Appliqué Apr 25 '13 at 20:38
• Ah, yes, if $f^\ast$ for example is upper not-atteinable bound of $f$, then $x \mapsto 1/(f^\ast-f(x))$ will be unbounded – Appliqué Apr 25 '13 at 21:01
No, it is not: there are $T_3$ spaces on which every real-valued continuous function is constant. E. K. van Douwen, A regular space on which every continuous real-valued function is constant, Nieuw Arch. Wisk. 20 (1972), 143-145, is a particularly nice example.


text:
# Greedy Problems

Greedy algorithms are algorithms that follows the problem-solving heuristic of making the locally optimal choice at each stage. You can not go back on your decisions once you've taken it.

Let's solve some greedy problems

Questions solved here

## Jump Game

Find the problem on Leetcode $$\to$$

### Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

### Example

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

### Approach

• We'll approach the problem in a reversed order. So we'll start from the end of the array and see if it is possible to reach that place, if we find any place from where we can reach the last index in the next iteration we'll see, that we can reach that index?
• We'll try to see the updated position is possible or not?

### Code

class Solution {
public:
bool canJump(vector<int>& nums) {
int to_reach = nums.size() - 1;
int index = nums.size() - 1;

while (index >=0) {
if (nums[index] + index >= to_reach) {
to_reach = index;
}

index--;
}

}
};

## Jump Game II

Find the problem on leetcode $$\to$$

### Problem Statement

Given similar to the last problem, an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Our goal is to reach the last index in the minimum number of jumps.

We can assume that you can always reach the last index.

### Example

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

### Approach

• We'll do a simple BFS like approach here. We are at first at the first index of the array. We'll see upto where we can reach and save it as level 1.
• Similarly we'll see from level 1 upto where maximum we can jump to, we'll mark it as level 2.
• From each level we'll jump to the next level until we reach the last index or cross that.
• To hold the values of the levels we'll use a pair<int, int> whose first element is the lower bound of the current level and second is the upper bound of the current level.

### C++ Code

class Solution {
public:
int jump(vector<int>& nums) {
// base cases
if (nums.size() == 1) return 0;

int jumpCounter = 0;

pair<int, int> level = {1, nums[0]};

int index = 1;

while (level.second < nums.size() - 1) {
// find if you can get out of this level, then find the max
// distance you can get out of this level?

// this level has bounds from level.first to level.second
int maxJumpToTheOutSide = 0;

for (int i=0; i<=level.second; i++) {
maxJumpToTheOutSide = std::max(maxJumpToTheOutSide, (nums[i] + i));
}

level.first = level.second + 1;
level.second = maxJumpToTheOutSide;
index = level.first;

jumpCounter++;
}

return jumpCounter + 1;
}
};


text:
# Implicit form for a logarithmic spiral

I was wondering if there is an implicit form for a logarithmic spiral. For example, if

$$x=e^{-t}\cos(t)\\y=e^{-t}\sin(t)$$

we can write $$x^2+y^2=e^{-2t}$$ and $$y/x=\tan(t)$$ which yields $$x^2+y^2=e^{-2\arctan(y/x)}$$ for $$x\neq0$$, but of course I would like to find one defined for any $$(x,y)\in\mathbb{R}^2$$. Any help?

Rearranging the given equation gives the new equation $$y=x\tan{\bigg(\ln{\bigg(\frac{1}{\sqrt{x^2+y^2}}\bigg)}\bigg)}$$ which is defined for any $$(x,y)\in\mathbb{R}^2$$.

• No. Moreover, $\ln(1/(\sqrt{x^2+y^2))}=(-1/2)\ln(x^2 + y^2)$. – MarianD Mar 6 at 22:50
• @JeanMarie, I'm right with my "No." The given parametric curve is not symmetric with respect to point [0, 0], while this curve is. So the OP's curve is a proper subset of this one. – MarianD Mar 6 at 23:31
• @JeanMarie, the error is in one-direction derivation, so from OP's equations folows this equation, but the opposite is not true. Similarly as $x = 2 \implies x^2 = 2^2$, but the second equation has 2 roots. – MarianD Mar 6 at 23:41
• @MarianD You are right. The error is in using function $\tan$ for quadrants II and III (generating the symmetrical part) whereas the derivation that has been done is only valid for quadrants I and IV. – Jean Marie Mar 6 at 23:42
• @JeanMarie, yes, you pinpoint it. – MarianD Mar 6 at 23:49

The implicit equation you give

$$x^2+y^2=e^{-2\arctan(y/x)}\tag{1}$$

is indeed not defined for $$x\neq0$$ but has the worst drawback that it generates a double spiral (the same issue met by the "solution" given by Peter Foreman) as shown here :

Fig. 1 : Formulation (1) provides a double spiral instead of a single one.

Nevertheless, there is a solution, suggested by @Blue (who so often has given very interesting remarks) : if we accept to consider "arctan2" as a function "like others", it suffices to transform (1) into

$$x^2+y^2=\exp(-2 \ \text{arctan2}(y,x))\tag{2}$$

(please note the arguments' order for atan2 : $$y$$, then $$x$$), or the equivalent form :

$$2 \ \text{arctan2}(y,x)+\log(x^2+y^2)=0\tag{3}$$

Another view of the issue : the spiral can be viewed as the projection of the intersection line of two surfaces as shown on Fig. 2 :

Fig. 2 : The logarithmic spiral as the vertical projection of the intersection line of surfaces with equations $$z=$$ln$$(x^2+y^2)$$ (a pseudo-cone) and $$z=-2 \arctan \! 2(y,x)$$

Remark : "arctan2", where the "2" means "with 2 arguments", finds its origin in numerical analysis (see for example https://en.wikipedia.org/wiki/Atan2 which traces it back to Fortran IV, i.e., around 1960). It is nowadays present in all scientific software, for example atan2 in Matlab, ArcTan[Y,X] with Mathematica... See its particular behavior along the negative $$x$$-axis "cut" in https://uk.mathworks.com/help/matlab/ref/atan2.html.