data-structures-and-algorithms

This repository contains implementation of some of the fundamental data structures and algorithms in Computer Science. It is primarily used as a teaching resource and is currently being developed by ex-2040s students.

Also, the structure of the codebase is optimised for IntelliJ IDEA since implementation are mostly written in Java.

Note: This is still being developed! Those below with links mean that they are complete (alongside testing). We project to complete CS2040s course content by November and along the way, add interesting algorithms/problems. If you wish to contribute, do drop me an email at [email protected].

Full List of Implementation (in alphabetical order):

Structures

• Adelson-Velskii and Landis (AVL) Binary Search Tree
• Disjoint Set
  • Quick Find
  • Weighted Union with path compression
• Heap
  • Max heap implementation
• Linked List
• LRU Cache
• Minimum Spanning Tree
• Queue
• Segment Tree
  • Array implementation
  • TreeNode implementation
• Stack
• Trie

Algorithms

• Counting Sort
• Cyclic Sort
  • Special case of O(n) time complexity
  • Generalized case of O(n^2) time complexity
• Knuth-Morris-Pratt aka KMP algorithm
• Matrix Operations
• Bubble Sort
• Insertion Sort
• Selection Sort
• Merge Sort
  • Recursive
  • Bottom-up iterative
• Quick Sort
  • 3-way Partitioning
• Radix Sort

Short-cut to CS2040S Material

1. Basic structures
   • Linked List
   • Stack
   • Queue
2. Binary Search
   • Peak Finding
3. Sorting
   • Bubble
   • Insertion
   • Selection
   • Merge
   • Quick
4. Trees
   • Binary search tree
   • AVL-tree
   • Kd-tree
   • Interval tree
   • Augmented tree for orthogonal range searching
5. Heap
6. Disjoint Set / Union Find
7. Hashing
   • Bloom filter
8. Basic graphs
   • Depth-first search
   • Breadth-first search
9. Graphs
   • Bellman-ford
   • Dijkstra
   • Directed acyclic graphs
10. Minimum spanning tree
    • Prim's
    • Kruskal's

Contributors

Andre

Kai Ting

Owen

Chang Xian

Yeo Shu Heng