I'm Zigang "Ivan" Xiao,
an engineer in bay area.
I have a cat called Moose.

about me

I write about technical stuff in the field of computer science, with a focus on Machine Learning, my hobbies, including guitar playing and ballroom dancing, and my life in US. Some of my posts are written in Chinese.

Source-highlight for Matlab/octave

- - posted in homebrew, matlab, tips

I recently worked with Matlab a lot. When in console, sometimes I want to use less to quickly examine the file content, and I have already set it up such that it uses source-highlight to output colorful escape sequence to the console. However, source-highlight does not come with a syntax support for Matlab by default. Luckily, this post and this (in Chinese) provides a solution.

Fix (Ugly) Safari 7.0 Not Using Local Pac File

- - posted in networking, osx

I found that Safari in Mavericks is not using local proxy.pac at all. Turns out because of sandboxing, it will not allow reading file from local. A traditional solution is to turn on Web Sharing, and thus use HTTP to read the pac file such as http://localhost/proxy.pac.

However, this cannot be done that simple, since Apple removed Web Sharing from normal version of Mavericks. To turn on the web service (Apache), do this:

1
sudo apachectl start

Also, place the pac file under /Library/WebServer/Documents, which is the default Document Root of Apache.

Tom Fischer proposed another way to get around, however I don’t think it a good idea to mess around the system files.

Saving $80 by Fixing MagSafe by Yourself

- - posted in diy, mac

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 rip-offs. 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.

Updating Octopress Theme

- - posted in octopress

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
rake update_source['theme name']

Without the brackets, it defaults to .themes/classic.

Caveats:

  • Do NOT use rake install to install the theme again, since it will overwrite the whole thing, including the files in source/_include/custom directory.
  • When working on the blog, anything outside of 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.

Graph Matching: Augmenting Path

- - posted in algorithm

Introduction

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.

Augmenting Paths

  • Alternating path: a path in which the edges belong alternatively to the matching and not to the matching
  • Augmenting path: an alternating path that starts from and ends on exposed vertices

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.

Network Flow: Push-relabel Algorithm

- - posted in algorithm

According to CLRS: Many of the asymptotically fastest maximum-flow algorithms are push-relabel algorithms, and the fastest actual implementations of maximum-flow algorithms are based on the push-relabel method. Push-relabel methods also efficiently solve other flow problems, such as the minimum-cost 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 in-flow may be larger than out-flow at a vertex. The amount of overflow is called ‘excess’.

Network Flow: Ford-Fulkerson Method

- - posted in algorithm

Basic method (framework) is Ford-Fulkerson. 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 \(s-t\) path and augment it. However, it has two problems: