C949v4 Study Guide | Memorize Terms

Array

a collection of homogenous elements stored in contiguous memory locations. Each element can be accessed using its index

Linked List

is a linear collection of elements called nodes, where each node contains data and a reference (or pointer) to the next node in the sequence.

BST

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

Hash Table

a data structure that maps keys to values using a hash function, which transforms the key into an index in an array

Heap

a specialized tree-based data structure that satisfies the heap property

List

include insertion, deletion, and access by index

Tuple

(key, value)

Stack

a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element added is the first one to be removed

push, pop, peek

Queue

a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed

enqueue, dequeue

Deque

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

Bag

(also known as a multiset) is a simple data structure that allows for storing a collection of elements where duplicate elements are allowed. Unlike a set, which requires all elements to be unique, a bag can contain multiple occurrences of the same element

Set

an abstract data structure that stores unique elements, with no specific order. It supports operations that allow the management of unique collections of data

Priority Queue

a specialized queue where each element has a priority assigned to it, and elements are processed based on their priority, with higher-priority elements being processed before lower-priority ones

Dictionary (Map)

a data structure that stores key-value pairs, where each unique key maps to a specific value. Provide efficient insertion, deletion, and lookup operations, typically in O(1) time on average due to the underlying hash table implementation

Boolean

Holds a true or false value

Int

Holds whole numbers

Char

Holds a single character

Floating Point, Double

Holds numbers with fractional parts

Garbage Collection

A process by which a computer's memory is automatically managed. It frees up memory that is no longer being used by the program.

Reference Count

A count of the number of times an object is referred to in a program.

Memory Allocation

The process of reserving memory space for an object in a program.

Linked Allocation

A memory allocation technique where memory is allocated in linked nodes. Each node contains a pointer to the next node

Sequential Allocation

A memory allocation technique where memory is allocated in a sequential manner.

Inheritance

allows you to create a new class that is based on an existing class, inheriting its attributes and methods.

Encapsulation

is the concept of restricting access to certain details of an object’s implementation. It involves using access specifiers to control the visibility of attributes and methods.

Access Specifiers

Python: Uses naming conventions (e.g., private or _private) rather than strict access specifiers.

C++: Uses public, protected, and private keywords to control access.

Polymorphism

allows objects of different classes to be treated as objects of a common base class, typically through method overriding.

Dijkstra's Algorithm

● Type: Greedy algorithm.

● Applicability: Works on graphs with non-negative edge weights.

● Time Complexity: O(V 2 ) for the simplest implementation, O(V log V+E) with a priority queue (using a binary heap), where V is the number of vertices and E is the number of edges.

● Functionality: It finds the shortest path from a single source vertex to all other vertices in a graph by iteratively selecting the vertex with the smallest known distance, updating the distances to its neighbors, and marking it as visited.

Bellman-Ford Algorithm

● Type: Dynamic programming algorithm.

● Applicability: Works on graphs with negative edge weights and can detect negative weight cycles.

● Time Complexity: O(V*E), where V is the number of vertices and E is the number of edges.

● Functionality: It calculates the shortest path from a single source vertex to all other vertices by relaxing all edges repeatedly over V−1 iterations.

Enumeration

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

Attributes

Variables that hold data related to the class. They define the state of an object.

Methods

Functions defined within a class that operate on its attributes or perform actions.

Constructor

A special method that initializes objects of the class. It is called when an object is created.

Destructor

A method that cleans up when an object is destroyed (in C++). Python manages memory automatically, so a destructor is less commonly used.