Finiteness Definiteness C949v4 Study Guide

Fill-in-the-blank flashcards covering major concepts from the C949v4 algorithms and data structures study guide.

The requirement that an algorithm eventually stops after a finite number of steps is called ___.

Finiteness

The property that every step of an algorithm is precisely and unambiguously specified is ___.

Definiteness

Values supplied to an algorithm before processing are its ___.

Inputs

The result produced after an algorithm finishes is known as the ___.

Output

If every operation of an algorithm can be performed in a finite amount of time using basic operations, the algorithm satisfies ___.

Effectiveness

The ability of one algorithmic solution to solve a whole class of problems rather than a single instance is called ___.

Generality

Breaking a problem into smaller, self-contained modules demonstrates the algorithmic feature of ___.

Modularity

The ease with which another designer can build on or expand an existing algorithm is its ___.

Extensibility

An algorithm that always produces the correct output for all valid inputs satisfies the factor of ___.

Correctness

Designing an algorithm so future changes require minimal modification supports ___.

Maintainability

Considering practical, real-world logical steps in an algorithm refers to its ___ factor.

Functionality

An algorithm that clearly defines the problem and handles unexpected input shows ___.

Robustness

If an algorithm is difficult to understand it lacks the ___ characteristic.

User-friendliness

Algorithms that are straightforward and easy to follow demonstrate ___.

Simplicity

Trying every possible solution until one works exemplifies the ___ algorithm type.

Brute Force

An algorithm that calls itself on smaller sub-instances until a base case is reached is a ___ algorithm.

Recursive

Transforming plaintext to ciphertext for privacy relies on an ___ algorithm.

Encryption

Systematically exploring choices and undoing wrong paths exemplifies ___ algorithms.

Backtracking

Algorithms whose goal is to locate a target value in data are called ___ algorithms.

Searching

Arranging items into a particular order is done by a ___ algorithm.

Sorting

Converting data to fixed-size codes for quick access uses a ___ algorithm.

Hashing

Dividing a task, conquering subproblems, and combining answers describes ___ algorithms.

Divide and Conquer

Making the best local choice at each stage typifies a ___ algorithm.

Greedy

Saving and reusing sub-results to avoid recomputation is the hallmark of ___ programming algorithms.

Dynamic

Algorithms that incorporate randomness in their steps are called ___ algorithms.

Randomized

In recursion, the simplest situation that stops further calls is the ___.

Base Case

The portion of a recursive algorithm that reduces the problem size is the ___.

Recursive Case

Each active recursive call is stored on the program's ___.

System Call Stack

The mathematical definition n! = n × (n−1)! illustrates the ___ problem solved recursively.

Factorial

Recursive solutions are often more elegant than iterative ones due to their ___.

Simplicity

A drawback of deep recursion is potential ___ overflow.

Stack

Sequentially examining each element until a match is found defines ___ search.

Linear

Linear search has a worst-case time complexity of ___.

O(n)

Dividing a sorted array in half repeatedly to find an element describes ___ search.

Binary

Binary search requires the data to be ___.

Sorted

The average-case time complexity of binary search is ___.

O(log n)

Estimating the likely position of a key in uniformly distributed data is the idea behind ___ search.

Interpolation

Exploring as far as possible along each branch before backtracking characterizes ___.

Depth-First Search (DFS)

Visiting all neighbors at the current depth before moving deeper is the strategy of ___.

Breadth-First Search (BFS)

Swapping adjacent out-of-order elements so big values "float" to the end is ___ sort.

Bubble

Repeatedly selecting the minimum remaining element and moving it to the front is ___ sort.

Selection

Building a sorted subsection by inserting each new element into its proper place defines ___ sort.

Insertion

Recursively splitting a list, sorting halves, and combining them is ___ sort.

Merge

Partitioning around a pivot and recursively sorting partitions is characteristic of ___.

Quicksort

Using a binary heap to repeatedly extract the maximum element implements ___ sort.

Heap Sort

Counting occurrences of each key to place items directly is ___ sort.

Counting

Sorting numbers digit by digit (often using counting sort inside) is ___ sort.

