1. Introduction to Data Structures and Algorithms Flashcards
data structure
A data structure is a way of organizing, storing, and performing operations on data.
record
A record is the data structure that stores subitems, often called fields, with a name associated with each subitem.
array
An array is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.
linked list
A linked list is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.
binary tree
A binary tree is a data structure in which each node stores data and has up to two children, known as a left child and a right child.
hash table
A hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.
max-heap
A max-heap is a tree that maintains the simple property that a node’s key is greater than or equal to the node’s childrens’ keys.
min-heap
A min-heap is a tree that maintains the simple property that a node’s key is less than or equal to the node’s childrens’ keys.
graph
A graph is a data structure for representing connections among items, and consists of vertices connected by edges.
vertex
A vertex represents an item in a graph.
edge
An edge represents a connection between two vertices in a graph.
algorithm
An algorithm describes a sequence of steps to solve a computational problem or perform a calculation.
computational problem
A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output.
NP-complete
NP-complete problems are a set of problems for which no known efficient algorithm exists.
abstract data type / ADT
An abstract data type (ADT) is a data type described by predefined user operations, such as ‘insert data at rear,’ without indicating how each operation is implemented.
list
A list is an ADT for holding ordered data.
dynamic array
A dynamic array is an ADT for holding ordered data and allowing indexed access.
stack
A stack is an ADT in which items are only inserted on or removed from the top of a stack.
queue
A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.
deque
A deque (pronounced ‘deck’ and short for double-ended queue) is an ADT in which items can be inserted and removed at both the front and back.
bag
A bag is an ADT for storing items in which the order does not matter and duplicate items are allowed.
set
A set is an ADT for a collection of distinct items.
priority queue
A priority queue is a queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.
dictionary
A dictionary is an ADT that associates (or maps) keys with values.
compression
Given data represented as some quantity of bits, compression transforms the data to use fewer bits.
Huffman coding
Huffman coding is a common compression technique that assigns fewer bits to frequent items, using a binary tree.
heuristic
Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.
heuristic algorithm
A heuristic algorithm is an algorithm that quickly determines a near optimal or approximate solution.
0-1 knapsack problem
0-1 knapsack problem: The knapsack problem with the quantity of each item limited to 1.
self-adjusting heuristic
A self-adjusting heuristic is an algorithm that modifies a data structure based on how that data structure is used.
Dynamic programming
Dynamic programming is a problem solving technique that splits a problem into smaller subproblems, computes and stores solutions to subproblems in memory, and then uses the stored solutions to solve the larger problem.
longest common substring
The longest common substring algorithm takes 2 strings as input and determines the longest substring that exists in both strings.
