Monthly Archives: June 2014

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(3) Quick Union

1

All right so QuickFind is too slow for huge problems. So, how are we going to do better? Our first attempt is an alternative called, Quick-union. This is so called lazy approach to algorithm design where we try to avoid doing work until we have to. It uses the same data structure or array ID with size M but now it has a different interpretation. We are going to think of that array as representing a set of trees that’s called a forest as depicted at right. So, each entry in the array is going to contain a reference to its parent in the tree. So, for example, 3’s parent is four, 4’s parent is nine. So 3’s entry is four and 4’s entry is nine in the array. Now each entry in the array has associated with it a root. That’s the root of its tree.

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(2) Quick Find

a

Now we’ll look at our first implementation of an algorithm for solving the dynamic connectivity problem, called Quick-find.
This is a so called eager algorithm, for solving kind activity problem. The data structure that we’re going to use to support the algorithm is simply an integer array indexed by object. The interpretation is the two objects, P and Q are connected if and only if, their entries in the array are the same.
So for example in this example with our ten objects the idea array that describes the situation after seven connections is illustrated in the middle of the slide. So that, after the, at this point zero, five, and six are all in the same connected component, because they have the same array entry, zero. One, two, and seven all have entry one. And three, four, eight, and nine all have entry eight.

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(1) Dynamic Connectivity

algorithm

Welcome back to algorithms. Today, we’re going to talk about the union find problem. A set of algorithms for solving the so-called dynamic connectivity problem. We’ll look at two classic algorithms. Quick Find and Quick Union, and some applications and improvements of those algorithms. The subtext of today’s lecture really is to go through the steps that we’ll follow over and over again to develop a useful algorithm. The first step is to model the problem. Try to understand, basically, what are the main elements of the problem that need to be solved. Then we’ll find some algorithm to solve the problem.

Tagged with:
Posted in Algorithm

Create a jQuery plugin to make your web as a speaker

web-speech-api

I there anyway to make your web text content spoken?

There are a lot of APIs we can use, but it is not easy to choose a suitable one. I tried with google translate speech api (e.g:http://translate.google.com/translate_tts?ie=UTF-8&q=what+are+you+doing&tl=en-us), but there is a limitation that the length of sentence can not be longer than 100 characters for one time call. Anyway we can split our large content into array of sentences and every item is one sentence which shorter than 100 characters. Then loop the array to call google’s API, but another problem raises up, google will cancel our call because the frequency is too high.

Tagged with: ,
Posted in Digital Multiple Media, Javascript

Anticorruption Activist Sentenced to More Than 6 Years in Prison

front1[1]

Two years ago, Liu Ping, one of three anticorruption activists sentenced on Thursday to prison terms of up to six and a half years, said she wanted to change China “one vote at a time.”

Posted in News Reading