B³₂

Done organic chemistry forever!

Posted on 2013-12-19 by Brian

I used to love organic chemistry. Especially synthesis problems, which I felt gave me a chance to exercise my creativity and problem-solving skills. When I was competing for a spot on the Canadian IChO team, organic chemistry was probably my strong suit (although it’s also Richard’s strong suit, and in fact he apparently beat me on every section). When I decided to study chemistry at U. of T., I decided to take mostly physical and organic chemistry courses. I avoided biochemistry, because there’s too much memorization, and analytical chemistry, because I thought it would be boring. And I couldn’t fit inorganic into my schedule initially, and I ended up just not taking any inorganic courses at all.

I’m sorry to say that I don’t love organic chemistry anymore. In fact, I’m sick of it. I’ve taken CHM249 (organic chemistry II), CHM342 (organic synthesis), and CHM440 (more organic synthesis, with a focus on pharmaceutical agents). Every time I took another organic chemistry course, there were more and more reactions to memorize. The memorization was not too bad in CHM249, but there also weren’t any challenging problems of the sort I used to love solving in high school. In CHM342 the amount of memorization increased significantly, and I had an especially hard time with drawing three-dimensional transition states and predicting stereochemistry. In CHM440 there were a total of 90 named reactions. I was actually scared of synthesis problems, because, with that many reactions, there is simply no way I would be able to see the right disconnections. Luckily, there weren’t any. Suffice it to say that this course confirmed my suspicion that it was the right choice not to go to grad school to study organic synthesis…

Anyway, I had my CHM440 final exam last week, and my CHM347 exam today (biochemistry; I didn’t want to take it but if I took only courses I liked then I wouldn’t be able to graduate). Next term I’m only taking statistical mechanics. This means I’ll never have to look at another curved arrow for the rest of my life. Yippee!

In retrospect, I greatly underestimated the difficulty of fourth year—or perhaps I just bit off more than I could chew. Three of the five courses I took (CHM440, high-energy physics, general relativity I) were cross-listed as grad courses, so I guess it was foolish of me to expect them not to be so hard. There was also a grad student in my (time-dependent) quantum chem course, and at any rate it was very grad-style, with a take-home final (which was way too hard) and a term paper. I was incredibly busy toward the end of the term, trying to keep up my GPA (not that it actually matters, but I guess it’s just an irrational drive of mine).

I’ve noticed something about myself: when I’m busy doing stuff I don’t want to do, I think of all the productive things I could be doing if I had free time, such as developing the PEG Judge, studying quantum field theory, learning Haskell, or maybe learning a new (human) language. Alas, once free time arrives, I basically waste time browsing Reddit and playing games. Anyone else do this?

Now for some more awesome news. We made ACM World Finals! I’ll be representing the University of Toronto in Russia in June, together with my teammates Hao Wei and Saman Samikermani. We weren’t sure whether we were going to make it, since CMU and UMich creamed us at the regionals, and solved more problems than we did. But I guess ACM just stuck to the recent trend of inviting the top three teams from our region. We’ve got a long road ahead of us; other teams are good—really, really good—and we’re all a bit out of practice. I just hope we don’t do too badly!

Posted in Uncategorized | 1 Comment

WKB approximation

Posted on 2013-11-13 by Brian

I have a confession to make: I’m scared of approximations.

Scandalous, isn’t it? For there are few things in physics that can be solved exactly, and so if we want to ever be able to do any calculations, rather than just sitting around and writing down one PDE after another that nobody will ever solve, we simply can’t do without approximations. What kind of physics major doesn’t like approximations?

And yet, they’ve never come easily to me. In contrast to theorems and exact solutions, which make a lot of sense to me, approximations always confuse me and feel like they’re something I just have to memorize, and I’m not very good at memorizing things. This started in high school, when we were discussing double-slit diffraction patterns. In order to get an expression for the approximate spacing between the bands, you’ve got to argue that because the screen is far away, you have nearly a right triangle, and $\sin \theta \approx \tan \theta \approx \theta$ , as shown here. In the end, I just memorized the formula and felt dirty about it.

In my second year of college, I took an intro quantum mechanics course. It began with a discussion of the wave-like nature of matter, the photoelectric effect, Compton scattering, bremsstrahlung, hydrogen atom energy levels, all that good stuff. Then we did the Schrödinger equation for a particle in a box, a free particle, and plenty of super annoying problems where you have a potential jump and you have to match coefficients at the discontinuity and compute transmission and reflection coefficients. At the very end of term, we were introduced to the WKB approximation for the first time. Now, the prof for this course is notoriously bad (fortunately, he no longer teaches it), so I could barely understand what was going on; in the end he just derived an approximate formula for the tunneling amplitude through a potential barrier, and said WKB wouldn’t be on the final exam. I was relieved, and hoped I’d never come across it again.

Fast forward to present. I’m taking a course called Applications of Quantum Mechanics, and it’s a thinly veiled physics course about time-dependent QM which happens to be classified as CHM (luckily for me, because I didn’t want to take any more organic courses). Naturally, the WKB approximation shows up. There’s a lengthy discussion in the text about assuming an exponential form, expanding in a power series, and then plugging it into the Schrödinger equation. It was terribly dry, so I ended up just looking at the formula. That’s when it finally made sense to me.

The WKB approximation gives the following expression for the wave function of a scattering momentum eigenstate (i.e., $E > V$ ) subject to a spatially varying potential $V(x)$ :

$\displaystyle \psi(x) \approx \frac{A}{\sqrt{p}} e^{i \int p/\hbar \, dx} + \frac{B}{\sqrt{p}} e^{-i \int p /\hbar \, dx}$

where $A$ and $B$ are constants, and the momentum function $p$ is defined as you would expect: $p(x) = \sqrt{2m(E-V(x))}$ .

In order to see why this formula makes sense, compare it to the case where $V = 0$ and we have a free particle. Here we have an exact solution for the momentum eigenstates:

$\displaystyle \psi(x) = C e^{ipx/\hbar} + D e^{-ipx/\hbar}$

From the free-particle solution we can see that as the wave travels, it picks up a phase shift proportional to its momentum. If it travels a distance $dx$ , then it incurs a phase shift of $p/\hbar \, dx$ .

The WKB approximation is nothing more than the extension of this to a spatially varying potential. Here $p$ is a function of $x$ , so the total phase shift up to a particular point isn’t just $px/\hbar$ , but has to be replaced by an integral, $\int p/\hbar \, dx$ .

There’s a twist, however; in order to conserve probability, the amplitude has to vary spatially. Because we have a stationary state, the probability current has to be constant. Now, the probability current transported by the wave $A' e^{ipx/\hbar}$ is proportional to $A'^2 p$ . For this to remain constant, we must have $A' = A/\sqrt{p}$ .

And really, that’s all there is to it: WKB is what you get when you assume that a free particle propagating through a potential maintains basically the same form; it just doesn’t accumulate a phase shift at a constant rate now since the potential isn’t constant, and its amplitude varies in order to conserve probability (just like how a classical wave’s amplitude decreases when it passes to a denser medium). There wasn’t anything to be scared of!

(In regions where $E < V$ , we instead have exponential decay of the wave function. The formula given above is still correct, but a factor of $i$ from the square root cancels the factor of $i$ already in the exponential, and you get a real argument. The factor of $(-1)^{1/4}$ in the denominator can be absorbed into the constant.)

Posted in Uncategorized | 1 Comment

ACM regionals, problems and solutions

Posted on 2013-11-11 by Brian

To avoid possible copyright-related issues, all problem statements have been paraphrased or summarized.

Problem A

You are given a 10 by 10 grid and told the sum in each row and in each column. The sum tells you how many cells in that row or column are occupied by a ship. Each ship is aligned to the grid, meaning that for any given cell it either occupies it completely or does not occupy it at all, and all cells occupied by a particular ship are contiguous within a single row or column (as in the game Battleship). Ships are completely contained within the grid. There are four one-cell ships, three two-cell ships, two three-cell ships, and one four-cell ship. Two different ships cannot overlap, nor can two vertically, horizontally, or diagonally adjacent cells be occupied by two different ships.

