1. Introduction to Data Structures and Algorithms
- Data Structure: A systematic way to organize and manage data so it can be used efficiently.
- Example: Arrays, Linked Lists, Trees, and Graphs.
- Example: Arrays, Linked Lists, Trees, and Graphs.
- Algorithm: A finite sequence of well-defined instructions to solve a problem or perform a task.
- Example: An algorithm to sort a list of student grades.
- Example: An algorithm to sort a list of student grades.
Importance:
- Enhances efficiency in processing large datasets.
- Reduces time complexity and space usage.
- Crucial for real-time systems, gaming engines, operating systems, etc.
2. Types of Data Structures
a. Linear Data Structures
- Arrays
- Contiguous memory allocation; indexed collection of elements.
- Example: int marks[5] = {75, 85, 90, 80, 70};
- Operations: Traverse all elements, search for a value, insert/delete (costly in middle).
- Contiguous memory allocation; indexed collection of elements.
- Linked Lists
- Nodes linked using pointers.
- Types:
- Singly Linked List: One-way pointer.
- Doubly Linked List: Two-way pointers.
- Circular Linked List: Last node links to the first node.
- Singly Linked List: One-way pointer.
- Example: Navigating a music playlist.
- Advantage: Dynamic memory usage, efficient insertion/deletion.
- Disadvantage: Sequential access only.
- Nodes linked using pointers.
- Stacks (LIFO – Last In, First Out)
- Operations: Push, Pop, Peek.
- Example: Undo functionality in word processors.
- Implemented using arrays or linked lists.
- Operations: Push, Pop, Peek.
- Queues (FIFO – First In, First Out)
- Types: Simple, Circular Queue, Priority Queue, Deque (Double-ended Queue).
- Operations: Enqueue, Dequeue.
- Example: CPU job scheduling.
- Types: Simple, Circular Queue, Priority Queue, Deque (Double-ended Queue).
b. Non-Linear Data Structures
- Trees
- Hierarchical structure with root, nodes, and leaves.
- Binary Tree: Each node has max 2 children.
- Binary Search Tree (BST): Left < Root < Right.
- AVL Tree: Self-balancing BST.
- B-Tree: Used in databases.
- Operations:
- Traversal:
- Inorder (Left, Root, Right)
- Preorder (Root, Left, Right)
- Postorder (Left, Right, Root)
- Inorder (Left, Root, Right)
- Traversal:
- Example: File systems, Expression trees.
- Hierarchical structure with root, nodes, and leaves.
- Graphs
- Vertices (nodes) and Edges (connections).
- Types:
- Directed/Undirected
- Weighted/Unweighted
- Directed/Undirected
- Representations:
- Adjacency Matrix
- Adjacency List
- Adjacency Matrix
- Traversals:
- BFS (Breadth-First Search)
- DFS (Depth-First Search)
- BFS (Breadth-First Search)
- Example: Social media connections, Road networks.
- Vertices (nodes) and Edges (connections).
c. Hashing
- Hash Table: Maps keys to values using a hash function.
- Example: Username lookup in login systems.
- Collision Resolution:
- Chaining: Linked lists at each index.
- Open Addressing: Linear/Quadratic probing.
- Chaining: Linked lists at each index.
3. Algorithms
a. Searching Algorithms
- Linear Search: O(n) – Check each element.
- Example: Searching a name in a contact list.
- Example: Searching a name in a contact list.
- Binary Search: O(log n) – Efficient on sorted data.
- Example: Dictionary word lookup.
- Example: Dictionary word lookup.
b. Sorting Algorithms
| Algorithm | Best | Worst | Stable | Use Case |
| Bubble Sort | O(n) | O(n²) | Yes | Simple, small datasets |
| Selection Sort | O(n²) | O(n²) | No | Memory efficiency |
| Insertion Sort | O(n) | O(n²) | Yes | Nearly sorted data |
| Merge Sort | O(n log n) | O(n log n) | Yes | Large datasets |
| Quick Sort | O(n log n) | O(n²) | No | General-purpose |
| Heap Sort | O(n log n) | O(n log n) | No | Priority queue implementation |
c. Recursion
- A function calling itself to solve subproblems.
- Example: Factorial, Fibonacci, Tree traversal.
- Base case + Recursive case = Correct recursion.
d. Dynamic Programming
- Solves overlapping subproblems using memoization.
- Examples:
- Fibonacci Series
- Knapsack Problem
- Longest Common Subsequence (LCS)
- Fibonacci Series
e. Greedy Algorithms
- Chooses the best solution at each step.
- Examples:
- Huffman Coding
- Minimum Spanning Tree (Prim’s, Kruskal’s)
- Fractional Knapsack
- Huffman Coding
f. Backtracking
- Tries all possibilities and backtracks on failure.
- Examples:
- N-Queens Problem
- Maze solving
- Sudoku Solver
- N-Queens Problem
4. Complexity Analysis
- Big O: Worst-case (O(n))
- Omega (Ω): Best-case
- Theta (θ): Average-case
| Complexity | Description | Example |
| O(1) | Constant | Accessing an array element |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Bubble sort |
| O(2ⁿ) | Exponential | Recursive Fibonacci |
5. Applications
- Web Crawling: BFS/DFS in graphs.
- Expression Parsing: Stack for infix to postfix conversion.
- Memory Management: Linked lists for dynamic memory allocation.
- Routing Algorithms: Dijkstra’s, Bellman-Ford using graphs.
- Scheduling in OS: Priority Queues using Heaps.
Games and AI: Trees for game moves, backtracking in puzzle games.
