Introduction to Computing Science: Comprehensive Review

Vocabulary practice flashcards covering core topics in Introduction to Computing Science, including binary representation, computing history, digital logic gates, von Neumann architecture, RAPTOR programming, search and sort algorithms, operating system process and memory management, and file system disk scheduling.

Positional Notation

A system of expressing numbers where the value of each digit depends on its position relative to the base $R$, computed as $\sum d_i \times R^i$.

Analog Data

A continuous representation of information that is analogous to the actual physical information it represents.

Digital Data

A discrete representation of information accomplished by breaking the information up into separate, distinct elements.

Reclocking

The periodic process of restoring a degrading digital signal back to its original sharp, distinct shape before too much signal degradation occurs.

Two's Complement

A binary representation of negative integers where the leftmost bit represents the sign ($1$ for negative, $0$ for positive), possessing only a single representation for zero and allowing addition and subtraction to be performed with identical hardware.

Number Overflow

A situation that occurs when a computed mathematical value cannot fit into the predetermined number of bits allocated for storage.

Floating Point Representation

A numeric format used to store real numbers on computers composed of a sign bit, a mantissa, and an exponent ($\text{sign} \times \text{mantissa} \times 2^{\text{exp}}$).

Character Set

A defined list of characters paired with the specific binary bit strings used to represent each character in memory.

ASCII

The American Standard Code for Information Interchange, which originally allocated $7$ bits per character to represent $128$ unique characters and later evolved into the $8$-bit Latin-1 Extended ASCII supporting $256$ characters.

Unicode

A $16$-bit character encoding standard designed to represent over $65{,}000$ characters from every written language in the world, built as a superset of ASCII whose first $256$ characters correspond to extended ASCII.

Compression Ratio

The mathematical ratio of the size of compressed data divided by the size of the original data, indicating how much storage reduction has occurred.

Keyword Encoding

A lossless text compression method wherein frequently appearing words in a document are substituted with single special characters not found elsewhere in the text.

Run-Length Encoding

A lossless compression technique (also known as recurrence coding) where repeated sequences of identical characters are replaced by a flag character, the character itself, and a count digit.

Huffman Encoding

A variable-length character encoding scheme that assigns shorter bit sequences to frequently occurring characters and longer sequences to infrequent characters, ensuring no bit string is a prefix of another.

Sampling Rate

The frequency at which an analog audio signal's voltage is measured per second; a rate of approximately $40{,}000$ times per second is sufficient to reproduce acceptable digital audio without noticeable human ear distortion.

Color Depth

The amount of data (expressed in number of bits) used to represent a color; TrueColor uses a $24$-bit depth ($8$ bits each for red, green, and blue) representing over $16.7$ million colors, while HiColor uses a $16$-bit depth.

Pixel

Short for picture element, it is an individual colored dot that forms the basic building block of digitized raster pictures.

Raster Graphics

A digital image format (such as BMP, GIF, and JPEG) that stores graphical data on a pixel-by-pixel basis.

Vector Graphics

A graphics format that represents images using mathematical formulas describing lines and geometric shapes, allowing images to be resized dynamically without loss of clarity.

Video Codec

A compressor/decompressor software tool utilizing spatial compression (reducing redundant blocks within a single frame) and temporal compression (storing only delta frame changes relative to a keyframe) to shrink video files.

Mechanical Procedure

A defined step-by-step procedure that can be executed routinely without requiring independent judgment or thought.

Algorithm

A precise, unambiguous, executable, and ordered mechanical procedure that is guaranteed to finish eventually.

Abacus

The earliest computing device that stores data via bead positions on rods but requires a human operator for rule execution control.

Pascal's Calculator

A mechanical gear-driven calculator designed by Blaise Pascal in France to perform addition and subtraction directly via its internal gear structure.

Stepped Reckoner

Gottfried Wilhelm Leibniz's gear-driven calculator that mechanizes addition, subtraction, multiplication, and division; Leibniz also proposed the binary system inspired by the Tai Chi symbol.

Difference Engine

A special-purpose mechanical calculator designed by Charles Babbage to compute mathematical tables by using the method of differences.

Ada Lovelace

The British mathematician historically recognized as the world's first programmer for creating and publishing an algorithm intended to run on Babbage's Analytical Engine.

Punched Card

A stiff paper card containing holes punched in specific patterns to represent data and algorithmic instructions, originated by Joseph Jacquard and utilized by Herman Hollerith for the 1890 U.S. census.

ENIAC

The Electronic Numerical Integrator and Computer, a pioneering early general-purpose electronic digital computer built with vacuum tubes at the University of Pennsylvania.

Transistor

A solid-state semiconductor switching device invented at Bell Labs in 1947 featuring three terminals (source, base, emitter) that replaced fragile, hot vacuum tubes.