How many possible configurations of the ten ships yield the given row and column sums?
If this number is greater than one, can we force the solution to be unique by further specifying the contents of some cell? We can specify it to be empty, occupied by the interior of a ship, occupied by the leftmost cell of a horizontal ship, occupied by the topmost cell of a vertical ship, occupied by the rightmost cell of a horizontal ship, occupied by the bottommost cell of a vertical ship, or occupied by a one-cell ship. If this is possible, find the “best” cell that allows us to do this, ranking first by lowest row number, then breaking ties by lowest column number, and then by type of contents, in the order listed in the previous sentence. If it is not possible, can we specify the contents of two cells and hence force the solution to be unique? Among multiple pairs of cells, find the best pair, that is, the one whose best cell is the best according to the rules for ranking single cells; ties are broken by the second best cells.

Solution

No team solved this problem during the contest. However, we may be reasonably certain that it can only be solved by a recursive backtracking approach, in which we will recursively generate all possible combinations of locations for the ten ships by adding one ship at a time, and pruning wherever adding a ship in a particular location would exceed the specified number of occupied cells in some row or column, and remembering that ships can’t overlap or be adjacent; whenever we manage to place all ships, increment the count of possible solutions. When trying to specify one or two cells in order to force a unique solution, we simply try all possibilities, starting from the best (i.e., empty cell in first row and first column, the empty cell in first row and second column, and so on) and again recursively generating all solutions, until we find something that give us exactly one solution. Because we didn’t attempt this problem, I can’t say what kind of optimizations are necessary to get AC.

Problem B

This problem asks to simulate cuckoo hashing. There are two arrays, of sizes $n_1 \leq 1000$ and $n_2 \leq 1000$ ( $n_1 \neq n_2$ ). A non-negative integer value $x$ would be stored at position $x \mod n_1$ in the first, and $x \mod n_2$ in the second. These two arrays together constitute a hash table. To insert a value into the hash table $x$ , insert it into the first array. If there is already some value $y$ in the position $x \mod n_1$ , then we have to move $y$ to the second array, storing it in position $y \mod n_2$ . And if there is already a value $z$ in that position, then we move it to the first array, in position $z \mod n_1$ , and so on—we keep shuffling values back and forth between the two hash tables until a value lands in an empty spot.

You are given a sequence of non-negative integers. Output the states of the two arrays after inserting all the values in order. It is guaranteed that each insertion will terminate.

Solution

Straightforward simulation.

To see that this is fast enough, first observe that it’s impossible to insert more than $n_1 + n_2$ values, so there will be at most 1999 integers given to insert. Furthermore, since it’s guaranteed that each insertion will terminate, it’s not too hard to see that there’s a linear limit on how many steps each insertion can take. To prove this, consider an undirected graph in which each vertex corresponds to a location in one of the two arrays and each edge corresponds to either an existing value or the value we’re inserting; the edge is incident upon the two vertices corresponding to the positions where the value can be stored (thus, the graph is bipartite). When we insert a value, we trace out a path along the edges, which terminates once it lands on an empty vertex. If an insertion is to terminate, then there can’t be more edges than vertices in the connected component of the edge corresponding to the value we’re inserting, because then there would be too few spots for all the values. So there are two cases:

Case 1: the number of edges is one less than the number of vertices (there are two empty spots). So the connected component is a tree. Because a tree has no cycles, we can never visit an edge twice (i.e., move a value that we’ve already moved). This gives the desired linear time bound.
Case 2: the number of edges equals the number of vertices (there is one empty spot). There is then exactly one cycle. In this case, observe that if we ever visit a vertex twice, this must be the first vertex on the cycle we visited. When we visit it the second time, we kick it back to its original position which must be outside the cycle since it was the first. After this, we are directed away from the cycle and so cannot enter it again. Thus in this case the number of iterations can’t be more than twice the number of edges.

I’m not sure whether I could’ve come up with this (extremely hand-wavy) proof during the contest, but I think you’re just supposed to intuitively realize the number of iterations is linearly bounded. The total number of iterations here can’t exceed $2 \times 1999^2$ , or about 8 million, so we would expect this to get in under the time limit.

Problem C

This problem deals with a modified version of the Playfair cipher. To encrypt a message, you first need to pick a secret key. Then you write the letters of the key, one at a time, in a 5 by 5 grid, with each letter occupying one cell. Squares are filled left to right, top to bottom. Duplicate letters in the key are skipped after the first time they’re written down. After this, unused squares in the grid are filled left to right, top to bottom, by the letters of the alphabet not present in the key, in order. I and J are considered the same letter, so there are only 25 letters in the alphabet, and thus the grid will end up containing a permutation of the alphabet.

A message is encrypted as digraphs, that is, two-letter pairs. For example, to encrypt ECNA, you would break it down as EC NA and then encrypt EC and NA separately, and concatenate the results. A special case occurs when the two letters in a pair are identical; in this case, in the original Playfair cipher, you insert the letter X after the first, and then the second actually becomes the first letter of the next pair; for example, HELLO would become HE LX LO and then these three pairs would be encrypted. If you end up with a single letter at the end, add an X to the end. (Evidently, a message such as FOX cannot be encrypted with this method.) In the modified version used in this problem, instead of always inserting the letter X, the first time you insert a letter you use A, the second time, you use B, and so on, skipping J, and wrapping around after Z. You also skip a letter if inserting it would give a pair of identical letters; for example, AARDVARK becomes AB AR DV AR KC, where we have skipped A.

After breaking down the message into letter pairs, we use the grid to encrypt each pair. If the two letters appear in the same row, then we replace each letter by the one immediately to the right of it in the grid, wrapping around if necessary. If they are in the same column, we replace each one by the one immediately below it, again wrapping around if necessary. If they are in neither the same row nor the same column, replace the first letter by the letter that lies in the same row as the first letter and same column as the second, and replace the second letter by the letter that lies in the same row as the second letter and same column as the first. Concatenate all the encrypted pairs to give the ciphertext. You are given a series of key-plaintext pairs. In each case output the corresponding ciphertext.

Solution

Simulation. I would say straightforward simulation, but I guess this problem isn’t exactly the most straightforward. Luckily, I wasn’t the one stuck coding this one :P

Problem D

On a web page of dimensions up to 10⁹ by 10⁹ pixels, up to 10000 disjoint axis-aligned squares are given, each of which has side length 10 pixels. Each square’s upper-left pixel has coordinates that are multiples of 10. Find the smallest set of pixels which both contains all the squares and is orthogonally convex, meaning that if two pixels in the same row belong to the set, then so do all the pixels between them in that row; likewise, if two pixels in the same column belong to the set, then so do all the pixels between them in that column. Output the vertices of this set in clockwise order starting from the topmost one (leftmost in case of a tie).

Solution

First, notice that we can replace each 10 by 10 square by its four vertices. For example, the square from (50, 60) to (59, 69) can be replaced by (50, 60), (50, 69), (59, 60), and (59, 69). The orthogonal convex hull of the $4n$ points thus obtained will be the same as that of the original set of squares, so we’ll just work with these $4n$ points instead.

To proceed, we basically walk around the hull in clockwise order. We start by identifying the topmost pixel (leftmost in case of a tie). This must be a vertex. To find the next vertex, we locate the topmost point which lies strictly to the right of it (in case of a tie, pick the rightmost). Then we find the topmost point which lies strictly to the right of that, and so on. Eventually we reach a point in the rightmost occupied column. Now we switch gears, and find the rightmost point that lies strictly below our current point (bottommost in case of a tie). Keep doing this until we get to the bottommost occupied column. Then switch gears again, repeatedly moving to the bottommost point that lies strictly to the left of the current point (leftmost in case of a tie). Finally, once we reach the leftmost occupied column, repeatedly move to the leftmost point that lies strictly above the current point. Eventually we reach the starting point, and we are done. Whenever we move from a point to another point that is in both a different row and different column, we have to insert an additional vertex. For example, in the first phase, when we are moving from a point to the topmost point strictly to the right, if the new point is strictly below the current point, then we insert a point which is in the same row as the new point but same column as the current point; the other three cases are analogous.

