Problem Solving Algorithms Flowcharts and Data Structures Study Notes

Fundamentals of Problem Solving

Problem Solving Definition
- Problem solving is the process of finding solutions to difficult or complex issues.
- It is the core process by which any kind of problem is solved.
Role of Computers in Problem Solving
- Problem solving is the fundamental core feature of computers.
- A computer is not naturally intelligent and cannot analyze a problem or generate a solution on its own.
- A human (the programmer) must:
- Analyze the problem.
- Develop specific instructions for solving the problem.
- Make the computer carry out those instructions.
- The primary responsibility of a programmer is to provide solutions to problems using computer systems.
- Steps for computer science learning:
1. Understand how a human solves a problem.
2. Understand how to translate that human solution into a format a computer can comprehend.
3. Write the specific computational steps required to accomplish the task.
- Note: In certain scenarios, a machine will solve a problem in a completely different manner than a human.
Definition of a Problem
- A problem is defined as a situation that prevents something from being achieved.
- It can manifest as a task, a situation, or any other obstacle.
- In simple terms, a problem is a question that requires an answer or a solution.
- It is generally considered a matter that is difficult to solve or settle, a doubtful case, or a complex task involving doubt and uncertainty.
Planning the Solution
- Problems are solved with computer assistance, requiring programmers to carefully plan and strategize tasks leading to a resolution.
Problem-Solving Strategies
- A strategy is an approach (or a series of approaches) created specifically to solve a computational problem.
- Strategies are designed based on the precise nature of the given problem.
- Strategies are flexible and outline various steps required to reach a solution.
- A strategy on its own might yield incorrect results, but an algorithm constructed from a valid strategy will always produce correct results.
- Strategy creation requires determining what the problem actually is and contrasting it with how the situation should ideally look without the problem.
- Asking questions regarding the end result helps identify the existing gap and create an effective solution strategy.
The Four-Step Problem-Solving Process
- Problem solving is a structured step-by-step process involving four primary stages:

Problem Solving Steps

Step 1: Define the Problem
- Defining or identifying the problem is the first, most difficult, and most critical step.
- Involves diagnosing the overall situation to ensure focus remains on the root problem rather than merely treating its symptoms.
- Requires describing the problem clearly, which helps others understand the exact issue.
Step 2: Generate Alternative Solutions
- Every problem generally has multiple solutions beyond the first idea that comes to mind.
- Postpone selecting a single final solution until several alternative approaches have been proposed.
- Evaluating multiple alternatives significantly increases the value of the ultimate ideal solution.
- Develop a thorough list of all feasible options for subsequent assessment.
- Useful tools during this phase include critical thinking techniques and team problem-solving methodologies.
Step 3: Evaluate and Select an Alternative
- A common error in problem solving is evaluating alternatives as soon as they are proposed, leading to the selection of the first acceptable option even if it is suboptimal.
- premature selection prevents teams from learning new insights necessary for genuine, long-term process improvement.
- Evaluate all proposed alternatives thoroughly prior to final selection.
Step 4: Implement and Follow Up on the Solution
- Solution plans must include contingency strategies specifying what actions to take if something goes wrong or if results do not meet expectations.
- Once implemented, track and measure real-world performance to answer:
  - Did the solution work?
  - Was it a good solution?
  - Were lessons learned that can be applied to future problems?
- Considerations for choosing the best solution:
  - Does it solve the current problem without creating new issues?
  - Is it acceptable to all stakeholders involved?
  - Is it achievable within budget constraints and specified timeframes?

Algorithms in Problem Solving

