Fundamentals of Computer Science and Python Programming Study Notes

Chapter 1 Objectives

  • Basic Features of an Algorithm: Describe the fundamental characteristics that define a computational process.
  • Hardware and Software Collaboration: Explain the relationship and interaction between physical components and instructional sets in computer architecture.
  • History of Computing: Summarize the evolution of computing from ancient aids to modern digital systems.
  • Python Programming: Compose and execute basic Python programs.

Introduction to Computer Technology

  • Pervasiveness of Computing: Computer technology is integrated into nearly all aspects of modern life, including video games, digital music, microwave ovens, cellular communications, and social networking.
  • Societal Role: It plays a vital role in entertainment, education, medicine, manufacturing, communications, government, and commerce.
  • Information Age: Society is currently characterized by an information-based economy and a "digital lifestyle."
  • The Study of Computer Science: Computer science is defined as the study of computation that enables this technology, focusing on the effective and appropriate use of computers to enhance human life.

Fundamental Ideas: Algorithms and Information Processing

  • Algorithms:

    • Informal Definition: An algorithm is like a recipe; it provides a set of instructions to perform a task (e.g., baking bread, making change, or assembling furniture).
    • Precise Definition: A sequence of steps that describes a computational process ending with a solution to a problem.
    • Example: Making Change (Method 1):
      1. Compute the difference between the purchase price and the amount given.
      2. Example: Purchase of 11 dozen eggs for $2.39\$2.39 with a $10\$10 bill results in a difference of $7.61\$7.61.
      3. The merchant selects coins and bills totaling $7.61\$7.61.
    • Example: Making Change (Method 2 - Counting Up):
      1. Start with the purchase price ($2.39\$2.39).
      2. Select coins to reach the next dollar amount ($0.61=3\$0.61 = 3 dimes, 11 nickel, 44 pennies).
      3. Select dollars to reach the next 55-dollar amount ($2\$2).
      4. Select a $5\$5 bill to reach $10\$10.
    • Example: Pencil and Paper Subtraction Algorithm:
      • Step 1: Write down the two numbers, larger above smaller, digits aligned in right-justified columns.
      • Step 2: Start with the rightmost column and work left.
      • Step 3: Write the difference between the two digits in the current column, borrowing a 11 from the next column to the left if necessary.
      • Step 4: If there is no next column to the left, stop. Otherwise, move to the next column and return to Step 3.
    • Key Features of an Algorithm:
      1. Finite Instructions: It must consist of a limited number of steps.
      2. Well-Defined Instructions: Each instruction must be effectively executable by a computing agent. For example, "compute the difference" is well-defined, but "divide by 00 (zero)" is not.
      3. Halts at a Solution: The process must eventually stop after achieving the result.
      4. General Class of Problems: It should solve a category of problems (e.g., a change-making algorithm should work for any two valid amounts of money).

  • Information Processing:

    • Historical Forms: Information has evolved from clay tablets in Mesopotamia to Greek texts, printed books, and abstract mathematical symbols.
    • Data: In the modern computing world, information is commonly referred to as data.
    • Mechanism: A computing agent takes established information as input, transforms it according to rules (algorithms), and produces new information as output.
    • Representational Capability: Computer scientists have learned to represent algorithms, images, music, speech, and video as information (digitization).