To efficiently move from one point to the next, all we have to do is precompute, for each of the (up to) 40000 points we have to work with, the topmost point to the right, the rightmost point below, the bottommost point to the left, and the leftmost point above. We can precompute the topmost point to the right of all points by sorting the points by x-coordinate and scanning from right to left, remembering the topmost point we’ve seen so far; the other three cases are analogous.

Problem E

In an $n \times n$ grid ( $n \leq 25$ ), some squares are occupied by obstacles. The leftmost and rightmost columns do not contain obstacles. There is initially a game piece in each cell of the leftmost column. You need to move them all to the rightmost column, using the minimum number of turns possible. In each turn, you can choose, for each piece, whether to move it or to leave it where it is; if you move a piece then you must move it into a vertically or horizontally adjacent cell that does not contain an obstacle. At the end of a turn, no two pieces can occupy the same square. What is the minimum number of turns necessary?

Solution

We didn’t solve this problem, but it seemed to us that we could do it with max flow. However, it’s somewhat unclear whether this approach would even fit in memory, let alone be fast enough.

First, we consider the problem of determining whether it is possible to solve the problem in $k$ turns. We can reduce this to max flow with vertex constraints. There is one vertex for each (cell, turn) combination. For example, if $k = 3$ , then there are four vertices for each cell: the cell at the beginning of the game, the cell after the first move, the cell after the second move, and the cell after the third move. Each vertex has a capacity of one. Each vertex has up to five outgoing edges (which we can take to have capacity one), each of which goes to some vertex corresponding to the next turn, and either the same cell, or a horizontally or vertically adjacent cell, as long as it does not contain an obstacle. There is an edge (which we can again take to have capacity one) from each vertex corresponding to the final state and a cell in the rightmost column to the sink. There is also an edge (which we can again take to have capacity one) from the source to each vertex corresponding to the initial state that is in the leftmost column. It is not hard to see that an augmenting path in this flow network corresponds to the movement of a game piece from the leftmost column in the initial state to the rightmost column in the final state; each edge that is not from the source or to the sink corresponds to the movement of the game piece from a particular cell in a particular turn to an adjacent cell in the next turn (or leaving it in the same cell); the vertex capacity constraint enforces not being able to have two pieces in the same cell in a given turn. If the max flow is $n$ , then we have moved $n$ pieces, that is, won the game.

Before we proceed, what is the complexity of this approach? Well, there are up to 625 cells, so there are about $625k$ internal vertices, each with up to about 5 outgoing edges, so $3125k$ edges. Furthermore, to enforce the vertex capacity constraints, we’ll have to split each vertex up into an incoming and outgoing vertex, with an edge between them, so now we’re up to $3750k$ edges. Because the graph has unit capacities and the max flow is at most 25, we can use DFS to find each augmenting path, and we have to go through 25 augmenting paths before we find the max flow. The complexity of DFS is $E+V = 5000k$ so the total number of operations is about $125000k$ .

Now, how do we find the minimum $k$ ? Well, we didn’t get that far, but it seems that a reasonable approach would be as follows: first just set $k = 0$ and create the corresponding flow network. Then, as long as the max flow of $n$ hasn’t been achieved yet because you can’t find a path in the residual network, add the next set of vertices and edges, corresponding to increasing $k$ by allowing an extra move (that is, add $n^2$ more vertices and join the current final state vertices to them, making the vertices just added the new final state vertices; also add edges from the rightmost column cells in the new vertex set to the sink) and check whether we can now find an augmenting path; if not, increase $k$ again, and so on. To efficiently determine whether an augmenting path exists in the new graph, all we have to do is run another DFS starting from reachable vertices in the previous final state cells, rather than doing a huge DFS from the source that will go through the entire graph again. This essentially means that every time we have to increase $k$ once or more, the total time taken for all the DFSing is about the same as that taken to do a single DFS in the graph corresponding to the final $k$ value before we find another augmenting path. That means the total number of operations is bounded by about $125000m$ , where $m$ is the answer (minimum number of turns). I’m not quite sure how large $m$ could be; it could certainly be as large as about $n^2/2$ , in the case that the obstacles force you to take a winding path through the grid. Putting $n = 25$ , we obtain a figure of about 39 million. Is this fast enough? I’m not sure.

Jacob argues that binary search on $k$ would be faster. At some point I’ll probably code up both and see who’s right.

Problem F

In a directed acyclic graph of up to 200 vertices, we say an edge is redundant if removing the edge does not alter the connectivity of the graph (i.e., if a path existed from one vertex to another in the original graph, a path must also exist when the redundant edge is removed). Find all redundant edges.

Solution

A naive approach is to simply try deleting each edge in turn, and then running a DFS from each vertex to determine whether the connectivity has changed. Unfortunately, this approach takes $O(EV(E+V))$ time, which is $O(V^5)$ in dense graphs, and is too slow for $V = 200$ .

A faster approach is to run Warshall’s algorithm for computing the transitive closure of the graph. Whenever we find that there is a path from $i$ to $k$ and a path from $k$ to $j$ , if there is an edge directly from $i$ to $j$ , that edge must be redundant. This is only true because the graph is acyclic! Deleting that edge can’t alter the connectivity of $i$ to $k$ or $k$ to $j$ , because $i < k < j$ in topological order, and thus the path from $i$ to $k$ can't use the edge from $i$ to $j$ , nor can the path from $k$ to $j$ . The running time of this approach is $O(V^3)$ .

Problem G

There is a horizontal line segment (the house) located above the origin on the Cartesian plane, and up to 10 decorations, each of which is also a line segment, and each of which is either reflective or non-reflective. There is a lamp located at the origin, which emits rays at all angles from $-\theta/2$ to $\theta/2$ to the vertical. Non-reflective decorations absorb all incident light, and reflective decorations act as mirrors that obey the law of reflection (and are reflective on both sides). It is guaranteed that a ray can only be reflected up to 100 times. What fraction of the house is actually illuminated?

Solution

I don’t think any teams solved this problem during the contest, so I have no idea how actually to do it. My suspicion is that it can be done using a brute force simulation approach, in which we simply sample the interval of angles and cast out a ray at each sampled angle, following its course until it either gets absorbed, reaches the house, or escapes to infinity. The fraction of the house illuminated only needs to be accurate to within one part in 10⁴ (a percentage rounded to the nearest hundredth). I’m not sure how finely you’d have to sample in order to get the right answer, but of course, if nobody else solves the problem, then the rational strategy is to just keep resubmitting until you get it accepted. The simulation is pretty easy to do; in each iteration you just have to check whether the ray intersects any of the (up to) 11 line segments specified. If it’s the house or one of the non-reflective decorations, or if it doesn’t intersect anything, you’re done; if it’s a mirror, then you have to iterate again, but you only have to do up to 100 iterations for each angle, so that’s 1100 operations. Let’s say you decided to sample $5\times 10^4$ angles; then you’d have to do a total of about 55 million operations. I suppose it’s plausible that this approach would work, but I can’t say for sure until I see the test data or official solutions.

