Definitions Flashcards
Record
A record is the data structure that stores subitems, often called fields, with a name associated with each subitem.
Array
An array is a data structure that stores an ordered list of items, where each item is directly accessible by a positional index.
Inserting an item at a specific location in an array requires making room for the item by shifting higher-indexed items.
Linked list
A linked list is a data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.
A linked list stores an ordered list of items. The links in each node define the order in which items are stored.
To insert new item in a linked list, a list node for the new item is first created. Item B’s next pointer is assigned to point to item C. Item A’s next pointer is updated to point to item B. No shifting of other items is required, which is an advantage of using linked lists.
Binary tree
A binary tree is a data structure in which each node stores data and has up to two children, known as a left child and a right child.
A binary tree node can have no children, a single left or right child, or both a left and right child.
Hash table
A hash table is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.
Heap
In data structures, a “heap” is a tree-based data structure where the nodes are arranged in a specific order, either with the largest value at the root (max-heap) or the smallest value at the root (min-heap), ensuring that the parent node always has a value greater than or equal to its children, making it particularly useful for implementing priority queues where you need to quickly access the highest or lowest priority element; it’s often implemented as a complete binary tree for efficient operations.
Key points about heaps:
- Heap property:
The core principle of a heap is the “heap property” which dictates the ordering of nodes within the tree, either with the parent node always having a larger value than its children (max-heap) or a smaller value (min-heap).
- Binary heap:
The most common implementation of a heap is a “binary heap” where each node has at most two children.
- Applications:
Heaps are used in algorithms like heapsort (for sorting data), Dijkstra’s algorithm (for finding shortest paths), and priority queues where elements need to be accessed based on their priority
A max-heap is a tree that maintains the simple property that a node’s key is greater than or equal to the node’s children’s keys.
A min-heap is a tree that maintains the simple property that a node’s key is less than or equal to the node’s children’s keys.
Graph
A graph is a data structure for representing connections among items, and consists of vertices connected by edges. A vertex represents an item in a graph. An edge represents a connection between two vertices in a graph.
Algorithm
An algorithm is a set of commands that must be followed for a computer to perform calculations or other problem-solving operations.
According to its formal definition, an algorithm is a finite set of instructions carried out in a specific order to perform a particular task. It is not the entire program or code; it is simple logic to a problem represented as an informal description in the form of a flowchart or pseudocode.
- Problem: A problem can be defined as a real-world problem or real-world instance problem for which you need to develop a program or set of instructions. An algorithm is a set of instructions.
- Algorithm: An algorithm is defined as a step-by-step process that will be designed for a problem.
- Input: After designing an algorithm, the algorithm is given the necessary and desired inputs.
- Processing unit: The input will be passed to the processing unit, producing the desired output.
- Output: The outcome or result of the program is referred to as the output.
Logical vs Physical data flow diagram
Logical DFDs (data flow diagrams) focus on what happens in a particular information flow: what information is being transmitted, what entities are receiving that info, what general processes occur, etc. The processes described in a logical DFD (data flow diagram) are business activities—a logical data flow diagram doesn’t delve into the technical aspects of a process or system, such as how the process is constructed and implemented. So you don’t need to include details like configuration or data storage technology. Non-technical employees should be able to understand these diagrams, making logical DFDs (data flow diagrams) an excellent tool for communicating with project stakeholders.
Physical data flow diagrams focus on how things happen in an information flow. These diagrams specify the software, hardware, files, and people involved in an information flow. A detailed physical data flow diagram can facilitate the development of the code needed to implement a data system.
NP-complete
NP-complete problems are a set of problems for which no known efficient algorithm exists. NP-complete problems have the following characteristics:
No efficient algorithm has been found to solve an NP-complete problem.
No one has proven that an efficient algorithm to solve an NP-complete problem is impossible.
If an efficient algorithm exists for one NP-complete problem, then all NP-complete problems can be solved efficiently.
By knowing a problem is NP-complete, instead of trying to find an efficient algorithm to solve the problem, a programmer can focus on finding an algorithm to efficiently find a good, but non-optimal, solution
Algorithm efficiency
Algorithm efficiency is most commonly measured by the algorithm runtime, and an efficient algorithm is one whose runtime increases no more than polynomially with respect to the input size.
In contrast, an algorithm with an exponential runtime is not efficient.
Abstract data types (ADTs)
An abstract data type (ADT) is a data type described by predefined user operations, such as “insert data at rear,” without indicating how each operation is implemented. An ADT can be implemented using different underlying data structures. However, a programmer need not have knowledge of the underlying implementation to use an ADT.
Abstract Data Types examples
List, Dynamic array, Stack, Queue, Deque, Bag, Set, Priority queue, Dictionary (Map)
Stack
A stack is an Abstract Data Type (ADT) in which items are only inserted on or removed from the top of a stack.
Common underlying data structures:
Linked list
Queue
A queue is an Abstract Data Type (ADT) in which items are inserted at the end of the queue and removed from the front of the queue.
Common underlying data structures:
Linked list
Deque
A deque (pronounced “deck” and short for double-ended queue) is an Abstract Data Type (ADT) in which items can be inserted and removed at both the front and back.
Common underlying data structures:
Linked list
Bag
A bag is an Abstract Data Type (ADT) for storing items in which the order does not matter and duplicate items are allowed.
Common underlying data structures:
Array, linked list
Set
A set is an Abstract Data Type (ADT) for a collection of distinct items. Duplicate items are not allowed.
Common underlying data structures:
Binary search tree, hash table
Priority Queue
A priority queue is a Abstract Data Type (ADT) queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority. Duplicate items are allowed.
Common underlying data structures:
Heap
Dictionary (map)
A dictionary is an Abstract Data Type (ADT) that associates (or maps) keys with values.
Common underlying data structures:
Hash table, binary search tree
Dynamic Array
A dynamic array is an Abstract Data Type (ADT) for holding ordered data and allowing indexed access.
Common underlying data structures:
Array
List
A list is an Abstract Data Type (ADT) for holding ordered data. Duplicate items are allowed.
Common underlying data structures:
Array, linked list
Heuristics
Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.
In practice, solving a problem in the optimal or most accurate way may require more computational resources than are available or feasible. Algorithms implemented for such problems often use a heuristic.
Self-adjusting heuristic
A self-adjusting heuristic is an algorithm that modifies a data structure based on how that data structure is used. Ex: Many self-adjusting data structures, such as red-black trees and AVL (Adelson-Velsky and Landis) trees, use a self-adjusting heuristic to keep the tree balanced. Tree balancing organizes data to allow for faster access.
Ex: A self-adjusting heuristic can be used to speed up searches for frequently-searched-for list items by moving a list item to the front of the list when that item is searched for. This heuristic is self-adjusting because the list items are adjusted when a search is performed.
Greedy algorithm
A greedy algorithm solves a problem by assuming that the optimal choice at a given moment during the algorithm will also be the optimal choice overall. Greedy algorithms tend to be efficient, but certain types of problems exist where greedy algorithms don’t find the best or optimal solution. However, greedy algorithms produce both efficient and optimal solutions for many problems, including the fractional knapsack problem and the activity selection problem.
Dynamic programming
Dynamic programming is a problem solving technique that splits a problem into smaller subproblems, computes and stores solutions to subproblems in memory, and then uses the stored solutions to solve the larger problem. Ex: Fibonacci numbers can be computed with an iterative approach that stores the 2 previous terms, instead of making recursive calls that recompute the same term many times over.
Peek(stack)
Returns but does not remove item at top of stack
Bounded stack
A bounded stack is a stack with a length that does not exceed a maximum value. The maximum is commonly the initial allocation size. Ex: A bounded stack with allocationSize = 100 cannot exceed a length of 100 items.
A bounded stack with a length equal to the maximum length is said to be full.
A bounded stack must have an attribute for maximum size and an if statement in the push() method. But the Stack class has neither, and so is an unbounded stack.
Unbounded stack
An unbounded stack is a stack with no upper limit on length. An unbounded stack’s length can increase indefinitely, so the stack’s array allocation size must also be able to increase indefinitely.
Queue
vs
Enqueue
vs
Dequeue
A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.
The queue enqueue operation inserts an item at the end of the queue.
The queue dequeue operation removes and returns the item at the front of the queue.
Ex: After the operations “Enqueue 7”, “Enqueue 14”, and “Enqueue 9”, “Dequeue” returns 7. A second “Dequeue” returns 14. A queue is referred to as a first-in first-out ADT. A queue can be implemented using a linked list or an array.
Trie
A trie (or prefix tree) is a tree representing a set of strings. Each non-root node represents a single character. Each node has at most one child per distinct alphabet character. A terminal node is a node that represents a terminating character, which is the end of a string in the trie.
Tries provide efficient storage and quick search for strings, and are often used to implement auto-complete and predictive text input.
Double data type
A “double” data type refers to a data type in programming that stores high-precision floating-point numbers, essentially allowing for decimal values with a larger range and more significant digits compared to a standard “float” data type; it is often called “double-precision” because it typically uses double the memory space of a float, usually occupying 8 bytes (64 bits) to store the value.
Key points about the double data type:
Precision:
- Can store numbers with more decimal places than a float, usually around 15-16 significant digits.
Range:
- Can represent very large and very small numbers compared to other data types.
Usage:
- Commonly used in scientific calculations, financial applications, and scenarios where high accuracy with decimal values is needed
Tuple
In Python, a tuple is an ordered, immutable sequence of elements. This means that once a tuple is created, its contents cannot be changed.
Key points about tuples:
- Immutable:
Unlike lists, you cannot modify the elements of a tuple after it is created.
- Ordered:
Elements in a tuple maintain their order, just like in lists.
- Heterogeneous:
Tuples can contain elements of different data types, such as integers, strings, floats, and even other tuples.
- Syntax:
Tuples are defined by enclosing elements within parentheses () and separating them with commas.
Example in Python:
my_tuple = (1, “hello”, 3.14, True)
Common use cases for tuples:
- Storing data that should not be changed:
Tuples are ideal for storing data that needs to remain constant, like coordinates or database records.
- Function return values:
Functions can return multiple values as a tuple, allowing for convenient packing and unpacking of data.
- Dictionary keys:
Tuples can be used as keys in dictionaries because they are hashable (immutable).
Garbage Collection
In data structures, “garbage collection” refers to an automated process where a program identifies and reclaims memory space occupied by data structures that are no longer being used, essentially removing “garbage” data and freeing up memory for new allocations, thus preventing memory leaks and simplifying memory management for developers.
Key points about garbage collection:
- Automatic process:
Unlike manual memory management, garbage collection happens automatically without explicit code from the programmer to deallocate memory.
- Identifying unreachable objects:
The garbage collector determines which data structures are no longer accessible by the program (considered “garbage”) by tracking references to objects.
- Reclaiming memory:
When an object is identified as garbage, the garbage collector reclaims its memory space, allowing it to be used for new data allocations.
- Implementation methods:
Different garbage collection algorithms exist, including reference counting and tracing algorithms, each with its own advantages and drawbacks.
Benefits of garbage collection:
- Reduced memory leaks:
By automatically reclaiming unused memory, garbage collection significantly decreases the risk of memory leaks, which can lead to program crashes.
- Simplified development:
Developers don’t need to manually manage memory allocation and deallocation, allowing them to focus on the core logic of their application.
Important considerations:
- Performance overhead:
Garbage collection can sometimes introduce a small performance overhead as the garbage collector needs to periodically scan memory for unused objects.
- Language support:
Most modern programming languages like Java, C#, and Python have built-in garbage collection mechanisms
Garbage is determined by identifying objects in a data structure that are no longer reachable from any active reference points, meaning they are not being used by the program and can be safely removed from memory; this is typically done by traversing the data structure starting from “root” objects and marking all reachable objects, with any remaining unmarked objects considered garbage
How do you determine the children in a heap list?
For an element at index i, the left child is located at index 2i + 1, and the right child is located at index 2i + 2.
i = index value
Preorder tree traversal
Preorder tree traversal is a depth-first search algorithm that visits the nodes of a tree in a specific order, starting with the root node, then the left subtree, and finally the right subtree
Pop()
A “pop()” function, when used on a list or array, removes the last element from that data structure and returns the value of the removed element; essentially, it takes the element off the end of the list and gives it back to you as the result of the function call
