Problem Solving

A structured approach to problem-solving, covering fundamental strategies, techniques, and logical reasoning for effective solutions.

Introduction

Problem-solving is a fundamental skill in mathematics, computer science, and daily life. It involves analyzing a problem, identifying potential solutions, and implementing an effective approach. This guide explores systematic problem-solving methods and logical techniques that enhance critical thinking and efficiency.

Steps in Problem Solving

A structured approach to problem-solving consists of the following steps:

1. Understanding the Problem: Read and analyze the problem carefully.
2. Breaking It Down: Divide the problem into smaller, manageable parts.
3. Identifying Known and Unknowns: Define given inputs and required outputs.
4. Choosing a Strategy: Select an appropriate technique such as brute force, divide and conquer, or dynamic programming.
5. Implementing the Solution: Execute the plan step by step.
6. Reviewing and Optimizing: Analyze efficiency and refine the solution.

Problem-Solving Strategies

1. Brute Force Approach

A straightforward method that checks all possibilities.

findLargest.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> numbers = {4, 7, 1, 9, 3};
    int max_num = *max_element(numbers.begin(), numbers.end());
    cout << "Largest Number: " << max_num << endl;
    return 0;
}

2. Divide and Conquer

Break the problem into subproblems, solve them individually, and combine results.

binarySearch.cpp

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

3. Dynamic Programming

Optimize by storing results of subproblems.

fibonacci.cpp

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<int, long long> memo;
long long fibonacci(int n) {
    if (n <= 2) return 1;
    if (memo.count(n)) return memo[n];
    return memo[n] = fibonacci(n-1) + fibonacci(n-2);
}

Real-World Problem-Solving Examples

Example 1: Scheduling Tasks Efficiently

Using a Greedy Algorithm for task scheduling.

taskScheduling.ts

const tasks = [
  [1, 4],
  [2, 6],
  [8, 9],
  [5, 7],
];
tasks.sort((a, b) => a[1] - b[1]);
let schedule = [],
  end_time = 0;
for (let [start, end] of tasks) {
  if (start >= end_time) {
    schedule.push([start, end]);
    end_time = end;
  }
}
console.log("Optimized Schedule:", schedule);

Example 2: Shortest Path in a Network

Using Dijkstra’s Algorithm.

dijkstra.ts

import { MinPriorityQueue } from "@datastructures-js/priority-queue";
function dijkstra(graph, start) {
  let pq = new MinPriorityQueue({ priority: (x) => x[0] });
  let distances = Object.fromEntries(
    Object.keys(graph).map((n) => [n, Infinity])
  );
  distances[start] = 0;
  pq.enqueue([0, start]);
  while (!pq.isEmpty()) {
    let [dist, node] = pq.dequeue();
    for (let [neighbor, weight] of graph[node]) {
      let newDist = dist + weight;
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
        pq.enqueue([newDist, neighbor]);
      }
    }
  }
  return distances;
}

Conclusion

Problem-solving is a skill that improves with practice. By applying structured techniques and logical reasoning, you can efficiently tackle complex problems in mathematics, computer science, and real-world scenarios.

Recommended Reading

• “How to Solve It” by George Pólya
• “Introduction to Algorithms” by Cormen, Leiserson, Rivest, and Stein
• “The Art of Problem Solving” by Richard Rusczyk