The other, non-hackish approach would be to compute the illuminated fraction exactly by considering only interesting angles. An interesting angle is an initial angle at which the ray grazes the endpoint of a some line segment. It is easy to see that between any two consecutive interesting angles, either the ray does not illuminate the house at all, or the image of the ray on the house varies monotonically and continuously, so that whatever portion of the house lies between the image of the ray at the first angle and the image of the ray at the second angle is completely illuminated. Taking the union of all such intervals would then give the total length illuminated. To do the actual angle sweep, we would first sort a list of all angles at which the ray would graze the endpoint of some interval. We would then consider each sub-interval between a pair of consecutive interesting angles. If, in this interval, the ray hits a mirror, then we have to recursively subdivide the interval by considering all the angles at which the ray could hit the mirror, reflect, and then graze the endpoint of another interval. If in one of those intervals the ray hits a second mirror, then we would have to recursively subdivide again, and so on.

Two questions remain. First of all, how do we compute the initial angle required to hit some target point after reflection from a sequence of mirrors $m_1, m_2, ..., m_k$ ? The answer is pretty clever: we reflect the target point $p$ across mirror $m_k$ to get point $p_k$ , and reflect $p_k$ across mirror $m_{k-1}$ to get point $p_{k-1}$ , and so on, finally reflecting across $m_1$ to get point $p_1$ . The ray from the origin to $p_1$ is then the same ray which would (potentially) reflect from all the mirrors in sequence and finally hit $p$ . (I imagine anyone who plays pool is familiar with this trick.) The second question is what the worst case running time of this approach is. I have no idea. I don’t have any idea whether this was the intended approach, or the brute force one. When the test data come out, maybe we’ll see. If I’m not too lazy, that is.

Problem H

In a $3\times n$ grid of squares ( $n \leq 1000$ ), each square contains an integer. We can place a domino across two squares and gain a number of points equal to the product of the numbers of the two squares. What is the maximum possible score, if we can place as many dominoes as we want but no two dominoes can overlap?

Solution

This problem can be solved using dynamic programming. We will define $f(k, o_1, o_2, o_3)$ as the maximum score obtainable given that all squares covered by dominoes are left of column $k$ , and $o_1$ specifies whether the top square in column $k-1$ is covered, likewise for $o_2$ and $o_3$ with the middle and bottom squares. The total number of states is then $2^3 n$ .

Computing the transitions is annoying. If we number the columns starting from zero, our base case is $k \leq 0$ ; here, no dominoes can be placed and the maximum score is 0. To compute $f(k, o_1, o_2, o_3)$ for $k > 0$ , we consider all possible arrangements of dominoes in column $k-1$ :

$o_1 = o_2 = o_3 = 0$ : column $k-1$ is empty. Then $f(k, 0, 0, 0) = \max_{o_1, o_2, o_3} f(k-1, o_1, o_2, o_3)$ : we have license to cover as many or as few squares in column $k-2$ as we wish, and then we’ll simply not put anything in column $k-1$ , and hence not gain any additional points.
$o_1 = 1; o_2 = o_3 = 0$ : Only the top square in column $k-1$ is filled. In this case the domino covering that square must also occupy the top square in column $k-2$ . The score we get is the value of this domino plus $\max_{o_2, o_3} f(k-1, 0, o_2, o_3)$ , where the 0 indicates that the top square must be initially uncovered in column $k-2$ , but we don’t care whether the other two squares are.
$o_1 = 0; o_2 = 1; o_3 = 0$ or $o_1 = 0; o_2 = 0; o_3 = 1$ : These are analogous to the previous case.
$o_1 = o_2 = 1; o_3 = 0$ : There are two ways we can cover the top and middle squares in column $k-1$ while leaving the bottom one empty. Either we can place a domino across these two squares, giving a maximum total score equal to the value of that domino plus $f(k, 0, 0, 0)$ (because once we remove this domino from the board we’ll have an empty column $k-1$ ). Or, we can place a domino on each that also covers the square to the left. The maximum score we could then obtain is the sum of the values of these two dominoes and $\max(f(k-1, 0, 0, 0), f(k-1, 0, 0, 1))$ (where we see that the bottom square in the previous column could be either covered or uncovered). The case $o_1 = 0; o_2 = o_3 = 1$ is analogous.
$o_1 = 1; o_2 = 0; o_3 = 1$ : This is only obtainable by placing a domino on the top square that also covers the square to its left, and a domino on the bottom square that also covers the square to its left. The maximum score you can get is then the sum of the values of these two dominoes plus $\max(f(k-1, 0, 0, 0), f(k-1, 0, 1, 0))$ , where we don’t care whether the middle square is covered in the previous column.
$o_1 = o_2 = o_3 = 1$ : There are three ways to obtain this. We could lay a domino across the top and middle squares, and have the domino covering the bottom square also cover the square to its left. The score here is the value of the first domino plus $f(k, 0, 0, 1)$ . We could also lay a domino across the bottom and middle squares, and have the domino covering the top square also cover the square to its left. The score here is the value of the first domino plus $f(k, 1, 0, 0)$ . Finally, we could have three different dominoes in this column, each also covering the square to the left. The score here is the sum of the values of the three dominoes plus $f(k-1, 0, 0, 0)$ .

The final answer is then $\max_{o_1, o_2, o_3} f(n, o_1, o_2, o_3)$ , since we ultimately don’t care which squares are covered in the last column.

Problem I

Consider the regular language (a|ab|bb)*. Place all strings in this language in order of increasing length, where words of the same length are ordered lexicographically. Suppose there are $n$ words per page in the dictionary ( $n \leq 30$ ). What are the first and last words on page number $m$ ( $m \leq 10^{18}$ )?

Solution

The first word on the $m$ ^th page has (one-based) rank $n(m-1) + 1$ . The last word on the $m$ ^th page has rank $nm$ . If we can figure out how to compute the $k$ ^th-ranked word in the dictionary, we just set $k = n(m-1)+1, nm$ to get the desired words. Note that $30 \times 10^{18}$ is too large to fit in a 64-bit integer, so I suggest using Java’s native bignums.

This problem, like most problems of the type find the kth lexicographically smallest element, is solved by using the ordering criteria to narrow down the characteristics of the sought element from coarsest to finest. That is, first we will determine the length of the sought word, then we will determine the first letter of the word, and so on, because words are ranked first by length, then by first letter, and so on.

To determine the length of the word, we first ask ourselves whether it could be of length 1. To do this, we compute the number of words of length 1. If this is less than or equal to $k$ , then we know that the $k$ ^th word has length 1. If not, then we compute the number of words of length 2. If the sum of the number of words of length 1 and 2 is less than or equal to $k$ , then we know that the $k$ ^th word has length 2. And so on. To do this efficiently, we would first subtract the number of words of length 1 from $k$ , then subtract the number of words of length 2, and so on, until we find $l$ such that the value of $k$ we have left over is less than or equal to the number of words of length $l$ . Then the desired word is the $k$ ^th word of length $l$ (where, remember, we have subtracted out the word counts for lengths $1, 2, ..., l-1$ already from $k$ ).

Next, we find the first character of the word, by computing the number of words of length $l$ that begin with the letter a. If $k$ is less than or equal to this, the word begins with a, otherwise, the word begins with b, and subtract the number of words beginning with a from $k$ . Then move on to the second letter; compute the number of words of length $l$ , which begin with the first letter we computed in the previous step, and compare this with $k$ , and so on. In this way we successively determine one letter after another, until we have constructed the entire word.

(I take this opportunity to reiterate that this approach is very general, and is almost always the approach used to solve find the kth lexicographically smallest element problems, or generally any kind of problem in which a set of items is ranked according to a succession of criteria and we have to find an item in a particular position of the sequence.)

Finding the number of words of a given length or the number of words of a given length and a given prefix—the computation you need to do over and over again in the preceding procedure—is actually easy once you realize that a word is in the language if and only if it starts with an even number of bs. Thus, if the prefix contains at least one a, you have free rein with the rest of the letters and there are $2^r$ words, where $r$ is the number of remaining letters. If there is no a in the prefix and an even number of bs, then there are $2^{r-1} + 2^{r-3} + ...$ words, where $2^{r-1}$ consist of a followed by whatever, $2^{r-3}$ correspond to bba followed by whatever, and so on. If there is no a in the prefix and an odd number of bs, then there are $2^{r-2} + 2^{r-4} + ...$ words, where $2^{r-2}$ correspond to ba followed by whatever, $2^{r-4}$ correspond to bbba followed by whatever, and so on.

