C949v4 ultimate vocab flashcards

C949v4 ultimate vocab flashcards that i made

Algorithm

A step-by-step procedure for solving a problem or performing a computation, characterized by finiteness, definiteness, input, output, effectiveness, and generality.

Finiteness

A characteristic of an algorithm that ensures it terminates after a finite number of steps.

Definiteness

A characteristic of an algorithm that ensures each step is precisely defined and unambiguous.

Input

The values provided to an algorithm before it begins processing.

Output

The result produced by an algorithm after it completes its steps.

Effectiveness

A characteristic of an algorithm that ensures each step can be performed in a finite amount of time using basic operations.

Generality

A characteristic of an algorithm that ensures it can solve a range of problems, not just a specific case.

Brute Force Algorithm

A straightforward approach that exhaustively tries all possible solutions to a problem.

Recursive Algorithm

An algorithm that solves a problem by breaking it into smaller instances of the same problem and solving them recursively.

Base Case

The condition in a recursive algorithm that stops the recursion and provides a direct solution.

Recursive Case

The part of a recursive algorithm that breaks the problem into smaller subproblems and calls itself to solve them.

Linear Search

A search algorithm that checks each element in a list sequentially until the target is found.

Binary Search

A search algorithm that repeatedly divides a sorted list in half to find a target element.

Hashing Algorithm

An algorithm that converts data into a fixed-size hash value, often used for fast data retrieval.

Divide and Conquer

An algorithmic approach that breaks a 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

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

Big O Notation

A mathematical notation that describes the upper bound of an algorithm's time or space complexity in the worst case.

O(1)

Constant time complexity, where the algorithm's runtime does not depend on the input size.

O(n)

Linear time complexity, where the algorithm's runtime grows proportionally with the input size.

O(log n)

Logarithmic time complexity, where the algorithm's runtime grows logarithmically with the input size.

O(n^2)

Quadratic time complexity, where the algorithm's runtime grows proportionally to the square of the input size.

Data Structure

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

Array

A data structure that stores elements in contiguous memory locations, allowing fast access by index.

Linked List

A linear data structure where each element (node) contains data and a reference to the next node.

Stack

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

Queue

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

Hash Table

A data structure that maps keys to values using a hash function for fast lookups.

Collision

A situation in hashing where two keys produce the same hash value.

Binary Search Tree (BST)

A tree data structure where each node has at most two children, and the left child is less than the parent, while the right child is greater.

Heap

A specialized tree-based data structure that satisfies the heap property (min-heap or max-heap).

Graph

A data structure consisting of nodes (vertices) connected by edges, which can be directed or undirected.

Depth-First Search (DFS)

A graph traversal algorithm that explores as far as possible along each branch before backtracking.

Breadth-First Search (BFS)

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

Dijkstra's Algorithm

A greedy algorithm that finds 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 that finds the shortest path from a single source vertex to all other vertices, even with negative edge weights.

Strongly-Typed Language

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

Weakly-Typed Language

A programming language where the type of a variable is flexible, and implicit type conversions are allowed.

Encapsulation

An object-oriented programming concept that restricts access to certain details of an object's implementation.

Inheritance

An object-oriented programming concept where a new class is based on an existing class, inheriting its attributes and methods.

Polymorphism

An object-oriented programming concept where objects of different classes can be treated as objects of a common base class.

Garbage Collection

A process in programming where memory that is no longer in use is automatically freed.

Data Flow Diagram (DFD)

A graphical representation of the flow of data through a system, showing processes, data stores, data flows, and external entities.

Process (in DFD)

A component in a DFD that represents how data is transformed or manipulated.

Data Store (in DFD)

A component in a DFD that represents where data is stored within the system.

External Entity (in DFD)

A component in a DFD that represents an outside system or user that interacts with the system.

AVL Tree

A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one.

Red-Black Tree

A self-balancing binary search tree with additional properties (e.g., nodes are colored red or black) to ensure balance.

B-Tree

A self-balancing tree data structure that maintains sorted data and allows for efficient insertion, deletion, and search operations.

In-Order Traversal

A tree traversal method that visits nodes in the order: left subtree, root, right subtree.

Pre-Order Traversal

A tree traversal method that visits nodes in the order: root, left subtree, right subtree.

Post-Order Traversal

