Introduction to Data Structures and Algorithms

Fundamentals of Data Structures

Data Structure Definition:
- A data structure is a particular way of organizing data in a computer so that it can be used efficiently.
- It represents the arrangement of data in memory locations to express values of the carrier set of an abstract data type.
- Provides a system to manage large volumes of data for users, such as in large-scale databases and internet indexing services.
- Key to the design of efficient algorithms.
Memory Foundation:
- Data structures rely on a computer's capability to fetch and store data at any location in memory.
- Memory locations are specified by a pointer — a bit string representing a memory address that can be stored in memory and manipulated by a computer program.
Primary Data Structure Types:
- Array:
- A fixed-length, ordered collection of values of the same data type stored in contiguous memory locations.
- Can be ordered across one or multiple dimensions.
- Composed of elements (values or variables), where each element is identified by at least one ( $1$ ) array index or key.
- Considered the simplest type of data structure.
- Categorized into one-dimensional arrays or two-dimensional arrays (matrices).
- Used to implement tables (especially lookup tables), lists, and strings across computer programs.
- List:
- An abstract data type representing a sequence of values, where identical values may appear more than once.
- Serves as a computer implementation of the mathematical concept of a finite sequence (the potentially infinite counterpart is a stream).
- Represents a foundational example of a container structure.
- Divided into two ( $2$ ) families:
  - Lists exposing an infrastructure for the first element and the remaining sequence of elements.
  - Lists providing a primary interface based on random access via an indexer.
- Linked List:
- Consists of chains of nodes, where each node contains information such as data and a pointer (reference or link) to the next node in the sequence.
- Complex variants add additional links beyond the single next pointer.
- Functions among the simplest and most common structures for implementing other abstract data types.
- Principal benefit over conventional arrays: elements can be inserted or removed easily without requiring reallocation or reorganization of the entire structure, as items do not need to be stored contiguously in memory or on disk.
- Stack:
- An abstract data type or collection where the primary operations are the addition of an entity (push) and the removal of an entity (pop).
- Operates as a Last-In-First-Out (LIFO) data structure, meaning the last element added must be the first one removed.
- Push and pop operations take place exclusively at one end of the structure, designated as the top of the stack.
- Supports a peek or top operation, which returns the value of the top element without removing it.
- Declared full and enters an overflow state when it lacks sufficient capacity to accept a pushed entity.
- Possesses a natural ordering where elements are removed in the exact reverse order of their insertion.
- Queue:
- An abstract data type or collection in which entities maintain a designated sequence order.
- Primary operations comprise adding entities to the rear terminal position and removing entities from the front terminal position.
- Functions as a First-In-First-Out (FIFO) linear data structure where the first element added is the first to be removed.
- Hashing:
- A method for storing and retrieving records from a database based on search key values.
- Enables insertion, deletion, and searching of records via a search key.
- Stores records inside an array called a hash table.
- Operates by performing a calculation on a search key $K$ using a hash function to identify the specific position in the table containing the record.
- Records are not ordered by value, as they are placed according to address calculations.
- Table positions are designated as slots. The total count of slots is represented by the variable $M$ , with slots numbered from $0$ to $M - 1$ .
- Trees:
- A hierarchical data structure composed of nodes (vertices) and edges containing no cycles.
- A tree lacking nodes is called a null or empty tree.
- A non-empty tree consists of a root node and potentially multiple levels of additional nodes forming a hierarchy.
- Defined recursively as a collection of nodes starting at a root node, where each node consists of a value and a list of references to child nodes, constrained such that no reference is duplicated and no reference points to the root.

Abstract Data Types (ADTs) and Operations