In the contest, we solved problems B, C, D, F, H, and I, and ran out of time trying to code E. After solving B, C, D, F, H, and I (not in that order), we had about 50 minutes left (?), and figured that E would be quickest to code. However, E turned out to be difficult to debug, and the nature of the algorithm meant we couldn’t use prewritten max flow code from our printed materials. In the end, we couldn’t even get it to work on the sample data.

Posted in Uncategorized | 2 Comments

ACM regionals

Posted on 2013-11-11 by Brian

Yesterday, I attended the 2013 East Central North America regional ACM programming contest, representing the University of Toronto. (My teammates were Saman Samikermani and Hao Wei.) The scoreboard isn’t available online yet, nor are the problems, but I can say that we placed fourth overall, behind CMU, Michigan, and CMU again. (It’s a bit demoralizing that their B team is better than our A team, isn’t it?)

This was only the second time I’ve attended regionals. The first time was in my first year, when I was at Waterloo. In second year I was going through that phase when I didn’t want to do any contests at all, and last year I declined to be on U of T’s ACM team because I was too busy and had no time to practice. It’s a shame, because that was Jacob’s second time at World Finals, and I think he and I together would’ve been pretty good. Oh well.

Now for the burning question: will we advance? Nobody can say for sure at this point. In general, the first place team is guaranteed to advance from each region, but if there was a team in the region that won a medal at finals last year, then this year they guarantee at least two teams from the region will advance. That means CMU and Michigan are going to advance for sure, since CMU won a medal last year. In the past few years they have actually taken three teams from our region; Jacob says they do this when the third place team isn’t too far behind the second place team, but that’s hardly precise enough to predict anything, and at any rate these rules aren’t written down anywhere. He also says that our chance of advancing is more than 50% but less than 90%. I guess that sounds reasonable.

My friend is going to email me a copy of the problem set later tonight (she kept the paper; I didn’t) and I’ll try to post solution sketches to some of the problems. My team didn’t solve all the problems, though, and official solutions and test data aren’t yet available, so I can’t necessarily promise correct or complete solutions.

On the way back from regionals I taught some of the other U of T people how to play Durak. We also played a few hands of Hearts, in which I was reminded that I’m horribly inattentive and usually fail to stop people from shooting. Fun times.

Posted in Uncategorized | 1 Comment

Dating and non-equilibrium thermodynamics

Posted on 2013-10-26 by Brian

The analogy between interpersonal relationships and chemical processes is well-established. Just about everyone understands what it means when you say, “we just didn’t have chemistry”. In fact, according to the Online Etymology Dictionary, this usage goes as far back as the 18^th century. The analogy can be fleshed out by the light-hearted addition of such concepts as “single displacement reaction” and “activation barrier”. Now, anyone who hasn’t taken a chemistry course is going to give you a funny look because they won’t know what you’re talking about, but I suppose that’s the price you pay for unlocking the “Used Chemistry Terms in Casual Conversation” achievement. (Wait, what do you mean, you don’t keep track?!)

I think I’m a bit odd, though, in actually taking the analogy seriously. A lot of people seem to have a fair amount of faith when it comes to their love lives: they don’t know how or when they’re going to meet their lifelong partners, but they’re sure it’s going to happen. What I believe, though, is a bit different: the system will eventually reach equilibrium, if you allow it to. I don’t postulate that you’re guaranteed to meet that special person, but I do submit that if you meet them and keep in touch for long enough, then you’ll eventually end up together. Furthermore, if you’re with the wrong person, it won’t last long.

Indeed, I like to imagine a spring between every pair of people. This spring doesn’t exist in real space, but an abstract space in which the distance between two people measures intimacy (greater intimacy means shorter distance). I like to say that every spring has an equilibrium length, which corresponds to how compatible you are, and that eventually, all those springs are going to reach equilibrium. If you’re not very close to someone whom you could be closer to, you’ll feel the desire to get to know them better—that’s how strangers become acquaintances, acquaintances become friends, and friends become… well… more than friends. That’s the restoring force. (Did I just wade into physics territory? It’s worth noting that the model of chemical bonding with a harmonic potential between two atoms is commonly taught in physical chemistry courses.) If you’re too close to someone, it’s going to come to an end eventually—the restoring force pushes you apart. Equilibrium is not always reached right away—for example, you might be dating, then break up and not talk to each other for a few months, but then, after a long period of time, you may be friends again—and that’s where the equilibrium distance might lie.

I also like to imagine a diverse set of protein molecules floating around in a solution. Some pairs will have very high binding constants; once they bind, they’ll stay together, for the most part… perhaps by chance a high-energy molecule will come by and break them apart, but they’ll be together again, sooner or later. A binding that isn’t very strong won’t stay together for long—it may break apart of its own accord, or a single displacement might occur. It’s important to note, of course, that two molecules are not going to end up bound together if they never come into contact. (Just like in real life.)

In a sense, then, what I’m saying is: if it’s meant to be, it’ll happen. Sooner or later. This is the attitude I’ve consistently taken whenever I’ve been plagued by anxiety-inducing hypotheticals. If you mess up, but the other person likes and understands you well enough, it’s recoverable; you’re only separated temporarily while the equilibrium re-establishes itself. (This is true of not only intimate relationships but also friendships.) If you feel like you “missed your chance” to make your move—well, it’s never too late—the most stable configuration awaits you. And if the person you love actually ends up with someone else—that person probably had a higher binding constant with them than you did… but not to worry, someone better for you might still be out there.

The only thing to watch out for here is that you don’t ignore the non-equilibrium regime. (Apparently, non-equilibrium thermodynamics has not been extensively studied, which is why equilibrium thermodynamics is very well understood, and non-equilibrium, not so much. This makes it difficult to study, among other things, biological systems, which are only interesting as long as they stay away from equilibrium… that is, alive.) So if the right person comes along, you don’t have to worry about how things will work out—they will. But it’s still worthwhile to consider what happens before that. A lot of people out there are in non-equilibrium relationships—sure, they might not end up married to their current partners, but many of them are still having a good time. You may as well seize the opportunity to enjoy non-equilibrium interactions if possible—after all, there’s no guarantee that you’ll meet that special somebody within your lifetime.

The disconnect between equilibrium and non-equilibrium thermodynamics is a source of some of what you might consider bad advice going around. For example, “be yourself” is good advice in the equilibrium regime—indeed, it might help equilibrium be established more quickly—but not so much in the non-equilibrium regime: if you just “be yourself”, but that isn’t a person that most people can relate to, you may end up with no non-equilibrium interactions. Nope—if you want to form that short-lived unstable species, you’ve got to pour energy into the system. Unfortunately, in this I have no advice to give. If I figure anything out, I’ll let you know. ;-P

Posted in Uncategorized | 1 Comment

Back to school update

Posted on 2013-10-11 by Brian

It’s been a while since I posted an update! I suppose that’s because I keep getting more modest and hence more rarely believe that something I came up with will be interesting to a wide audience. (Though, I assure you, I post just as much mildly amusing crap on Facebook as I always have.)

So I moved into my new apartment last month. I love the location—it’s only a few minutes away from campus so I usually don’t have to get up until about half an hour before my first class each day, and I don’t have class before 11 all week. Of course, I still manage to not get enough sleep, by staying up until 2:30 AM every day. Go figure, right? The only unfortunate thing is that internet access wasn’t provided. I signed up on (I believe) Sep. 6, but couldn’t get a technician to come over and set it up until Sep. 27. I was out of town but I forgot to tell my roommates that there were two technicians scheduled to come over, so we missed the second one and he couldn’t come until a week later, that is, Oct. 4. We also discovered that our modem was broken, so we had to order a new one, which didn’t arrive until last night! (To make things worse, I discovered while trying to configure the modem that my laptop’s Ethernet port is broken. Basically, everything that could go wrong, went wrong.)

