Princeton Alogorithm COS226 Week

brute force

image.png

except performance, another problem is backup.
in many applications, we want to avoid backup in text stream.

image.png

brute force alogroithm is not always good enough.
linear-time guarantee, avoid backup in text stream;

KMP

suppose we are searching in text for pattern BAAAAAA

suppose we match 5 chars in pattern, with mismatch on 6th char.
we know previous 6 chars in text are BAAAAB
we donot need to back up text pointer

image.png

KMP algorithm is a clever method to always avoid backup.

DFA is abstract string-search machine.
there are three properites:

1. finite number of states (including start and halt)
2. exactly one transition for each char in alphabet

3. accept if sequence of transitions leads to halt state

   
   image.png

key differences from brute-force implementation

1. need to precompute dfa[][] from pattern

2. text pointer i never decrements

   
   image.png

How to build dfa from pattern?

match transition. if any state j and next char c == pat.charAt(j), go to j + 1

image.png

mismatch transition. if in state j and next char c != pat.charAt(j), then the last j-1 characters of input are pat[i..j-1], followed by c

image.png

java implementation

image.png

Boyer-moore

intuition is that we could scan characters in pattern from right to left

can skip as many as M text chars when finding one not in the pattern

image.png

how much to skip?
we could precompute index of rightmost occurrence of character c in pattern (-1 if character not in pattern)

image.png
image.png

best case N / M
worst case M * N

image.png
but we can improve worst case to 3N character compares by adding a KMP-like rule to guard against repetive patterns

Rabin-Karp

compute a hash of pattern character 0 to M - 1
for each i, compute a hash of text characters i to M + i - 1
if pattern hash = text substring hash, check for a match

image.png image.png image.png

Monte carlo version: return match if hash match
Las Vagas version: check for substring match if hash match; continue search if false collision

Key properties

Theory. if Q is a sufficiently large random prime (about M*N^2) then the probability of a false collision is about 1 / N

Choose Q to be large prime under reasonable assumptions, probability of a collision is about 1 / Q

if we choose monte carlo version:
always run in linear time;
extremely likely to return correct answer (but not always!)

las vagas version:
always returns correct answer
extremely likely to run in linear time (but worst case is M * N)

Advantages.

Extends to 2d patterns.
Extends to finding multiple patterns.

Disadvantages.

Arithmetic ops slower than char compares.
Las Vegas version requires backup.
Poor worst-case guarantee.

add extra credit to extend Rabin-Karp to efficiently search for any
one of P possible patterns in a text of length N

image.png

QUIZ

Q1 Cyclic rotation of a string

image.png

we append same string on the origin string. eg. 'abc' -> 'abcabc' then run KMP to check other str in substring of 'abcabc' and same length with 'abc'

Q2 Tandem repeat

image.png

mark base string as long as possible but less equal than string s, then use kmp to find the maxJ, after we can the maxJ, we can get the answer by maxJ divided by base string length.

Q3 Longest palindromic substring

image.png

nlogn solution is using karp-rabin and binary search. the thing we could know, longer palindromic string contains shorter palindromic string. thus binary search could used. if we cannot find palindromic string, we need to end = mid - 1; if we can find palindromic string, we could try longer, start = mid + 1;
the important thing we need to check odd and even number both in one binary search.

the next thing we need to design an algorithm to given a length L, check palindromic exists or not. this could solved by karp-rabin.
another hard point is that we could not use divide operation, because it will loss accuracy. what should maintain is two base. details see the code.

O(n) solution also called manacher algorithm.
https://mp.weixin.qq.com/s/EiJum3-44TqXZN4apuSQUQ

Project Boggle Game

this project is to combine the TRIE and DFS together.
foreach DFS, we have a Trie Node related to this level search.
so the possible progress step is first familiarize yourself with the BoggleBoard.java

then create boggle solver, to dfs to enumerate all string that can be composed by following sequences of adjacent dice.when the current path corresponds to a string that is not a prefix of any word in the dictionary, there is no need to expand the path further.

in the end, Deal with the special two-letter sequence Qu.

for the bonus

Make sure that you have implemented the critical backtracking optimization described above. means when next trie node is null. no need to dfs more.

Recall that the alphabet consists of only the 26 letters A through Z. use trie 26, more space but faster than TNT

it is usually almost identical to the previous prefix query, except that it is one letter longer. no need to write prefix query, just keep the state TrieNode, and current board position in each dfs.

Precompute the Boggle graph, i.e., the set of cubes adjacent to each cube. But don't necessarily use a heavyweight Graph object. y,x to caculate the key for every point, which means key = y * width + x, then for every point, save current key's neighbors key in int[][] graph , therefore we need a letter array to map the key to the letter in board. (0.85x -> 0.5x)

saved a string field in TrieNode, when meet a TrieNode string field is not null, saved it in bag (implemented in first version)

saved a sign for current call id, every call should increase this id, to know this word already been added. instead of using a set. (implemented in first version )

check dictionary words during build the trie tree , if Q is not valid, just continue it. i do not saved TrieNode u as Q's child. because in board, there only exists Qu, not any Qx. (0.5x -> 0.4x)

course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226