Logic Gate

A fundamental electronic hardware component that accepts one or more electrical binary input signals and outputs a single binary signal based on a Boolean operation.

XOR Gate

A logic gate whose Boolean expression is $X = A \oplus B$, yielding an output of $1$ if exactly one input is $1$, and $0$ if both inputs are identical.

Combinational Circuit

A digital circuit whose output values at any instant are determined entirely and directly by the current input values without internal memory.

Sequential Circuit

A digital circuit whose output is a function of both the current input signals and the circuit's prior internal state, enabling data storage.

Half Adder

A combinational circuit that adds two individual binary input bits ($A$ and $B$) and produces two outputs: a sum bit ($\text{Sum} = A \oplus B$) and a carry bit ($\text{Carry} = A \cdot B$).

Full Adder

A combinational circuit that adds two binary input bits along with an incoming carry-in bit, producing a sum output bit and a carry-out output bit.

Multiplexer

A circuit that directs one of several input data lines ($D_0$ through $D_n$) to a single output line based on the binary configuration of select control lines.

S-R Latch

A basic sequential memory circuit constructed with cross-coupled feedback gates that stores a single bit of information, maintaining its state as long as inputs $S$ and $R$ are set to $1$.

Integrated Circuit

A small silicon semiconductor chip housing multiple interconnected gates, categorized by gate density into SSI ($1\text{--}10$), MSI ($10\text{--}100$), LSI ($100\text{--}100{,}000$), and VLSI (over $100{,}000$).

Moore's Law

The observation made by Gordon Moore in 1965 stating that the number of transistors placed on an integrated circuit chip doubles roughly every two years.

Von Neumann Architecture

A fundamental computer design framework based on the stored-program concept, containing a Central Processing Unit (ALU and Control Unit), Memory, and Input/Output units connected by a system bus.

Addressability

The specific number of bits stored in each individually addressable memory location of a computer (such as byte-addressable or word-addressable).

Program Counter

A dedicated register located inside the CPU control unit that holds the memory address of the next instruction to be fetched and executed.

Instruction Register

A dedicated CPU register in the control unit that stores a copy of the instruction currently being decoded and executed.

Fetch-Execution Cycle

The continuous four-step operational sequence followed by a CPU: (1) Fetch the next instruction, (2) Decode the instruction, (3) Get data if needed, and (4) Execute the instruction.

RAM

Random Access Memory; volatile read/write main memory wherein each individual storage cell can be directly accessed, losing its stored bit values upon power termination.

ROM

Read Only Memory; non-volatile memory whose bit patterns are permanently burned during manufacture to store fundamental boot instructions.

Hard Disk Drive Geometry

The structural layout of a magnetic hard drive composed of spinning platters on a spindle, concentric tracks, pie-shaped sectors, and vertical cylinders serviced by moving read/write heads.

Access Time

The total elapsed duration required for a magnetic disk drive to read or write data, calculated as the sum of seek time (head movement to track) and latency (rotational delay of sector).

System Bus

A shared set of physical communication wires connecting the CPU, memory, and I/O devices, consisting of a data bus, address bus, and control bus.

Compiler

A systems program that translates source code written in a high-level programming language entirely into machine code ahead of time, allowing subsequent execution as an independent program.

Interpreter

A translating program that processes high-level programming instructions statement by statement, translating and immediately executing each instruction in sequence.

RAPTOR

A visual programming development environment created by Dr. Carlisle at the United States Air Force Academy based on executing flowcharts to design and test algorithms.

RAPTOR Symbols

The standard set of graphical blocks in RAPTOR, including input statements, assignment statements, procedure calls, output statements, selection blocks, and loop constructs.

Array

An ordered data structure that groups multiple related values of the same type under a single identifier, where individual items are referenced via a numerical index.

Parallel Arrays

Two or more distinct arrays whose corresponding elements at matching indices contain logically related information (such as student IDs and test scores).

Blocking Input

An input operation (such as Wait_For_Key or Get_Key) that suspends and halts program execution until the user supplies the requested keyboard or mouse action.

Nonblocking Input

A status-checking function (such as Key_Hit or Mouse_Button_Down) that immediately retrieves current peripheral hardware states without halting program flow.

Process Abstraction

The software engineering technique of encapsulating complex statement sequences into a named entity—such as a RAPTOR subchart or procedure—so it can be executed as a conceptual unit.

Procedure Parameter

A specialized variable defined within a procedure interface that receives values on invocation (Input) or passes computed values back to the calling routine (Output).

Brute-Force Algorithm

A problem-solving strategy that methodically enumerates every possible candidate in the search space and evaluates whether each candidate satisfies the problem constraints.

Modulo Operation

An arithmetic operation (denoted as mod or rem) that computes and returns the integer remainder of dividing one number by another.

Prime Number

A natural number strictly greater than $1$ that possesses no positive divisors other than $1$ and itself, testable by checking potential factors up to $\lfloor\sqrt{n}\rfloor$.

Substitution Cipher

A classical symmetric encryption technique wherein characters of a plaintext message are substituted systematically with corresponding characters from a defined ciphertext alphabet.

Recursion

A programming technique wherein a function or procedure calls itself repeatedly to solve smaller instances of the same problem until reaching a termination condition called a base case.

Towers of Hanoi

A classical mathematical puzzle involving moving $n$ graduated disks across three pegs from source to destination without placing a larger disk on a smaller one, solved recursively.

Linear Search

A sequential search algorithm that inspects list elements one by one from the beginning to find a target value, working on unsorted collections.

Binary Search

An efficient searching algorithm that operates on sorted data by repeatedly dividing the search space in half after comparing the key with the median element.

Selection Sort

An in-place comparison sorting algorithm that repeatedly identifies the smallest element from the unsorted segment of an array and swaps it with the element at the current index.

Bubble Sort

A sorting algorithm that steps through an array, compares adjacent pairs of elements, and swaps them if out of order, causing smaller values to gradually bubble to the top.

Operating System

The central core of system software that manages hardware resources (memory, CPU, I/O devices) and provides an execution environment and user interface.

Multiprogramming

The operating system technique of maintaining multiple programs simultaneously in main memory to compete for CPU access and maximize hardware utilization.

Process

A dynamic program in execution, maintained by the operating system through an allocated memory space, process control block, and lifecycle states.

Logical Address

A relative memory location assigned to a program or variable starting at offset $0$, which the operating system maps to a physical hardware memory address via address binding.

Base and Bounds Registers

A pair of CPU registers used in partition memory management; the base register holds the partition's starting physical address and the bounds register holds its total length.

Dynamic Partitions

A memory management scheme where partitions are dynamically created to match the exact size requested by incoming programs, leaving smaller free holes.

Partition Allocation Strategies

Algorithms that determine partition assignment: First Fit allocates the first sufficiently large hole, Best Fit allocates the smallest viable hole, and Worst Fit allocates the largest hole.

Compaction

The operating system process of relocating active programs in physical memory to consolidate fragmented free memory holes into a single continuous block.

Process States

The developmental stages of a process: New (creation), Ready (awaiting CPU dispatch), Running (executing instructions on CPU), Waiting (awaiting I/O or an event), and Terminated (execution complete).

Preemptive Scheduling

A CPU scheduling approach where the operating system can forcibly interrupt and move an actively running process back to the ready state to dispatch another task.

Turnaround Time

The total elapsed duration between when a process enters the ready state and when it completes execution for the last time.

Shortest Job Next

A nonpreemptive CPU scheduling algorithm that selects the ready process with the smallest estimated service time, provably minimizing average turnaround time.

Round Robin Scheduling

A widely used preemptive CPU scheduling algorithm that grants each ready process a fixed time slice (quantum) in circular order to ensure fair resource allocation.

File

A named collection of related data stored in secondary memory, recognized by the user as the smallest indivisible unit of non-volatile storage.

File System

The logical organizing mechanism provided by an operating system allowing users and applications to create, access, manage, and structure data as files and directories.

Binary File

A file formatted with application-specific bit organizations that requires a dedicated program to interpret and view, in contrast to character-encoded text files.

File Truncation

A file system operation that clears the contents and size of an existing file down to zero while preserving its entry and metadata in directory tables.

Direct Access

A file access technique allowing users to reposition the current file pointer directly to any designated logical record number to perform reads or writes out of order.

Directory Tree

A hierarchical organizational structure of nested directories and subdirectories extending downward from a primary root directory (C:\ in Windows or / in Unix).

Current Working Directory

The specific subdirectory in which the user or active process is currently operating in the file system hierarchy.

Absolute Path

A complete file path specification that begins explicitly at the root directory and traces every directory level down to the target file.

Relative Path

A file path specification defined relative to the current working directory, commonly using . for the current directory and .. for the parent directory.

Disk Scheduling

The technique employed by the operating system to prioritize and order pending magnetic disk input/output requests to minimize mechanical read/write head movement.

Shortest-Seek-Time-First

A disk scheduling algorithm that services the pending cylinder request closest to the current head position, which reduces average seek time but can cause starvation for distant requests.

SCAN Disk Scheduling

Also called the elevator algorithm, a disk scheduling method where heads sweep continuously between the spindle and outer platter edge, servicing requests along the path to prevent starvation.

LOOK Disk Scheduling

A variation of the SCAN disk scheduling algorithm where read/write heads only travel as far as the outermost and innermost pending cylinder requests before reversing direction.