I’m taking five courses this term: Introduction to High Energy Physics, Relativity Theory I (i.e., intro to general relativity), Applications of Quantum Mechanics, Organic Chemistry of Biological Compounds, and The Synthesis of Modern Pharmaceutical Agents. I originally wasn’t going to take the synthesis course, because I didn’t want to have to memorize a lot of reactions; instead I signed up for a supposedly easy course on polymers. I dropped it like a hot potato, however, when I found out there was a term paper, and the synthesis course was the least intolerable course that remained. Ironically, I found out the very same day that the quantum mechanics course has a term paper, too, but at least I actually like quantum mechanics.

Contrary to expectation, I managed to get hired as a TA this term. I was hoping for an upper-year course on algorithms or data structures, because that’s my favourite area of CS, of course, but I ended up getting CSC108, an introductory course. Apparently they expanded enrollment by 50% since last year. If that weren’t the case, I probably would not have gotten any TA position at all, since grad students have priority. So really, I can’t complain. (It pays really well, too.)

Oh, and one last thing. I’ve accepted a full-time offer with Google in their Mountain View office, starting next September!

Posted in Uncategorized | 2 Comments

Ode to the Hard Sciences

Posted on 2013-09-07 by Brian

I was looking through some old documents of mine in an effort to track down the exact date when I first began using LaTeX, when I stumbled upon a poem I had written back in grade 12 for an Independent Study Unit (ISU). Here it is:

Despite great diff’rences in shape and size,
The observant student finds in awe,
Man, beast, and vegetable when analyzed,
Obey the selfsame set of natural laws.

The beauty of nature exemplified,
Finds its cause in ultimate reduction,
In flowers, peacocks, and the butterflies,
To imperative of reproduction.

In such a way the pleasant genes survive,
Passed down through ages by the DNA,
Which has its own behaviour derive,
From laws that hold all back from disarray.

‘Tis laws of chemistry of which I speak,
Which govern all things whether live or not,
Not just concoctions of a science geek,
But things far too small for the eyes to spot.

Indeed, the vibrant colours in the sky,
From lighting fireworks one does produce,
Can be explained through theories that rely,
Upon results from chemistry induced.

But these are inter-atom interactions,
Resulting from an elaborate dance.
Electrons after nuclear attraction,
Do not themselves align as though by chance.

That is, the chemistry itself has cause,
For it is born from ever-simpler ways,
Material reality thus draws,
Method from the mechanical gaze,

Of physics, which on Earth does reign supreme;
Its realm extends throughout the universe.
Its greatest secrets lying in extremes:
The galaxies and particles diverse.

The first, said Einstein, they can be described,
By treating space as a large rubber sheet,
Its curvature by his theories prescribed,
But in the end we found them incomplete.

For on the other end of this grand scale,
Is where we find the very very small,
Not even our most gifted minds avail,
To scry the outcome when they hit the wall!

But though we cannot right now unify,
The laws that rule the very small and great,
A common thread can be identified,
And all known sciences it does predate.

This thread, it runs through all we can conceive,
Yes, even that which only does exist,
In the logic which the mind perceives,
And yet in the real world it does persist.

‘Tis mathematics which all truths dictates,
The closest thing to God that we possess.
So vast the scope in which it operates,
I name it human thinking’s best success.

Each student in the class had to choose an English-language poet for the ISU, and one of the assignments was to compose an original poem in our chosen poet’s style. I was pretty nervous since I’ve never been a great creative writer, but I was pleasantly surprised to discover that Percy Shelley, my chosen poet, had experimented with chemistry and electricity. I used this as an excuse to write my poem about science.

ABAB rhyme schemes are common in Shelley’s poetry, as is iambic pentameter, so I attempted to use both in this poem, though, reading through it again, I notice I did a rather incomplete job of the latter.

The line “To scry the outcome when they hit the wall!” makes me cringe a bit, and, looking through the comments in the original document, I can see that it made me cringe back then too. Of course, in particle accelerators we do not fire the particles at walls, but I had to take some poetic license to make the damn thing rhyme…

Posted in Uncategorized | Leave a comment

Mid-point update

Posted on 2013-06-30 by Brian

I’ve just finished the seventh week of my fourteen-week internship at Google. Google has been keeping me busy; it’s really important that I perform well, as I only have one more year of school left, and then I’m going to become a full-time software engineer! It’s too early to say whether I’ll probably get a full-time offer from Google, but I’m hopeful of course. My future plans are finally starting to crystallize.

In seven weeks from now I’ll be back home in Toronto for three weeks of well-earned relaxation before starting my final year of college. Oh, did I say relaxation? Ha. Actually, if I can just muster up enough self-discipline, I’m actually going to scramble to teach myself how to cook before I move into my downtown apartment. (Yes, the horrible meal plan at Vic was a deal-breaker for me.) Believe it or not, this place is only about five minutes away from LM and MP (where I have most of my classes) and the price is quite nice too. I just have to make sure I manage to sublet it during next summer, otherwise my finances might be a bit tight.

I haven’t really felt challenged during my undergrad. But good news: I’m finally done all my breadth requirements, and I have some space left in my timetable. I’ve always wanted to learn general relativity and quantum field theory, but they’re just so daunting to learn on my own. So I’m thinking of taking PHY483, PHY484, and PHY489. I was concerned about not being smart enough to handle these topics, but a friend of mine took PHY483 and assured me that it’s not impossibly difficult, so I might as well give it a shot.

But wait! What about CS? Well, yes. So, over the last year, I’ve become painfully aware that, while I’m a decent software engineer, I lack knowledge in many key areas compared to people who actually took CS in college. Some of those areas include: programming languages; databases and distributed systems; concurrency; and operating systems. I don’t like not knowing things, so I do plan to learn at least some of these things. Unfortunately, I’m only allowed to take up to three 300+ level CSC courses since I’m not a CSC student, and I’ve already taken one (it was a research project course, and I ended up failing miserably at it). But then I realized: why bother trying to cram CSC courses into my timetable at all, when I can take as many as I want during the summer online (e.g., on Coursera)? So that’s going to be my plan: finish my degree and then try to make up for that degree not being a CS degree. I’m sure I still won’t be as knowledgeable as a real CS major, but damned if I don’t do my best.

And then, in fall of 2014, I’ll start life out in the Real World as a software engineer. I’ve been a student for my entire life so far, and then suddenly, my responsibilities are going to shift. My mom always told me that, as a student, my #1 priority in life is to study well; and that’s something I’ve been very comfortable with, since I’m a good student. But everything is going to change soon. I’m nervous. But also excited.

I’m going to close this post off with an update on my love life. (Since, obviously, that’s the most interesting part, right?) My girlfriend and I broke up a few weeks ago. We split on good terms, and we’re still best friends, so yes, you can still invite both of us to the same event without making things awkward. Of course, breakups are never easy, and the last few weeks have definitely been tough. Coding is a lot less fun than it normally is; focusing on physics is sometimes impossible. But things are gradually getting better.

Posted in Uncategorized | 3 Comments

On the “nice guy” straw man

Posted on 2013-06-02 by Brian

I came across an interesting image, linked from a Reddit comment, just now.

The image consists of nine panels. Each of the first eight depicts a Forever Alone rageface, and contains a snippet of text. In order:

Doesn’t maintain physical fitness, style, or personal hygiene, yet judges women on appearance.
Has cripping self-esteem issues that make him come off as needy and desperate.
Claims to be a “nice guy”, but befriends women solely because he wants to sleep with them.
Refuses to “settle” for a less physically attractive woman, but expects women to settle for him.
Complains that women only like assholes, but only thinks of women in terms of sex.
Sacrifices his desires to please any woman who pays attention to him, making himself a martyr.
Thinks of himself as “sensitive”, is in fact a spineless wimp who won’t stand up for himself. (N.B.: Comma splice.)
Is just as manipulative in the intentions of his “niceness” as an asshole is with abuse.

