Algorithms and Data Structures Flashcards

Flashcards covering key vocabulary related to algorithms and data structures.

Algorithm

A finite sequence of well-defined, computer-implementable instructions, typically to solve a class of specific problems or to perform a computation.

Finiteness

An algorithm must complete after a finite number of steps.

Definiteness

Each step in an algorithm must be precisely defined and unambiguous.

Input

An algorithm requires one or more inputs from a predetermined range of acceptable values.

Output

An algorithm must produce one or more outputs that have a clear relationship to the inputs.

Effectiveness

An algorithm's operations must be basic and executable in a finite amount of time with available resources.

Generality

An algorithm should be applicable to a range of inputs, not just a single case.

Modularity

The principle of breaking down a problem into smaller, manageable modules.

Extensibility

An algorithm should be designed so that other programmers can easily use and adapt it.

Correctness

An algorithm should produce the desired output for all valid inputs.

Maintainability

An algorithm should be easy to understand and modify without introducing significant changes.

Functionality

An algorithm should solve a real-world problem by taking into account various logical steps.

Robustness

An algorithm should be able to clearly define and handle the problem it is designed to solve.

User-friendly

An algorithm's design should be easy to understand.

Simplicity

An algorithm should be easy to understand if it is simple.

Brute Force Algorithm

A straightforward approach that exhaustively tries all possible solutions.

Recursive Algorithm

A method that solves a problem by breaking it into smaller, similar subproblems.

Encryption Algorithm

An algorithm used to transform data into a secure, unreadable format.

Backtracking Algorithm

A trial-and-error technique used to explore potential solutions by undoing choices when they lead to an incorrect outcome.

Searching Algorithm

An algorithm designed to find a specific target within a dataset.

Sorting Algorithm

An algorithm aimed at arranging elements in a specific order.

Hashing Algorithm

An algorithm that converts data into a fixed-size hash value for rapid data access.

Divide and Conquer Algorithm

An algorithm that breaks a complex problem into smaller subproblems, solves them independently, and combines their solutions.

Greedy Algorithm

An algorithm that makes locally optimal choices at each step in the hope of finding a global optimum.

Dynamic Programming Algorithm

An algorithm that stores and reuses intermediate results to avoid redundant computations.

Randomized Algorithm

An algorithm that utilizes randomness in its steps to achieve a solution.

Base Case

The condition under which a recursive algorithm stops.

Recursive Case

The part of a recursive algorithm that breaks the problem down into smaller instances.

Stack

A data structure used to store each recursive call in a system.

Linear Search

A simple search algorithm that sequentially checks each element until the target is found.

Binary Search

A search algorithm that repeatedly divides the search interval in half, requiring a sorted data set.

Interpolation Search

Like binary search, but estimates the position of the target element based on its value within a uniformly distributed dataset.

Depth-First Search (DFS)

A graph/tree traversal algorithm that explores as far as possible along one branch before backtracking.

Breadth-First Search (BFS)

A graph/tree traversal algorithm that explores all neighbors at the present depth before moving on to nodes at the next depth level.

Bubble Sort

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Selection Sort

A sorting algorithm that repeatedly finds the minimum element from the unsorted portion and places it at the beginning.

Insertion Sort

A sorting algorithm that builds a sorted list one element at a time by inserting each new element into its correct position.

Merge Sort

A divide-and-conquer sorting algorithm that divides the list into halves, sorts each half, and then merges them.

Quicksort

A sorting algorithm that selects a “pivot” element and partitions the array around it, recursively sorting the partitions.

Heap Sort

A sorting algorithm that uses a binary heap data structure to build a max-heap and repeatedly extracts the maximum element.

Counting Sort

A non-comparative sorting algorithm that counts the occurrences of each element and uses this information to place elements.

Radix Sort

A sorting algorithm that sorts numbers by processing individual digits.

Bucket Sort

A sorting algorithm that distributes elements into buckets and sorts each bucket individually.

Shell Sort

A generalization of insertion sort that sorts elements at specific intervals and gradually reduces the interval.

Big O Notation

A notation that describes the upper bound on the time or space complexity of an algorithm, representing the worst-case scenario.

O(1) - Constant Time

The algorithm takes the same amount of time regardless of the size of the input.