Abstract Data Type Definition:
- A mathematical model for a class of data structures exhibiting similar behavior, or for programming language data types sharing identical semantics.
- Defined exclusively by the operations that may be executed on it, alongside mathematical preconditions and constraints governing the effects and operational costs.
Summary of Operations by ADT:
- Abstract Array:
- Adding elements
- Sorting elements
- Searching elements
- Re-arranging elements
- Performing matrix operations
- Pre-fix and post-fix operations
- Abstract List:
- Inserting
- Searching
- Deletion
- Abstract Link:
- Checking whether the list is empty
- Accessing a node to modify it or obtain stored information
- Traversing the list to access all elements (e.g., printing or searching for specific elements)
- Determining the size (total number of elements) of the list
- Inserting or removing a specific element
- Constructing a list by reading elements from an input stream
- Converting a list to and from arrays, strings, and other structures
- Abstract Stack:
- Push: Inserts a data item into the structure
- Pop: Extracts an item from the structure
- Peek or Top: Examines the data on top of the structure without removing it
- Abstract Queue:
- Enqueue: Joins the queue at the rear
- Dequeue: Removes the first element from the queue
- Front: Accesses and serves the first element in the queue
- Abstract Hashing:
- Add (Insert)
- Delete (Remove)
- Abstract Tree:
- Searching
- Insertion
- Deletion
- Traversal
- Sort

Introduction to Algorithms

Algorithm Concept and Role:
- An algorithm is a finite sequence of steps designed to accomplish a computational task.
- Steps must be simple and definite enough for computer execution, and the process must terminate after a finite number of steps.
- Different algorithms can perform the same task using distinct instruction sets while varying in execution time, required space, or computational effort.
- Functions as a computational procedure taking an input value or set of values and producing an output value or set of values.
- Accepts data, manipulates it according to prescribed rules, and yields required values.
- Illustrated conceptually by a recipe, though computer algorithms frequently involve iterative steps and logical or comparison decisions.
- Executing an algorithm correctly will fail to solve a problem if the underlying algorithm is flawed or inappropriate for the task.
- Fundamental to computer information processing; software programs are essentially algorithms providing explicit instructions in exact order.
Core Characteristics of Algorithms:
- Exactness: Every step must be exact, precise, and unambiguously described to eliminate uncertainty.
- Termination: Must terminate after a finite number of steps to provide a solution; endless loops must be strictly avoided.
- Effectiveness: Must generate correct results at all times.
- Generality: Must successfully solve every instance of a given problem.
- Uniqueness: Outcomes of each step must be uniquely defined, depending solely on the input and results of preceding steps.
- Finiteness: Stops after executing a finite quantity of instructions.
- Output: Must always produce an output.

Expressing Algorithms and Flowchart Conventions

Methods for Expressing Algorithms:
- Human Language:
- Describes operational steps using natural language rather than formal code or mathematical notation.
- Designed to make logic understandable to individuals without technical syntax requirements or specific software tools.
- Pseudocode:
- An informal, high-level description of the operational principles of an algorithm or program.
- Details actions to be executed and their exact execution order.
- Employs the structural conventions of programming languages while prioritizing human readability over machine execution.
- Omits low-level details such as variable declarations, system-specific code, and subroutines.
- Commonly used in textbooks, scientific literature, and initial planning phases to outline program structure before coding.
- Example Pseudocode Structure:
  1. Start the program
  2. Enter two numbers $X$ , $Y$
  3. Multiply the two numbers together
  4. Print product
  5. End program
- Flowchart:
- A diagrammatic representation of an algorithm, workflow, or process.
- Displays individual steps using various geometric boxes and specifies execution order using connecting arrows.
- Provides a visual model for analyzing, designing, documenting, or managing processes and software programs.
Flowchart Symbol Standards:

Terminal: Indicates the starting and ending points of a set of computer-related processes.
Input/Output: Denotes any input or output operation.
Computer Processing: Shows processing tasks performed by a computer system.
Predefined Processing: Indicates a process or procedure not specifically defined within the current flowchart.
Comment: Used to write explanatory text or clarify specific flowchart elements.
Flow Line: Connects symbols together, establishing execution direction and sequence.
Document Input/Output: Used when input originates from a physical or digital document, or when output is routed to a document.
Decision: Represents a logical point in a process where a decision determines subsequent actions.
On-page Connector: Connects flowchart paths continuing on the same page.
Off-page Connector: Connects flowchart paths continuing onto separate pages.