\trans@languagepath ->\languagename, English.错误处理

2012年5月11日 09:45 

\documentclass{beamer}
\usetheme{default}
\begin{document}

\begin{frame}{A sample slide}
A displayed formula:

\[
  \int_{-\infty}^\infty e^{-x^2} \, dx = \sqrt{\pi}
\]

\begin{theorem}
  In a right triangle, the square of hypotenuse equals
  the sum of squares of two other sides.
\end{theorem}
\end{frame}

\end{document}

会出现类似如下的错误：

! Undefined control sequence. \trans@languagepath ->\languagename
l.54 \end{frame}

1、\usepackage[english]{babel}宏包加上就没有问题了

2、按照上面的链接的解决方案，即更新升级下MIktex的beamer包，问题便自动解决了。
CTeX->MikTeX->Maintenance(Admin)->Updat(Admin)

注意：升级MIktex的beamer包的时候，必须关闭所有有关latex的文件

http://hi.baidu.com/zjunmm/blog/item/0915d010d7ce2d175aaf53d1.html/cmtid/259538d857650d69d1164e6d

评论(4) 阅读(4765)

Dynamic Programming Problems经典问题集

2012年3月05日 09:21

1. The Integer Knapsack Problem (Duplicate Items Permitted):

You have $n$types of items, where the$i^{th}$ item type has an integer size $s_i$and a real value. $v_i$

You are trying to fill a knapsack of total capacity $C$with a selection of items of maximum value.

You can add multiple items of the same type to the knapsack.

Solution: Let M(j) denote the maximum value you can pack into a size j knapsack.

We can express M(j)recursively in terms of solutions to smaller problems as follows:

$$M(j)= \left\{ \begin{aligned}\overset{}\max\{M(j-1) , \max_{i=1...n}M(j-s_i)+v_i \} \quad j\ge 1\\ \\ 0 \quad j \le 0 \end{aligned}\right. $$

Computing each M(j)value will require $\Theta(n)$ time, and we need to sequentially compute $C$such values.
Therefore, total running time is $\Theta(nC)$ . Total space is $\Theta(n)$ .

The value of $M(C)$ will contain the value of the optimal knapsack packing.

We can reconstruct the list of items in the optimal solution by maintaining and following “backpointers”

2. Maximum Value Contiguous Subsequence.

Given a sequence of $n$ real numbers $A_1, ... A_n$,

determine a contiguous subsequence $A_1, ... A_j$ for which the sum of elements in the subsequence is maximized.

Solution: Let $M(j)$denote the max sum over all windows ending at $j$

$M(j) = max\{ M(j-1)+A[j], A[j]\}$

It only takes linear time $O(n)$to run the program since it only need to solve $n$sub-problems and each takes constnt time.

3. Making Change: You are given $n$ types of coin denominations of values  $v_1 < v_2 ... < v_n$ (all integers).

Assume $v_1 =1$, so you can always make change for any amount of money C.

Give an algorithm which makes change for an amount of money C with as few coins as possible.

Solution: Let $M(j)$denote the min number of coins required to make changes for amount of money $j$

$M(j)=\min_{i=1...n}\{M(j-v_i)\}+1$

It takes $O(nC)$ time because we are solving $C$subproblems,

each of which requires minimization $O(n)$ different terms. (Similar to integer knapsack problem)

4. Longest Increasing Subsequence. Given a sequence of n real numbers $A_1, ... A_n$,

determine a subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a strictly increasing sequence.

Solution: Let $L(j)denote the longest strictly increasing subsequence ending at position$j$ , therefore,

$L(j) = \max\limits_{i<j}\limits_{A[i]<A[j]}\{ L(i)\}+1 $

to find the solution overall, it has to find the maximum over all potential ending points $j$of $L(j) :

$\max\limits_{j=1...n}\{L(j)\}$

since the longest increasing subsequence could end anywhere.

The algorithm takes $O(n^2)$time to run because I have to sort $n$subproblems and each of them takes $O(n)$time.

5.Box Stacking:

You are given a set of $n$ types of rectangular 3-D boxes, where the $i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real numbers).

You want to create a stack of boxes which is as tall as possible,

but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.

Of course, you can rotate a box so that any side functions as its base.

It is also allowable to use multiple instances of the same type of box.

Solution: constraint : can only stack box $i$on box $j$if $w_i<w_j$ and $d_i<d_j$

(without loss of generality, assume $w_i\le d_i$ ).

First sort the base area by decreasing order:

then let $H(j)$ denote the tallest box stack I could form with box $j$on top, so

$H(j) = \max\limits_{i<j, w_i<w_j, d_i<d_j}\{ H(i)\}+h_j $

