cs445 final

Sorting algorithm: comparison-based vs non-comparison-based

A comparison-based sorting algorithm only uses comparisons between keys (e.g.,

Stable sort: definition

A stable sorting algorithm preserves the relative order of equal keys: if two elements have the same key and appear in order in the input, they appear in the same order in the output.

In-place sort: definition

An in-place sorting algorithm uses only O(1) extra memory (aside from recursion stack or a few variables). It rearranges the elements within the original array or collection.

Selection sort: basic idea

Repeatedly find the minimum element from the unsorted portion of the array and swap it into the next position in the sorted portion, building a sorted prefix from left to right.

Selection sort: time complexity

Selection sort performs Θ(n^2) comparisons in best, average, and worst cases, because it always scans the remaining unsorted elements to find a minimum for each position.

Selection sort: stability and space

Selection sort is in-place (O(1) extra space) but not stable, because swapping the minimum into position can move equal keys past one another.

Insertion sort: basic idea

Builds a sorted prefix by repeatedly taking the next element and inserting it into the correct position within the already-sorted part using shifts.

Insertion sort: time complexity

Insertion sort is Θ(n) in the best case (already sorted input) and Θ(n^2) in average and worst cases (e.g., reverse-sorted input).

Insertion sort: stability and space

Insertion sort is stable (does not change the relative order of equal keys) and in-place (O(1) extra space).

Shell sort: basic idea

Shell sort generalizes insertion sort by first sorting elements far apart using a sequence of decreasing gaps, then finishing with a standard insertion sort when the gap is 1.

Shell sort: effect of gap sequence

The choice of gap sequence strongly affects performance. Simple sequences may give O(n^2) time, while better sequences can yield subquadratic performance in practice.

Merge sort: basic idea

Merge sort uses divide-and-conquer: split the array into two halves, recursively sort each half, and then merge the two sorted halves into one sorted array.

Merge sort: time complexity

Merge sort runs in Θ(n log n) time in best, average, and worst cases, because each level of recursion merges in O(n) time and there are O(log n) levels.

Merge sort: stability and space

Merge sort is stable and typically requires O(n) extra space to hold temporary arrays during the merge step.

Quicksort: basic idea

Quicksort chooses a pivot, partitions the array so that elements less than the pivot go left and elements greater than the pivot go right, then recursively sorts the left and right subarrays.

Quicksort: time complexity

Quicksort has average-case time Θ(n log n) with reasonably balanced partitions, but worst-case time Θ(n^2) when partitions are extremely unbalanced (e.g., pivot always smallest or largest).

Quicksort: in-place and stability

Standard quicksort is in-place (uses O(log n) stack space) but not stable; maintaining stability usually requires extra storage or a different partition scheme.

Radix sort (LSD): when applicable

LSD radix sort is used for keys that can be viewed as sequences of digits of fixed or bounded length (e.g., integers in a limited range, fixed-length strings), and works best when the digit range (base) is not too large.

Radix sort (LSD): basic idea

Process digits from least significant to most significant. In each pass, stably bucket-sort the keys by the current digit. After the final (most significant) digit pass, the array is sorted.

Radix sort (LSD): time complexity

LSD radix sort with counting sort per digit runs in O(d * (n + b)), where n is the number of keys, d is the number of digits, and b is the digit base; often written O(dn) when b is small.

Queue ADT: definition

A queue is a First-In, First-Out (FIFO) collection where elements are inserted at the back (enqueue) and removed from the front (dequeue).

Queue ADT: core operations

The main operations are enqueue(x) to add an element at the back, dequeue() to remove and return the front element, front()/peek() to look at the front without removing, and isEmpty() to check if it has no elements.

Queue ADT: typical runtimes

A well-implemented queue (array-based circular buffer or linked list) supports enqueue and dequeue in O(1) time.

Circular array queue: idea

A queue implemented with a fixed-size array and two indices (front and back), where indices wrap around using modulo arithmetic to reuse freed slots when elements are dequeued.

Linked-list queue: idea

A queue implemented with a singly linked list that maintains pointers to both the head (front) and tail (back), supporting O(1) enqueue at the tail and O(1) dequeue from the head.

Iterator: definition

An iterator is an object that provides a standard way to traverse a collection (e.g., hasNext and next methods), without exposing or depending on the collection’s internal representation.

Iterator: advantages

Iterators preserve encapsulation by hiding representation, allow a uniform traversal interface across many data structures, and can safely support removal of elements during traversal via an iterator-provided remove() method.

Dictionary / Map ADT: definition

A dictionary (or map) is an abstract data type that stores key–value pairs and supports operations such as insert(key, value), find/search(key), and remove(key).

Dictionary / Map ADT: typical operations

The core operations are insert(key, value), get/find(key) to retrieve the value for a key, remove(key) to delete the mapping, and sometimes update(key, value) if the key already exists.

Hash table: basic idea

A hash table implements a dictionary by applying a hash function h(key) to map keys to indices in an array; collisions (multiple keys mapping to the same index) are handled by techniques like separate chaining or open addressing.

Hash function: goal

A hash function deterministically maps keys to integer indices, aiming to distribute keys approximately uniformly across the table to minimize collisions and keep operations fast on average.

Load factor α: definition

The load factor α of a hash table is n / m, where n is the number of stored elements and m is the number of slots (buckets) in the table; it measures how full the table is.

Separate chaining: collision resolution

In separate chaining, each table slot holds a linked list (or similar structure) of key–value pairs that hash to that index; collisions are stored in the chain for that bucket.

Open addressing: collision resolution

In open addressing, all elements are stored directly in the hash table array. When a collision occurs, the algorithm probes alternative indices (using linear probing, quadratic probing, or double hashing) until it finds an empty slot.

Linear probing: probe sequence

For linear probing, if the initial index is i = h(key), the probe sequence for collisions is i, i+1, i+2, … (mod m), scanning forward until an empty slot is found.

Quadratic probing: probe sequence

For quadratic probing, from initial index i = h(key), the probe sequence might be i + 1^2, i + 2^2, i + 3^2, … (mod m), which spreads out probes and reduces primary clustering.

Primary clustering: definition

In open addressing with linear probing, primary clustering is the formation of long contiguous runs of occupied slots, which increase the average number of probes and hurt performance.

Hash table: expected vs worst-case runtime

With a good hash function and a reasonable load factor, hash table operations (insert, find, remove) run in expected O(1) time; but in the worst case (many collisions) they can degrade to O(n).

String matching: naive algorithm

The naive string matching algorithm checks every possible alignment of the pattern in the text and, for each alignment, compares the pattern characters to the text characters one by one.

String matching: naive algorithm complexity

The naive algorithm runs in O(n * m) worst-case time, where n is the text length and m is the pattern length, because each of O(n) alignments may require up to m comparisons.

Rabin–Karp: basic idea

Rabin–Karp computes a hash for the pattern and rolling hashes for each length-m substring of the text; it compares hashes to quickly filter candidate matches and only does full character-by-character checks when hashes match.

Rabin–Karp: complexity properties

Rabin–Karp has worst-case time O(n * m) if many hash collisions require full verification, but expected time O(n + m) with a good hash function and low collision probability since most positions only require O(1) hash comparisons.

String matching: pattern and text lengths

For string matching, n usually denotes the text length and m denotes the pattern length; valid starting positions for a length-m pattern in a length-n text range from 0 to n - m inclusive.

Use cases: when queues are natural

A queue is a natural model for problems with FIFO behavior, such as job scheduling, breadth-first search in graphs, buffering requests, and handling events in order of arrival.

Use cases: when hash tables are natural

Hash tables are ideal when you need fast average-case insert and lookup by key, such as symbol tables, caches, dictionaries, and sets where order does not matter but membership queries are frequent.

Use cases: when stable sorting matters

Stable sorting matters when you sort by multiple keys in stages (e.g., sort by last name then by first name) or you want to preserve the relative order of records with equal keys.