Data Structures & Algorithms: Problem Solving and Complexity Analysis

Foundations of Problem Solving

Problem solving serves as a universal competency that underpins technical, operational, and strategic success across programming and systems thinking.
Definition of Problem Solving: A structured process of identifying a challenge, analyzing its core components, and developing a logical, effective solution.
Key Attributes of Problem Solving:
- Clarity in understanding the problem: Establishing precise comprehension of the challenge before attempting to solve it.
- Logical decomposition of tasks: Breaking down complex systems or problems into manageable, discrete sub-tasks.
- Strategic planning and execution: Designing systematic steps and executing them methodically.
- Evaluation and refinement of solutions: Continuously testing, validating, and optimizing developed solutions.
Inspirational Motto: "La juventud es la esperanza de nuestro futuro." ~ Jose Rizal.

The Problem-Solving Process

The Problem-Solving Process Diagram

The structured framework for problem solving comprises six sequential phases:
- Problem Identification:
- Define the issue clearly and unambiguously.
- Distinguish carefully between surface symptoms and actual root causes.
- Determine the complete scope and potential operational impact of the problem.
- Analysis:
- Gather all relevant data, parameters, and system constraints.
- Identify underlying patterns, dependencies, and operational limitations.
- Break down the problem into smaller, interdependent logical components.
- Solution Design:
- Brainstorm multiple candidate solution approaches.
- Utilize structural tools such as pseudocode, flowcharts, or architectural diagrams.
- Ensure design consideration for key engineering principles: modularity, scalability, and robust error handling.
- Implementation:
- Translate the structured plan into executable program code or operational workflows.
- Comply strictly with industry best practices and documentation standards.
- Testing and Evaluation:
- Validate produced outputs against anticipated target results.
- Test for edge cases, boundary conditions, unexpected inputs, and exceptions.
- Assess overall system performance, runtime efficiency, and reliability.
- Refinement and Maintenance:
- Optimize execution logic, data structures, and overall code architecture.
- Update system documentation to reflect modifications.
- Continuously monitor systems for emerging operational issues or performance enhancements.

Strategies for Effective Problem Solving

Strategies Diagram

Core strategies employed in algorithmic and systems problem solving:
- Divide and Conquer: Partitioning a complex problem into smaller, independent sub-problems, solving each individually, and combining their results.
- Trial and Error: Systematically testing various approaches and evaluating outcomes until a functional solution is found.
- Pattern Recognition: Identifying recurring structural patterns, similarities, or behavioral trends across distinct problems.
- Algorithmic Thinking: Applying step-by-step logic, deterministic rules, and sequence structures to reach a solution.
- Root Cause Analysis: Investigating fundamental underlying causes rather than merely addressing visible symptoms.

Understanding Pseudocode and Designing Solutions

Pseudocode is a simplified, structured language used to describe an algorithm's logical flow using plain English.
Fundamental Characteristics of Pseudocode:
- Written in structured, clear English format.
- Completely language-neutral and free from specific programming syntax constraints.
- Easy to read and write for programmers, systems analysts, and non-technical stakeholders.
- Focuses purely on logic, structure, and algorithmic flow.
- Serves as an essential bridge between high-level conceptual design and final software implementation.
Example Pseudocode Structure: text START INPUT user_age IF user_age >= 18 THEN DISPLAY "Access granted" ELSE DISPLAY "Access denied" END   
Architectural Benefits of Planning with Pseudocode:
- Clarifies core program objectives, processing steps, decision branches, loops, and module interactions.
- Reduces logic errors prior to actual code implementation.
- Facilitates team collaboration, communication, and code review.
- Guarantees adherence to system design specifications.
The Input-Process-Output (IPO) Cycle:

INPUT number PROCESS square = number * number OUTPUT square

Input: Receiving operational input data (e.g., INPUT number).
Process: Transforming input data using algorithmic operations (e.g., PROCESS square = number * number).
Output: Displaying or returning the computed output (e.g., OUTPUT square).

Big O Notation and Complexity Analysis

Big O Notation Chart

