Glossary
Base Case
The condition in a recursive method that stops the recursion, preventing an infinite loop. It defines the simplest instance of the problem that can be solved directly.
Example:
In a recursive countdown, the base case might be when the number reaches 0, at which point the countdown stops.
Binary Search
An efficient searching algorithm that repeatedly divides the search interval in half. It requires the data to be presorted.
Example:
Finding a word in a dictionary is like performing a binary search: you open to the middle, decide if your word is before or after, and then repeat the process on the chosen half.
Insertion Sort
A simple sorting algorithm that builds the final sorted array (or list) one item at a time. It iterates through the input elements and inserts each element into its correct position in the sorted part of the array.
Example:
When sorting a hand of playing cards, you might use insertion sort by picking up one card at a time and placing it into its correct position among the cards already in your hand.
Iterative
A programming approach that uses loops (like `for` or `while`) to repeat a block of code until a certain condition is met, rather than calling itself.
Example:
Calculating the sum of numbers from 1 to 10 can be done iteratively by using a for loop that adds each number to a running total.
Linear Search
A sequential searching algorithm that checks each element in a list one by one until the target element is found or the end of the list is reached.
Example:
To find a specific book in an unsorted pile, you would perform a linear search, checking each book from top to bottom until you find the one you need.
Merge Sort
An efficient, comparison-based sorting algorithm that works by dividing a list into two halves, recursively sorting each half, and then merging the sorted halves back together.
Example:
Imagine sorting two separate, already sorted piles of papers into one large sorted pile; this 'merging' step is key to how merge sort combines its sorted sub-lists.
Presorted
Describes a list or array whose elements are already arranged in a specific order (e.g., ascending or descending) before a particular algorithm is applied.
Example:
For a binary search to work correctly, the list of student IDs must be presorted numerically.
Recursion
A programming technique where a method calls itself to solve a problem by breaking it down into smaller, similar subproblems until a base case is reached.
Example:
Calculating the factorial of a number, like 5!, can be done using recursion where 5! = 5 * 4!, and 4! = 4 * 3!, and so on, until 1! (the base case).
Recursive Call
The act of a method invoking itself within its own definition, typically with modified parameters that move closer to the base case.
Example:
When a function calculates fib(n) by calling fib(n-1) and fib(n-2), these are recursive calls that break the problem into smaller Fibonacci calculations.
Selection Sort
A simple sorting algorithm that repeatedly finds the minimum element from the unsorted part of the list and puts it at the beginning of the sorted part.
Example:
To sort a list of student scores using selection sort, you'd find the lowest score, move it to the front, then find the next lowest from the remaining scores, and so on.