Module 1: Introduction to Data Structures and Complexity - Vocabulary Flashcards

Vocabulary flashcards covering key terms from the notes on data structures, classifications, examples, and algorithm complexity.

Data

Values or attributes used in calculations, decision-making, and problem-solving.

Primitive Data

Basic building blocks that store single values; fixed size and fast; directly supported by hardware.

Non-Primitive Data (Reference Types)

Derived from primitive types; can store multiple values or collections; refer to memory locations rather than store data directly.

Abstract Data Type (ADT)

A blueprint for organizing data; defines operations and behavior without specifying how data is stored.

Structure

Defines how data is stored and accessed in memory and the rules governing operations like insertion, deletion, and searching.

Characteristics of a Structure

Determines how data is linked, memory usage, and processing time for operations.

Linear Data Structures

Data arranged sequentially; each element has a unique predecessor and successor; efficient for sequential access.

Non-Linear Data Structures

Data arranged hierarchically or multi-level; elements may connect to multiple others; efficient for complex relationships.

Static Data Structures

Fixed size; memory allocated at compile-time; fast access but less flexible.

Dynamic Data Structures

Grow or shrink at runtime; memory allocated dynamically; more flexible but with allocation overhead.

Arrays

Fixed-size collection of elements stored contiguously in memory.

Linked List

Collection of nodes where each node contains data and a reference to the next node.

Stack

Last-In, First-Out data structure; used in function calls and undo/redo operations.

Queue

First-In, First-Out data structure; used in scheduling and message processing.

Trees

Hierarchical structure with nodes connected as parent-child relationships; used in databases, file systems, and AI.

Graphs

Nodes connected by edges, representing relationships; used in social networks, web crawling, and shortest path algorithms.

Hash Tables

Key-value stores for fast retrieval; used in caching, dictionaries, and indexing.

Data Access Speed

How quickly data can be read or written; a key criterion for choosing a data structure.

Memory Constraints

Limitations on memory usage that influence data structure choice.

Complex Relationships

Hierarchical or network-like relationships that are efficiently represented by trees or graphs.

Dynamic vs Static Needs

Whether data size changes; guides choice between dynamic and static data structures.

Primitive Data Structures

Basic built-in types (e.g., int, float, char, bool) that are atomic and fixed in memory.

Non-Primitive Data Structures (Examples)

Structures built from primitives, such as arrays and structs.

Classes & Objects

Object-oriented programming constructs; classes define types and objects are instances.

B-Trees

Balanced tree data structure used for efficient indexing in databases.

Inverted Indexes

Index mapping keywords to documents/pages used in search engines.

PageRank

Ranking algorithm used to determine the relevance of web pages in search engines.

BFS / DFS

Breadth-First Search and Depth-First Search, graph traversal algorithms.

Syntax Trees & Symbol Tables

Data structures used by compilers to represent code and manage identifiers.

Parsing Algorithms

Algorithms (e.g., recursive descent) used to analyze program structure.

Big O Notation

Notation expressing the upper bound of an algorithm's time or space growth.

Time Complexity

Growth of an algorithm's runtime with respect to input size.

Space Complexity

Growth of an algorithm's memory usage, including auxiliary space.

Auxiliary Space

Extra memory used by an algorithm beyond input data.

Input Storage

Memory required to hold the input data.

Contiguous Memory

Memory allocated in a single, continuous block.