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

• Detect cycle in a linked list

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