Programs which create and manipulate different data structures and algorithms.
Here, in this project, we try to write codes for all types of data structures as well as algorithms in Python. Below is the list of data structures we have written code for till now:
- Matrix Multiplication
Problem Description:
Given 2 user input matrix, figure out the matrix multiplication of the matrices (if possible) and return the resultant matrix.
Input:
A -> a (m * n) matrix
B -> a (p * q) matrix
Output:
C -> a (m * q) matrix if n = p, otherwise, Not Divisible!
Linked List
- Create a linked list.
- Display a linked list.
- Insert at the beginning of the linked list.
- Insert at the end of the linked list.
- Insert element after a particular value in the linked list.
- Insert element before a particular value in the linked list.
- Insert element at the k-th position in the linked list.
- Delete from the beginning of the linked list.
- Delete from the end of the linked list.
- Delete user inputted elements from the linked list.
- Delete after a particular value from the linked list.
- Delete before a particular value from the linked list.
- Delete at the k-th position from the linked list.
- Delete the entire list.
- Sort the entire list.
- Reverse a list.
- Count the number of nodes in a list.
- Search for a number in the list.
- Find the root n-th node in the list (in one scan).
- Detect and remove a loop from the linked list.
Stack
- Create a stack - Display a stack - Push an element in stack - Pop an element in stack - Infix to Postfix conversion - Infix to Prefix conversion - Prefix to Infix - Prefix to Postfix - Postfix to Prefix - Postfix to Infix - Tower of Hanoi using Stack (no recursion) - Reverse a stack using recursion - Sort a stack using recursion - Sort a stack using a temporary stack - Reverse a stack without using extra space in O(n) - Delete middle element of a stack - Sorting array using Stacks - Check if a queue can be sorted into another queue using a stack - Check if an array is stack sortable - Implement Queue using Stacks
Queue
- Create a queue - Display a queue - Enqueue - Dequeue - LRU Cache Implementation - Implement Stack using Queues - Efficiently implement k Queues in a single array - Deque using Circular array - Implement Stack and Queue using Deque - Priority Queue using Doubly Linked List - Reversing a Queue - Sort a Queue
Tree
Binary Search Tree (Using Recursion)- Insert a value in Binary Search Tree - Preorder tree traversal - Postorder tree traversal - Inorder tree traversal - Searching in a Binary Search Tree - Getting minimum and maxmimum value in Binary Search TreeAVL tree
- Insert an element in an AVL Tree - Preorder traversal - Inorder traversal - Deletion of value from AVL TreeThreaded Binary Search Tree
- Insertion in Threaded Binary Tree
Graph
- Representation of DFS graph - Representation of BFS graph
M-way Search Tree
- Searching - Insertion - Deletion
B Tree
- Insertion - Deletion
Graph
- Detect cycle in a Directed graph - Detect cycle in a Undirected graph - Longest Path in a Directed Acyclic Graph - Topological Sorting - Check whether a given graph is Bipartite or not - Snake and Ladder Problem
List
- Memory Efficient DLL - XOR Linked List - Self-Organizing List - Unrolled Linked ListSkip List
- Insertion - Searching - Deletion
Segment Tree
- Sum of given range - Range Minimum Query - Lazy Propagation - Persistent Segment Tree
Trie
- Insert - Search - Delete - Longest Prefix Matching - Implement Reverse DNS Look Up Cache - Implement Forward DNS Look Up Cache
Binary Indexed Tree or Fenwick Tree
- Representation of Binary Indexed Tree - Two Dimensional Binary Indexed Tree or Fenwick Tree - Range Updates and Point Queries - Range Updates and Range Queries
Suffix Array and Suffix Tree
- Create a Suffix Array - Create a Suffix Array in O(nLogn) - kasai’s Algorithm for Construction of LCP array from Suffix Array - Pattern Searching using Suffix Tree (Introduction of Suffix Tree) - Ukkonen’s Suffix Tree Construction - Generalized Suffix Tree - Suffix Tree Application
Splay Tree
- Insert - Search
Red Black Tree
- Insertion - Deletion
K Dimensional Tree
- Search & Insertion - Find the minimum value - Deletion
Misc
- Treap (A Randomized Binary Search Tree) - Ternary Search Tree - Interval Tree - Implement LRU Cache - Sort numbers stored on different machines - Find the k most frequent words from a file - Given a sequence of words, print all anagrams together - Tournament Tree (Winner Tree) and Binary Heap - Decision Trees – Fake (Counterfeit) Coin Puzzle (12 Coin Puzzle) - Spaghetti Stack - Data Structure for Dictionary and Spell Checker? - Cartesian Tree - Cartesian Tree Sorting - Sparse Set - Centroid Decomposition of Tree - Gomory-Hu Tree
- Linear Probing
- Quadratic Probing
- Heapification
- Linear Search (Sequential Search)
- Binary Search
- Interpolation Search
- Jump Search
- Exponential Search
- Ternary Search
- Bubble Sort (Optimized version)
- Insertion Sort
- Selection Sort
- Merge Sort
- Quick Sort
- Counting Sort
- Heap Sort
- Radix Sort
- Bucket Sort
- ShellSort
- Comb Sort
- Pigeonhole Sort
- Cycle Sort
- Fractional Knapsack
- Huffman Code
- Kruskal’s Minimum Spanning Tree Algorithm
- Activity Selection Problem
- Efficient Huffman Coding for Sorted Input
- Prim’s Minimum Spanning Tree Algorithm
- Prim’s MST for Adjacency List Representation
- Dijkstra’s Shortest Path Algorithm
- Dijkstra’s Algorithm for Adjacency List Representation
- Job Sequencing Problem
- Quiz on Greedy Algorithms
- Greedy Algorithm to find Minimum number of Coins
- K Centers Problem
- Minimum Number of Platforms Required for a Railway/Bus Station
- Multistage Graph Problem
- All pairs Shortest Path (Floyd-Warshall)
- Matrix Chain Multiplication
- Optimal Binary Search Tree
- Amortized Analysis
- Potential Method
- Topological Sort
- Strongly Connected Components (SCC)
- Dijkstra's Algorithm
- Bellman-Ford Algorithm