Data Structures & Algorithms

This repository contains implementation and discussion notes (intuition, applications, analysis) of some fundamental data structures and algorithms in Computer Science.
It is aligned with CS2040s syllabus taught by Prof Seth at NUS.

The work here is continually being developed by CS2040s Teaching Assistants(TAs) and ex-2040s students, under the guidance of Prof Seth. It is still in its infant stage, mostly covering lecture content and discussion notes. Future plans include deeper discussion into the tougher parts of tutorials and even practice problems / puzzles related to DSA.

The project's structure is optimised for IntelliJ IDEA as per the course's preferred IDE. Gradle is used for development.

Full List (in alphabetical order):

Data Structures

• Adelson-Velskii and Landis (AVL) Binary Search Tree
• Disjoint Set / Union Find
  • Quick Find
  • Weighted Union
    • Path compression
• Hashing
  • Chaining
  • Open Addressing
• Heap
  • Max heap implementation
• Linked List
• LRU Cache
• Minimum Spanning Tree
  • Kruskal
  • Prim's
  • Boruvska
• Queue
  • Deque
  • Monotonic Queue
• Segment Tree
• Stack
• Trie

Algorithms

• Bubble Sort
• Binary Search
  • Template
• Counting Sort
• Cyclic Sort
  • Special case of O(n) time complexity
  • Generalized case of O(n^2) time complexity
• Insertion Sort
• Knuth-Morris-Pratt aka KMP algorithm
• Merge Sort
  • Recursive
  • Bottom-up iterative
• Quick Sort
  • Hoare's
  • Lomuto's
  • Paranoid
  • 3-way Partitioning
• Radix Sort
• Selection Sort

CS2040S Syllabus (in rough order)

1. Basic structures
   • Linked List
   • Stack
   • Queue
2. Binary Search
   • Peak Finding
   • Template
3. Sorting
   • Bubble
   • Insertion
   • Selection
   • Merge
   • Quick
     • Hoare's
     • Lomuto's (Not discussed in CS2040s)
     • Paranoid
     • 3-way Partitioning
   • Counting Sort (found in tutorial)
   • Radix Sort (found in tutorial)
4. Trees
   • Binary search tree
   • AVL-tree
   • Trie
   • B-Tree
   • Red-Black Tree (Not covered in CS2040s but useful!)
   • Orthogonal Range Searching (WIP)
   • Interval Trees (WIP)
5. Binary Heap (Max heap)
6. Disjoint Set / Union Find
   • Quick Find
   • Weighted Union (with path compression)
7. Hashing
   • Chaining
   • Open Addressing
   • Bloom filter (WIP)
8. Basic graphs (WIP)
   • Depth-first search
   • Breadth-first search
9. Graphs (WIP)
   • Bellman-ford
   • Dijkstra
   • Directed acyclic graphs algorithms
     • Post-order DFS
     • Kahn's
   • Floyd Warshall
10. Minimum spanning tree (WIP)
    • Prim's
    • Kruskal's

Set-up

If you are a CS2040s student, your IDEA configurations should already be compatible with this project structure. So, feel free to clone and use it as you see fit. Note, below configuration is as per CS2040s PS1 set-up guide.

1. Choose Java Version 11.0.XX for Project SDK. You can download it here
   • Create account and login if necessary
   • Make sure to download the correct one compatible with your hardware
2. Download IntelliJ (Community Edition) here if you do not have it.
3. Fork the repo and clone it on your local device
4. Launch IntelliJ on your device and under the Projects tab, and click open. Navigate to where the local repo is cloned
   1. Configure to Java SDK (if not done) by first heading to File on the top-left panel,
   2. Click on Project Structure...
   3. Apply the desired Java SDK in the SDK: dropdown. Remember to click Apply.
5. You can test if everything is properly set-up with the command:
   ./gradlew clean test
   All files should be compiled and all testcases should pass.

Usage

The resources here can be directly viewed from GitHub interface, but it is advisable for you to fork and clone it to your local desktop, especially if you wish to tweak or play with custom inputs. There is a folder where you can import and run the algorithms/structures here for your own input. See here.

Disclaimer

While our team of TAs and students have diligently verified the correctness of our code, there might still be some discrepancies or deviation from lecture content (perhaps due to new changes). In which case, you are strongly advised to raise it up to us or consult your TA regarding any suspicions on the use of the information shared here.

Contributors

See the team!