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