DSA Notes

# DSA Notes

## 1. Introduction

- Topics Covered:

- Functions, arrays

- Introduction to pointers, structures, and dynamic allocation

- Linked structures

- Time and space requirements

- Algorithm Analysis:

- Asymptotic notations

- Running time calculations

---

## 2. Stack

- Abstract Data Types (ADTs)

- Implementation:

- Using vectors

- Array-based implementation

- Multiple stacks

- Applications:

- Conversion from infix to postfix

- Evaluation of postfix expressions

- Prefix notation

---

## 3. Queue

- Introduction:

- Linear queue

- Circular queue

- De-queue

- Priority queue

- Implementation:

- Array-based queue implementation

- Applications:

- General list operations

---

## 4. Linked Lists

- Introduction:

- Pointer-based implementation

- Types of Linked Lists:

- Linear linked lists

- Circular linked lists

- Doubly linked lists

- Doubly circular linked lists

- Applications:

- Linked stacks and queues

- Polynomials

- High-precision arithmetic

- Josephus problem

---

## 5. Recursion

- Concepts:

- Recursion algorithms

- Types of recursion

- Removal of recursion

---

## 6. Graphs and Trees

- Trees:

- Tree terminology

- Binary tree representation and traversal

- Threaded binary tree

- Binary search tree concepts and implementation

- Advanced trees: Heap tree, AVL tree, Red-Black tree

---

## 7. Hashing

- Operations:

- Insert, search, delete

- Collision Resolution Techniques

---

## 8. Search Methods

- Techniques:

- Linear search

- Binary search

- Complexities:

- Analysis of searching algorithms

---

## 9. Sorting

- Introduction to Sorting Techniques

- Comparison of Sorting Algorithms

- Complexities of Sorting Algorithms