with our free apps for iPhone, iPad and Android

Get Started

Already have an account?

Log In

NLPA Review of Basic Data
Structures and Algorithms
by Thomas Breuel
# NLPA Review of Basic Data
Structures and Algorithms

## language classes

### by machine

### by language

### by algorithm

## data structures

### comparison-based

### hashing

### alphabet-based

## algorithms

### sorting

### Boyer-Moore

### Hunt-McIlroy

### Levenshtein distance

0.0 stars - 0 reviews
range from 0 to 5

finite state automata

pushdown automata

linear bounded automata

turing machines

regular

context free

context sensitive

phrase structure

(uncomputable)

recursive descent parsing, top-down parser, predictive, no backtracking, LL(k) grammars, context free, only examines next k tokens, no left recursion, backup, backtracking, may not terminate at all, may take exponential time

LR parsers, bottom-up parsers, deterministic context free languages, linear time

binary trees, unbalanced binary trees, worst case O(log n) operations, red-black trees, AA trees, AVL trees, B-tree, Splay trees, cf. self-organizing lists, amortized O(log n) operations, scapegoat tree, randomized O(log n) operations, treaps, implement a regular binary tree, perform rotations on the binary tree to maintain the heap property

skiplists, example, create sparser and sparser lists by randomly selecting subelements, go along sparse list until you've gone to far, then go down to next level, alternatively, can create a non-randomized, amortized version of this algorithm

hash tables, chaining, hash buckets contain lists of elements, open addressing, hash buckets contain elements themselves (or an empty indicator), collisions are handled by, linear probing, polynomial probing, double hashing, issues, resizing, collision handling, iteration

hash functions, desired properties, deterministic, output should be uniform across its range for input distributions, general issues, hashing numbers, hashing strings, cryptographic hashing, universal hashing, perfect hash function

Bloom filters, similar to hashing, hash entries are just 1 bit each, indicating whether that bucket has ever been used, if the Bloom filter returns false, the key has not been previously added, if the Bloom filter returns true, the key may have been added, or we may have a false positive, repeat with multiple bits to get probability estimates for false positives

tries

radix tree

patricia tree

suffix tree

suffix array

quicksort

mergesort

radix sort

string search

UNIX tool: fgrep

problem, find a string in a text (perhaps repeatedly), input: query, text, output: position of first match, can spend time and memory on preprocessing the string, preprocesses query, not text

brute force solution, match at position 0, return if match, advance to next position and repeat

Boyer-Moore, idea: when we look at one character in the text, it gives us additional information about positions where the string can't match

NB: you don't need to know the details of the algorithm, but you should know the name, what it does, and what the idea is

longest common subsequence

UNIX tool: diff

problem, given two sequences, find the longest common subsequence (not substring)

NB: you don't need to know the details of the algorithm, but you should know the name and what it does

minimum number of edits necessary to transform one string into another

UNIX tool: agrep

problem: given two input string, find the minimum number of insertions, deletions, and substitutions to transform one into another

solution: dynamic programming

(already covered this in previous classes; you need to know this algorithm well, it's the prototypical dynamic programming algorithm)