The final panel shows the Forever Alone character reading Reddit, with the sarcastic text, “What a nice guy.”

Is this really what people now associate with the term “nice guy”?

I’ve prided myself on being a nice guy for many years, long before I started seriously thinking about dating and relationships. Now, I normally feel uncomfortable saying good things about myself, because I know I can’t be objective; I’ll make an exception here. I have integrity and a strong sense of justice, and I aim to be the type of person you can trust with your life, your life savings, or your reputation. I’m genuine, and I won’t keep you around if I don’t like you, nor will I pretend to care about you if I don’t, but if you want to talk about your problems anyway, I’ll listen and do my best to be non-judgemental. I am reliable in that when I say I’ll do something, I make a commitment to doing it. I am at least somewhat generous; I’ll help you with your homework and the only thing I expect in return is that you’ll think of me as intelligent and helpful.

I am a nice guy, or at least I self-identify as such and I feel I have earned the privilege to do so. Every time I read a title that says “nice guys aren’t actually nice”, I feel insulted. If I’m in a bad mood, I’ll just close it. If I’m in a good mood, I might read it, knowing full well what kind of drivel it’s going to contain (refer to numbered points above). I’m basically putting up with a barrage of media telling me what an asshole I am, and I’m sick of it.

You might object that I’ve missed the point of those articles. Try me. There are three possibilities that I can see. Lest you argue that I’m the one throwing out straw men here, I’m going to provide some examples.

They are redefining “nice guy” to mean a person who has some or all of the negative qualities elaborated above, and then just reiterating the definition; this makes the entire article tautological. Here is an example. The title says it all. In summary, the article defines “Nice Guy” as different from a guy who is actually nice, by specifying that a “Nice Guy” is a guy who hates women for rejecting him.
They are claiming that a guy who refers to himself as a “nice guy” in fact has some or all of the negative qualities elaborated above. Here is an example. The first two lines say it loud and clear: A guy who proclaims himself “nice guy” is not nice (followed by 13 examples of how they’re supposedly assholes.)
They are claiming that if a heterosexual man seems nice but is undesired by women, it is probably because he has some or all of the negative qualities elaborated above. It was a bit harder to find an example for this, but I’d definitely seen it before, so I dug a bit deeper: here. The author targets a certain type of man by opening with, “I’m pulling back the curtain to reveal five secrets you always suspected about those male friends you would take home to ma, but never home from the bar: the nice guys.”, then calls them “hollow-balled shitbirds” and so on.

Option 1 is the least bad of the three. Being apparently tautological, it strikes me as a massive, ranting waste of words, and the tone always suggests to me that it could just as well have been option 2 or 3 if the author had just chosen their words slightly differently.

Option 2 is a bit worse. It’s related to my original concern. It means I can no longer refer to myself as a “nice guy” because the term evokes a straw man that will earn me instant hatred and trash my reputation by making me look horribly misogynistic.

Option 3 is the worst of all, and I find it unbelievably insulting.^* You know what? I know why dating is so hard for me, and it has nothing to do with this asinine caricature you’ve made of me. It’s because I have interests not often shared by women; it’s because I’m only interested in relationships that have the potential to lead to long-term stability and commitment, and I’m aware of my own flaws that would make that difficult with most women; and it’s because I believe the only worthwhile monogamous relationships are the ones in which both partners prefer each other, as they are, to all other potential partners.^**

So how do I think such articles should be written? They should say something like this:

If you think you’re a nice guy but women don’t seem to be attracted to you, you should seriously consider the fact that they aren’t rejecting you because you’re nice. Check that you’re not engaging in any of the following undesirable behaviours:
…
If you’re doing any of these things, stop. They aren’t helping your chances and may be contributing to unhealthy attitudes toward women.

If I came across an article written like this, it would strike me as genuine and well-intentioned and I would be able to avoid taking it personally, as it clearly does not apply to me as long as I don’t exhibit any of the behaviours it would go on to discuss. It also would allow me to continue calling myself a “nice guy”. After all, I am nice, and I refuse to be ashamed of it.

Sadly, I can’t recall a single instance of such an article.

^* I might project the image that I don’t take offense to anything and that I feel smugly superior to more emotional people who take offense easily, but this is quite inaccurate. I do get offended by some things, but here as always I want to reiterate that I don’t think anyone has wronged me for offending me. The offense is always related to something I perceive as an actual wrong; the offense is never wrong in and of itself.

^** I’m not sure what kind of polygamous or non-traditional relationships are worthwhile, but I don’t have to worry about that because I have no particular desire for a polygamous or otherwise non-traditional relationship.

Posted in Uncategorized | 2 Comments

Electrochemical potentials from first principles (part 2)

Posted on 2013-04-24 by Brian

Now let’s revisit Hess’s law and the standard values $\Delta H_f^\circ, \Delta G_f^\circ, S^\circ$ found in tables in the back of most textbooks.

In part 1, I pointed out, just as any textbook would, that we can compute the voltage of any full redox reaction by breaking it down into the reduction and oxidation half-reactions and adding their voltages. (You get the oxidation voltage by flipping the sign on the corresponding reduction potential.) This is true even if the half-reactions involve different numbers of electrons as written, because the fundamental meaning of voltage is energy per electron; when we combine the two half-reactions properly, the oxidation half-reaction must produce as many electrons as the reduction half-reaction consumes.

I said that if we have $N$ half-reactions, then this lets us compute the voltages of all $N^2$ full reactions we can get by combining them pairwise, just by tabulating the $N$ half-reaction potentials. This might sound like it’s “good enough”, but it isn’t. There are millions of known substances, but a practically unlimited number of half-reactions we could potentially compose from them. Tabulating all half-reaction voltages, in the hopes of being able to compute full-reaction voltages from them, is impossible.

But that’s okay, because half-reaction voltages aren’t all independent of each other, just like full-reaction voltages turned out not to be independent of each other (which we used in part 1 to justify our gauge fixing).

Here’s a simple example. Consider the following three half-reactions, under some uniform, specified set of conditions. (If they aren’t all occurring under the same set of conditions, you need to use Nernst’s equation to transform some or all of the voltages to a standard set of conditions; but more on that later.)

Fe³⁺ + e^– → Fe²⁺
Fe²⁺ + 2e^– → Fe
Fe³⁺ + 3e^– → Fe

Denote their standard reduction potentials by $E_1, E_2, E_3$ , respectively. Can we derive a relationship between the three? The answer is yes, and the reason is that these half-reactions all involve the same substances (loosely speaking). But here, caution must be exercised. Half-reaction 3 is the sum of half-reactions 1 and 2, but that does not mean its voltage is the sum of the voltages of half-reactions 1 and 2. The only time we can directly add is when the result is a full-reaction (with no dangling electrons) rather than a half-reaction. The bottom line is that $E_3 \neq E_1 + E_2$ in general, when adding half-reactions.

The correct method for solving this kind of problem is to rewrite the voltages as free energy changes and apply Hess’s law. Since reaction 3 is the sum of reaction 1 and reaction 2, it must also be true that $\Delta G_3 = \Delta G_1 + \Delta G_2$ . In the first reaction one electron is transferred, so $\Delta G_1 = -FE_1$ ; likewise in reactions 2 and 3, $\Delta G_2 = -2FE_2$ and $\Delta G_3 = -3FE_2$ , respectively. The result is $-3FE_3 = -2FE_2 - FE_1$ . Cancelling a factor of $-F$ gives our desired relationship: $3E_3 = E_1 + 2E_2$ . In general, $n_3 E_3 = n_1 E_1 + n_2 E_2$ .

