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 …

1. Shortest Paths APIs

context: directe, weighted graphs.

shortest path variants

in terms of vertices:

• source-sink: form one vertex to another
• single source: from one vertex to all others (considered in this lecture)
• all pairs

constraints on edge weights:

• nonnegative weights
• arbitary weights
• eculidean

cycles:

• no directed cycles
• no negative …

1. Introduction to MSTs

Given: undirected connecte graph G with positive edge weights.
def. Spanning tree T
is a subgraph of G, that is both tree (connected, acyclic) and spanning(all vertices are included).

⇒ Goal: find a spanning tree with minimum weight sum.

2. Greedy Algorithm

assumptions for simplification:

• edge …

1. Intro to digraphs

Has profound differences wrt undirected graphs.

def: digraph
edges: have directions
vertex: distinguish indeg and outdeg

digraph pbs:

• path/shortest path
• topological sort: Can you draw a digraph so that all edges point upwards?
• strong connectivity: Is there a directed path between all pairs of vertices …

1. Intro to graphs

Graph: vertices connected by edges.

terminology:

• path: sequence of vertices connected by edges
• cycle: path with same starting and ending vertex
• two vertices are connected: if there is a path between

ex of graph problems:

• path: or connectivity
• shortest path
• cycle
• Euler tour (ouii..)
• Hamilton tour …