A tree traversal method that visits nodes in the order: left subtree, right subtree, root.

Min-Heap

A heap data structure where the parent node is always less than or equal to its children.

Max-Heap

A heap data structure where the parent node is always greater than or equal to its children.

Set

A data structure that stores unique elements with no specific order.

Heapify

The process of converting an unsorted array into a heap data structure.

Map (Dictionary)

A data structure that stores key-value pairs, allowing for efficient lookups, insertions, and deletions.

Hash Function

A function that converts input (key) into a fixed-size value (hash) used for indexing in a hash table.

Chaining

A collision resolution technique in hash tables where multiple elements are stored in the same bucket using a linked list.

Open Addressing

A collision resolution technique in hash tables where collisions are resolved by finding another open slot in the table.

Deque (Double-Ended Queue)

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

Bag (Multiset)

A data structure that allows duplicate elements, unlike a set.

Record

A composite data structure that stores a collection of related fields, each with a specific name and data type.

Abstract Data Type (ADT)

A theoretical model of a data structure that defines its behavior (operations) without specifying its implementation.

Primitive Data Type

A basic data type provided by a programming language (e.g., int, float, char).

Composite Data Type

A data type constructed from primitive data types (e.g., arrays, structures).

Enumeration (Enum)

A user-defined data type that consists of a set of named constants.

Static Variable Declaration

A variable declaration where memory is allocated at compile time, and the type and size are fixed.

Dynamic Variable Declaration

A variable declaration where memory is allocated at runtime, and the type and size can change.

Assignment Operator

An operator used to assign a value to a variable (e.g., =, +=, -=).

Logical Operator

An operator used to combine or negate conditions (e.g., and, or, not).

Bitwise Operator

An operator that performs operations on the binary representation of numbers (e.g., &, |, ^).

Constructor

A special method in a class that initializes objects when they are created.

Destructor

A special method in a class that cleans up resources when an object is destroyed.

Reference Count

A count of the number of references to an object, used in memory management.

Sequential Allocation

A memory allocation technique where memory is allocated in a sequential manner (e.g., arrays).

Linked Allocation

A memory allocation technique where memory is allocated in linked nodes (e.g., linked lists).

Insertion Operation

An operation that adds an element to a data structure (e.g., inserting into an array, linked list, or tree).

Deletion Operation

An operation that removes an element from a data structure (e.g., deleting from an array, linked list, or tree).

Search Operation

An operation that finds a specific element in a data structure (e.g., linear search, binary search).

Access Operation

An operation that retrieves an element from a data structure (e.g., accessing an array element by index).

Push Operation

An operation that adds an element to the top of a stack.

Pop Operation

An operation that removes and returns the top element from a stack.

Enqueue Operation

An operation that adds an element to the rear of a queue.

Dequeue Operation

An operation that removes and returns the front element from a queue.

Peek Operation

An operation that retrieves the top or front element of a stack or queue without removing it.

Heapify Up (Percolate Up)

The process of moving a newly inserted element up in a heap to maintain the heap property.

Heapify Down (Percolate Down)

The process of moving an element down in a heap to maintain the heap property after deletion.

Union Operation (Set)

An operation that combines two sets into one, containing all unique elements from both sets.

Intersection Operation (Set)

An operation that returns a set containing only the elements common to two sets.

Difference Operation (Set)

An operation that returns a set containing elements in one set but not in another.

Traversal Operation

An operation that visits all elements in a data structure (e.g., tree traversal, graph traversal).

Sorting Operation

An operation that arranges elements in a specific order (e.g., ascending, descending).

Hashing Operation

An operation that converts a key into a hash value for efficient storage and retrieval.

Collision Resolution

Techniques used to handle situations where two keys produce the same hash value (e.g., chaining, open addressing).

Rotations (AVL Tree)

Operations performed to rebalance an AVL tree after insertion or deletion (e.g., single rotation, double rotation).

Balancing (Tree)

The process of ensuring that a tree remains balanced (e.g., AVL trees, Red-Black trees).

Priority Queue

A data structure where elements are removed based on their priority (e.g., using a heap).

Adjacency List

A way to represent a graph where each vertex stores a list of its adjacent vertices.

Adjacency Matrix

A way to represent a graph using a 2D array where each cell indicates whether an edge exists between two vertices.