Programming Design Study Notes

2. ALGORITHMS, FLOWCHARTS, DATA TYPES AND PSEUDOCODE

2.1 ALGORITHMS

  • Definition and Origin:

    • The term algorithm originates from the name of Abu Ja'far Mohammed ibn Musa al-Khowarizmi, a pioneering Arabic mathematician who developed rules for performing basic arithmetic operations on decimal numbers.

    • An algorithm is defined as a representation of a solution to a problem, fundamentally a procedure that transforms a current situation into a desired one.

  • Problem Definition:

    • A problem can be conceptualized as the gap between the current situation and a desired situation.

    • Solutions to trivial problems (e.g., making breakfast, traveling) require minimal effort, whereas complex problems demand clear expression and communication of the solution.

  • Importance of Algorithms in Computer Science:

    • The significance of algorithms stems from the need for detailed instructions when a computer is utilized in problem-solving.

    • An effective algorithm must be explicitly outlined so that a computer can execute it precisely.

  • Description Levels:

    • Algorithms can be described at various abstraction levels; however, their conceptual approach remains constant regardless of the audience (human vs computer).

    • Example of an Algorithm: A cake recipe represents an algorithm detailing ingredients and steps to achieve a cooked product.

    • Ingredients:

      • 4 extra-large eggs, beaten

      • 1.5 cups of stock

      • 0.5 teaspoon salt

      • 1 scallion, minced

      • 1 cup small shrimp or lobster flakes

      • 1 tablespoon soy sauce

      • 1 tablespoon oil

    • Procedure Steps:

      1. Mix all ingredients (except oil) in a deep bowl.

      2. Add 1 inch of water to a wide pot and place the bowl inside.

      3. Cover the pot and steam for 15 minutes.

      4. Heat oil until hot and pour over custard.

      5. Steam for an additional 5 minutes.

  • Definition of a Procedure:

    • A finite sequence of clearly defined instructions that can be mechanically executed in a finite time.

    • A proper procedure breaks down problem solutions into understandable parts.

    • For computers, this involves programming that encompasses the algorithm and provides a direct implementational guide for execution.

  • Definition of an Algorithm:

    • An algorithm is a procedure consisting of a finite set of unambiguous rules (instructions), specifying a finite sequence of operations that yields a solution to a problem or class of problems based on allowable input.

    • This can also be articulated as a sequential list of instructions for a process.

    • A recipe serves as a good analogy for understanding algorithms, demonstrating the need for ingredient lists and procedural methods.

  • Computational Complexities:

    • Algorithms may range in complexity and can encapsulate countless elementary computational steps executed by a computer (e.g., large-scale processes like manufacturing control or airline reservations).

  • Translation to Code:

    • Translating an algorithm into computer code poses challenges due to the complexity of machine code.

    • Higher-level programming languages (C, Pascal) facilitate this translation process by abstracting technical details into more understandable formats.

  • Algorithm Design:

    • Designing an algorithm requires an awareness of problem-solving strategies as applied to programming issues, with flowcharts or pseudocode often being employed for visualization.

