Algorithmic Representation and Computer and Foundations and Computer Science and Science Notes

Algorithmic Representation and Modern Computer Science

Representation of Algorithms

• Notation Requirements: Algorithms must be expressed in a notation that is clear, precise, and unambiguous. Potential notations include natural language, high-level programming languages, and pseudocode.
• Natural Language Limitations:
  • Verbosity and Structure: Natural languages (e.g., English, Spanish, Japanese) are extremely verbose, leading to rambling and unstructured text. The lack of line numbering, indentation, or highlighting makes it difficult to locate specific sections, such as the start of a loop.
  • Ambiguity: Natural language is "rich" in interpretation and depends on context or experience. This allows multiple readers to interpret the same instruction differently (e.g., the phrase "the shortest path" could refer to time, distance, or another metric).
  • Lack of Precision: Phrases like "that operation" may be unclear, leading to inconsistent execution patterns.
• High-Level Programming Language Limitations:
  • Excessive Detail: Using languages like C++ or Java forces a designer to worry about technicalities such as punctuation, semicolons, grammar, and syntax (e.g., the difference between carry = 0; and Carry = 0;) too early in the process.
  • Abstraction: During the initial design, thoughts should remain at a high abstract level. Technical details, such as array declarations like int[] a = new int[100];, clutter thinking and are considered out of place in the design stage.
• Pseudocode as a Compromise:
  • Definition: A set of English-language constructs designed to resemble programming statements without being executable on a computer.
  • Characteristics: It is simple, highly readable, and has virtually no strict grammatical rules. It is often jokingly called "a programming language without the details."
  • Advantages: It provides a well-defined structure that is easier to visualize than prose. Because it resembles real programming languages, translating pseudocode into a computer program is relatively simple (as seen in Figure 1.2 and Figures 1.3/1.4).
  • Flexibility: Pseudocode is an informal design notation. It is not rigidly standardized; users can modify or select constructs that best fit their personal problem-solving style.

Sequential Operations in Pseudocode

• Basic Types: Algorithms include three primary sequential operations: computation, input, and output.
• Variables: A variable is a named storage location capable of holding a data value, comparable to a "mailbox" where values can be placed or retrieved.
• Computation Operations:
  • Notation: Set the value of "variable" to "arithmetic expression".
  • Functionality: The computing agent evaluates the arithmetic expression and stores the result in the specified variable. Any previous value in the variable is discarded and replaced.
  • Capabilities of the Computing Agent: Designers can assume the agent functions like a multifunction calculator, knowing basic operations ($+$, $-$, $\times$, $/$), square roots ($\text{sqrt}$), absolute values, trigonometric functions ($\text{sin}$, $\text{cos}$, $\text{tan}$), and constants like $\pi$.
  • Error Conditions: If an expression involves a variable that has not yet been assigned a value, the instruction is not effectively computable, causing an error.
• Input Operations:
  • Goal: To provide data values from the "outside world" (anything external to the computing agent) to the agent.
  • Notation: Get values for "variable", "variable", ....
  • Procedure: When the algorithm reaches an input instruction, it pauses and waits for the outside world to provide values (e.g., via a keyboard). Once received and stored, the algorithm proceeds to the next instruction.
• Output Operations:
  • Goal: To send results or messages from the computing agent to the outside world for display or storage.
  • Notation: Print the values of "variable", "variable", ....
  • Display Modes: Results can be viewed on screens (computers, tablets, smartphones) or printed on paper.
  • Messages: Output can include text messages to inform the user of status or errors (e.g., Print the message ‘Sorry, no answers could be computed.’). Messages are typically enclosed in single quotation marks to distinguish them from variables.
• Input/Output Hardware: In computers, communication occurs via devices such as physical keyboards, virtual keypads, screens, mice, printers, hard drives, cameras, and touch screens.

Algorithmic Examples and Case Studies

• Average Miles per Gallon Algorithm (Version 1):
  1. Get values for gallons used, starting mileage, ending mileage.
  2. Set value of distance driven to (ending mileage $-$ starting mileage).
  3. Set value of average miles per gallon to (distance driven $+$ gallons used).
  4. Print the value of average miles per gallon.
  5. Stop.
• Circle Area Calculation:
  • Instruction: Set the value of Area to (\pi \times r^2).
  • This evaluates the expression $\pi \times r^2$ using a previously provided radius $r$.
• The Addition Algorithm: Summarized as performing operations like Set the value of ci to (ai + bi + carry) and Set the value of i to (i + 1).
• Quadratic Formula: The formula $Roots = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$ is not effectively computable if the discriminant $(b^2 - 4ac)$ is negative (assuming real numbers are required) or if $a = 0$.
• Multiplication via Repeated Addition: Multiplication of two positive numbers $a$ and $b$ can be sketched as adding $a$ to itself exactly $b$ times.
• Euclid's Greatest Common Divisor (GCD) Algorithm (2,300 years old):
  1. Get two positive integers as input; call the larger $I$ and the smaller $J$.
  2. Divide $I$ by $J$, and call the remainder $R$.
  3. If $R$ is not $0$, reset $I$ to the value of $J$, reset $J$ to the value of $R$, and return to Step 2.
  4. Print the answer, which is the value of $J$.
  5. Stop.

The Six-Layer Hierarchy of Computer Science

• Level 1: The Algorithmic Foundations: (Chapters 2, 3) Focuses on designing and representing algorithms and their role in problem solving.
• Level 2: The Hardware World: (Chapters 4, 5) Focuses on low-level machine details, electronic circuits, and physical computer hardware.
• Level 3: The Virtual Machine: (Chapters 6, 7, 8) Addresses the intermediate layer where hardware is managed as a machine.
• Level 4: The Software World: (Chapters 9, 10, 11, 12) Includes programming languages (C++, Python, Java, Perl), software development, and the translation of high-level programs into machine language (Chapter 11). Chapter 12 discusses the limits of computing.
• Level 5: Applications: (Chapters 13, 14, 15, 16) Explores uses of software such as simulation, visualization, ecommerce, databases, artificial intelligence (AI), computer graphics, and entertainment.
• Level 6: Social Issues: (Chapter 17) Investigates the social, ethical, legal, and professional impacts of technology, including computer crime, privacy, intellectual property, and social networks (Facebook, Twitter, LinkedIn, Pinterest).

Questions and Discussion Topics

• Traveling Salesperson Problem: Design an algorithm for a salesperson to visit 25 cities exactly once while minimizing mileage. Analyzing $10,000,000$ paths per second to find the optimal route is a common computational challenge.
• Computing Performance Metrics: Determining processing speed in GIPS (billions of instructions per second) and computational speed in GFlops (billions of floating point operations per second).
• Memory and Storage:
  • Comparison of current memory size to first-, second-, and third-generation computers.
  • Storage Analysis: A standard DVD holds approximately $5 \times 10^9$ characters. Estimating the equivalent shelf space in printed books involves assuming $5$ characters per word, $300$ words per page, and $300$ pages per inch of shelf space.
• Emerging Computing Models:
  • Ubiquitous Computing: Computers automatically providing services without user awareness (e.g., cars communicating with garage door openers).
  • Cloud Computing: Networking software providing transparent access to remote data and applications.
• App Ecosystems: Android users have access to $2.8$ million apps, while the Apple App Store offers $2.2$ million apps for download.
• Historical Pioneers: Research focuses include Pascal, Liebnitz, Jacquard, Babbage, Lovelace, Hollerith, Eckert, Mauchly, Aiken, Zuse, Atanosoff, Turing, and Von Neumann.