Core Motivation for Complexity Analysis:
- Addresses fundamental software performance questions: How fast will an algorithm execute? How much memory capacity will it require?
- Enables developers to predict runtime behavior and memory utilization without physically running code.
- Uses Big O Notation as the universal standard language for expressing operational efficiency.
Key Aspects of Big O Notation:
- Formally describes the theoretical upper bound of an algorithm's growth rate.
- Focuses on analyzing worst-case performance scenarios.
- Allows objective standardization and comparison of algorithmic scalability.
Primary Time Complexity Classes:
- Constant Time - $O(1)$ :
- Number of execution steps remains unchanged regardless of input size.
- Metaphor: Opening a locked box with a key. Whether the box contains $1$ item or $1,000$ items, it takes exactly one turn of the key.
- Practical example: Accessing an array element directly via its index.
- Linear Time - $O(n)$ :
- Total execution steps grow in direct, 1-to-1 proportion with input size n$.\n * Metaphor: Checking student attendance on a printed class list. A list of 10 $students requires$ 10 $checks;$ 100 $students require$ 100 checks.\n * Practical example: Linear search through an unsorted array.\n * **Logarithmic Time - O(log(n))**:\n * Execution steps grow very slowly because the remaining search space is cut in half at each step.\n * Metaphor: Searching for a contact in a printed phone book by repeatedly opening to the middle and cutting the remaining pages in half.\n * Scale performance: For an input size of 1,000,000 $items, logarithmic search requires only about$ 20 operational steps.\n * Practical examples: Binary search, balanced tree lookup.\n * **Quadratic Time - O(n^2)**:\n * Execution steps grow proportionally to the square of the input size n$.
- Metaphor: Comparing every student in a classroom directly against every other student. A group of $10$ students requires $100$ comparisons; $100$ students require $10,000$ comparisons.
- Practical examples: Bubble sort, insertion sort, nested loop operations.

Complexity Characteristics of Data Structures

Complexity in Data Structures Table

Operations and Space Complexity Matrix:
- Array:
- Access Complexity: $O(1)$
- Search Complexity: $O(n)$
- Insertion / Deletion Complexity: $O(n)$
- Space Complexity: $O(n)$
- Linked List:
- Access Complexity: $O(n)$
- Search Complexity: $O(n)$
- Insertion / Deletion Complexity: $O(1)$ (at the head pointer)
- Space Complexity: $O(n)$
- Stack / Queue:
- Access Complexity: $O(1)$
- Search Complexity: $O(n)$
- Insertion / Deletion Complexity: $O(1)$
- Space Complexity: $O(n)$
- Hash Table:
- Access Complexity: $O(1)$
- Search Complexity: $O(1)$
- Insertion / Deletion Complexity: $O(1)$
- Space Complexity: $O(n)$
- Binary Tree:
- Access Complexity: $O(\log(n))$
- Search Complexity: $O(\log(n))$
- Insertion / Deletion Complexity: $O(\log(n))$
- Space Complexity: $O(n)$
Practical Importance of Big O Analysis:
- Assists in selecting appropriate data structures for processing massive datasets.
- Prevents critical software bottlenecks during execution.
- Guarantees long-term application scalability, maintainability, and resource optimization.

Applied Problem-Solving Scenarios and Analysis

Example Problem: Apple Bagging Computation
- Scenario: Micah has $3$ apples and receives $3$ additional apples from Mike. Plastic bags have a strict capacity limit of $2$ apples per bag.
- Problem Analysis & Answers:
- a) Required answer: $3$ plastic bags.
- b) Pseudocode: text BEGIN SET apples_initial = 3 SET apples_given = 3 SET total_apples = apples_initial + apples_given SET capacity_per_bag = 2 SET bags_needed = total_apples / capacity_per_bag IF total_apples MOD capacity_per_bag != 0 THEN bags_needed = bags_needed + 1 END IF DISPLAY "Total apples: ", total_apples DISPLAY "Plastic bags needed: ", bags_needed END       
- c) Big O Complexity: $O(1)$ Constant Time.
Scenario 1: River Crossing Puzzle (3 Filipinos and 3 Aswangs)

River Crossing Illustration

Rules and Constraints:
- Three Filipinos and three Aswangs must cross a river using one boat.
- Boat maximum carrying capacity is $2$ individuals per trip.
- If Aswangs outnumber Filipinos on either bank of the river at any point, the Aswangs will eat the Filipinos.
- The boat requires at least one passenger aboard to row it across.
Step-by-Step Execution Sequence for Safe Crossing:
- Step 1: Two Aswangs row across to Bank B ( $3$ Filipinos, $1$ Aswang on Bank A; $2$ Aswangs on Bank B).
- Step 2: One Aswang rows back to Bank A ( $3$ Filipinos, $2$ Aswangs on Bank A; $1$ Aswang on Bank B).
- Step 3: Two Aswangs row across to Bank B ( $3$ Filipinos, $0$ Aswangs on Bank A; $3$ Aswangs on Bank B).
- Step 4: One Aswang rows back to Bank A ( $3$ Filipinos, $1$ Aswang on Bank A; $2$ Aswangs on Bank B).
- Step 5: Two Filipinos row across to Bank B ( $1$ Filipino, $1$ Aswang on Bank A; $2$ Filipinos, $2$ Aswangs on Bank B).
- Step 6: One Filipino and one Aswang row back to Bank A ( $2$ Filipinos, $2$ Aswangs on Bank A; $1$ Filipino, $1$ Aswang on Bank B).
- Step 7: Two Filipinos row across to Bank B ( $0$ Filipinos, $2$ Aswangs on Bank A; $3$ Filipinos, $1$ Aswang on Bank B).
- Step 8: One Aswang rows back to Bank A ( $0$ Filipinos, $3$ Aswangs on Bank A; $3$ Filipinos, $0$ Aswangs on Bank B).
- Step 9: Two Aswangs row across to Bank B ( $0$ Filipinos, $1$ Aswang on Bank A; $3$ Filipinos, $2$ Aswangs on Bank B).
- Step 10: One Aswang rows back to Bank A ( $0$ Filipinos, $2$ Aswangs on Bank A; $3$ Filipinos, $1$ Aswang on Bank B).
- Step 11: Two Aswangs row across to Bank B. All $3$ Filipinos and $3$ Aswangs are safely across on Bank B without casualties.
- Scenario 2: Bomb Defusal Water Jug Problem

Bomb Defusal Diagram

Rules and Constraints:
- A bomb must be defused within $15\text{ minutes}$ by placing exactly $4\text{ liters}$ of water onto a pressure sensor.
- Equipment available: One empty $5\text{-liter}$ bottle and one empty $3\text{-liter}$ jug.
- Neither container is transparent or marked with gradations. An unlimited water faucet is nearby.
Step-by-Step Defusal Procedure:
- Step 1: Fill the $5\text{-liter}$ bottle completely with water from the faucet ( $5\text{L}$ in bottle, $0\text{L}$ in jug).
- Step 2: Pour water from the $5\text{-liter}$ bottle into the $3\text{-liter}$ jug until the jug is full ( $2\text{L}$ remaining in bottle, $3\text{L}$ in jug).
- Step 3: Empty the $3\text{-liter}$ jug completely onto the ground ( $2\text{L}$ in bottle, $0\text{L}$ in jug).
- Step 4: Transfer the remaining $2\text{ liters}$ from the $5\text{-liter}$ bottle into the $3\text{-liter}$ jug ( $0\text{L}$ in bottle, $2\text{L}$ in jug).
- Step 5: Refill the $5\text{-liter}$ bottle completely from the faucet ( $5\text{L}$ in bottle, $2\text{L}$ in jug).
- Step 6: Carefully pour water from the $5\text{-liter}$ bottle into the $3\text{-liter}$ jug until full. Since the $3\text{-liter}$ jug already contains $2\text{ liters}$ , it takes exactly $1\text{ liter}$ , leaving exactly $4\text{ liters}$ inside the $5\text{-liter}$ bottle ( $4\text{L}$ in bottle, $3\text{L}$ in jug).
- Step 7: Place the $5\text{-liter}$ bottle containing exactly $4\text{ liters}$ onto the sensor to deactivate the bomb safely.
- Scenario 3: 8 Gift Boxes and Balance Scale Puzzle

Balance Scale Illustration Gift Box Problem Statement

Rules and Constraints:
- There are $8$ gift boxes identical in size, color, wrapping, and appearance.
- One box contains a taped $1000\text{ peso}$ bill, making its weight slightly heavier (shaking produces no sound).
- A specialized balance scale sensitive up to $0.001\,\mu\text{g}$ is available.
- The balance scale may be used a maximum of $2$ times.
Divide and Conquer / Logarithmic Search Solution:
- Weighing 1:
  - Divide the $8$ boxes into three groups: Group A with $3$ boxes (boxes 1, 2, 3), Group B with $3$ boxes (boxes 4, 5, 6), and Group C with $2$ boxes (boxes 7, 8).
  - Place Group A on the left pan and Group B on the right pan of the balance scale.
  - Outcome 1A: If Group A and Group B balance equally, the target box containing the bill is in Group C (boxes 7 or 8).
  - Outcome 1B: If the scale tips (e.g., Group A drops lower), the target box is within that heavier $3\text{-box}$ group.
- Weighing 2:
  - Following Outcome 1A: Place box 7 on the left pan and box 8 on the right pan. The heavier pan immediately identifies the target box containing the $1000\text{ peso}$ bill.
  - Following Outcome 1B: Take any two boxes from the heavier $3\text{-box}$ group (e.g., box 1 and box 2) and place one on each pan. If one pan drops lower, that pan holds the target box. If they balance equally, the unweighed third box (box 3) contains the $1000\text{ peso}$ bill.
Complexity Classification: Implements a ternary logarithmic search strategy $O(\log_3(n))$ , successfully isolating the target item within $2$ weighings for $n = 8$ items.