I’m Zigang Xiao (Ivan),
a PhD candidate
in University of Illinois.

about me

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 ;)

archives

categories

found on

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: Hopcroft-Karp Algorithm

- - posted in algorithm

Overview

Hopcroft-Karp 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.

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:

Installing a New Car Stereo

- - posted in DIY, car

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 note-worthy features include:

  • iPod/iPhone support. Control the iphone directly from the panel.
  • App support. This includes I-heart-radio, pandora, etc.
  • Bluetooth Audio: stream music directly from a paired device. Even supports Pandora!
  • Upgraded FM/AM support. Displays text from radio stations.