Algorithms and Data Structures Flashcards

Vocabulary-style flashcards based on lecture notes covering algorithm analysis, data structures, recursion, and sorting algorithms.

Algorithms Analysis

A measurement of 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

A measure of efficiency calculated by counting the number of operations performed, assuming every individual operation has an identical time cost.

Memory Resource

A measure of efficiency calculated by evaluating variable declarations and dynamically allocated memory.

Abstract Data Type (ADT)

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

Data Structure

The concrete underlying representation used to implement an ADT, such as an Array, Linked List, or Hash Table.

Constant $O(1)$

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

Logarithmic $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 size increases.

Linear $O(n)$

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

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

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

Quadratic $O(n^2)$

A growth rate described mathematically by a parabola.

Exponential $O(2^n)$

A growth rate where every additional unit of data requires a complete doubling of resources, causing the curve to shoot 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{ } \b{

Omega (\text{\Omega})

An asymptotic notation indicating a lower bound.

Theta (\text{\Theta})

An asymptotic notation representing an exact bound.

Little-o ($o$)

An asymptotic notation defining an upper bound that will never actually be reached.

Dominating Term

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

List ADT

A sequence of values characterized by an ordering (first, second, etc.) which is independent of whether the data values themselves are sorted.

Singly Linked List

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

Doubly Linked List

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

Sentinel Nodes

Boundary nodes at the front and back of a linked list that hold no valid data and eliminate pointer edge cases by ensuring pointers are never raw null values.

Stack

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

Queue

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

Recursion

A method of solving complex problems by taking one small step and restating the remaining problem in terms of itself.

Base Case

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

Run-Time Stack

A memory structure where every recursive function call allocates a new frame to house its distinct local variables and parameters.

Linear Search

A search algorithm that starts at index 0 and inspects elements sequentially one-by-one until the target matches or the list ends; works on unsorted lists.

Binary Search

A search algorithm that targets the midpoint of a sorted search range and discards half of the elements at each step; requires random access.

Bubble Sort

An $O(n^2)$ algorithm that compares adjacent pairs and swaps them if out of order, repeating until the largest value bubbles to the back.

Selection Sort

An $O(n^2)$ algorithm that scans the unsorted segment for the absolute minimum value and swaps it into the boundary index of the sorted section.

Insertion Sort

An $O(n^2)$ algorithm that pulls the next unsorted value, shifts sorted items up to open a slot, and drops the value into its relative position.

Merge Sort

A recursive divide and conquer algorithm that splits lists into halves until they reach the base case of size 0 or 1 and then merges them back together.

Quick Sort

An in-place divide and conquer sorting strategy that utilizes partitioning around a pivot value.

Table ADT

An unordered collection mapping unique keys to values, where keys must be distinct but data values can be duplicates.

Hash Table

A data structure that uses a hash function to transform a unique key into a numeric index within an underlying array for direct access.

Load Factor (\text{\lambda})

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

Chaining (Closed Addressing)

A collision resolution strategy where every index in the array stores a pointer to a linked list of records that map to that specific index.

Linear Probing (Open Addressing)

A collision resolution strategy that checks index $i+1, i+2, i+3$, etc., until an open slot is found.

Tombstoning

A method for handling removal in linear probing where a slot status is flipped to 'Deleted' so searches do not stop, but new insertions can overwrite it.