Chapter 3: Data Structures and Algorithms

abstract data type (ADT)

consists of all data structures that share common functionality

abstraction

process of simplifying a concept in order to represent it in a computer

adjacent

in a graph abstract data type, the relationship between two vertices connected by an edge

algorithm analysis

study of the results produced by the outputs as well as how the algorithm produces those outputs

algorithm design pattern

solution to well-known computing problems

algorithmic paradigm

common concept and ideas behind algorithm design patterns

algorithmic problem solving

refers to a particular set of approaches and methods for designing algorithms that draws on computing’s historical connections to the study of mathematical problem solving

array list

data structure that stores elements next to each other in memory

asymptotic analysis

evaluates the time that an algorithm takes to produce a result as the size of the input increases

asymptotic notation

mathematical notation that formally defines the order of growth

AVL tree

balanced binary search tree data structure often used to implement sets or maps that organizes elements according to the AVL tree property

AVL tree property

requires the left and right subtrees to be balanced at every node in the tree

balanced binary search tree

introduces additional properties that ensure that the tree will never enter a worst-case situation by reorganizing elements to maintain balance

Big O notation

most common type of asymptotic notation in computer science used to measure worst case complexity

binary heap

binary tree data structure used to implement priority queues that organizes elements according to the heap property

binary logarithm

tells how many times a large number needs to be divided by 2 until it reaches 1

binary search algorithm

recursively narrows down the possible locations for the target in the sorted list

binary search tree

tree data structure often used to implement sets and maps that organizes elements according to the binary tree property and the search tree property

binary tree property

requires that each node can have either zero, one, or two children

breadth-first search

iteratively explores each neighbor, expanding the search level-by-level breadth-first

brute-force algorithm

solves combinatorial problems by systematically enumerating all potential solutions in order to identify the best candidate solution

canonical algorithm

well-known algorithm

case analysis

way to account for variation in runtime based on factors other than the size of the problem

child node

descendant of another node

collision

situation where multiple objects hash to the same integer index value

combinatorial explosion

exponential number of solutions to a combinatorial problem that makes brute-force algorithms unusable in practice

combinatorial problem

involves identifying the best candidate solution out of a space of many potential solutions

comparison sorting

sorting of a list of elements where elements are not assigned numeric values but rather defined in relation to other elements

complexity

condition based on the degree of computational resources that an algorithm consumes during its execution in relation to the size of the input

compression

problem of representing information using less data storage

constant

type of order of growth that does not take more resources as the size of the problem increases

correctness

whether the outputs produced by an algorithm match the expected or desired results across the range of possible inputs

cost model

characterization of runtime in terms of more abstract operations such as the number of repetitions

count sorting

sorting a list of elements by organizing elements into categories and rearranging the categories into a logical order

cryptography

problem of masking or obfuscating text to make it unintelligible

data structure

complex data type with specific representation and specific functionality

data structure problem

computational problem involving the storage and retrieval of elements for implementing abstract data types such as lists, sets, maps, and priority queues

data type

determines how computers process data by defining the possible values for data and the possible functionality or operations on that data

depth-first search

graph traversal algorithm that recursively explores each neighbor, continuing as far possible along each subproblem depth-first

Dijkstra’s algorithm

maintains a priority queue of vertices in the graph ordered by distance from the start and repeatedly selects the next shortest path to an unconnected part of the graph

divide and conquer algorithm

algorithmic paradigm that breaks down a problem into smaller subproblems (divide), recursively solves each subproblem (conquer), and then combines the result of each subproblem in order to inform the overall solution

edge

relationship between vertices or nodes

element

individual data point

experimental analysis

evaluates an algorithm’s runtime by recording how long it takes to run a program implementation of it

functionality

operations such as adding, retrieving, and removing elements

graph

represents binary relations among collection of entities, specifically vertices and edges

graph problem

computational problem involving graphs that represent relationships between data

greedy algorithm

solves combinatorial problems by repeatedly applying a simple rule to select the next element to include in the solution

hash table

implements sets and maps by applying the concept of hashing

hashing

problem of assigning a meaningful integer index for each object

heap property

requires that the priority value of each node in the heap is greater than or equal to the priority values of its children

