Covers: Lec1-Lec8
Topics/Problems:
Line-by-line approximate time complexity of loops and algorithms
Z-algorithms and time analysis
- Computing Z-values out of Z-box
- Computing Z-values outside of Z-box (using pre-computed Z-values)
- Understanding the notion of Z-box
- Understanding the notion of Z-value
- Understanding the notion of Z-array
- Application of Z-algorithm
- Time complexity of precomputing the Z-array (using the advanced strategy vs only the naive strategy)
- Time complexity of matching and finding the pattern P in T
- Goal of Z-algorithm
Naive String Matching Algorithm
Naive and Enhanced Rabin-Karp
- How is Enhanced better than Naive
Integer Multiplication Algorithm (Decimal and Binary)
- Calculating Big-O Time Complexity
- How the Algorithm Works
Masters Theorem
- Generic Master’s Theorem
Methods of Solving a Recurrence Relation
- Recurrence Tree
- Expansion
Order of Growth
- Understand the order of growth time bounds: slowest to fastest runtime