The Structure of a Modern Computer System

  • System Components: A computer system consists of Hardware (physical devices) and Software (sets of algorithms represented as programs).

  • Hardware Components:

    • Central Processing Unit (CPU): Often called the processor; consists of electronic switches that perform logical, arithmetic, and control operations. It fetches, decodes, and executes binary instructions from memory.
    • Memory (RAM): Primary or internal memory stores information as patterns of binary digits (11s and 00s), known as bits.
      • Volatility: Data in primary memory (RAMRAM) is lost if power is turned off.
      • Cells: Memory is organized into cells (e.g., a system might have 88 cells, each storing 1616 bits).
    • Input Devices: Convert human-readable information (text, sound, images) into computational data. Examples: keyboard, mouse, trackpad, microphone, touchscreen.
    • Output Devices: Convert processed data back into human-usable forms. Examples: monitor, speakers.
    • Ports: Connect the computer to networks and external devices (cameras, smartphones).
    • Secondary Memory: Permanent storage that survives power loss. Types include:
      • Magnetic Media: Tapes and hard disks.
      • Semiconductor Media: Flash memory sticks.
      • Optical Media: CDs and DVDs.

  • Computer Software:

    • Machine Code: Programs represented in binary digits.
    • System Software: Includes the Loader (which automates loading programs into memory) and the Operating System (OS).
      • Operating System Examples: Linux, Apple macOS, Microsoft Windows.
      • OS Functions: Managing memory and storage, scheduling concurrent programs, managing communications between CPU and I/O, and providing user interfaces.
    • User Interfaces:
      1. Terminal-Based: Uses keyboard input and text display.
      2. Graphical User Interface (GUI): Uses windows, icons, and menus (the desktop metaphor) with pointing devices.
      3. Touchscreen: Supports direct manipulation via gestures (pinches, swipes).
    • Application Software (Apps): Programs designed for specific tasks (e.g., web browsers, word processors, games).

History of Computing Systems

  • Early Developments (Before 1800):

    • Muhammad ibn Musa al-Khwarizmi: Ninth-century Persian mathematician; the word "algorithm" is derived from his name.
    • Euclid: Developed an algorithm for the greatest common divisor 2,3002,300 years ago.
    • Abacus: Ancient calculating aid using beads on wires.
    • Blaise Pascal: Built a mechanical addition device in the 17th17^{th} century.
    • Gottfried Wilhelm Leibniz: Built a mechanical calculator for multiplication; proposed a universal language for calculation.

  • The 19th19^{th} Century:

    • Joseph-Marie Jacquard: Invented a loom that used punched cards to automate weaving patterns; first machine to execute an algorithm automatically.
    • Charles Babbage: Designed the Analytical Engine, which included a mill (arithmetic unit), store (memory), operator (instruction runner), and output. It was never completed due to lack of funds.
    • Herman Hollerith: Developed a punched card machine for the U.S. Census; co-founded the company that became IBMIBM.
    • George Boole: Developed a system of logic (Boolean logic) with values TRUETRUE and FALSEFALSE and operations ANDAND, OROR, and NOTNOT.

  • The 20th20^{th} Century (1930s-1950s):

    • Alan Turing: Explored the theoretical limits of computation; developed the concept of a universal machine.
    • Claude Shannon: Demonstrated in "A Symbolic Analysis of Relay and Switching Circuits" how Boolean logic could represent digital switching in hardware.
    • First Electronic Digital Computers (1940s):
      • Mark I (1944): Electromechanical device at Harvard under Howard Aiken.
      • ENIAC (1943-1945): Electronic Numerical Integrator and Calculator; used vacuum tubes; 1,000×1,000\times faster than Mark I.
      • ABC (1942): Atanasoff-Berry Computer; solved simultaneous linear equations; regarded as the first electronic digital computer.
      • Colossus (1943): Built in England to crack the German Enigma code.
    • John von Neumann (1946): Realized program instructions could be stored in binary form in memory (stored-program computer).
    • Programming Evolution:
      • Assembly Language (Early 1950s): Used mnemonic codes (e.g., ADDADD, OUTPUTOUTPUT) instead of binary.
      • FORTRAN (1954): Formula Translation Language developed by John Backus (IBMIBM) for scientific applications.
      • COBOL (Early 1960s): Common Business Oriented Language developed by Grace Murray Hopper for government and business data processing.
      • LISP (1958-1960): List Processing developed by John McCarthy (MITMIT) for symbolic processing and artificial intelligence.

  • Modern Advancements (1965-Present):

    • Transistors: Replaced vacuum tubes; smaller, cheaper, and more reliable.
    • Integrated Circuits (Early 1960s): Etched transistors onto silicon wafers.
    • Moore's Law (1965): Gordon Moore predicted processing speed and storage capacity would double, and cost would decrease by half, approximately every 1818 months. This trend has held for over 5050 years.
    • Time-Sharing: Allowed multiple users to use one computer simultaneously via terminals.
    • Personal Computing:
      • Douglas Engelbart: Invented the mouse and designed early window/icon interfaces.
      • Alan Kay: Developed the Alto (Xerox PARC) and the Smalltalk language; envisioned the "DynaBook."
      • Steve Jobs: Launched the Macintosh in 19841984 (first mass-produced GUI computer).
      • Bill Gates & Paul Allen: Developed MS-DOS; partnered with IBMIBM.
    • Networking:
      • ARPANETARPANET: Precursor to the Internet (late 1960s).
      • Ethernet: Developed by Bob Metcalfe at Xerox.
    • World Wide Web: Created by Tim Berners-Lee in 19921992; designed HTTPHTTP (Hypertext Transfer Protocol) and HTMLHTML (Hypertext Markup Language).
    • Search and Big Data: Sergey Brin and Larry Page (Google) developed indexing/search algorithms. The term "Big Data" refers to large-scale data mining for trends and predictions.

