# Problem Setting

CREATED: 200701060230 ** Stack

- Sorting using 3 stacks, using 2 stacks
- Pushing and popping, rails
- Simulation of VM

** Queue

- Knight tour
- Maze exploration

** Analysis/sorting

- hotel
- bus driver
- max contig sum

** Heap

- keep top k elements
- univeristy admissions

** Recursion

- arbitrary configuration of ToH
- ToH with pairs of discs

** Hashing

- permutation <-> number
- word ladder
- rabin karp string matching

** Unsorted

- Optimal binary search tree in O(n^2) by Knuth
- Convert a given BST into a complete tree
- Given a tree, two nodes x, y, determine if x R y ** R = ancestor, descendant, left, right
- Tree isomorphism
- Group of anagrams
- Coolumb ruler
- Local alignment
- RNA folding
- Largest rectangle in 0/1 matrix
- Range query using segment tree
- Modified Floyd ** no of paths between two vertices ** no of even/odd length paths ** no of shortest paths ** label and length of lexicographically first shortest path
- Edit distance ** cursor at first letter ** operations: advance, replace, delete, kill, insert
- Rock games, splitting piles
- No of topological ordering of a DAG
- 1-1 mappings
- Betweeness of edges

** References

- //Text algorithms//, Crochermore Kyttes
- //Algorithms for finding patterns in strings//, Aho
- //Algorithms on Strings, Trees and Sequences//, Gusfield