Radix

Distributing items into buckets and sorting each bucket embodies ___ sort.

Bucket

Sorting elements that are far apart and gradually reducing the gap is done by ___ sort.

Shell

Algorithms with constant-time complexity are denoted ___.

O(1)

Algorithms whose complexity grows logarithmically with input size are ___.

O(log n)

Linear-time algorithms have complexity ___.

O(n)

Merge sort and heap sort run in ___ time complexity.

O(n log n)

Bubble, insertion, and selection sorts are examples of ___ time algorithms.

O(n^2)

Algorithms whose running time doubles with each additional input element have ___ complexity.

Exponential (O(2^n))

Brute-force permutation algorithms often have ___ time complexity.

Factorial (O(n!))

In Big-O, constant multipliers are ignored; thus O(3n) simplifies to ___.

O(n)

Of the terms in O(n² + n + log n), the dominant term kept is ___.

n²

Changing the base of a logarithm only introduces a constant, so O(log₂ n) is simplified to ___.

O(log n)

Nested loops where each runs n times result in overall complexity ___.

O(n²)

A basic building-block type like int or char is a ___ data type.

Primitive

A collection of related fields treated as a single unit is called a ___.

Record

A data structure of contiguous memory allowing O(1) indexed access is an ___.

Array

Nodes linked by pointers form a ___ list.

Linked

A LIFO data structure where push adds and pop removes from the same end is a ___.

Stack

A collection permitting duplicates and focusing on element counts is called a ___.

Bag (Multiset)

A FIFO data structure where enqueue adds at rear and dequeue removes from front is a ___.

Queue

Allowing insertion and deletion at both ends, a ___ combines stack and queue features.

Deque

Key–value storage with average O(1) operations is provided by a ___.

Hash Table

The formulas childLeft = 2i+1 and childRight = 2i+2 apply to nodes in a ___.

Binary Heap

In a max-heap, every parent node is ___ than or equal to its children.

Greater

A hierarchical structure with a single root and child nodes is a ___.

Tree

A binary search tree keeps left child values ___ the parent.

Less than

A BST that self-balances by keeping height differences ≤1 is an ___ tree.

AVL

A self-balancing BST using red and black node colors is a ___ tree.

Red-Black

A multi-way search tree optimized for disk access in databases is a ___.

B-Tree

Visiting Node → Left → Right is ___ traversal.

Pre-Order (NLR)

Left → Node → Right traversal of a BST outputs keys in ___ order.

Sorted (Ascending)

The traversal order Left → Right → Node is called ___.

Post-Order (LRN)

A set stores only ___ elements, ignoring duplicates.

Unique

Edges with optional direction connecting vertices define a ___.

Graph

Choosing the smallest known distance vertex repeatedly finds shortest paths in ___ algorithm.

Dijkstra's

An algorithm that can handle negative edge weights and detect negative cycles is ___.

Bellman-Ford

Automatically reclaiming unused memory at runtime is called ___.

Garbage Collection

In reference counting, when the count reaches ___, the object is deleted.

Zero

Memory allocated at compile time with fixed size is a ___ variable.

Static

Memory allocated on the heap at runtime is known as ___ allocation.

Dynamic

Languages that forbid implicit type coercion are considered __-typed.

Strongly

JavaScript allows automatic conversions, so it is a __-typed language.

Weakly

The operator that both adds and assigns in one step is ___.

+=

In standard precedence, multiplication is evaluated ___ addition.

Before

A loop that continues while a condition remains True is a ___ loop.

While

The statement that immediately exits the nearest loop is ___.

break

Skipping the rest of the current iteration and continuing the loop uses the ___ statement.

continue

Choosing among many constant values of a single expression can be done with a ___ statement (in C/C++).

switch-case

Combining data and behavior, a ___ defines objects in OOP.

Class

A special method that initializes a newly created object is the ___.

Constructor

Hiding internal details behind public interfaces illustrates ___.

Encapsulation

Allowing a subclass to provide its own version of a parent method demonstrates ___.

Polymorphism

The formula key % size used to compute an index is part of the ___ function.

Hash