This raises a pressing question, though. We used the formula $\Delta G = -nFE$ for half-reactions here, but only derived it for full reactions in part 1. In fact, what does $\Delta G$ even mean for a half-reaction anyway? It’s the free energy of the right side minus the free energy of the left side… but what if one side or the other contains dangling electrons?

We can deal with this problem in two ways. One is to combine each half-reaction with the standard hydrogen electrode half-reaction, which I will halve, for the sake of mathematical convenience, that is, 1/2 H₂ → H⁺ + e^–. Because this half-reaction is defined to have voltage zero, when we add it to any of our half-reactions, we can get a full-reaction whose voltage equals the voltage of the original half-reaction. Thus:

Fe³⁺ + 1/2 H₂ → Fe²⁺ + H⁺
Fe²⁺ + H₂ → Fe + 2H⁺
Fe³⁺ + 3/2 H₂ → Fe + 3H⁺

Now the voltages of these three full-reactions are as follows: $E_a = E_1; E_b = E_2; E_c = E_3$ ; again, this is true because $E_a = E_1 - E_0^\circ$ and so on, where $E_0^\circ = 0$ is the standard reduction potential of our standard hydrogen electrode reference reaction. Now we can apply the formula $\Delta G = -nFE$ rigorously. So what we get is $\Delta G_c = \Delta G_a + \Delta G_b$ , or $-3FE_c = -FE_a -2FE_b$ . But since each full reaction voltage equals the corresponding half-reaction voltage, we end up at the same conclusion: $-3FE_3 = -FE_1 -2FE_2$ , and so on. So what we can do is just apply the formula $\Delta G = -nFE$ to half-reactions willy-nilly because, as this example demonstrates, it’s shorthand that allows us to reach the same conclusion as we would have if, more rigorously, we had used full-reactions by combining with the reference cell.

The other way we can think about this is to carefully think about how we defined half-reaction potentials in the first place. I omitted a small detail in part 1, which is that the absolute half-reaction potentials actually depend on the nature of the wire—wires made of more electropositive metals don’t want electrons as much, for example. But that doesn’t matter because the number of electrons in the wire doesn’t ever change; all the wire does is ferry electrons from one half-cell to the other. Mathematically, the absolute potential inside the wire, $V_e$ , always cancels out. Indeed, we might as well represent the transfer of electrons from anode to cathode by the sum of a different set of two processes: one in which an electron moves from the anode to infinity, and another in which an electron moves from infinity to the cathode. If we do this, then the half-reaction potentials truly depend only on the nature of the participating substances (and their states), and not at all on the wire; and furthermore we can now define $\Delta G$ properly for a half-reaction, by declaring that whenever “e^–” appears on either the left or right side, its free energy is considered to be zero, since it now represents a standard reference point derived from our hypothetical half-processes—an infinitely dilute electron gas located infinitely far away from everything else.

Indeed, in a certain sense, it’s rather unfortunate that we had to use convoluted reasoning simply because we’re dealing with electrochemical reactions, in which electrons are transferred, rather than “ordinary” chemical reactions. A lot of chemical reactions can’t be broken down in a straightforward manner into two halves the way electrochemical reactions can, and yet, we manage to compute their $\Delta H$ and $\Delta G$ values, rather than just looking up each reaction separately in a table. We accomplish this using the standard enthalpies and standard free energies of formation in conjunction with Hess’s law. In theory, as long as we know these values for all individual substances under our reaction conditions, we can predict the $\Delta H$ and $\Delta G$ values for all chemical reactions under that set of conditions. The number of possible reactions that can be obtained from a given set of substances is vastly greater than the number of substances, so tabulating the standard electrode potentials for “all” half-reactions we’re interested in is far less practical than tabulating the standard enthalpies and free energies of formation for all substances we’re interested in.

In essence, basic electrochemistry looks harder than “normal” chemistry because many students are confused by what to do with the electrons, and because it seems like we use voltages to describe electrochemical reactions whereas we use free energies (which are perhaps simpler to understand) for non-electrochemical reactions. Thermochemically, however, the electrons ought to be treated as first-class citizens, that simply have their $\Delta H_f$ and $\Delta G_f$ set to zero under all conditions. If we think of half-reactions in this way, we can treat them in the same way as other reactions; we should be able to compute the potential of any half-reaction if we know just the $\Delta G_f^\circ$ of all participants.

To flesh out this idea, let’s consider the following reaction: 1/2 Cl₂ + e^– → Cl^–. This looks like a standard formation reaction for chloride ion. Certainly we cannot form an ion only from neutral elements, so we define the standard formation reaction for an anion as the half-reaction with one mole of the anion on the right side, and the constituent elements in their standard states together with an appropriate number of electrons on the left side; for a cation we define it the same way except that electrons go on the right side. We can measure this reaction’s voltage in the laboratory, and thus obtain the free energy change of this reaction. We will refer to this as the standard free energy of formation $\Delta G_f^\circ$ for chloride ion, just like with neutral substances. This standard formation reaction trivially satisfies Hess’s law, because its $\Delta G$ is equal to $\Delta G_f^\circ$ of the right side minus the sum of all $\Delta G_f^\circ$ values on the left; but the former describes the same reaction, and the latter is zero since we defined it to be zero for the elements in their standard states plus the dangling electron e^–.

Then, when considering a more complex half-reaction, such as: MnO₄^– + 8H⁺ + 5e^– → Mn²⁺ + 4H₂O, we can compute its free energy change by using the tabulated free energies of formation of all participants, and, again, noting that this is zero for the dangling electrons 5e^–.

Recall that we fixed a gauge by selecting the standard hydrogen electrode as the reference point for voltage. This gauge freedom exists in the free energy formulation as well. For, under this choice of gauge, the free energy of formation of H⁺ is exactly zero; but for any other choice of gauge, it is a nonzero number, and the free energies of formation of all other ions are shifted also; but once electrons are balanced, we still get the same value for the free energy change of a full-reaction as we would under any other choice of gauge.

That being said, the equation $\Delta G = \Delta G^\circ + RT \log Q$ applies to half-reactions. When we treat the electron as a reactant or product, the expression for $Q$ should include a factor of “[e^–]”. This is always one, so you can just cross it out, because the electron gas is always in its standard state. Dividing through by $-nF$ gives the Nernst equation: $E = E^\circ - \frac{RT}{nF} \log Q$ .

Okay, if you agree with everything I’ve said, then I’ve achieved my “agenda” this whole time, which is equal rights for the electron. Okay, I’m joking, but also half-serious. Some textbooks pretend that half-reactions are not “real” and that they are only used as a bookkeeping mechanism, i.e., so you can balance redox reactions by the half-reaction method and compute their voltages by adding the half-reaction voltages. But I feel that they stretch this a bit when they tabulate free energies of formation for ions, such as sulfate, in the back. If you don’t accept the reality of a half-reaction, then how can you make sense of $\Delta G_f^\circ$ values for ions?

This leads logically to the approach I have taken: accept that half-reactions are just like other reactions; accept that they have real $\Delta G$ values; see that this allows us to consider the standard free energies of formation of neutral molecules and ions in the same way; and accord the electron status as a separate “substance” in half-reactions, whose $\Delta G_f^\circ$ is zero. I think this is the least confusing way to regard the entirety of basic electrochemistry.

Posted in Uncategorized | Leave a comment

Done organic chemistry forever!

WKB approximation

ACM regionals, problems and solutions

Problem A

Solution

Problem B

Solution

Problem C

Solution

Problem D

Solution

Problem E

Solution

Problem F

Solution

Problem G

Solution

Problem H

Solution

Problem I

Solution

ACM regionals

Dating and non-equilibrium thermodynamics

Back to school update

Ode to the Hard Sciences

Mid-point update

On the “nice guy” straw man

Electrochemical potentials from first principles (part 2)

Recent Posts

Archives

Categories

Blogroll

Live Traffic Feed

Meta