O(log n) - Logarithmic Time

The runtime increases logarithmically as the input size increases.

O(n) - Linear Time

The runtime increases linearly with the size of the input.

O(n log n) - Log-Linear Time

The runtime increases more than linearly but less than quadratically.

O(n2) - Quadratic Time

The runtime increases quadratically with the size of the input.

O(2n) - Exponential Time

The runtime doubles with each additional element in the input.

O(n!) - Factorial Time

The runtime increases factorially with the size of the input.

Data Type

A classification that specifies the type of data that a variable can hold in programming.

Primitive Data Types

Basic building blocks of data in a programming language.

Integer

Holds whole numbers.

Floating Point

Holds numbers with fractional parts.

Character

Holds a single character.

Boolean

Holds a true or false value.

Composite Data Types

Data types constructed from primitive types.

Arrays

A collection of elements of the same data type.

Structures

A collection of different data types.

User-Defined Data Types

Data types created by the user, typically by combining primitive data types.

Enumeration (Enum)

A data type in programming that allows a variable to be a set of predefined constants.

Data Structure

A specific way of organizing and storing data in a computer so that it can be accessed and modified efficiently.

Abstract Data Type (ADT)

A theoretical model of a data structure that defines the behavior from the user's point of view, without specifying the underlying implementation.

Array

A collection of homogeneous elements stored in contiguous memory locations.

Linked List

A linear collection of elements called nodes, where each node contains data and a reference to the next node in the sequence.

Singly Linked List

Linked list where each node points to the next node.

Doubly Linked List

Linked list where each node points to both the next and previous nodes.

Circular Linked List

Linked list where the last node points back to the first node, forming a loop.

Stack

A linear data structure that follows the Last-In-First-Out (LIFO) principle.

Bag (Multiset)

A data structure that allows for storing a collection of elements where duplicate elements are allowed.

Queue

A linear data structure that follows the First-In-First-Out (FIFO) principle.

Deque

A linear data structure that allows insertion and deletion of elements from both the front and rear ends.

Hash Table

A data structure that maps keys to values using a hash function for efficient lookup.

Hashing

The process of mapping keys to indices in an array using a hash function.

Hash Function

A function that converts input (key) into a fixed-size value, typically an integer, which serves as an index in the hash table array.

Tree

A hierarchical data structure composed of nodes, where each node contains a value and references to child nodes.

Binary Tree

A tree where each node has at most two children (left and right).

Binary Search Tree (BST)

A binary tree where the left child contains values less than the parent, and the right child contains values greater than the parent.

Full Binary Tree

A binary tree in which every node has either 0 or 2 children.

Complete Binary Tree

A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.

Perfect Binary Tree

A binary tree in which all interior nodes have two children and all leaves are at the same level.

Balanced Binary Tree

A binary tree where the height of the left and right subtrees of any node differ by at most one.

AVL Trees

A self-balancing binary search tree in which the height of the two child subtrees of any node differs by at most one.

Red-Black Trees

A binary search tree where the tree is kept balanced by performing rotations and color changes during insertions and deletions.

B-Trees

A self-balancing search tree in which nodes can have more than two children, commonly used in databases and file systems.

Heap

A specialized tree-based data structure that satisfies the heap property.

Set

An abstract data structure that stores unique elements, with no specific order.

Graph

A collection of nodes (vertices) connected by edges.

Directed Graph (Digraph)

A graph where all edges have a direction.

Undirected Graph

A graph where edges do not have direction.

Weighted Graph

A graph where edges have weights representing costs or distances.

Unweighted Graph

A graph where edges have no weights.

Dijkstra's Algorithm

A greedy algorithm for finding the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.

Bellman-Ford Algorithm

A dynamic programming algorithm for finding the shortest path from a single source vertex to all other vertices in a graph, including graphs with negative edge weights, and can detect negative weight cycles.

Static Variable

A variable allocated memory at compile time, with a known type and size before the program runs.

Dynamic Variable

A variable allocated memory at runtime, with a type and size determined during program execution.

Strongly-Typed Language

A language where the type of a variable is strictly enforced, and implicit conversions between incompatible types are not allowed.

Weakly-Typed Language

A language where the type system is more flexible, allowing implicit conversions between types.