Skip to content

Latest commit

 

History

History
137 lines (104 loc) · 2.9 KB

README.md

File metadata and controls

137 lines (104 loc) · 2.9 KB

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