nguyentito / miscalgo Goto Github PK

A repository for some throw-away algorithmic code I wrote at some point in my life. Because there's not enough useless stuff on GitHub already.

• C
  • Parallel merge sort
• Haskell
  • Calculator for arithmetic expressions with an ad-hoc parser (written in high school; the code is rather ugly)
  • Longest increasing subsequence (using a binary tree instead of an array)
• OCaml
  • Huffman encoding (also written a very long time ago!)
  • Quadtree-based solution to a Prologin exercise (this is not the intended solution, but it works and its performance is good enough)
  • Cycle decomposition for permutations
  • Exhaustive search in Cantor space ("seemingly impossible functional programs")
• Ruby
  • Optimal bitonic tour (a classic exercise from CLRS)
  • Maximum antichain in a finite poset (using bipartite maximum matching + Dilworth's theorem), applied to the divisibility order on positive integers
• Rust (old version, probably not compatible with the current one)
  • Knuth-Morris-Pratt string matching
  • Manacher's algorithm for the longest palindromic substring problem (with QuickCheck tests)