General Definitions Flashcards
Binary Search
Searching an array by recursively chopping it in half
Insertion Sort
Inserting element x into the sorted portion of the array 0..x
Selection Sort
Building the sorted portion of the array (0..x) by selecting the smallest element in the unsorted portion (x..L) and placing it at x.
Merge Sort
Recursively dividing the array in half, then (effectively) performing selection sort when “working back up”/rebuilding the array
Quick Sort
Choose an element as pivot (p), move elements less than p to left, elements greater than p to right. Do this recursively.
Radix Sort
Element length must be equal!
Place each element in the array into queue buckets, then pull from buckets to rebuild array. Do this for each character in the element’s “key”/value
Abstract Data Type
Semantic behavior of a data structure
Data Structures
A specific implementation of an ADT
Pre-condition
A statement that must be true before method execution
Caller’s responsibility
Post-condition
A statement that must be true after the method execution
Implementer’s responsibility
Loop invariant
A statement that must always remain true, including during execution
Constant time operation
An operation that does not depend on the input size
e.g. reading/writing memory, math, returns
asymptotic runtime complexity
Number of constant time operations an algorithm performs relative to the input size.
Big O classes
The asymptotic runtime complexity of an algorithm with lower-order terms dropped
e.g. N!, K^N, N^K, N log(N), N, log(N), 1
Recursion
A method that calls itself during execution
Recursion: Well-defined
A recursive method that contains valid base cases such that it will (eventually) terminate
Recursion: Phases
Divide, Conquer, Combine
definitions for each phase straightforward
Merge Sort: Where does the “actual sorting” happen?
Combine
Quick Sort: Where does the “actual sorting” happen?
Divide
Sorting algorithms: Stable
Maintains the original order of elements with the same key while sorting
Sorting algorithms: In-place
Requires less than O(N) storage space, excluding the input
Comparison Sort
A sorting algorithm that sorts by using comparisons
everything except Radix
Tree
ADT where keys are stored as nodes with a parent (and potentially children)
Heap
A complete binary tree where each element is greater than or equal to its parent
Trie
A tree where keys are stored by tracing the edges between nodes
Priority Queue
ADT where elements are pulled based on some pre-defined priority.
Trie methods
Contains: Returns boolean if the path to target exists
Insert: Creates nodes along the target path if they don’t already exist
Delete: Lazily deletes a key by setting terminates to false (does not actually remove from memory!)
Heap methods
Peek: Returns root without removing it
Poll: Returns and removes the overall root, then moves last element to root, then swap down until invariant is true
Add: Place element on end, then swap upwards until invariant is true
Map
ADT for unique keys being associated with a value
Generics
A thing in Java that lets you use any non-primitive type in its place
Comparable
Java interface that defines how a data type can compare to itself using compareTo() (and thus Object.equals())
