Introduction to Computer Science and Algorithmic Thinking

Core Concepts and Common Misconceptions of Computer Science

• Primary Misconceptions Regarding Computer Science:

  • Computer science is merely the study of computers.

  • Computer science is solely the study of how to write computer programs.

  • Computer science is strictly the study of the uses and applications of computers and software.

• Formal Definition of Computer Science:

  • Computer science is defined as the study of algorithms, which includes four fundamental domains:

  • Their formal and mathematical properties.

  • Their hardware realizations.

  • Their linguistic realizations.

  • Their practical applications.

• Core Objectives of Computational Study:

  • Comprehending the formal definition and properties of algorithms.

  • Formulating everyday processes into precise algorithmic steps.

  • Identifying whether an algorithm contains ambiguous instructions or operations that are not effectively computable.

  • Tracing the evolution of modern computer science from mathematical theories and mechanical devices to electronic computers.

Algorithmic Operations and Construction

• Informal Definition of an Algorithm:

  • An ordered sequence of instructions that is guaranteed to solve a specific, well-defined problem.

• Canonical Structure of an Informal Algorithm:

  • Step $1$: Perform action.

  • Step $2$: Perform action.

  • Step $3$: Perform action.

  • $\\dots$

  • Step $n$: Stop.

• Three Basic Types of Operations Used to Construct Algorithms:

  • Sequential Operations:

  • Executes a single, well-defined instruction or task in sequential order.

  • Conditional Operations:

  • Asks a specific question or tests a condition, and selects the subsequent operation based on the outcome of that answer.

  • Iterative Operations:

  • Provides looping instructions that instruct the computing agent to loop back and repeat the execution of a prior block of instructions rather than moving forward.

Practical Examples of Algorithms

• Algorithm for Preparing Morning Coffee:

  • Step $1$: Decide to make coffee.

  • Step $2$: Fill the kettle with water and turn it on.

  • Step $3$: Add a filter to the Coffee Maker machine.

  • Step $4$: Measure and add coffee grounds to the filter.

  • Step $5$: Pour the water into the machine's reservoir.

  • Step $6$: Allow the coffee to brew for the appropriate time.

  • Step $7$: Pour the coffee into a cup.

  • Step $8$: Add any desired extras like milk, sugar, or flavors.

  • Step $9$: Enjoy your coffee.

