Questions
2 questions per semester paper
Difficulty
Medium
Importance
High yield for University Semester exams
Overview
Hashing and Divide-and-Conquer are fundamental algorithmic techniques used to optimize searching and problem-solving efficiency. Understanding these is crucial for exams as they form the backbone of data structure performance analysis and recursive algorithm design.
Hash Tables and Collision Resolution
Hashing allows for nearly constant time complexity O(1) for searching, inserting, and deleting data by mapping keys to indices. Collisions occur when multiple keys map to the same hash index, requiring robust resolution strategies to maintain performance.
- Hash Function: h(k) = k mod m
- Chaining: storing elements in a linked list at each bucket
- Open Addressing: Linear Probing, Quadratic Probing, Double Hashing
- Load Factor (alpha) = n/m where n is keys and m is slots
- Primary Clustering issue in linear probing
Divide-and-Conquer Paradigm
The Divide-and-Conquer strategy solves a problem by breaking it into smaller sub-problems of the same type, solving them recursively, and combining the results. This technique is the foundation for efficient sorting and searching algorithms.
- Divide: partition the problem into smaller instances
- Conquer: solve sub-problems recursively
- Combine: merge sub-problem solutions into the final answer
- Classic examples: Merge Sort, Quick Sort, Binary Search
- Strassen's Matrix Multiplication
Master Theorem Basics
The Master Theorem provides a convenient way to determine the Big-O time complexity of divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n). It is the standard tool used in examinations to evaluate the efficiency of recursive functions without manual expansion.
- Form: T(n) = aT(n/b) + O(n^d)
- Case 1: If a > b^d, T(n) = O(n^(logb a))
- Case 2: If a = b^d, T(n) = O(n^d log n)
- Case 3: If a < b^d, T(n) = O(n^d)
- Used for analyzing algorithms like Merge Sort (a=2, b=2, d=1)
Formula Sheet
h(k) = k mod m
alpha = n / m
T(n) = aT(n/b) + f(n)
Exam Tip
When applying the Master Theorem, always verify if the recurrence matches the standard form before choosing the case, as minor deviations make the theorem inapplicable.
Common Mistakes
- Forgetting to check for primary clustering in open addressing during exams.
- Incorrectly identifying the variables 'a', 'b', and 'd' in the Master Theorem recurrence relation.
- Failing to mention the 'Combine' step when describing the Divide-and-Conquer paradigm.
More Revision Notes
Ready to test yourself?
Play topic-wise Hashing & Divide-and-Conquer questions in Aspirant Arcade — gamified MCQ practice.
Download Free