Data Structures and Algorithms
Based on CS-201, Data Structures, KTU curriculum.
To run locally, fork this repository and clone it.
Table of contents
1) Application of Arrays
2) Linked Lists
3) Stacks, Queues and Heaps
4) Hashing Algorithms
5) Sorting Algorithms
6) Trees
7) Graphs
1) Application of Arrays
Basics
- Sparse matrix Addition
- Sparse matrix multilplication
- Polynomial addition
- Polynomial multiplication
2) Linked Lists
Basics
- Insert element at head
- Insert element at the tail
- Insert element at any position
- Count number of nodes
- Search for an element
- Delete first element
- Delete last element
- Delete an element at a given position
- Implement Circular linked list
- Implement Doubly linked list
Easy
- Find minimum and maximum value
- Reverse a linked list
- Swap any two adjacent nodes
- Print middle node
- Swap head and tail
- Count number of nodes in circular linked lists
- Count even and odd nodes
- Concatenate two linked lists
- Swap first half with second half
- Find predecessor and successor nodes
- Check if linked list is circular
- Check if length is odd or even
- Delete alternate Nodes
Medium
- Insert into sorted linked list
- Sort a linked list - MergeSort, BubbleSort, SelectionSort, InsertionSort
- Remove duplicates from linked list
- Remove all occurences of a given element
- Copy common elements into third linked list
- Split into 3 linked list based on value
- Split into odd and even linked list
- Check if a linked list forms a palindrome
- Find distance between two given nodes in a circular linked list
- Find union of 2 linked lists
Hard
- Reverse only second half of linked list
- Merge two sorted linked lists in-place
- Rotate a linked list by k places
Miscellaneous
3) Stacks, Queues and Heaps
Basics
- Implement stack using array
- Implement stack using linked list
- Implement queue using array
- Implement queue using linked list
- Implement circular queue
- Implement Deque
- Build max Heap from array (naive method)
- Build min Heap from array (naive method)
- Build max Heap from array using Heapify
- Build min Heap from array using Heapify
Easy
- Reverse a number using stack
- Check for palindrome using stack
- Check for valid parentheses
- Convert infix expression to postfix
- Evaluate postfix expression
- Evaluate prefix expression
- Reverse elements a queue using stack
Medium
- Implement queue using two stacks
- Implement stack using two queues
- Implement priority queue - Using Array 1, Using Array 2 , Using LinkedList 1, Using LinkedList 2, Using Heap(simple), Using Heap(advanced)
4) Hashing Algorithms
Basics
- Insert set of keys into a hash table of given size using division method and linear probing.
- Store each words of a natural language text in a hash table of given size using the mod function and perform search.
5) Sorting Algorithms
Basics
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
Miscellaneous
- Randomized quick sort
- Counting sort
6) Trees
Basics
- Linked representation and Sequential representation of binary trees
- Preorder Traversal (Recursive and Iterative)
- Inorder Traversal (Recursive and Iterative)
- Postorder traversal (Recursive and Iterative)
- Level order Traversal
- Find height, number of nodes and number of vertices
- Implement Binary Search Tree (BST) and perform insertion, searching and deletion
Easy
- Create linked representation of binary tree from sequential and vice versa
- Check if two trees are same
- Check if linked and sequential represented binary trees are same
- Find minimum and maximum in a BST
- Count and delete leaf nodes
- Find sum of leaf nodes
- Count degree of nodes
- print all elements in a given range in a BST
Medium
- Print nodes at a given level
- Find all ancestors of a given node
- Find the sibling of a given node
- Check if a binary tree is a binary search tree
- Print nodes at each level and find their sum
- Find and remove maximum element in a BST
- Find and remove minimum element in a BST
- Check if there is a path sum
- Check if tree is Symmetric
- Find second largest element in a BST without using inorder array
- Find sum of all left leaves and right leaves
- Find kth smallest element in a BST
Hard
- Delete all nodes in a given range
- Merge 2 binary trees
- Create binary tree when Preorder & Inorder given
- Create binary tree when Postorder & Inorder given
Miscellaneous
- Invert a binary tree
- DFS Spanning tree
- BFS Spanning tree
- Minimum cost spanning tree (using Kruskal's Algorithm)
7) Graphs
Basics
- Adjacency Matrix representation
- Adjacency List representation
- Depth First Search and Traversal - Recursive and Iterative
- Breadth First Search and Traversal