Applications of Algorithms in Information Technology (IT)
- Algorithms are used across all domains of IT.
- Search Engine Example: Accepts search strings of keywords and operators as input, queries an associated database for relevant pages, and returns organized results.
- Online Advertising Example: Accepts input data such as age, gender, geographic region, and user interests, displaying advertisements exclusively to matching user profiles.
Definition of an Algorithm
- An algorithm is a structured set of instructions, steps, or rules followed to complete a problem-solving task.
- It serves as a precise tool for solving well-specified computational problems.
Everyday Examples of Algorithms
- Morning routines followed after waking up.
- Following step-by-step driving instructions to reach a destination.
- Following recipes while cooking meals or preparing tea.
Methods to Express Algorithm Designs
1. Pseudocode
2. Flowcharts
Role of Algorithms in Problem Solving
- Ensures exact, predictable, and optimal results every single time it executes.
- Highly valuable when high accuracy is required or when recurring problems must be solved repeatedly.
- Forms the base logic for software programs, executing inputs to compute required outputs.
- Programmers design algorithms for diverse functions ranging from user data retrieval to complex formula computations.
- Formatted output data is presented to users in a meaningful structure to enable informed decision-making.
Qualities of Good Algorithms
- Precision: Inputs and outputs must be clearly and precisely defined.
- Unambiguous Steps: Every individual step must be unambiguous and clear in intention.
- Efficiency: Represents the most effective path among alternative problem-solving routes.
- Language-Agnostic: Must NOT include language-specific computer code; written universally so it can be implemented across various programming languages.
Detailed Algorithm Examples
- Algorithm 1: Making a Cup of Tea
- Step 1: Start
- Step 2: Place fresh water in a pot or kettle.
- Step 3: Boil the water.
- Step 4: Add black tea leaves into the pot.
- Step 5: Add milk into the pot.
- Step 6: Add sugar.
- Step 7: Boil for some time.
- Step 8: Stop
- Algorithm 2: Sum of Two Numbers
- Step 1: Start
- Step 2: Declare variables $\text{num1}$ , $\text{num2}$ , and $\text{sum}$ .
- Step 3: Read values $\text{num1}$ and $\text{num2}$ .
- Step 4: Add $\text{num1}$ and $\text{num2}$ and assign the result to $\text{sum}$ : $\text{sum} = \text{num1} + \text{num2}$
- Step 5: Display $\text{sum}$
- Step 6: Stop
- Algorithm 3: Average of Three Numbers
- Step 1: Start
- Step 2: Declare variables $\text{num1}$ , $\text{num2}$ , $\text{num3}$ , and $\text{avg}$ .
- Step 3: Read values $\text{num1}$ , $\text{num2}$ , and $\text{num3}$ .
- Step 4: Apply formula $\{\text{Average} = \text{Sum} / \text{No. of values}\}$ : $\text{avg} = (\text{num1} + \text{num2} + \text{num3}) / 3$
- Step 5: Display $\text{avg}$
- Step 6: Stop
- Algorithm 4: Volume of a Box
- Step 1: Start
- Step 2: Declare variables $\text{length}$ , $\text{width}$ , $\text{height}$ , and $\text{volume}$ .
- Step 3: Read values $\text{length}$ , $\text{width}$ , and $\text{height}$ .
- Step 4: Apply formula $\{\text{Volume} = \text{length} \times \text{width} \times \text{height}\}$ : $\text{volume} = \text{length} \times \text{width} \times \text{height}$
- Step 5: Display $\text{volume}$
- Step 6: Stop
- Algorithm 5: Percent Calculation
- Step 1: Start
- Step 2: Declare variables $\text{part}$ , $\text{total}$ , and $\text{percentage}$ .
- Step 3: Read values $\text{part}$ and $\text{total}$ .
- Step 4: Apply formula $\{\text{Percentage} = (\text{part} / \text{total}) \times 100\}$ : $\text{percentage} = (\text{part} / \text{total}) \times 100$
- Step 5: Display $\text{percentage}$
- Step 6: Stop

Flowcharts

Definition and Overview
- A flowchart is a diagrammatic/graphical physical representation of the problem-solving process.
- Illustrates the explicit sequence of steps and operational logic prior to writing program code.
- Serves as a general-purpose communication tool using standard geometric symbols connected by directed lines or arrows showing procedural flow.
Types of Flowcharts
- Information System Flowcharts: Display the overarching flow of data from raw source documents through to final distribution to users.
- Program Flowcharts: Display the specific sequence of instructions or logical steps within a single program or subroutine.
Standard Flowchart Symbols
- Start/Stop (Terminal)
- Shape: Oval
- Description: Represents the explicit start and end points of a program or flowchart sequence.
- Arrows (Flowlines)
- Shape: Directed Arrow
- Description: Indicates the exact direction of process flow from one step or symbol to another.
- Process
- Shape: Rectangle
- Description: Indicates internal processing operations or calculations (typically a single operational step). Contains text inside the rectangle; exactly one arrow originates out from it.
- Input/Output (I/O)
- Shape: Parallelogram
- Description: Denotes any input or output operation where the system receives data or presents calculated output results.
- Decision / Condition
- Shape: Diamond
- Description: Displays a conditional evaluation step written within the diamond. Features two exit arrows pointing to distinct branches based on evaluation (True/False or Yes/No).
Importance and Advantages of Flowcharts
- Provides instant visual representation of logic that can be comprehended in a single glance.
- Simplifies communication of program logic to clients and non-technical stakeholders.
- Acts as primary program documentation for software maintenance, expansion, and logic updates.
- Serves as an architectural blueprint during actual programming and code implementation.
Sample Flowchart Logic Execution
- Task: Reads three numbers, computes sum and percentage, and outputs performance criteria.
- Process Steps:
1. Start
2. Input values $x$ , $y$ , $z$
3. Calculate $\text{Sum} = x + y + z$
4. Calculate $\text{Percent} = \text{Sum} / 300 \times 100$
5. Decision: Is $\text{percent} > 70$ ?
  - If Yes: Print "Well done"
  - If No: Print "Work hard"
