Data Structures and Algorithms 💻

This is a collection of implementations and interactive visualisers of classic data structures and algorithms in C.

This repository contains the backend code for the web terminal interface here.

Use incognito mode to prevent any chrome extensions from interfering with the formatting and avoid resizing the window.

View my notes here!

Table of Contents

• Interactive Linked List
• Interactive Binary Search Tree
• Interactive AVL Tree
• Interactive Splay Tree
• Interactive Unweighted Graph (Directed and Undirected)
• Interactive Weighted Graph (Directed and Undirected)
• Interactive Hash Table
• Interactive Heap
• Sorting Algorithms Benchmarker

Demo

Watch a video demo here.

Setup Instructions

Simple Setup for COMP2521

When connected to CSE servers, just copy and paste these commands onto the terminal and hit enter after pasting each one:

1. git clone https://github.com/Tymotex/Tactile-DS.git && cd Tactile-DS
2. ./util/scripts/make_recurse.sh .
3. You now have access to all the interactive data structures. The commands to run each of them are:
   • Linked Lists:
     1. cd linked-list/iterative-version or cd linked-list/recursive-version
     2. ./testLinkedList <space separated integers> - initially constructs a linked list from the supplied sequence of integers. Eg. ./testLinkedList 42 10 4 20
   • Binary Search Tree:
     1. cd binary-tree
     2. ./testTree <space separated integers> - initially constructs a tree from the supplied sequence of integers. Eg. ./testTree 6 3 10 1 4 8 12 7 9
   • AVL Tree:
     1. cd avl-tree
     2. ./testTree <space separated integers> - initially constructs an AVLtree from the supplied sequence of integers. Eg. ./testTree 1 2 3 4 5 6 7
   • Splay Tree:
     1. cd splay-tree
     2. ./testTree <space separated integers> - initially constructs a splay tree from the supplied sequence of integers. Eg. ./testTree 5 3 8 7 4
   • Graphs:
     • Unweighted
       • Undirected
         1. cd unweighted-graph
         2. ./testGraph <num vertices>|<input file> - creates an empty graph with the specified number of vertices OR constructs a graph with edges specified in an input file. Eg. ./testGraph 10 or ./testGraph tests/1.in
       • Directed
         1. cd unweighted-digraph
         2. ./testGraph <num vertices>|<input file> - creates an empty graph with the specified number of vertices OR constructs a graph with edges specified in an input file. Eg. ./testGraph 10 or ./testGraph tests/1.in
     • Weighted
       • Undirected
         1. cd weighted-graph
         2. ./testGraph <num vertices>|<input file> - creates an empty graph with the specified number of vertices OR constructs a graph with edges specified in an input file. Eg. ./testGraph 10 or ./testGraph tests/1.in
       • Directed
         1. cd weighted-digraph
         2. ./testGraph <num vertices>|<input file> - creates an empty graph with the specified number of vertices OR constructs a graph with edges specified in an input file. Eg. ./testGraph 10 or ./testGraph tests/1.in
   • Hash Table:
     1. cd hash-table
     2. ./testHash <size> - creates an empty hash table with the specified size (otherwise defaults to 10 slots). Eg. ./testHash 12
   • Heap:
     1. cd heap
     2. ./testHeap <size> - creates an empty hash table with the specified size (otherwise defaults to 10 slots). Eg. ./testHeap 12
   • Sorting Algorithms:
     1. cd sorting-algos
     2. Optional: generate sequences using: ./generate-tests -n <num random files> <list of sizes>. Eg. ./generate-tests -n 5 10 100 1000
     3. ./testSort <filename> - takes in a file containing a sequence of numbers. Eg. ./testSort tests/random100_1 or ./testSort --silent tests/random_100_1

Running for Development

To get Tactile-DS running locally:

1. git clone https://github.com/Tymotex/Tactile-DS.git && cd Tactile-DS - downloads this repository and changes directory to the project root directory
2. Install GoTTy
3. Run bundle install in the root directory to install Ruby dependencies. See the ruby bundler. This project uses Ruby v2.7.0
4. ./util/scripts/make_recurse.sh - recursively runs make on all subdirectories. This automatically compiles all the data structures
5. ruby terminal-menu.rb - starts the selection menu where all the interactive visualisers can be accessed

Web Deployment

Instructions for testing/deploying the web-based version:

1. sh server.sh --start - runs the terminal sharing web service. Access at localhost:8080. Use nohup sh server.sh --start & to start the server as a background process
2. sh server.sh --stop - kills the web terminal server process

Running via Docker (Recommended)

Alternatively, run the following commands to run Tactile-DS in a Docker
container.

git clone https://github.com/Tymotex/Tactile-DS.git
cd Tactile-DS
docker build -t tactile-ds
docker run -p 8080:8080 tactile-ds

Interactive Linked List

An interactive linked list builder written in C. Supports standard operations (iteratively and recursively) such as insertion, deletion, searching, sorting and reversing.

Implementation for each command is viewable in linked-list.c and linked-list.h in the linked-list/iterative-version and linked-list/recursive-version directories. View the source code here.

Example Usage:

Interactive Binary Search Tree

An interactive binary search tree builder written in C. Supports standard operations such as insertion, deletion, rotation, and in-order, pre-order, post-order and level-order printing.

Implementation for each command is viewable in tree.c and tree.h in the binary-tree directory. View the source code here.

Example Usage:

Interactive AVL Tree

An interactive AVL tree builder written in C. Supports AVL insertion, AVL deletion and commands to print the height of each node and the height balance of each node.

Implementation for each command is viewable in tree.c and tree.h in the avl-tree directory. View the source code here.

Example Usage:

Interactive Splay Tree

An interactive splay tree builder written in C. Splay trees differ from regular BSTs in that searching and inserting a value involves bringing the target/inserted node to the root.

Implementation for each command is viewable in tree.c and tree.h in the splay-tree directory. View the source code here.

Example Usage:

Interactive Unweighted Graphs

Interactive unweighted directed/undirected graph builder written in C.

Implementation for each command is viewable in graph.c, graph.h, graph-algos.c and graph-algos.h in the unweighted-graph and unweighted-digraph directories.

• View source code for unweighted graphs algorithms here and basic functions here
• View source code for unweighted digraphs algorithms here and basic functions here

Example Usage:

Digraph:

Undirected Graph:

Interactive Weighted Graphs

Interactive weighted directed/undirected graph builder written in C. Implements Dijkstra’s algorithm for determining a single source spanning tree.

Implementation for each command is viewable in graph.c, graph.h, graph-algos.c, graph-algos.h, dijkstra.c and dijkstra.h in the weighted-graph and weighted-digraph directories.

• View source code for weighted graphs algorithms here, basic functions here and Dijkstra’s algorithm here
• View source code for weighted digraphs algorithms here, basic functions here and Dijkstra’s algorithm here

Example Usage:

Digraph:

Undirected Graph:

Interactive Hash Table (Lookup Table)

Interactive hash table written in C for storing key-value pairs.

Implementation for each command is viewable in hash-table.c and hash-table.h in the hash-table directory. View source code here.

Example Usage:

Interactive Heap

Interactive max heap table written in C.

Implementation for each command is viewable in heap.c and heap.h in the heap directory. View source code here.

Example Usage:

Interactive Sorting Algorithms

A collection of classic sort algorithms written in C. Timing data is shown for each sort algorithm used.

Implementation for each command is viewable in sort.c and sort.h in the sorting-algos directory. View source code here.

Example Usage: