iruka

A collection of classical data structures and algorithms implemented in Typescript. Click the 📹 emoji for tutorials.

The repository's primary goal is educational. Hence, all implementations include a prolific number of comments which guide the reader. The name of the project, iruka, is an ode to Iruka sensei from Naruto. He became a teacher to pass on the Will of Fire, and teach the future ninja of the leaf village. Likewise, this project is here to teach the future software engineers of earth.

You can use this package in your projects if you so wish. Test coverage will be kept at 100%. To install the package, use npm or yarn:

yarn add dsa-ts

Data Structures

• [x] Sequences
  • [x] 📹 Linked List
  • [x] 📹 Stack
  • [x] 📹 Queue
  • [x] Double-ended Queue
  • [x] 📹 Circular Buffer
• [x] Priority Queues
  • [x] 📹 Binary Heap
  • [x] D-Heap
  • [x] 📹 Indexed Binary Heap
  • [x] Mergeable Heaps
    • [x] 📹 Binomial Heap
    • [x] 📹 Lazy Binomial Heap
    • [x] 📹 Fibonnaci Heap
• [x] Search Trees
  • [x] 📹 Binary Search Tree
  • [x] 📹 AVL Tree
  • [x] Red-black Tree
  • [x] B-Tree
• [x] Hash Tables
  • [x] 📹 Hash Table (Separate Chaining)
  • [x] Hash Table (Open Addressing)
    • [x] Hash Table (Linear Probing)
    • [x] Hash Table (Quadratic Probing)
    • [x] Hash Table (Double Hashing)

Algorithms

• [x] Search
  • [x] Binary Search
  • [x] Breadth-first Search
  • [x] Depth-first Search
• [x] Sorting
  • [x] Merge Sort
  • [x] Quick Sort
  • [x] Heap Sort
  • [x] Topological Sort (DFS)
  • [x] Topological Sort (Kahns)
  • [x] Counting Sort
  • [ ] Bucket Sort
• [] Graph Theory
  • [] Graphs
    • [x] Shortest Paths
      • [x] Dijkstra's SSSP
      • [x] Bellman-Ford SSSP
      • [x] Floyd-Warshall APSP
    • [ ] Minimum Spanning Tree
  • [ ] Network Flow

References

• Fundamental Data Structures
• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Algorithm Design by Jon Kleinberg and Éva Tardos
• Algorithms by William Fiset
• Algorithms by Jeff Erickson
• Stanford CS 166
• Harvard CS 224

Contributing

When contributing to this repository, please first discuss the change you wish to make via issue, email, or any other method with the owners of this repository before making a change.

Commiting Process

The commit process does not directly use git. dsa-ts uses commitizen to ensure we are comitting semantic commits. To commit, use the command yarn commit, and follow the citizen cli which prompts you for various metainfo regarding the commit. After the pre-commit tests are run successfully, you are able to push to your development branch with git push.

License

This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects