Data, Data Structures & Algorithms

All computer programs fundamentally perform a single task: transforming input data into output information using structured sequences of instructions. Understanding the distinction between abstract contracts and physical memory layouts is the essential prerequisite for analyzing time and space efficiency.

By the end of this chapter, you will be able to:

• Differentiate between raw data, semantic information, and physical memory representations.
• Distinguish between an Abstract Data Type (ADT) and its concrete data structure implementation.
• Evaluate algorithms against Donald Knuth's 5 cardinal criteria for computational validity.
• Articulate the distinction between platform-independent algorithmic complexity and hardware-dependent program execution.
• Apply the 7-stage algorithm design pipeline to formalize problems from constraints to verified implementations.

---

In computer science, Data consists of raw, unorganized symbols, numbers, characters, or bit patterns collected without semantic context. Data carries no inherent meaning until it is structured, processed, and contextualized into Information.

1. Atomic (Primitive) Data: Indivisible values directly manipulated by hardware ALU instructions:
   • Integers ($\mathbb{Z}$): Two's complement representation (e.g., 42, -107)
   • Floating-Point: IEEE 754 standard (e.g., 3.14159)
   • Characters: Fixed-width ASCII or variable-width UTF-8 code points
   • Booleans: Single-bit logical states ($\{0,1\}$)
2. Composite (Non-Primitive) Data: Structured aggregations of atomic elements:
   • Arrays, Structs, Strings, Tuples, and Unions

---

A fundamental architectural principle of software engineering is the separation of interface from implementation.

• Abstract Data Type (ADT): The mathematical specification of what operations are supported, their parameter contracts, and their behavioral invariants, independent of memory layout.
• Concrete Data Structure: The physical memory organization (contiguous blocks, pointer-linked heap nodes, or indexed buffers) that executes those operations in RAM.

---

An Algorithm is a finite, deterministic sequence of well-defined computational instructions that transforms valid inputs into verified outputs.

Every computational procedure operates within three interdependent boundaries:

1. Data Model (Structure): Dictates whether memory access is contiguous ($O(1)$ cache lines) or pointer-chasing ($O(n)$ memory latency).
2. Time Complexity (CPU): The count of elementary machine operations executed as input size $n$ grows.
3. Space Complexity (RAM): The auxiliary memory allocated for stack frames, heap buffers, and auxiliary metadata.

---

To be considered formally sound and production-ready, any procedure must satisfy Donald Knuth's 5 Cardinal Criteria:

1. Input: Must accept zero or more externally supplied parameters from a well-defined domain.
2. Output: Must yield at least one quantity mathematically related to the inputs.
3. Definiteness (Unambiguity): Each instruction must be clear, deterministic, and impossible to misinterpret.
4. Finiteness: The procedure must terminate after a finite number of steps for all valid inputs. An infinite process is not an algorithm.
5. Effectiveness (Feasibility): Each step must be sufficiently basic that it could in principle be executed by a human using paper and pencil in finite time.

• Correctness: Guarantees valid output for all boundary conditions, null inputs, and extreme scale.
• Robustness: Gracefully reports errors on invalid inputs rather than causing undefined behavior.
• Asymptotic Optimality: Minimizes the growth rate of runtime $T(n)$ and space $S(n)$.

---

---

Professional engineers follow a disciplined, 7-stage workflow when engineering computational solutions:

1. Problem Formalization: Identify input constraints, data types, value ranges, and explicit output guarantees.
2. Resource Budgeting: Ascertain target hardware constraints (RAM limits, 1-second CPU budget $\approx 10^8$ operations).
3. Paradigm Selection: Evaluate design strategies (Divide & Conquer, Greedy Choice, Dynamic Programming, Backtracking, Two Pointers).
4. Formulate Invariants: Specify step-by-step state transitions and formulate inductive loop invariants.
5. Proof of Correctness: Prove that the invariant holds on initialization, is maintained across iterations, and establishes correctness on termination.
6. Asymptotic Analysis: Derive worst-, average-, and best-case bounds for time $T(n)$ and auxiliary space $S(n)$.
7. Implementation & Validation: Code the solution cleanly in the target language and verify boundary conditions with stress tests.

---

• Data Structures Shape Performance: The same logical data yields radically different performance profiles depending on whether it is stored in contiguous arrays or pointer-linked nodes.
• ADT Abstraction: Code to the ADT interface while selecting the concrete data structure that satisfies your runtime and memory budgets.
• Algorithms Transcends Syntax: Programming languages and frameworks change constantly, but algorithmic complexity and correctness invariants remain timeless.

---

1. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.), Section 1.1: Algorithms. Addison-Wesley.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 1: The Role of Algorithms in Computing. MIT Press.
3. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.4: Analysis of Algorithms. Addison-Wesley.