#Algorithms in Python

这是学习笔记Algorithms,欢迎访问。

这个项目的教材基于Algorithms by Sanjoy Dasgupta & Christos Papadimitriou & Umesh Vazirani,可以从这里翻阅。

所有的算法实现语言均为Python,在Python2.6.6的环境下均能测试通过。

##关于实现

基本上所有的实现方案都是照抄书上的伪代码_ (:3」∠)_ 让人感觉Python真是简单易懂,写出来的代码跟书上的伪代码没差嘛!所以,嗯,也就是说, 这些实现都只是玩具,不要用到实际环境中 。

比如说,关于求(x**y) % z,在 modular_arithmetic.py 中有函数 modexp(x, y, z) ,但我觉得你不用想都知道,肯定还是 pow(x, y[, z]) 来得更快。再比如UniHashing类,肯定也没有dict类高效且经得起碰撞。

所以,这些都是玩具= =

##目前进度:

• Chapter 0: Prologue
  • Fibonacci numbers fibonacci.py
• Chapter 1: Algorithms with numbers
  • Basic arithmetic basic_arithmetic.py
  • modular arithmetic modular_arithmetic.py
  • Euclid's algorithm euclid.py
  • Primality test primality.py
  • Generating primes primality.py
  • RSA rsa.py
  • Universal hashing hashing.py
• Chapter 2: Divide-and-conquer algorithms
  • divide-and-conquer multiplication basic_arithmetic.py
  • Mergesort mergesort.py
  • the fast Fourier transform fft.py
  • Polynomial multiplication fft.py
• Chapter 3: Decompositions of graphs
  • Depth-first search dfs.py
• Chapter 4: Paths in graphs
  • Breadth-first search bfs.py
  • Dijkstra's shortest-path algorithm shortest_path.py
  • Bellman-Ford algorithm for single-source shortest path shortest_path.py
• Chapter 5: Greedy algorithms
  • Kruskal's mininum spanning tree algorithm mst.py
  • Prim's mininum spanning tree algorithm binary_heap.py mst.py
  • Huffman encoding huffman.py
• Chapter 6: Dynamic programming
  • Edit distance edit_distance.py