第3章データ構造とアルゴリズム

consists of all data structures that share common functionality

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

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

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

solution to well-known computing problems

common concept and ideas behind algorithm design patterns

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

data structure that stores elements next to each other in memory

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

mathematical notation that formally defines the order of growth

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

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

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

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

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

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

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

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

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

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

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

well-known algorithm

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

descendant of another node

situation where multiple objects hash to the same integer index value

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

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

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

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

problem of representing information using less data storage

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

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

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

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

problem of masking or obfuscating text to make it unintelligible

complex data type with specific representation and specific functionality

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

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

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

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

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

relationship between vertices or nodes

individual data point

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

operations such as adding, retrieving, and removing elements

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

computational problem involving graphs that represent relationships between data

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

implements sets and maps by applying the concept of hashing

problem of assigning a meaningful integer index for each object

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

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

position or address for an element in a list

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

problems that do not have efficient, polynomial-time algorithms

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

node at the bottom of a tree that has no children

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

category of data structures where elements are ordered in a line

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

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

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

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

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

problem of searching for a text pattern within a document

canonical divide and conquer algorithm for comparison sorting

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

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

represents an element in a tree or graph

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

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

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

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

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

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³)

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

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

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

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

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

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

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

solves problems by transforming them into other problems

particular way of organizing a collection of elements

node at the top of the tree

study of how much time it takes to run an algorithm

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

problem of retrieving a target element from a collection of elements

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

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

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

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

problem of rearranging elements into a logical order

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

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

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

smaller instance of a problem that can be solved independently

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

problems that computers can solve in a reasonable amount of time

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

problem of exploring all the vertices in a graph

hierarchical data structure

abstract model of computation for executing any computer algorithm

problem of finding the shortest paths in terms of the number of edges

represents an element in a graph or special type of it such as a tree

problem of finding the shortest paths in terms of the sum of the edge weights