S3 DS LAB

To run locally, fork this repository and clone it.
To compile and run a C program in terminal, use the following commands

gcc program_name.c -o program_name
program_name

Table of contents

1) Application of Arrays

2) Linked Lists

3) Stacks and Queues

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

• Reverse a linked list
• Merge two sorted linked lists
• Swap any two nodes
• Print middle node
• Swap head and tail
• Count even and odd nodes
• Concatenate two linked lists
• Swap first half with second half
• Find predecessor and successor nodes

Medium

• Insert into sorted linked list
• Sort a linked list
• Remove duplicates from linked list
• Remove all occurences of a given element
• Copy common elements into third linked list

Advanced

• Detect cycle in a linked list
• Rotate linked list by k places

3) Stacks and Queues

Basics

• Implement stack using array
• Implement stack using linked list
• Implement queue using array
• Implement queue using linked list
• Implement circular queue
• Implement Deque

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

Medium

• Implement queue using two stacks
• Implement stack using two queues
• Implement priority queue

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

6) Trees

Basics

• Linked and Sequential representation of binary trees
• Preorder, Inorder, Postorder traversal (Recursive and Iterative)
• Level order Traversal
• Find height, number of nodes and number of vertices
• Implement Binary Search Tree (BST)
• Insertion, Deletion, Searching in BST

Easy

• Create linked representation of binary tree from sequential and vice versa
• Find minimum and maximum in a BST
• Count leaf nodes

Medium

• Find sum of each level in a tree

7) Graphs

Basics

• Adjacency Matrix representation
• Adjacency List representation
• Depth First Search and Traversal (Recursive and Iterative)
• Breadth First Search and Traversal