2.2 FLOWCHARTS

  • Purpose of Flowcharting:

    • Flowcharting is a visual tool used to delineate the steps in a process.

    • A flowchart is composed of symbols (boxes, diamonds) indicating specific actions, connected by arrows showing the sequence of operations.

  • Flowcharting Symbols:

    • Numerous symbols exist for flowcharting, particularly in computing, but commonly utilized symbols include the following:

    1. Terminal: Marks the start or end of a procedure.

    2. Process: Designates internal operations within the processor or memory.

    3. Input/Output: Represents data input/output operations.

    4. Decision: Indicates a decision point leading to binary outcomes (yes/no).

    5. Connector: Links sections of the flowchart without introducing intersecting lines.

    6. Predefined Process: Signifies invoking a subroutine or interrupt program.

    7. Flow Lines: Indicate direction and flow of process sequence.

  • General Rules for Flowcharting:

    1. Connect all boxes with arrows.

    2. Entry points for flow symbols should be solely from the top; exits should be at the bottom.

    3. Decisions usually have dual exit points.

    4. Flow typically moves from top to bottom, upward flows are limited.

    5. Connectors facilitate flow continuity over various pages or segments.

    6. Subroutines must have their independent flowcharts.

    7. Flowcharts begin with a terminal or predefined process symbol.

    8. Conclusion points in flowcharts may also utilize the terminal symbol.

  • Flowcharting Tips:

    • Accurately depict the process as it occurs in reality, not as dictated by perceived norms.

    • Modify existing processes where necessary to enhance efficiency and recognition.

    • Test flowcharts through practical follow-through to identify discrepancies and adjust accordingly.

    • Include cognitive steps, such as decision-making processes, to mitigate gaps in procedural compliance.

  • Examples of Algorithms and Flowcharts:

    • Example 1: Algorithm and flowchart for summing test scores:

    • Algorithm:

      1. Start

      2. Sum = 0

      3. Get the first test score

      4. Add to sum

      5. Repeat for subsequent scores

      6. Output the total sum

      7. Stop

    • Flowchart: Steps represented with visuals indicating the above process.

    • Example 2:

    • More concise algorithm using a unique terminating value to establish a finite loop for summation:

      1. Start

      2. Sum = 0

      3. Get a value.

      4. If value is -1, stop; otherwise, add it to the sum and repeat.

      5. Output the sum and terminate.

3. DATA TYPES

  • Overview of Data Types:

    • Programming languages typically support various fundamental data types, which include:

    • Integer Types: Whole numbers, including positive, negative, and zero (e.g., -22, 0, 456).

    • Computers may impose limitations on integer range based on memory allocation.

    • Real Numbers: Divided into

      • Fixed Point: Contains an explicit decimal point (e.g., 1.5, -0.569).

      • Floating Point: Represented as binary fractions, with two components: mantissa and exponent (e.g., 0.123 * 10^2).

    • Character Types: Comprise letters, digits, or symbols that need to be enclosed in quotation marks in programming contexts (e.g., PRINT "Hello World").

    • Boolean Types: Represent conditions and can take on two values: True or False.

  • Data Item Uses:

    • Constants: Fixed-value data that remains unchanged throughout program execution, here represented by numerical values.

    • Variables: Symbolic names assigned to data items, capable of changing values during program execution. Examples of variable operations include:

    • Initialization (e.g., count = 0).

    • Incrementing a counter (e.g., count = count + 1).

    • Accumulating sums (e.g., sum = sum + item).

    • Overwriting values (e.g., y = 3*x + 4).

  • Assignment Operations: Involves syntax as follows:

    • Pascal: variable := expression

    • C/C++/Java: variable = expression

    • Note: The order and compatibility of assignments hold importance in programming.

2.5 PSEUDOCODE

  • Definition of Pseudocode:

    • Pseudocode serves as a high-level algorithm description devoid of specific programming syntax.

    • It models coding structures while remaining accessible to a broader audience than distinct programming languages.

  • Nature and Variants:

    • Pseudocode adapts to distinct formats, often borrowing conventions from known languages, and can include natural language where details are unclear.

  • Types of Control Structures:

    • Sequence Structure: Basic step progression with no conditional branching.

      • Example: Average calculation via summation.

    • Decision Structure (Selection): Includes if statements to navigate choices based on logical conditions.

    • Repetitive Structure (Iteration): Allows the repetition of a block of code until a specified condition is met (e.g., While loop, For loop).

    • Example Pseudocode for different structures:

    • For Loop: FOR (starting state; stopping condition; increment) { }

    • While Loop: WHILE (condition is true) { }

    • Repeat Until Loop: REPEAT { } UNTIL (condition is true)

  • Conclusion on Control Structures:

    • Control structures effectively streamline programming and enhance clarity in complex logic flows, which builds towards efficient algorithm development and implementation.