Space/Time Trade-offs and Algorithms

These flashcards cover key concepts related to space/time trade-offs, different sorting algorithms, string matching techniques, and hashing strategies.

Space/Time Trade-offs

The balance between the memory consumed by an algorithm (space) and the time taken to execute it (time), often requiring a sacrifice of one for the other.

Input enhancement

A preprocessing technique that stores data for later use to improve the efficiency of solving a problem.

Counting Sort

A sorting algorithm that counts the frequency of each element and organizes them based on these counts, with an efficiency of O(n^2).

Distribution Counting Sort

A special-purpose sorting algorithm efficient for small, known input value frequencies, with an efficiency of O(n).

String Matching

An algorithmic approach for finding occurrences of a pattern within a text, which can be enhanced to skip comparisons based on character occurrences.

Hash Function

A function that maps keys to indices in a hash table, often using operations like key mod m, where m is the table size.

Collisions in Hashing

Situations where two different keys are mapped to the same index in a hash table, requiring strategies like separate chaining or closed hashing.

Separate Chaining

A collision resolution strategy where each bucket in a hash table stores a list of entries assigned to that bucket.

Closed Hashing

A collision resolution strategy where, upon collision, the algorithm searches linearly for the next available bucket.

Efficiency of Hash Table

Insert, get, and delete operations in a hash table can generally be performed in O(1) time if the hash function is of good quality.