This post summarizes some common useful tips in LaTeX editing.
I write about technical stuff in the field of computer science, my hobbies, including guitar playing and ballroom dancing, and my study abroad experience in US. And yes, some of my posts are in Chinese ;)
This post summarizes some common useful tips in LaTeX editing.
After four years of use, the wire on my MagSafe finally fray out. After searching a bit, I found that a new one costs $80!! My old memories came back: almost all accessories by Apple are ripoffs. See how low the ratings are:
I know that this can be easily fixed if you know a little soldering and have courage: the adapter is working perfectly fine, it is just the wires. I decided to DIY. There are several pretty good articles on how to open the MagSafe and how to solder it.
The themes are stored in .themes/<name>
, we can use the rake command to update either the source or style, as documented in the office website. However, the syntax should be more clear, i.e.,
1


Without the brackets, it defaults to .themes/classic
.
Caveats:
rake install
to install the theme again, since it will overwrite the whole thing, including the files in source/_include/custom
directory.source/_include/custom
should be considered the theme. Thus, do not make changes directly in source
. Make changes to theme and update the theme to reflect the changes to the blog.HopcroftKarp algorithm also utilizes the augmenting path. The difference between the simple augmenting path algorithm is, instead of searching augmenting path one by one, it looks for many paths in the same time. The paths found at each iteration are in fact vertex disjoint path. By doing so, the number of iterations can be cut down, since there cannot be too many disjoing paths.
The major observation is that the length of augementing path grows at each step. Thus, if we keep finding a set of vertex disjoint augmenting paths, the algorithm is guaranteed to stop eventually and faster than finding the path one by one.
Let \(G=(V, E)\) be an undirected graph. Matching in \(G\) is a subset of edges \(M \subseteq E\) such that at most one edge is incident to each vertex in \(V\).
A vertex is matched is it is incident to some edge in \(M\), otherwise it is called free or exposed.
Clearly, an augmenting path can be ‘flipped’ to increase the matching size by one, i.e., just make free vertex matched and make matched vertex free in this path.
Berge’s Theorem: The matching M is maximum iff there is no augmenting path w.r.t. \(M\). I personally think the proof is easy but quite powerful.
Thus, we can immediately use the theorem to design an algorithm: find augmenting path iteratively until no more can be found. The problem is how we can find the augmenting path.
According to CLRS: Many of the asymptotically fastest maximumflow algorithms are pushrelabel algorithms, and the fastest actual implementations of maximumflow algorithms are based on the pushrelabel method. Pushrelabel methods also efficiently solve other flow problems, such as the minimumcost flow problem.
This algorithm has a very different flavor. The overall idea is to generate a ‘preflow’ that may not satisfy the flow properties, and keep ‘pushing’) and ‘elevating’ (relabelling) the vertices until we cannot do that. We then remove the ‘excess’ from the preflow and obtain a valid flow, which is also a max flow. In particular, the inflow may be larger than outflow at a vertex. The amount of overflow is called ‘excess’.
Basic method (framework) is FordFulkerson. It’s called a “method” because it’s general, there can be different implementation that yield different complexity. It looks like this:
Let F be an empty flow
While there is augmenting path P from s to t
Augment F with P
End while
The problem is how we find the augmenting path efficiently. A naive implementation is to use DFS to randomly pick a \(st\) path and augment it. However, it has two problems:
I did not realize until my car’s radio’s broken that, with less than a hundred bucks, you can buy a new Head Unit with nearly all functionality. Some noteworthy features include: