Algorithmic Strategies - Study Notes
Chapter Summary
This chapter explores the fundamental concepts of algorithmic strategies. It details how step-by-step procedures can be analyzed for efficiency based on time and space complexities. Various essential searching techniques, sorting techniques, and design paradigms such as dynamic programming are comprehensively discussed to provide a complete computational perspective.
Learning Objectives
- Understand the foundational and technical perspectives of algorithms.
- Analyze the efficiency, time complexity, and space complexity of computational procedures.
- Develop and trace searching algorithms like Linear Search and Binary Search.
- Master sorting strategies such as Bubble Sort, Selection Sort, and Insertion Sort.
- Grasp the concepts of dynamic programming and optimization through memoization.
Key Concepts and Definitions
Algorithm
An algorithm is a finite set of instructions designed to accomplish a specific task. It is a step-by-step procedure that operates independently of any programming language.
Space-Time Tradeoff
A computational design methodology where memory consumption is reduced at the cost of execution speed, or conversely, execution speed is increased at the cost of using more memory space.
Asymptotic Notations
Meaningful mathematical statements used to describe the limiting behavior of an algorithm's time or space complexity. The primary notations are Big O (worst-case upper bound), Big Omega (best-case lower bound), and Big Theta (average tight bound).
Memoization
An optimization technique used in dynamic programming that speeds up programs by storing the results of expensive function calls and returning the cached results when the same inputs recur.
Worked Methods
Traces of Sorting and Searching
For Linear Search, the target value is compared sequentially with each element from the starting index of the array until a match is found. For Binary Search, the list must be sorted beforehand; the target is repeatedly compared with the middle element of the segment, halving the search space each time.
For Bubble Sort, adjacent elements are compared and swapped if they are in the incorrect order, causing the largest elements to bubble up to their correct position at the end of each pass. Selection Sort improves on this by executing only one swap per pass after finding the minimum element in the remaining unsorted sub-array. Insertion Sort progressively builds a sorted sublist by inserting elements one by one into their appropriate relative positions.
Common Exam Traps
- Binary Search on Unsorted Lists: Trying to perform a Binary Search on an unsorted array is a classic error. Always ensure the data is sorted before using this strategy.
- Swap Counts in Sorting: Confusing the number of swaps in Bubble Sort with Selection Sort. Bubble Sort may perform multiple swaps in a single pass, whereas Selection Sort performs at most one swap per pass.
- Space Complexity Parts: Forgetting that space complexity is the sum of both the fixed part (constants, simple variables) and the variable part (recursion stacks, dynamic arrays).
Exam Tips
- Memorize the exact definition of algorithm characteristics like definiteness, correctness, and finiteness.
- Be prepared to calculate the average number of comparisons in sequential search using the formula (n + 1) / 2.
- Understand how to trace the values of low, high, and mid during manual binary search step-by-step questions.
- Ensure you can differentiate between dynamic programming (overlapping subproblems) and divide-and-conquer strategies.