Questions and Answers
What is the time complexity of mergesort?
$\Theta(n \log n)$
In the general Divide-and-Conquer recurrence $T(n) = aT(n/b) + f(n)$, what does the Master Theorem state when $a > bd$?
$T(n) \in \Theta(n^{\log_b a})$
What is the time complexity of matrix multiplication using Strassen’s algorithm?
$\Theta(n^{\log_2 7})$
If $T(n) = 4T(n/2) + n^2$, what is the time complexity according to the Master Theorem?
Signup and view all the answers
What is the primary advantage of using Strassen’s algorithm for matrix multiplication?
Signup and view all the answers
Study Notes
Divide and Conquer Strategy
- A well-known algorithm design strategy that involves dividing an instance of a problem into two or more smaller instances
- Divide the problem into smaller instances
- Solve the smaller instances recursively
Examples of Decrease by a Constant
- Insertion sort
- Topological sorting
Examples of Decrease by a Constant Factor
- Binary search
- Bisection method
- Exponentiation by squaring
- Multiplication
Examples of Variable-Size Decrease
- Euclid’s algorithm
- Selection by partition
Lecture Topics
Sorting Algorithms
- Mergesort
- Quicksort
Binary Tree Traversals
- Applications and uses of binary tree traversals
Binary Search
- Applications and uses of binary search
Multiplication of Large Integers
- Importance and applications of multiplying large integers
Matrix Multiplication
- Strassen’s algorithm for efficient matrix multiplication
Computational Geometry
- Closest-pair algorithm
- Convex-hull algorithms
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
