Algorithms and Data Structures Lecture Review

Comprehensive vocabulary flashcards covering algorithm analysis, growth rates, data structures, recursion, sorting, searching, and hash tables based on lecture notes.

Algorithms Analysis

A methodology that measures the growth rate of resource needs (time and memory) as data size increases, specifically calculating how much more resource is consumed to process $n+1$ pieces of data.

Time Resource (Measurement)

Measured by counting the number of operations performed, assuming that every individual operation has an identical time cost.

Memory Resource (Measurement)

Calculated by evaluating variable declarations and dynamically allocated memory instead of tracking operation counts.

Abstract Data Type (ADT)

Defines what a collection does and its properties without specifying how it is coded (e.g., List, Table).

Data Structure

The concrete underlying representation (e.g., Array, Linked List, Hash Table) used to implement an Abstract Data Type (ADT).

Constant Growth Rate $O(1)$

A growth rate where resource needs do not increase with data size, represented by a flat horizontal line.

Logarithmic Growth Rate $O(\text{log}(n))$

A growth rate where resource needs grow by one unit every time the data volume doubles; the curve flattens as data grows.

Linear Growth Rate $O(n)$

A growth rate where resource usage and data size are directly proportional, forming a non-horizontal straight line.

Loglinear Growth Rate $O(n \text{log}(n))$

A growth rate represented by a curved line where the curve is more pronounced for lower data values than higher ones.

Quadratic Growth Rate $O(n^2)$

A growth rate described mathematically by a parabola.

Cubic Growth Rate $O(n^3)$

A growth rate that looks similar to a quadratic curve but grows significantly faster.

Exponential Growth Rate $O(2^n)$

A growth rate where every additional unit of data requires a doubling of resources, shooting up to near-vertical.

Formal Big-O Definition

$T(n)$ is $O(f(n))$ if and only if for some constants $c$ and $n_0$, T(n) \text{\textle} cf(n) for all n \text{\textge} n_0.

Omega (\text{\textOmega})

Asymptotic notation used to indicate a lower bound.

Theta (\text{\textTheta})

Asymptotic notation used to represent an exact bound.

Little-o ($o$)

Asymptotic notation that defines an upper bound that will never actually be reached.

Dominating Term

The single term in a polynomial expression that grows so fast that all other terms and constants become insignificant as $n$ scales up.

Polynomial Form (Analysis Step 4)

The standard mathematical expression represented as T(n) = a_xn^x + a_{x-1}n^{x-1} + \text{\textdots} + a_1n + a_0.

Recurrence Relation

A mathematical formula used in recursive function analysis to express the operation count of a recursive step (e.g., $T(n) = 6 + T(n-1)$).

List ADT

A sequence of values characterized by an ordering, where there is an explicit first and second item, regardless of whether the values themselves are sorted.

Random Access (Array vs Linked List)

Constant time $O(1)$ via index for arrays, and linear time $O(n)$ for linked lists because they must be stepped through sequentially.

Resizing Behavior (Array)

A high-cost linear copy ($O(n)$) performed when an array is full, usually resulting in doubling the size.

Linked List Memory Usage Rule

In a singly linked list of integers, memory usage is double that of an array storing the same data; an array more than 50 \text{\textpercent} full is more space-efficient than the equivalent linked list.

Singly Linked List

A list where each node contains data and exactly one pointer referencing the next node in the sequence.

Doubly Linked List

A list where each node contains data and two pointers: one for the next node and one for the previous node.

Sentinel Nodes

Permanent boundary nodes at the front and back of a linked list that do not hold valid data and eliminate pointer edge cases like null values.

Stack

A First In, Last Out (FILO) structure where elements are pushed and popped strictly from the front/top.

Queue

A First In, First Out (FIFO) structure where elements are enqueued at the back and dequeued from the front.

Circular Ring Structure

An array implementation for a queue that uses modulo math and two indices (front and back) to achieve $O(1)$ efficiency for adding and removing elements.

Base Case

A scenario in recursion so basic that the function returns a value immediately without further recursive calls.

Recursive Case

A pathway that invokes the function itself with altered arguments designed to step closer to the base case.

Run-time Stack Frame

A newly allocated frame on the stack that houses a recursive function's distinct local variables and parameters; it pops off when a return statement is reached.

Stack Overflow

A crash caused by exhausting stack memory resources, often due to massive data or an incorrect base case in recursion.

Linear Search

A searching algorithm that inspects elements sequentially from index 0; it has a worst-case performance of $O(n)$.

Binary Search

An algorithm that targets the midpoint of a sorted array and discards half the search range in each step; it requires sorted data and constant-time random access, performing at $O(\text{log}(n))$..

Bubble Sort

An $O(n^2)$ sorting algorithm that repeatedly steps through the list, compares adjacent pairs, and swaps them if they are out of order.

Selection Sort

An $O(n^2)$ sorting algorithm that scans an unsorted segment to find the minimum value and swaps it into the boundary of the sorted section.

Insertion Sort

An $O(n^2)$ sorting algorithm that pulls values from an unsorted piece and shifts the sorted items to drop the value into its relatively correct position.

Merge Sort

A recursive divide and conquer algorithm that splits a list into halves, sorts them, and merges them back together at $O(n \text{log}(n))$ complexity.

Quick Sort

A divide and conquer strategy that partitions data around a pivot value; it operates in-place with an average performance of $O(n \text{log}(n))$.

Partitioning Algorithm

The $O(n)$ process in Quick Sort where a pivot is moved to the end, smaller elements are shifted to the front, and the pivot is swapped back to its correct central position.

Cut-off Optimization

A technique in Quick Sort where recursion stops once a partition drops below a threshold (16 to 32 elements) and switches to Insertion Sort.

Table ADT

An unordered collection mapping unique keys to data values.

Hash Function

A function that transforms a unique key into a numeric index, distributing values uniformly and randomly across available array slots.

Load Factor (\text{\textlambda})

The measure of hash table fullness calculated as \text{\textlambda} = \frac{\text{number of records in table}}{\text{number of locations}}.

Pigeonhole Principle

The principle stating that because possible keys ($m$) outnumber capacity ($n$), multiple distinct keys will inevitably hash to the same index, causing collisions.

Chaining (Closed Addressing)

A collision resolution strategy where each array index stores a pointer to a linked list of records; it has an average search performance of \text{\textTheta}(1 + \text{\textlambda}).

Linear Probing (Open Addressing)

A collision resolution strategy that stores exactly one record per slot, checking successive slots (i+1, i+2, \text{\textdots}) when a collision occurs.

Cluster

A contiguous block of adjacent filled slots in a linear probing hash table that slows down lookups.

Tombstoning

A removal method for linear probing where a slot status is set to 'Deleted' so that searches continue past it while new insertions can overwrite it.