The algorithm takes $O(n^2)$time to run because I have to sort $n$subproblems and each of them takes $O(n)$time.

At the end, the solution is found by taking the max of all potential top boxes $j$of $H(j)$.

(Since we are not sure in the optimal solution, which box is on top)

6. Building Bridges.

Consider a 2-D map with a horizontal river passing through its center.

There are $n$cities on the southern bank with x-coordinates $a_1... a_n$and $n$ cities on the northern bank with x-coordinates $b_1 ... b_n$.

You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross.

When connecting cities, you are only allowed to connect the the ith city on the northern ban to the ith city on the southern bank.

Solution: consider the south bank city (below the river) $i$,

let $x(i)$denote the index of corresponding city on the north bank ($x(i)=3$ in the figure).

So we could compute the $x(i)$by sorting in $O(n\log n)$time.

Now we want to find the longest increasing subsequence through $x(1), ... x(n)$, so it is identical to problem 4.

7. Balanced Partition:You have a set of n integers each in the range 0 . . .K.

Partition these integers into two subsets such that you minimize $S_1 - S_2$,

where $S_1$ and $S_2$ denote the sums of the elements in each of the two subsets.

Solution: Use $$P(i,j)= \left\{ \begin{aligned}\overset{}1 \quad \text{if some subset of } \{A_1, ... A_n\} \text{has sum of j}\\0 \quad \text{otherwise}\end{aligned}\right.$$ where $i \in [0,n]$ and $j \in [0,nK]$

therefore, $P(i,j)=1$if $P(i-1, j)=1$ or $P(i-1, j-A_i)=1$

dynamic programming formula is:

$P(i,j)=\max\{P(i-1,j), P(i-1, j-A_i)\}$

this procedure takes $O(n^2K)$time to compute.

To solve the original problem, let $S=\sum(A_i)/2$, and the purpose is to make $S_1 - S_2$ close to 0 as possible.

what we want to find is:

$\min\limits_{i\le S}\{S-i: P(n, i)=1\}$

8. Edit Distance.

Given two text strings A of length n and B of length m,

you want to transform A into B with a minimum number of operations of the following types:

delete a character from A, insert a character into A,

or change some character in A into a new character.

The minimal number of such operations required to transform A into B is called the edit distance between A and B.

Solution: Use $C_i, C_d, C_r$to denote the cost for inserting, deleting or replacing a letter.

The goal is to compute the minimum cost of translating A to B.

Let $T(i,j)$denote the minimum cost of translating $A[1...i]$into $B[1...j]$, then

$$T(i,j)= \left\{\begin{aligned}\overset{}C_d + T(i-1, j) \\ C_i+T(i, j-1) \\ \overset{} T(i-1, j-1) \quad if \quad A[i]=B[j] \\ C_d+T(i-1,j-1) \quad if \quad A[i] \neq B[j] \end{aligned}\right.$$

It takes $O(nm)$time to compute and final solution is stored in $T(n,m)$

评论(243) 阅读(18328)

在Gmail中选出所有未读邮件[zz]

2012年2月01日 09:54

几天不看邮件，就有几百封新邮件了，Gmail中分了很多页显示。其中多数是广告。

不过一直显示有N封未读邮件，看着不舒服。 要能找出所有未读的邮件，一起标记成已读就好了。

貌似Gmail的界面中并没有提供按钮可以做到这件事，不过想想Google的搜索特长，应该可以通过搜索搞定。
在搜索框里输入ls:unread，再点搜索即可。
简化版的指令是l:^u，效果是一样的。

还有一些类似的指令：

  • l:^u from:tim 找出所有来自tim的未读邮件；
  • l:^u l:^t 找出所有未读的加了星标的邮件；
  • l:^u l:^k subject:hi 找出所有垃圾箱中的标题包含“hi”的邮件。

http://leonax.net/p3253/search-all-unread-mail-in-gmail/

评论(7) 阅读(3323)

ubuntu 11.10 unable to mount ipod

2012年1月04日 06:35

安装iFuse

sudo apt-get install libimobiledevice-utils

评论(9) 阅读(4150)

C++ —用sstream把int转成string类型的方法

2011年9月15日 08:59

itoa是把整型转成char*,如果要转成string类型的话，可以用如下方法

In order to convert an int (or any other numeric type, e.g., float, double, etc.) to string, you can use:

#include <sstream>

int i = 5;
std::string s;
std::stringstream out;
out << i;
s = out.str();

来自：http://notfaq.wordpress.com/2006/08/30/c-convert-int-to-string/

评论(19) 阅读(4175)