Skip to content

leo000leo/Algorithm

 
 

Repository files navigation

Algorithm

Algorithm and data structures exercises.

Build with Cpp and Ruby.

DataStructures

Cpp

  1. ListNode: node for single linked list.
  2. LinkedList: single linked list based on pointer.
  3. Polynomial: polynomial class based on linked list, which supports operators +, - and *.
  4. Stack: stack based on linked list.
  5. StackBasedOnArray: stack based on array.
  6. Queue: queue based on linked list.
  7. QueueBasedOnArray: queue based on array.
  8. PriorityQueue: priority queue based on linked list.
  9. BinaryHeap: Binary heap based on array.
  10. SymbolTable: Symbol table based on linked list.
  11. OrderlySymbolTable: Orderly symbol table based on priority queue.
  12. BinarySearchTree: Binary search tree based on pointer.
  13. TwoThreeTree: 2-3-tree based on pointer, waiting for testing.
  14. RBTree: Red-black tree based on pointer.
  15. AVLTree: AVL tree based on pointer.
  16. HashTable: Separate chaining hash table based on array and symbol table.
  17. Graph: Undirected graph based on red black tree(vertex) and symbol table(adjacent vertex set).
  18. Digraph: Directed graph based on red black tree(vertex) and symbol table(adjacent vertex set).
  19. WeightedGraph: Weighted graph based on red black tree(vertex) and symbol table(adjacent vertex set).
  20. WeightedDigraph: Weighted directed graph based on red black tree(vertex) and symbol table(adjacent vertex set).

Ruby

  1. Aplhabet: alphabet based on array.

Algorithm

Cpp

  1. BucketSort: bucket sort, time-O(num_max + num_size), space-O(num_max).
  2. RadixSort: radix sort, time-O(num_msd(num_size)), space-O(num_size * num_radix).
  3. SymbolPairChecker: check the symbol pairs in string, time-online-O(n), space-O(n).
  4. PostfixExpressionManager: evaluate a postfix expression(time-O(n), space-O(1)) or convert an infix expression to postfix expression(time-O(n), space-O(N)).
  5. SelectionSort: selection sort, time-O(n^2), space-O(1).
  6. insertionSort: insertion sort, time-O(n)~O(n^2), space-O(1).
  7. shellSort: shell sort, time-O(n)~O(n^(3/2))(faster than insertion sort), space-O(1).
  8. mergeSort: merge sort, time-O(n * log(n)), space-O(Pn).
  9. quickSort: quick sort, optimized by insertion sort, median3 and 3way, time-O(n * log(n)), space-O(n).
  10. heapSort: heap sort, time-O(n * log(n)), space-O(n).
  11. binarySearch: binary search, time-O(log(n)), space-O(1).
  12. GraphDFS, GraphPathsDFS, GraphPathsBFS: algorithms for searching in graphs.
  13. DigraphDFS, DigraphPathsDFS, DigraphPathsBFS: algorithms for searching in graphs.
  14. DigraphFindCycle: find the cycle in an digraph.
  15. DigraphDFO: depth-first-order algorithm for digraph.
  16. DigraphTopological: topological sorting for an non-cycle digraph.
  17. DigraphSCCKosaraju: find all strongly connected components in a digraph.
  18. UnionFind: a tool class to solve problems about dynamic connectivity.
  19. WeightedGraphMSTPrim: find the Minimum Spanning Tree for a weighted graph with prim algorithm.
  20. WeightedGraphMSTKruskal: find the Minimum Spanning Tree for a weighted graph with kruskal algorithm.
  21. WeightedDigraphSPDijkstra: find the shortest path for a connected weighted digraph which has no negative weight with dijkstra algorithm.
  22. WeightedDigraphSPAcyclic: find the shortest path for a weighted DAG with a simple and fast algorithm.

Ruby

  1. Sorting: sortings for string, includes msd, lsd, q3w.

About

Algorithm and data structures exercises.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 97.5%
  • Ruby 1.8%
  • CMake 0.7%