Introduction-to-Algorithms

書籍:アルゴリズムイントロダクションの C++ / Fortran / Python / Cilk Plus による実装。

Overview

残念ながら問題の見落としや、Fibonacci Heap などのように紛失してしまったコード部分もあります。

C++ を思い出しながら書いたプログラムなのであまり洗練されたコードではありません。
また、当時は git のようなバージョン管理ツールを本格的に使用していなかったので、基本的には Initial commit で完結してしまっています。

Graph アルゴリズムに関しては こちら に書き直したものがあります。

• 基礎 (Foundations)
  • 挿入ソート (Insertion sort)
  • Strassenのアルゴリズム (Strassen’s Algorithm)
  • マージソート (Merge sort)
• ソートと順序統計量 (Sort and Order Statistics)
  • ヒープソート (Heap sort)
  • クイックソート (Quick sort)
  • 中央値と順序統計量 (Medians and Order Statistics)
• データ構造 (Data Structures)
  • スタック (Stack)
  • キュー (Queue)
  • 2分探索木 (Binary Search Trees)
  • 2色木 (Red Black Trees)
  • AVL木 (AVL Trees)
• 高度な設計と解析の手法 (Advanced Design and Analysis Techniques)
  • 動的計画法 (Dynamic Programming)
  • 貪欲アルゴリズム (Greedy Algorithms)
• 高度なデータ構造 (Advanced Data Structures)
  • B木 (B-Trees)
  • 互いに素な集合族 (Disjoint-set)
• 基本的グラフアルゴリズム (Elementary Graph Algorithms)
  • 幅優先探索 (Breadth-first Search)
  • 深さ優先探索 (Depth-first Search)
  • トポロジカルソート (Topological sort)
  • 強連結成分 (Strongly connected components)
• 最小全域木 (Minimu Spanning Trees)
  • Primのアルゴリズム (Prim’s Algorithm)
  • Kruskalのアルゴリズム (Kruskal’s Algorithm)
• 単一始点最短路 (Single-Shource Shortest Paths)
  • Dijkstraのアルゴリズム (Dijkstra’s Algorithm)
  • Bellman-Fordのアルゴリズム (Bellman-Ford’s Algorithm)
• 全点対最短路 (All-Pairs Shortest Paths)
  • Floyd-Warshallのアルゴリズム (Floyd-Warshall’s Algorithm)
• 最大フロー (Maximum Flow)
  • Ford-Fulkersonのアルゴリズム (Ford-Fulkerson’s Algorithm)
  • Edmonds-Karpのアルゴリズム (Edmonds-Karp’s Algorithm)
• マルチスレッドアルゴリズム (MultiThreaded Algorithms)
  • Fibonacciのアルゴリズム (Fibonacci’s Algorithm)
  • 行列積 (Matrix Multiply)
  • マージソート (Merge Sort)
• 行列演算 (Matrix Operations)
  • LPU分解 (LUP decomposition)
• 線形計画法 (Linear Programming)
  • シンプレックスアルゴリズム (The simplex algorithm)
• 多項式とFFT (Polinomials and the FFT)
  • DTFとFFT (The DFT and FFT)
• 数論的アルゴリズム (Number-Theoric Algorithms)
  • 最大公約数 (Greatest common divisor)
  • 剰余演算 (Modular zrthmeric)
  • Miller-Rabinのアルゴリズム (Miller-Rabin’s Algorithm)
• 文字列照合 (String Matching)
  • 素朴な文字列照合アルゴリズム (The naive string-matching Algorithm)
  • Rabin-Karpのアルゴリズム (Rabin-Karp’s Algorithm)
  • 有限オートマトンを用いる文字列照合 (String matching with finite automata)
  • Knuth-Morris-Prattのアルゴリズム (Knuth-Morris-Pratt’s Algorithm)
• 計算幾何学 (Computational Geometry)
  • 線分交差判定 (Determining whether any pair of segments intersects)
  • 凸包の構成 (Finding the convex hull)
  • 最近点対の発見 (Finding the closest pair of points)
• 近似アルゴリズム (Approxmetry Algorithms)
  • 頂点被覆問題 (The vertex-cover problem)