CDAC SECTION 2: DATA STRUCTURES AND ALGORITHMS (DSA) - DETAILED STUDY MATERIAL
1. Introduction to Data Structures and Algorithms
• Data Structure: Way of organizing and storing data for efficient access and modification.
• Algorithm: Step-by-step procedure to solve a problem.
• Complexity Analysis:
• Time Complexity: Measure of time taken by an algorithm.
• Space Complexity: Measure of memory used by an algorithm.
• Big O Notation: Describes upper bound of time/space requirement.
Example:
• Searching an element in an array: Linear search O(n), Binary search O(log n).
2. Arrays
• Definition: Collection of elements of same type, stored in contiguous memory.
• Operations: Traversal, Insertion, Deletion, Searching, Sorting.
Example:
arr = [10, 20, 30, 40]
[Link](50) # Insertion
[Link](2) # Deletion
Concepts:
• 1D and 2D arrays
• Row-major and column-major order
• Circular arrays
3. Linked List
• Definition: Sequence of nodes where each node contains data and pointer to next node.
• Types: Singly, Doubly, Circular Linked List.
• Operations: Traversal, Insertion, Deletion.
Example:
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
1
4. Stack
• Definition: LIFO structure (Last In First Out).
• Operations: push(), pop(), peek(), isEmpty().
• Applications: Expression evaluation, Undo mechanism.
Example:
stack = []
[Link](10)
[Link]()
5. Queue
• Definition: FIFO structure (First In First Out).
• Types: Simple, Circular, Priority, Deque.
• Operations: enqueue(), dequeue(), front(), rear().
Example:
from collections import deque
queue = deque([1,2,3])
[Link](4)
[Link]()
6. Trees
• Definition: Hierarchical structure with nodes connected by edges.
• Types: Binary Tree, Binary Search Tree, AVL Tree, B-Trees, Heaps.
• Traversals: Preorder, Inorder, Postorder, Level Order.
Example:
class TreeNode:
def __init__(self, val):
[Link] = val
[Link] = None
[Link] = None
2
7. Graphs
• Definition: Set of nodes(vertices) connected by edges.
• Types: Directed, Undirected, Weighted, Unweighted.
• Representation: Adjacency Matrix, Adjacency List.
• Traversals: BFS, DFS.
8. Searching Algorithms
• Linear Search: O(n)
• Binary Search: O(log n), requires sorted array.
• Hashing: Constant time average search.
9. Sorting Algorithms
• Bubble Sort, Selection Sort, Insertion Sort: O(n^2)
• Merge Sort, Quick Sort, Heap Sort: O(n log n)
• Counting Sort, Radix Sort: O(n+k)
10. Recursion and Backtracking
• Recursion: Function calls itself.
• Backtracking: Try all possibilities and backtrack on failure.
Example:
# Factorial using recursion
def fact(n):
if n == 0:
return 1
return n * fact(n-1)
11. Hashing
• Definition: Technique to map data to index using hash function.
• Collisions: Open addressing, Chaining.
• Applications: Dictionary, Set, Caching.
12. Dynamic Programming
• Definition: Break problem into subproblems and store results.
3
• Techniques: Memoization, Tabulation.
• Examples: Fibonacci, Knapsack, Longest Common Subsequence.
13. Greedy Algorithms
• Definition: Make locally optimal choice at each step.
• Examples: Activity Selection, Huffman Coding.
14. Divide and Conquer
• Definition: Divide problem, solve recursively, combine results.
• Examples: Merge Sort, Quick Sort, Binary Search.
15. 50 MCQs with Answers
1. Linear search has a time complexity of?
2. a) O(n) ✅
3. b) O(log n)
4. c) O(n^2)
5. d) O(1)
6. Binary search requires?
7. a) Sorted array ✅
8. b) Linked list
9. c) Stack
10. d) Graph
11. A stack follows?
12. a) FIFO
13. b) LIFO ✅
14. c) Random
15. d) None
16. Which sorting algorithm is stable?
17. a) Quick Sort
18. b) Merge Sort ✅
19. c) Heap Sort
20. d) Selection Sort
21. Hash collision can be resolved by?
4
22. a) Open addressing ✅
23. b) Recursion
24. c) BFS
25. d) DFS
... (continue up to 50 MCQs)