1. Introduction to Data Compression

pb: reduce the size of a file, to save space/time for storing/transmitting.
applications: generic file compression(gzip), multimedia (mp3), communication(skype).

From binary data B, ⇒ generate a compressed representation C(B).

lossless compression: get exactly B from C(B)
compression ratio: |C(B …

I. 工作

学业

三月初结束了在X的最后几门考试, X的课从来都不简单, 但我真的很享受, 尤其是那些数学课.
(不过刚考完就sb了: 陪伴我两年的杯子丢了...)

Polytechnique, 从憧憬 …

1. Regular Expressions

pb: pattern matching.

regular expression

Is a notation to specify a set of strings.
basic operations:

• concatenation
• or
• closure: "0 or more appearances of chars"
• parentheses

additional operations (added for convinence):

ex. [A-C]+ is equivalent to (A|B|C)(A|B|C)*.

吐槽名句:

2 …

今天简单介绍一下优先队列(priority queue, 以下简称PQ)这个数据结构的实现.

PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的 …

1. Introduction to substring search

"most ingenious algorithm we've seen so far"
**pb. **having two strings, pattern and text, len(pattern)=M << len(text)=N, try to find pattern in text.

ex. indexOf method of String in java.

2. Brute-Force Substring Search

function signature:
public static int search(String pat …

今天总结一下非常有用的快速排序(qsort)算法, 以及由此衍生的一些其他相关算法(Knuth shuffle, quick select, 3-way partition).

快速排序的算法可以用三 …

More efficient version of symbol-table where the keys are strings.

1. R-way Tries

Two implementations of symbol tables that we've seen:

when keys are strings:
(L=string length, N=number of strings, R=radix)

for string keys ⇒ do better by avoiding examing the entire key.

goal: faster than hashtable, more …

This week: string sort.

1. Strings in Java

char data type

• char in C

8-bit integer, 256 characters, 7-bit ASCII code

• char in Java

16-bit Unicode

String data type

String: immutable sequence of characters
operations: lengthe, ith char, substring, concatenate

implementation: using a char[], maintain a length and an offset …

今天介绍一个论文写作的神器: TeXmacs !

0. Why TeXmacs?

一说到"论文写作神器"一般大家首先想到的就是LaTeX, 确实LaTeX写出来的数学公式和文章的排版非常漂亮. 但是作为一个几年来 …

1. Introduction to Maxflow

Min-cut pb

• input: edge-weighted digraph G, each edge e has weight("capacity") c[e]>=0, a source vertex s, a target vertex t.
• def. an **st-cut **(A,B) is a partition of vertices into 2 disjoint sets A and B, with s in set A and …