Getting Started with Python Programming

  • Background: Invented by Guido van Rossum in the early 1990s. It is a high-level, interpreted, general-purpose language.
  • The Python Shell (IDLE):
    • An interactive developmental environment.
    • The prompt >>> indicates the shell is ready for input.
    • The version used in this text is Python 33 (specifically 3.6.13.6.1), which is not compatible with Python 22.
  • Color-Coding Scheme in IDLE:
    • Black: Numbers, operator symbols, variables, punctuation.
    • Blue: Outputs in the IDLE shell.
    • Green: Strings (text within quotation marks).
    • Orange: Keywords (e.g., def, if, while).
    • Purple: Built-in function names (e.g., abs, round, int, print).
    • Red: Program comments (preceded by #) and error messages.

Python Basic Functions and Syntax

  • The print Function: Displays results in the console.
    • Syntax: print(<expression>) or print(<expression>, ..., <expression>).
    • Example: print("Hi there") outputs Hi there.
    • The end="" argument prevents a newline at the end of output.
  • The input Function: Prompts the user for keyboard input.
    • Syntax: <variable> = input(<string_prompt>).
    • Returns input as a string.
  • Type Conversion Functions:
    • int(<string>): Converts a string of digits into an integer value.
    • float(<string>): Converts a string of digits into a floating-point (decimal) value.
  • String Concatenation: + glues two strings together.

How Python Works: Behind the Scenes

  1. Source Code: The interpreter reads the programmer's code and checks the syntax (grammatical rules).
  2. Byte Code: If syntax is correct, the interpreter translates source code into byte code.
  3. Python Virtual Machine (PVM): The byte code is executed by the PVM. Errors occurring here are run-time errors.

Detecting and Correcting Syntax Errors

  • Syntax Errors: Occur when code violates the language rules. Execution halts immediately.
  • Examples:
    • NameError: Referencing a variable name that hasn't been defined (e.g., typing lenth instead of length).
    • Unexpected Indent: Incorrect spacing at the beginning of a line. In Python, indentation is significant for defining code structure.
    • Invalid Syntax: Incomplete expressions (e.g., 3 +).

Review Questions and Discussion

  • Common Algorithms: Recipes, instructions for building sheds.
  • Information Sources: Books, CDs, running computers.
  • General-Purpose Devices: Laptops, cell phones (modern ones).
  • I/O Classification:
    • Input: Microphone, House.
    • Output: Monitor, Speaker, Printer.
  • Definitions:
    • IDLE: Used to edit, save, and run Python programs.
    • Syntax: The set of rules for forming sentences in a language.