KEMBAR78
DSA Complete Notes | PDF | Queue (Abstract Data Type) | Computer Programming
Scribd
Upload
197 views4 pages

DSA Complete Notes

The document provides a comprehensive overview of Data Structures and Algorithms (DSA), detailing the types of data structures including primitive and non-primitive structures, as well as various algorithms for searching, sorting, and graph traversal. It covers essential concepts such as trees, graphs, and their traversals, along with algorithmic strategies like recursion, dynamic programming, and greedy algorithms. Additionally, it discusses time and space complexity, emphasizing the practical applications of DSA in fields like databases and networking.

Uploaded by

Kartik Srivastava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
197 views4 pages

DSA Complete Notes

The document provides a comprehensive overview of Data Structures and Algorithms (DSA), detailing the types of data structures including primitive and non-primitive structures, as well as various algorithms for searching, sorting, and graph traversal. It covers essential concepts such as trees, graphs, and their traversals, along with algorithmic strategies like recursion, dynamic programming, and greedy algorithms. Additionally, it discusses time and space complexity, emphasizing the practical applications of DSA in fields like databases and networking.

Uploaded by

Kartik Srivastava
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Complete Notes on Data Structures and Algorithms (DSA)

1. Introduction to DSA

- Data Structures: Ways to store and organize data efficiently for access and modification.

- Algorithms: Step-by-step procedures or formulas for solving problems.

2. Types of Data Structures

a) Primitive Data Structures:

- Integer, Float, Character, Boolean.

b) Non-Primitive Data Structures:

1. Linear Data Structures:

- Arrays: Fixed-size sequential collection of elements.

- Linked Lists: Collection of nodes where each node points to the next.

- Types: Singly, Doubly, Circular.

- Stacks: LIFO (Last In First Out) principle.

- Operations: Push, Pop, Peek.

- Queues: FIFO (First In First Out).

- Types: Simple Queue, Circular Queue, Priority Queue, Deque.

2. Non-Linear Data Structures:

- Trees: Hierarchical structure.

- Types: Binary Tree, Binary Search Tree, AVL Tree, Heap, B-Tree.

- Graphs: Set of nodes (vertices) connected by edges.

- Representations: Adjacency Matrix, Adjacency List.


3. Trees (Detailed)

A tree is a non-linear, hierarchical data structure consisting of nodes.

- Terminology:

- Root, Parent, Child, Leaf, Height.

- Types of Trees:

1. Binary Tree: Each node has up to 2 children.

2. Binary Search Tree (BST): Left child < Node < Right child.

3. AVL Tree: Self-balancing BST with balance factor.

4. Heap: Complete binary tree (Max-Heap, Min-Heap).

5. B-Tree: Balanced tree for databases.

6. Trie: Prefix tree for strings.

- Tree Traversals:

- Inorder, Preorder, Postorder, Level Order.

4. Graphs (Detailed)

Graphs are collections of vertices (nodes) and edges (connections).

- Types: Directed, Undirected, Weighted, Unweighted.

- Representation: Adjacency Matrix, Adjacency List.

- Graph Traversals:

1. Breadth First Search (BFS)

2. Depth First Search (DFS)

5. Algorithms (Detailed)
a) Searching Algorithms

1. Linear Search: O(n)

2. Binary Search: O(log n)

b) Sorting Algorithms

1. Bubble Sort: O(n^2)

2. Selection Sort: O(n^2)

3. Insertion Sort: O(n^2)

4. Merge Sort: O(n log n)

5. Quick Sort: O(n log n)

6. Heap Sort: O(n log n)

c) Recursion

- Function calling itself; used in factorial, Fibonacci, tree traversals.

d) Dynamic Programming (DP)

- Solves problems by combining subproblems.

- Example: Fibonacci, 0/1 Knapsack, LCS.

e) Greedy Algorithms

- Locally optimal choices.

- Example: Huffman Coding, Kruskal's, Prim's.

f) Divide and Conquer

- Divide problem, solve recursively.

- Example: Merge Sort, Quick Sort, Binary Search.


g) Backtracking

- Systematic trial and error.

- Example: N-Queens, Sudoku.

h) Shortest Path Algorithms

1. Dijkstra's Algorithm

2. Bellman-Ford Algorithm

3. Floyd-Warshall Algorithm

4. A* Search Algorithm

6. Time and Space Complexity

- Big O Notation: O(1), O(log n), O(n), O(n log n), O(n^2)

7. Applications of DSA in Real World

- Databases, Networking, Compilers, Operating Systems, Cryptography.

You might also like