Data Structures and Algorithms (DSA)

This repository contains implementations and explanations of various data structures and algorithms. The topics covered are fundamental to understanding and mastering DSA for competitive programming, coding interviews, and academic purposes.

Table of Contents

1. Introduction and Analysis of Algorithms
2. Divide & Conquer Algorithms
3. Greedy Algorithms
4. Dynamic Programming
5. Exploring Graphs
6. Backtracking and Branch & Bound
7. String Matching & NP Completeness
8. Data Structures

Introduction and Analysis of Algorithms

• Definition, Properties, Types of Algorithms
• Algorithm Analysis: Parameters, Design Techniques of Algorithms
• Asymptotic Analysis: Big O, Big Omega & Big Theta Notations, Lower Bound, Upper Bound and Tight Bound, Best Case, Worst Case, Average Case
• Analyzing Control Statement: Loop invariant and the correctness of the algorithm
• Recurrences: Substitution method, recursion tree method, master method
• Sorting Techniques with Analysis: Bubble Sort, Selection Sort, Insertion Sort

Divide & Conquer Algorithms

• Structure of Divide-and-Conquer Algorithms
• Examples: Binary Search, Quick Sort, Merge Sort, Strassen Multiplication, Max-Min Problem

Greedy Algorithms

• Introduction, Elements of Greedy Strategy
• Minimum Spanning Tree: Kruskal's & Prim's Algorithm
• Shortest Path: Dijkstra’s Algorithm
• Knapsack Problem, Activity Selection Problem, Huffman Codes

Dynamic Programming

• Principle of Optimality
• Problems: 0/1 Knapsack Problem, Making Change Problem, Chain Matrix Multiplication, Longest Common Subsequence
• All Pair Shortest Paths: Warshall’s and Floyd’s Algorithms

Exploring Graphs

• Introduction to Graphs and Games
• Graph Types: Undirected Graph, Directed Graph
• Graph Traversal: Depth First Search, Breadth First Search
• Topological Sort

Backtracking and Branch & Bound

• Introduction to Backtracking
• Problems: 0/1 Knapsack Problem, N-Queens Problem, Travelling Salesman Problem

String Matching & NP Completeness

String Matching

• Introduction to String Matching
• Algorithms: Rabin-Karp Algorithm, Knuth-Morris-Pratt Algorithm, String Matching using Finite Automata

NP Completeness

• Introduction to NP Completeness
• Problems: P Class Problems, NP Class Problems, Hamiltonian Cycle

Data Structures

Stack

• Introduction to Stack
• Operations: Push, Pop, Peek
• Applications: Expression Evaluation, Backtracking

Queue

• Introduction to Queue
• Operations: Enqueue, Dequeue, Front, Rear
• Types: Circular Queue, Priority Queue
• Applications: Scheduling, Buffer Management

Linked List

• Introduction to Linked List
• Types: Singly Linked List, Doubly Linked List, Circular Linked List
• Operations: Insertion, Deletion, Traversal
• Applications: Dynamic Memory Allocation, Implementation of Stack and Queue

Tree

• Introduction to Trees
• Types: Binary Tree, Binary Search Tree, AVL Tree, B-Tree
• Operations: Insertion, Deletion, Traversal (Inorder, Preorder, Postorder)
• Applications: Hierarchical Data Representation, Database Indexing

Graph

• Introduction to Graphs
• Representations: Adjacency Matrix, Adjacency List
• Graph Traversal: Depth First Search, Breadth First Search
• Applications: Social Networks, Pathfinding Algorithms

Hash

• Introduction to Hashing
• Hash Functions: Division Method, Multiplication Method
• Collision Resolution Techniques: Chaining, Open Addressing (Linear Probing, Quadratic Probing, Double Hashing)
• Applications: Hash Tables, Caches

Contributing

Contributions are welcome!