6. Stop

Sample Flowchart Diagram

Detailed Comparison: Algorithm vs. Flowchart
- Format
- Algorithm: Textual step-by-step description.
- Flowchart: Diagrammatic visual representation using geometric shapes.
- Representation
- Algorithm: Text-based pseudocode.
- Flowchart: Visual symbols and directed flow lines.
- Debugging
- Algorithm: Easier to debug logical text errors.
- Flowchart: More difficult to debug complex graphical layouts.
- Construction and Comprehension
- Algorithm: Can be more difficult to construct and read as complexity grows.
- Flowchart: Easy to construct visually and quick to understand.
- Rule Adherence
- Algorithm: Flexible; does not follow rigid syntax rules.
- Flowchart: Strict compliance with specific symbol usage rules.

Data Structures

Definition of Data Structure
- A data structure is a specialized scheme for organizing and storing data in a computer so that it can be utilized efficiently.
- Data structures are categorized into Linear Data Structures and Non-Linear Data Structures.
Linear Data Structures
- Elements are arranged sequentially in a continuous single-level line.
- Each element connects directly to its adjacent previous and next elements.
- Allows linear traversal in a single execution run.
- Simple to implement because physical computer memory is organized sequentially.
- Less efficient in terms of overall memory utilization.
- Main Examples: Stack, Queue, Array.
- Stack
- A linear structure adhering to LIFO (Last In First Out) or FILO (First In Last Out) execution order.
- Data added last is removed first; data added first is removed last.
- Access is restricted strictly to the top of the stack; elements cannot be inserted or removed from the middle or bottom.
- Real-world Metaphor: A stack of cafeteria plates where the topmost plate is removed first and the bottom plate remains until all others are removed.
- Terminology & Operations:
  - Push: Operation to insert an element onto the top of the stack.
  - Pop: Operation to remove an element from the top of the stack.
  - Overflow State: Occurs when attempting to push onto a completely full stack.
  - Underflow State: Occurs when attempting to pop from an entirely empty stack.

Stack Data Structure

Queue
- A linear structure adhering to FIFO (First In First Out) execution order.
- The element inserted first is processed and removed first.
- Real-world Metaphor: A line of students waiting at school or patrons at a cinema ticket counter.
- Structural Terminology & Operations:
  - Front / Head: The designated exit end where deletions take place.
  - Rear / Tail: The designated entry end where new insertions take place.
  - Enqueue: The process of adding a new element to the rear of the queue.
  - Dequeue: The process of removing an element from the front of the queue.
  - Element Ordering Constraint: Newly inserted items cannot be removed until all preceding elements in line have been dequeued.
Array
- A linear data structure that holds a finite, ordered collection of homogeneous elements (all of the exact same data type).
- Elements are stored in contiguous, successive memory addresses.
- Core Definitions:
  - Element: Each individual value stored within the array.
  - Index: A unique, consecutive numerical identifier that references the specific location of an element.
- Common Operations Performed on Arrays:
  - Traversal
  - Search
  - Insertion
  - Deletion
  - Sorting
- Non-Linear Data Structures
Elements are not connected in sequential order.
Individual elements can connect to multiple adjacent nodes along diverse computational paths.
Supports multi-level hierarchical structures.
Cannot be traversed entirely in a single run.
Implementation is complex, but memory utilization efficiency is vastly superior compared to linear structures.
Main Examples: Trees, Graphs.
Tree
- Represents data organized in explicit hierarchical relationships.
- Elements are represented as nodes connected visually by edges.
- Core Components:
  - Root Node: The primary top node that serves as the entry point for the structure.
  - Parent Node: A node that connects downward to lower-level nodes.
  - Child Node: A node connected beneath a parent node.
- Binary Tree / Binary Search Tree: A specialized tree structure where every node has a maximum limit of two child nodes.

Tree Data Structure Diagram

Graph
- A non-linear data structure consisting of a finite set of vertices (nodes) linked together by edges (connecting lines).
- Nodes store record data (e.g., student roll numbers, names, marks) and can connect to any arbitrary number of edges.
- Graphs do not feature a central root node or hierarchical parent-child relationships; cycles can freely form.
- Real-World Network Applications:
  - Telephone communications systems.
  - Social media networks (e.g., Facebook, where individual profiles are nodes and friend connections represent edges).
- Primary Categories of Graphs:
  1. Undirected Graph: Edges are entirely bidirectional. Traversals between connected nodes can occur in both directions (from node 1 to 2, and from node 2 to 1).
  2. Directed Graph: Edges feature directionality indicated by arrowheads. Traversals can only occur strictly in the designated arrow direction (e.g., node 1 to node 2, but not reverse).