M1 Part 2 & 3

Generics

• Type Parameter: The placeholder for the actual type that will be used, and a symbol that can be substituted with any concrete type.

• Parameterized Type: A generic class or interface that has one or more type parameters.

• Bounded Type Parameter: A type parameter with constraints, specifying that the type must be a subclass of a particular class or implement a particular interface.

• Generic Method: A method that includes its own type parameters.

• Generic Class: A class that can operate on objects of various types while providing compile-time type safety.

Linear Search

• Linear Search (Brute Force): A straightforward search algorithm that checks each element in a collection sequentially until the target element is found or the end of the collection is reached.

• Equality Comparison: Checking if two elements have the same value. This is the most common comparison in a linear search.

• Identity Comparison: Checking if two elements refer to the exact same object in memory. This is more stringent than equality and is often used in reference types.

• Abstracted Comparison: Using a generic mechanism for comparison that allows the linear search algorithm to work with different types of data. This abstraction can be achieved by passing a comparator function or implementing a Comparable interface.

Binary Search

• Binary Search: An efficient algorithm for finding a target value within a sorted list by repeatedly dividing the search interval in half.

• Sorted List: A list where elements are ordered, either in ascending or descending order, which is a prerequisite for binary search.

• Target Value: The value that the algorithm is searching for within the sorted list.

• Middle Element: The element located at the midpoint of the current search range. This element is compared with the target value to determine which half of the list to continue the search in.

• Search Range: The portion of the list currently being considered, defined by two indices: the start and end of the range.

• Left Half: The segment of the list before the middle element. If the target value is less than the middle element, the search continues in this portion.

• Right Half: The segment of the list after the middle element. If the target value is greater than the middle element, the search continues in this portion.

• Iterative Binary Search: A version of binary search that uses a loop to repeatedly narrow down the search range.

Sorting

• Sorting: The process of arranging elements in a specific order, typically ascending or descending, based on a comparison function.

• Order (Ascending/Descending):

  • Ascending: Arranging elements from smallest to largest.

  • Descending: Arranging elements from largest to smallest.

• Stable Sorting: A sorting algorithm is stable if it preserves the relative order of equal elements from the input in the output.

• In-Place Sorting: A sorting algorithm is in-place if it requires only a constant amount of extra space aside from the input data.

• Comparison-Based Sorting: Sorting algorithms that determine the order of elements by comparing them to one another using a comparison function (e.g., less than, greater than).

• Bubble Sort: A simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• Selection Sort: A comparison-based algorithm that repeatedly finds the minimum (or maximum) element from the unsorted portion and places it at the beginning (or end) of the list.

• Insertion Sort: A comparison-based algorithm that builds the final sorted list one item at a time by repeatedly taking the next element and inserting it into its correct position among the already sorted elements.

• Best Case: The scenario where the algorithm performs the fewest steps.

• Worst Case: The scenario where the algorithm performs the most steps.

• Average Case: The expected performance across all possible inputs, often considered the most practical measure.