Introduction to Computers, Data Representation, and Program Execution

Fundamentals of Computing and Hardware Architecture

Definition of a Computer:
- A computer is a general-purpose electronic device that can be programmed to carry out a finite set of arithmetic or logical operations.
- Because the sequence of operations can be readily changed, a computer can solve more than one kind of problem, distinguishing it from single-purpose devices.
- Core functional capabilities include:
- Taking input from users or external devices.
- Processing the input according to programmed instructions.
- Storing information internally or externally if required.
- Producing output for users or downstream systems.
Computers Versus Basic Calculators:
- A basic calculator is hard-coded to perform only a fixed, pre-wired set of mathematical functions.
- A computer is fully programmable and designed to perform any computational task instructed by software.
Core Axioms of Computing:
- There is no magic to computing.
- Computers do not have minds of their own; humans must tell them exactly what to do.
- Computers follow instructions completely and precisely.
Definitions of Core Roles and Concepts:
- Program: A set of sequential instructions that a computer follows to perform a designated task. Commonly referred to as software.
- Programmer / Software Developer: A person who possesses the technical capability to design, create, and test computer programs.
Major Hardware Components:
- Hardware refers to the physical, tangible devices that make up a computer system.
- A computer operates as a cooperative system composed of several major interconnected components:
- Central Processing Unit ( $\text{CPU}$
- Main memory ( $\text{RAM}$
- Secondary storage devices
- Input and output devices
**The Central Processing Unit ( $\text{CPU}$
- The $\text{CPU}$ is the internal component that executes instructions and actually runs programs.
- It serves as the most critical hardware unit; without it, software cannot execute.
- Historical Form vs. Microprocessors:
- Early computers relied on massive $\text{CPUs}$ that occupied entire rooms or large multi-cabinet enclosures.
- Microprocessor: A complete $\text{CPU}$ fabricated on a single small silicon semiconductor chip. It represents the modern physical implementation of the theoretical $\text{CPU}$ architecture.
**Main Memory ( $\text{RAM}$
- Role: Serves as the immediate workspace where the computer stores a program while that program is actively running, alongside the active data utilized by the program.
- Nomenclature: Referred to as Random Access Memory ( $\text{RAM}$ .
- Performance: The $\text{CPU}$ can access arbitrary memory locations in $\text{RAM}$ at high speeds.
- Volatility: Main memory is volatile memory; its storage is strictly temporary during active operation, and its contents are entirely erased when the computer loses electrical power.
Secondary Storage Devices:
- Secondary storage is non-volatile memory designed to hold programs and data reliably over extended periods.
- Operating systems and software programs reside permanently in secondary storage and are dynamically loaded into main memory ( $\text{RAM}$ ) only when execution is required.
- Categories of Secondary Storage:
- Magnetic Disk Drive: Magnetically encodes and reads binary data on spinning circular platters.
- **Solid-State Drive ( $\text{SSD}$
  - Operates significantly faster than magnetic disk drives due to having zero moving mechanical parts.
  - Constructed from millions of microscopic transistors termed $\text{NAND}$ flash memory cells, which trap electrical charges to represent stored bits.
- Flash Memory: Portable solid-state media (utilized in $\text{USB}$ pen drives, smartphones, and memory cards) built upon $\text{NAND}$ flash architecture.
- Optical Devices: Media such as $\text{CDs}$ and $\text{DVDs}$ that read and write data patterns optically via lasers.
Input and Output ( $\text{I/O}$ ) Devices:
- Input Devices:
- Defined as components that collect data from human users, the physical environment, or other external devices.
- Examples include keyboards, mice, touchscreens, scanners, and digital cameras.
- Disk drives operate in an input capacity when retrieving stored programs or files to load them into main memory.
- Output Devices:
- Components responsible for formatting and presenting processed data to users or transmitting it to external hardware.
- Formats of output include text, visual images, audio signals, or raw bit streams.
- Standard output hardware includes visual display monitors and printers.
- Storage drives (such as magnetic hard drives and $\text{USB}$ flash drives) function as output devices when the $\text{CPU}$ transmits processed data to be saved onto them.
Software Taxonomy:
- Everything executed by computer hardware is directed by software, divided into two broad categories:
- Application Software: Programs engineered to make the computer productive for human everyday tasks (e.g., word processors, email clients, video games, and web browsers).
- System Software: Programs that manage, coordinate, and control the foundational low-level operations of the hardware:
  - *Operating System ( $\text{OS}$
  - Directly manages hardware resources, device allocation, and program scheduling.
  - Utility Programs:
  - Specialized tools designed to safeguard data or optimize performance (e.g., antivirus suites, disk defragmenters).
  - Software Development Tools:
  - Specialized utilities utilized by developers to create, debug, and translate programs (e.g., compilers, assemblers, and Integrated Development Environments [IDEs] such as VS Code and Codeblocks).

Data Representation and Binary Systems

The Bit as a Fundamental Unit:
- All data inside modern computers is stored as sequences of binary digits: 0s and 1s (bits).
- A bit is a microscopic physical electronic component that holds an electrical charge representing one of two discrete voltage levels, functioning analogously to a two-position light switch (ON or OFF).
- An individual byte consists of exactly $8$ bits.
- A single byte provides sufficient memory capacity to represent an individual typographic character or a small integer.
Binary Number System Mechanics:
- Computers implement a positional base- $2$ (binary) number system.
- For an $n$ -bit integer, each bit position $j$ (indexed from right to left, starting at position index $0$ up to $n-1$ ) carries a positional weight equivalent to $2^j$ (or $2^{j-1}$ if position index numbering starts at $1$ ):
- Bit position $0$ : $2^0 = 1$
- Bit position $1$ : $2^1 = 2$
- Bit position $2$ : $2^2 = 4$
- Bit position $3$ : $2^3 = 8$
- Bit position $4$ : $2^4 = 16$
- Bit position $5$ : $2^5 = 32$
- Bit position $6$ : $2^6 = 64$
- Bit position $7$ : $2^7 = 128$
- The decimal equivalent of any binary sequence is determined by summing the positional values corresponding to every bit set to 1.
- Single Byte Capacity Limits:
- Minimum value ( $8$ bits off, 00000000): $0$
- Maximum value ( $8$ bits on, 11111111): $128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255$
- Storing values greater than $255$ requires grouping multiple contiguous bytes together in memory.
Worked Numerical Conversion Examples:
- Conversion of $1011_{(2)}$ to Decimal: $\text{Position 3: } 1 \times 2^3 = 8$ $\text{Position 2: } 0 \times 2^2 = 0$ $\text{Position 1: } 1 \times 2^1 = 2$ $\text{Position 0: } 1 \times 2^0 = 1$ $\text{Sum} = 8 + 0 + 2 + 1 = 11_{(10)}$
- Conversion of $10011101_{(2)}$ to Decimal: $\text{Bit at position } 7 \, (2^7) = 128$ $\text{Bit at position } 6 \, (2^6) = 0$ $\text{Bit at position } 5 \, (2^5) = 0$ $\text{Bit at position } 4 \, (2^4) = 16$ $\text{Bit at position } 3 \, (2^3) = 8$ $\text{Bit at position } 2 \, (2^2) = 4$ $\text{Bit at position } 1 \, (2^1) = 0$ $\text{Bit at position } 0 \, (2^0) = 1$ $\text{Total Sum} = 128 + 16 + 8 + 4 + 1 = 157_{(10)}$

Binary to decimal conversion using toggle switches

Character Encoding Schemes:
- Textual characters cannot be stored natively; they are mapped to numeric codes, which are subsequently stored as binary bit patterns.
- ASCII (American Standard Code for Information Interchange):
- Historically dominant encoding standard defining codes for exactly $128$ characters (decimal values $0$ through $127$ ).
- Character mappings encompass:
  - Control characters ( $0$ to $31$ and $127$ ): Non-printing commands such as NUL (null, $0$ ), SOH (start of heading, $1$ ), STX ( $2$ ), ETX ( $3$ ), EOT ( $4$ ), ENQ ( $5$ ), ACK ( $6$ ), BEL ( $7$ ), BS (backspace, $8$ ), TAB ( $9$ ), LF (line feed, $10$ ), VT ( $11$ ), FF ( $12$ ), CR (carriage return, $13$ ), ESC (escape, $27$ ), and DEL ( $127$ ).
  - Printable symbols and digits ( $32$ to $63$ ): Space ( $32$ ), punctuation marks, and numeric digits 0 to 9 (decimal $48$ through $57$ ).
  - Uppercase Latin alphabet ( $65$ to $90$ ): Character 'A' corresponds to decimal $65$ , mapped to binary 01000001 ( $64 + 1$ ); sequentially extends to 'Z' ( $90$ ).
  - Lowercase Latin alphabet ( $97$ to $122$ ): Character 'a' corresponds to decimal $97$ ; sequentially extends to 'z' ( $122$ ).
- Unicode:
- Advanced universal standard developed to overcome the $128$ -character limit of ASCII.
- Fully backwards compatible with ASCII while providing code points for characters, symbols, and scripts from virtually all written world languages.

ASCII encoding of character A

Encoding Other Digital Media Types:
- The term digital applies to any hardware platform that represents and stores data strictly as binary sequences.
- Digital Imagery:
- Composed of a matrix of tiny spatial elements called pixels.
- To store an image, each pixel is converted into a binary number representing its specific color channel values.
- Digital Audio/Music:
- Composed of continuous sound waves divided into small, sequential discrete time intervals called samples.
- Each audio sample is digitized by converting its instantaneous amplitude into a representative binary number.

Program Execution and the CPU Instruction Cycle

CPU Architecture and Machine Instructions:
- The $\text{CPU}$ is physically engineered to execute a predefined set of simple atomic operations directly on data, including:
- Reading data from memory.
- Basic arithmetic: adding, subtracting, multiplying, and dividing numbers.
- The $\text{CPU}$ only understands instructions formatted in its native machine language, configured within its hardware instruction set.
- Instruction sets are brand- and architecture-specific; each class of processor implements its own unique machine language.
- To accomplish meaningful, high-level computational work, the $\text{CPU}$ must execute millions of these primitive atomic operations in rapid sequence.
Flow of Information During Execution (e.g., Water Bill Calculation):
- Step 1 (Input Phase): Input data (such as raw utility meter readings) is entered via an input device (e.g., keyboard) and directed into memory.
- Step 2 (Processing Phase): The $\text{CPU}$ accesses both the machine language program instructions and the input data stored in memory. It computes results and transfers the calculated output back into dedicated memory structures.
- Step 3 (Output Phase): The program output (the final water bill document) is dispatched from memory to an output device (such as a visual display monitor or printer).

Information flow during program execution

Loading from Storage to Memory:
- A computer program permanently resides on secondary storage media (such as a hard disk drive or solid-state drive).
- Each time the program is executed, it must be copied across data buses from secondary storage into volatile main memory ( $\text{RAM}$ ) so the $\text{CPU}$ can access its instructions at high speed.

Program loading from secondary storage to RAM and execution by CPU

The Three-Step Fetch-Decode-Execute Cycle:
- The $\text{CPU}$ executes programs by continuously repeating a foundational hardware processing loop:
1. Fetch:
  - The $\text{CPU}$ reads the next binary instruction in the sequence from main memory ( $\text{RAM}$ ) into internal processor registers.
2. Decode:
  - The internal electronic control circuitry decodes the binary instruction bit pattern to determine which operation must be carried out.
  - If the instruction requires operands, the $\text{CPU}$ fetches the necessary data variables from memory.
3. Execute:
  - The $\text{CPU}$ executes the determined operation (e.g., performing arithmetic or routing data between registers), completing the instruction cycle before advancing to the next cycle.

The Fetch-Decode-Execute CPU cycle

The Computational Gap and Levels of Abstraction

The Computational "Gap":
- Represents the structural divide between human-centric conceptual problem descriptions (such as word processing, playing interactive video games, and browsing websites) and low-level physical implementation on silicon (10101101...).
The Layered Hierarchy of Abstraction:
- Bridging the gap requires traversing multiple successive engineering layers:
- Problems: Real-world human challenges requiring computational solutions.
- Algorithms: Systematic step-by-step mathematical and logical procedures.
- Language (Program): Formal programmable syntax translating algorithms into code.
- Machine (ISA) Architecture: Instruction Set Architecture ( $\text{ISA}$ ; the computer-specific hardware-software interface boundary specifying available instructions, addressing modes, and registers.
- Microarchitecture: The manufacturer-specific internal structural design that physically realizes the $\text{ISA}$ (e.g., pipelining, execution units, cache layouts).
- Circuits: Digital logic configurations constructed from interconnected logic gates.
- Devices: Physical solid-state components (silicon transistors) governed by semiconductor physics.
- Descending through these layers introduces increasing structural constraints and specific engineering choices.

The abstraction hierarchy for overcoming the computational gap

Why Natural Languages Are Unsuitable for Computer Programming:
- Natural human languages cannot be used to program machines due to three critical structural deficiencies:
- Incomplete: Natural languages lack specialized syntactic constructs, vocabulary, and rigid structures required to express deterministic computer procedures.
- Imprecise: Natural languages contain vast numbers of synonyms and descriptive variations for identical concepts, preventing direct, unambiguous translation into discrete machine instructions.
- Ambiguous: The most completely unacceptable property for computing. Humans infer the meaning of ambiguous statements using non-textual cues such as vocal tone, inflection, physical context, and shared cultural knowledge—mechanisms completely unavailable to mechanical computers.

Algorithms and Program Development

Formal Definition and Properties of an Algorithm:
- An algorithm is a rigorous, step-by-step procedural sequence designed to solve a specified computational problem.
- Every valid algorithm must strictly satisfy three properties:
- Finiteness: The procedure must guarantee termination after a finite number of discrete execution steps.
- Definiteness: Each individual step within the sequence must be precisely, rigorously, and unambiguously defined.
- Effective Computability: Every step must be fundamentally feasible, mechanical, and capable of being carried out exactly.
Standard Algorithmic Problem Examples:
- Algorithm for determining the largest $N$ numbers within an arbitrary dataset.
- Algorithm for sorting names into strictly alphabetical sequence.
- Algorithm for searching and locating a specific target data element within a massive collection of items.
Characteristics of Programming Languages:
- The operational step following algorithm design is converting the algorithmic logic into a software program using a formal programming language.
- Programming languages communicate directly with computing hardware through strict grammatical rules.
- They are purely mechanical rather than organic, ensuring that all valid statements are free of ambiguity.
- Over $1,000$ distinct programming languages exist, each optimized for specific problem domains:
- Financial processing and automated business reporting (e.g., COBOL).
- Manipulation of symbolic lists and declarative expressions (e.g., Lisp).
- Natural language processing and artificial intelligence.

Programming Language Hierarchy and Translation Systems

Language Classification: Low-Level vs. High-Level:
- Low-Level Languages (LLL):
- Machine Language: Binary sequences (10100001...) processed natively by the $\text{CPU}$ . Writing programs directly in machine code is impractically slow, error-prone, and cognitively difficult for humans.
- Assembly Language:
  - Replaces raw binary sequences with short alphanumeric mnemonic codes (e.g., mov eax, Z, add eax, 2, mov Y, eax).
  - Greatly simplifies low-level manual programming.
  - Requires an Assembler—a specialized utility program that translates assembly mnemonics into matching binary machine language instructions.
- High-Level Languages (HLL):
- Examples include C, C++, Java, and Python.
- Enable software engineers to author complex, powerful applications quickly without intimate knowledge of internal $\text{CPU}$ circuitry or writing granular assembly instructions.
- Intuitive, structured, and human-readable.

Assembler translating assembly language to machine code

Core Terminology in High-Level Languages:
- Key Words: Reserved words with predefined meanings hardcoded into the language's grammar; they cannot be redefined for arbitrary variables.
- Operators: Syntactic symbols that perform specific computational actions or data manipulations (e.g., mathematical symbols like +, -, *, /).
- Syntax: The strict set of formal structural and grammatical rules governing how valid statements must be written.
- Statement: An individual instruction expressing a complete operation in a high-level language.
- Source Code: The human-readable collection of statements written by a programmer.
- Syntax Error: A code defect resulting from a violation of the language's syntax rules; it completely halts the translation process.
Levels of Translation (Example Workflow):
- An algorithm conceived by a human is initially translated manually into high-level C code: c = a + b;
- A compiler translates the C statement into assembly language: ADD r0, r1, r2
- An assembler translates the assembly code into machine language bits: 0010110010010001111
- The physical machine executes the binary instructions directly on the processor.

Levels of translation from algorithm to execution

Comparison of Translation Paradigms: Compilers versus Interpreters:
- Compilers:
- Process and translate an entire high-level program file into a separate, standalone machine language executable file before execution.
- Once compilation is complete, the resulting binary executable can run on any compatible hardware system independently.
- Does not require the presence of the original source code or the compiler during subsequent executions.
- Interpreters:
- Translate and execute source code instructions dynamically on a line-by-line basis.
- Reads a single high-level statement, converts it to equivalent machine language, instructs the $\text{CPU}$ to execute it immediately, and then advances to the subsequent instruction.
- Does not create a persistent, separate machine language binary.
- Used by languages such as Python.
- Requires distributing the raw source code along with the interpreter software to execute the program on different machines.

Compilation process from high-level code to machine language

Interpretation and immediate execution of high-level code

Questions & Discussion

In-Class Discussion: Checking if an Integer is Odd or Even:
- Problem: Formulate the operational logic required to evaluate whether an arbitrary input integer is odd or even.
- Core Logical Consideration: Testing the mathematical divisibility of the number by $2$ (evaluating the remainder via modulo arithmetic $n \pmod 2$ or inspecting the least significant binary bit at position $2^0$ ).
Think Prompt: Primality Testing:
- Problem: Formulate an algorithm to determine whether a given integer is prime or composite.
- Conceptual Scope: Developing a finite, definite procedure to verify that the integer has no positive divisors other than $1$ and itself, considering efficiency beyond brute-force trial division up to $n-1$ .