• Algorithm for Crossing the Street Safely:

  • Step $1$: Decide to cross the street.

  • Step $2$: Locate a designated crosswalk or intersection.

  • Step $3$:

  • If the signal indicates it is safe to cross (e.g., green light or walk signal), proceed to the next step.

  • If the signal indicates not to cross (e.g., red light or don't walk signal), wait.

  • Step $4$: Even if the signal indicates it is safe, look and check for oncoming vehicles from both directions.

  • Step $5$: Cross the street quickly and safely while maintaining awareness of unexpected hazards.

  • Step $6$: Continue walking until safely reaching the other side of the street.

  • Step $7$: Target reached; safely situated on the other side.

Algorithmic Problem Solving and Computing Agents

• Automation and Significance of Algorithms:

  • Formalizing an algorithm for a given problem enables the complete automation of its solution.

• Computing Agents:

  • Defined as any entity—whether a machine, robot, person, or physical object—that carries out the precise steps of an algorithm.

• Limits and Categories of Computational Problems:

  • Unsolvable problems: Certain problems mathematically cannot be solved by any algorithm.

  • Inefficient solutions: Some problems have algorithmic solutions that execute too slowly to be practical.

  • Unknown solutions: Some problems do not yet have known algorithmic solutions.

• Historical Revolutions in Human Productivity:

  • The Industrial Revolution ($19\text{th}$ century): Mechanized and automated repetitive physical tasks.

  • The Computer Revolution ($20\text{th}$ and $21\text{st}$ centuries): Mechanized and automated repetitive mental tasks through algorithms implemented on computer hardware.

Formal Definition and Formal Properties of Algorithms

• Rigorous Definition of an Algorithm:

  • A well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.

• Structural Components of the Formal Definition:

  • Well-Ordered Collection:

  • The sequence is clear and unambiguous such that upon finishing any given operation, the computing agent explicitly knows which operation to execute next.

  • Unambiguous Operation (Primitive):

  • An instruction that can be understood directly by the computing agent without requiring further explanation, breakdown, or simplification.

  • Effectively Computable Operation:

  • It is insufficient for an instruction to merely be understandable; it must also be physically and logically doable by the computing agent.

  • Examples of Ambiguous/Non-computable Statements:

    • "Go back and do it again" (Ambiguous: fails to specify what task to repeat).

    • "Start over" (Ambiguous: fails to specify from which step to restart).

  • Result Production and Finite Halting:

  • Observable Output: To verify correctness, an algorithm must yield an observable outcome for the user, such as:

    • A numerical answer.

    • A newly created object.

    • A change in the external environment.

  • Halting Condition: The algorithm must terminate after a finite number of steps.

  • Infinite Loop: An execution cycle that fails to halt and runs indefinitely; typically represents a logic error in algorithmic design.

History of Computing: The Early Period (Up to 1940)

• Seventeenth-Century Developments (Mechanical Automation of Arithmetic):

  • John Napier ($1614$): Invented logarithms to simplify complex mathematical calculations involving multiplication and division.

  • Invention of the Slide Rule ($c.\,1622$): Created as a mechanical analog calculation device based on logarithmic scales.

  • Blaise Pascal ($1642$): Designed and built the Pascaline, an early mechanical addition and subtraction calculator.

• Gottfried Leibnitz ($1673$): Constructed a mechanical calculator known as Leibnitz's Wheel capable of multiplication and division.

• Limitations of Seventeenth-Century Calculating Devices:

  • Could represent numbers using physical components like gears and dials.

  • Could perform basic arithmetic operations.

  • Lacked internal memory to store data or intermediate calculated values.

  • Were non-programmable (users could not input a sequence of instructions to be executed automatically).

  • Nineteenth-Century Developments (Punched Cards and Programmability):

• Joseph Jacquard ($1801$): Designed an automated mechanical loom controlled by perforated punched cards to weave complex textiles and patterns automatically.

• Herman Hollerith ($1880\text{s}$ onward):

  • Developed electromechanical punched card processing machines to tabulate, tally, and sort census data for the U.S. Census Bureau.

  • Founded the Computer-Tabulating-Recording Company, which was renamed International Business Machines (IBM) in $1924$

  • Charles Babbage and Mechanical Computing Architecture:

• Difference Engine ($1823$):

  • Mechanical calculating machine engineered to calculate polynomial functions and solve complex mathematical equations.

  • Capable of addition, subtraction, multiplication, and division accurate to six significant digits.

• Analytical Engine:

  • Fully designed programmable mechanical computer that was never physically completed during Babbage's lifetime.

  • Designed with structural components directly analogous to modern digital computer architecture:

    • Mill: Arithmetic/Logic Unit (ALU).

    • Store: Memory storage.

    • Operator: Central Processor.

    • Output Unit: Input/Output interface.

• Summary of Nineteenth-Century Advances:

  • Remained entirely mechanical in operation.

  • Introduced essential computing principles: digital representation of numbers, manipulation operations, stored memory, and step-by-step programmability.

History of Computing: The Birth of Computers (1940–1950)

• Major Early Computing Systems:

  • Mark I ($1944$): Electromechanical computer relying on a hybrid system of physical relays, electrical magnets, and mechanical gears for data processing and storage.

  • Colossus ($1943$): Special-purpose electronic device developed with contributions from Alan Turing to decipher high-level encrypted German communications for the British Enigma project.

  • ENIAC (Electronic Numerical Integrator and Calculator) ($1946$): Unveiled as the first publicly known fully electronic, general-purpose computer.

• Stored Program Architecture and Commercialization:

  • John Von Neumann:

  • Formulated the stored-program computer model where both data and program instructions reside together in central computer memory.

  • EDVAC ($1949$):

  • Built at the University of Pennsylvania as one of the earliest operational stored-program computers based on Von Neumann's design.

  • UNIVAC I:

  • Commercialized iteration of EDVAC architecture, becoming the first mass-produced commercial computer system.

  • Architectural Influence:

  • Modern digital computer architectures overwhelmingly utilize the fundamental Von Neumann architecture.

History of Computing: The Modern Era (1950 to Present)

• First Generation of Computing ($1950\text{--}1957$):

  • Hardware Basis: Vacuum tubes utilized for computational processing and memory circuitry.

• System Characteristics: Extremely large room-sized footprints, high cost, fragile components generating significant heat, requiring climate-controlled environments and specialized technical operators.

  • Second Generation of Computing ($1957\text{--}1965$):

• Hardware Basis: Transistors replaced vacuum tubes for logic gates, and magnetic core memories were introduced.

• Software Innovations: Development of early high-level programming languages, including FORTRAN and COBOL.

  • Third Generation of Computing ($1965\text{--}1975$):

• Hardware Basis: Invention and integration of Integrated Circuits (ICs).

• Industry Milestones: Appearance of the first desk-sized minicomputers (replacing massive room-sized mainframes) and the formal establishment of an independent commercial software industry.

  • Fourth Generation of Computing ($1975\text{--}1985$):

• Hardware Basis: Microprocessors containing complete central processing units on single silicon chips.

• Technological Advances: Introduction of desktop microcomputers (personal computers), broad distribution of computer networking, electronic mail (email), Graphical User Interfaces (GUIs), and embedded computing systems.

  • Fifth Generation of Computing ($1985\text{--}\text{Present}$):

• Computational Capabilities: Massively parallel processing architectures capable of performing quadrillions ($10^{15}$) of floating-point operations per second.

• Key Technologies: Handheld mobile and digital systems, widespread wireless networking, high-capacity cloud storage infrastructure, ubiquitous computing, advanced multimedia systems (incorporating real-time audio, video, and voice synthesis), ultra-high-definition graphics, and virtual reality implementations.