heapsort algorithm

adds all elements to a binary heap priority queue data structure using the comparison operation to determine priority value and returns the sorted list by repeatedly removing from the priority queue element-by-element

index

position or address for an element in a list

interval scheduling problem

combinatorial problem involving a list of scheduled tasks with the goal of finding the largest non-overlapping set of tasks that can be completed

intractable

problems that do not have efficient, polynomial-time algorithms

Kruskal’s algorithm

greedy algorithm that sorts the list of edges in the graph by weight

leaf node

node at the bottom of a tree that has no children

linear

type of order of growth where the resources required to run the algorithm increases at about the same rate as the size of the problem increases

linear data structure

category of data structures where elements are ordered in a line

linked list

data structure that does not necessarily store elements next to each other and instead works by maintaining, for each element, a link to the next element in the list

list

ordered sequence of elements and allows adding, retrieving, and removing elements from any position in the list

logarithm

tells how many times a large number needs to be divided by a small number until it reaches 1

longest path

problem of finding the highest-cost way to get from one vertex to another without repeating vertices

map

represents unordered associations between key-value pairs of elements, where each key can only appear once in the map

matching

problem of searching for a text pattern within a document

merge sort

canonical divide and conquer algorithm for comparison sorting

minimum spanning tree

problem of finding a lowest-cost way to connect all the vertices to each other

model of computation

rules of the underlying computer that is ultimately responsible for executing the algorithm

node

represents an element in a tree or graph

nondeterministic algorithm

special kind of Turing machine, which at each step can non-deterministically choose which instruction to execute and is considered to successfully find a solution if any combination of these nondeterministic choices leads to a correct solution

nondeterministic polynomial (NP) time complexity class

all problems that can be solved in polynomial time by a nondeterministic algorithm

NP-complete

all the hardest NP problems—the combinatorial problems for which we do not have deterministic polynomial-time algorithms

order of growth

geometric prediction of an algorithm’s time or space complexity as a function of the size of the problem

perfectly balanced

for every node in the binary search tree, its left and right subtrees contain the same number of elements

polynomial (P) time complexity class

all problems that have runtimes described with a polynomial expression such as O(1), O(log N), O(N), O(N log N), O(N²), O(N³)

Prim’s algorithm

greedy algorithm that maintains a priority queue of vertices in the graph ordered by connecting edge weight

priority queue

represents a collection of elements where each element has an associated priority value

problem

task with specific input data and output data corresponding to each input

problem model

simplified, abstract representation of a more complex real-world problem

program

realization or implementation of an algorithm written in a formal programming language

quicksort algorithm

recursively sorts data by applying the binary search tree algorithm design pattern to partition data around pivot elements

reachable vertex

vertex that can be reached if a path or sequence of edges from the start vertex exists

reduction algorithm

solves problems by transforming them into other problems

representation

particular way of organizing a collection of elements

root node

node at the top of the tree

runtime analysis

study of how much time it takes to run an algorithm

search tree property

requires that elements in the tree are organized least-to-greatest from left-to-right

searching

problem of retrieving a target element from a collection of elements

sequential search algorithm

searching algorithm that sequentially checks the collection element-by-element for the target

set

represents an unordered collection of unique elements and allows adding, retrieving, and removing elements from the set

shortest path

problem of finding a lowest-cost way to get from one vertex to another

shortest paths tree

output of the shortest paths problem, the lowest-cost way to get from one vertex to every other reachable vertex in a graph

sorting

problem of rearranging elements into a logical order

space complexity

formal measure of how much memory an algorithm requires during its execution as it relates to the size of the problem

step

basic operation in the computer, such as looking up a single value, adding two values, or comparing two values

string problem

computational problem involving text or information represented as a sequence of characters

subproblem

smaller instance of a problem that can be solved independently

time complexity

formal measure of how much time an algorithm requires during execution as it relates to the size of the problem

tractable

problems that computers can solve in a reasonable amount of time

traveling salesperson problem (TSP)

problem of, given the path cost of every pair of vertices, finding the lowest-cost tour, or path from a start vertex visiting every vertex in the graph once including a return to the start vertex