Problem Solving Basics: Problem Definition, Logical Reasoning, Decomposition, Software

Design Concept of an Algorithm, Algorithm Representation – Algorithm Discovery – Iterative

Structures – Recursive Structures – Efficiency and Correctness - Implementation of Algorithms -
Fundamental Algorithms: Exchanging the values of two variables, Counting, Summation of a set
of numbers, Factorial computation, Generation of Fibonacci Sequence, Reversing the digits of an
Integer, Base Conversion.

1. Problem Definition
The first and most critical step in problem-solving is to clearly and precisely define the problem.
A vague or incorrect problem definition leads to wasted effort and an incorrect solution. Problem
definition involves understanding the problem's context, identifying the given inputs, and
specifying the desired outputs.
A well-defined problem statement should answer the following:
 What is the initial state or given data? (Input)
 What is the desired final state or goal? (Output)
 What are the constraints or rules that must be followed? (Limitations)
 What resources are available? (Time, Tools, Knowledge)
This process often involves dialogue with stakeholders to eliminate ambiguity. A problem should
be defined in terms of "what" needs to be achieved, not "how" it will be achieved, which is the
role of the algorithm.
Example: Poor vs. Good Problem Definition
 Poor: "Make our website better." (Vague, unmeasurable)
 Good: "Our website's product page has a 90% bounce rate. We need to redesign the 'Add
to Cart' button to increase its click-through rate by 25% within two months, without
changing the backend infrastructure." (Specific, measurable, achievable, constrained).
Tool: Input-Process-Output (IPO) Model
A simple but effective model for defining a problem.
+-------------------------+
| INPUT | --> The given data (e.g., a list of numbers)
+-------------------------+
|
V
+-------------------------+
| PROCESS | --> The transformation (e.g., sort the list)
+-------------------------+
|
V
+-------------------------+
| OUTPUT | --> The desired result (e.g., a sorted list)
+-------------------------+

2. Logical Reasoning
Logical reasoning is the process of using a rational, systematic series of steps based on sound
mathematical and logical principles to arrive at a conclusion. In problem-solving, it is the glue
that connects the problem definition to the solution. It involves:
 Deductive Reasoning: Applying general rules to specific cases to reach a logically
certain conclusion. If the rules are true, the conclusion is guaranteed to be true.
o Example: All algorithms are sequences of steps. Bubble Sort is an
algorithm. Therefore, Bubble Sort is a sequence of steps.
 Inductive Reasoning: Making generalized conclusions based on specific observations or
patterns. The conclusion is likely but not guaranteed.
o Example: I tested the sorting algorithm on 100 different lists, and it worked
correctly. Therefore, the algorithm will probably work for all lists. (Testing can
show the presence of bugs, but not their absence).
 Abductive Reasoning: Inferring the most likely explanation or cause for an observation.
This is often used in debugging.
o Example: The program crashed after the user entered a negative number. The
code doesn't handle negative numbers. Therefore, the crash was likely caused by
the unhandled negative input.
Logical reasoning is essential for predicting the behavior of an algorithm without having to run it
for every possible input, a process known as verification.
3. Decomposition
Decomposition is the strategy of breaking down a complex, large problem into smaller, simpler,
and more manageable sub-problems. These sub-problems are easier to understand, solve, and
often can be worked on independently or in parallel. The solutions to these sub-problems are
then combined to form the solution to the original complex problem.
This is a fundamental skill in computer science and software engineering, directly
enabling modular programming, where large programs are divided into smaller modules,
functions, or classes.
Flowchart: The Process of Decomposition
+--------------------------------+
| Complex Problem: |
| "Build a Web Browser" |
+--------------------------------+
|
V
+--------------------------------+
| Decomposition |
+--------------------------------+
|
+------------+------------+------------+
| | | |
V V V V
+----------------+ +----------------+ +----------------+ +----------------+
| Rendering | | Network | | JavaScript | | User Interface|
| Engine | | Stack | | Interpreter | | (UI) |
| (HTML/CSS) | | (HTTP, TLS) | | | | |
+----------------+ +----------------+ +----------------+ +----------------+
| | | |
+------------+------------+------------+
|
V
+--------------------------------+
| Integrated Web Browser |
+--------------------------------+

Example: Decomposing "Plan a University Class Schedule"

 Sub-problem 1: List all required courses for a degree.
 Sub-problem 2: List all course offerings for the semester (time, professor).
 Sub-problem 3: Identify and resolve time conflicts between desired courses.
 Sub-problem 4: Assign priority to courses (e.g., prerequisite first).
4. Software Design Concept of an Algorithm
An algorithm is a well-defined, finite, step-by-step procedure or formula for solving a problem or
accomplishing a specific task. It is the blueprint for the solution, independent of any
programming language. A valid algorithm must possess five key characteristics:
1. Finiteness: It must terminate after a finite number of steps.
2. Definiteness: Each step must be precisely defined and unambiguous.
3. Input: It has zero or more well-defined inputs.
4. Output: It produces one or more well-defined outputs.
5. Effectiveness: Each operation must be basic enough to be done exactly and in a finite
amount of time.
Example: Algorithm for Making Tea
1. Pour water into the kettle.
2. Boil the water.
3. Place a tea bag in a cup.
4. Pour the boiled water into the cup.
5. Let the tea bag steep for 3 minutes.
6. Remove the tea bag.
7. Add sugar or milk if desired.
This is a valid algorithm: it's finite, definite, has inputs (water, tea bag), produces an output (a
cup of tea), and each step is effective.

5. Algorithm Representation & Discovery

Algorithms are represented before coding to aid in logic design and communication.
 Natural Language: Easy to understand but can be ambiguous (e.g., the tea-making
algorithm above).
 Flowcharts: A visual representation using standardized symbols. Excellent for showing
control flow.
 Pseudocode: A high-level, informal, English-like description of code structure. It uses
the logic of programming but without strict syntax rules.
Algorithm Discovery is the creative process of finding the procedure to solve the problem. It's
not a mechanical process but involves intuition, experience, and techniques like pattern
recognition (have I solved a similar problem before?) and working backwards from the desired
output.
Flowchart Symbols:
+-------------+ +-------------+ +-------------------+
| Oval | | Parallelogram | Rectangle |
| | | | | |
| [Start/End] | | [Input/ | | [Process] |
| | | Output] | | |
+-------------+ +-------------+ +-------------------+

+-------------+ +-------------+
| Diamond | | Circle |
| | | |
| [Decision] | | [Connector] |
| | | |
+-------------+ +-------------+

6. Iterative & Recursive Structures

 Iterative Structures (Loops): Repeat a block of code multiple times until a terminating
condition is met. They use keywords like for, while, and do-while.
o Use Case: When the number of repetitions is known or is based on a condition
that changes during the loop's execution (e.g., process each item in a list).
 Recursive Structures: A function calls itself to solve a smaller instance of the same
problem. It must have:
1. A base case: a simple, solvable instance that stops the recursion.
2. A recursive case: a call to itself with a modified input that moves towards the
base case.
o Use Case: For problems that can naturally be broken into self-similar sub-
problems (e.g., traversing tree-like structures, Tower of Hanoi).
Example: Factorial of n (n!)
 Iterative Approach:
def factorial_iterative(n):
result = 1
for i in range(1, n+1): # Iterate from 1 to n
result = result * i
return result
  Recursive Approach:
python
def factorial_recursive(n):
if n == 0: # Base case: 0! is 1
return 1
else: # Recursive case: n! = n * (n-1)!
return n * factorial_recursive(n-1)

7. Efficiency and Correctness

 Correctness: An algorithm is correct if, for every input, it halts and produces the correct
output. This can be proven formally using mathematical techniques (like loop
invariants) or checked through extensive testing.
 Efficiency (Complexity Analysis): This measures the resources an algorithm requires,
primarily time (how long it takes to run) and space (how much memory it uses).
Efficiency is expressed using Big O notation, which describes the worst-case scenario
growth rate of an algorithm relative to its input size (n).
o O(1) - Constant Time: The runtime is independent of the input size (e.g.,
accessing an array element by index).
o O(n) - Linear Time: The runtime grows proportionally with the input size (e.g.,
finding the maximum value in an unsorted list).
o O(n²) - Quadratic Time: The runtime is proportional to the square of the input
size (e.g., a simple nested loop bubble sort).
Choosing an efficient algorithm is crucial for handling large-scale data.

8. Fundamental Algorithms
1. Exchanging Values of Two Variables
 Problem: Swap the values stored in variables a and b.
 Solution: Requires a temporary variable.
 Algorithm:
1. temp = a
2. a = b
3. b = temp
  Why a temp variable? Without it, doing a = b would overwrite the original value of a,
making it impossible to assign to b.
2. Counting
 Problem: Count the number of items in a list that meet a specific condition.
 Algorithm:
1. Initialize a counter variable to 0.
2. For each item in the list:
1. If the item meets the condition, increment the counter by 1.
3. The final value of the counter is the answer.
 Flowchart:

3. Summation of a Set of Numbers

 Problem: Calculate the sum of all numbers in a list.
 Algorithm:
1. Initialize a sum variable to 0.
2. For each number in the list:
1. Add the number to the sum.
3. The final value of the sum is the answer.
4. Factorial Computation (n!)
 Problem: Compute the product of all positive integers from 1 to n.
 Formula: n! = n * (n-1) * (n-2) * ... * 1 , where 0! = 1.
 Algorithm: (See iterative and recursive examples in section 6).

5. Generation of the Fibonacci Sequence

 Problem: Generate the first n terms of the Fibonacci sequence (each term is the sum of
the two preceding ones: 0, 1, 1, 2, 3, 5, 8...).
 Algorithm (Iterative):
1. Let a = 0, b = 1.
2. Print a and b.
3. For i from 3 to n:
1. next = a + b
2. Print next
3. a = b
4. b = next
6. Reversing the Digits of an Integer
 Problem: Reverse the digits of a positive integer (e.g., 1234 becomes 4321).
 Algorithm:
1. Initialize reversed_num = 0.
2. While the original number num is greater than 0:
1. digit = num % 10 (Get the last digit)
2. reversed_num = (reversed_num * 10) + digit
3. num = num // 10 (Remove the last digit)
3. reversed_num is the answer.
7. Base Conversion (Decimal to Base-b)
 Problem: Convert a decimal number to its representation in another base (e.g., base-
2/binary, base-16/hexadecimal).
 Algorithm (Repeated Division):
1. Create an empty list for digits.
2. While the decimal number n is greater than 0:
1. digit = n % b (Find the remainder)
2. Record the digit (converting 10-15 to A-F if base > 10).
3. n = n // b (Perform integer division)
3. The answer is the sequence of recorded digits read in reverse order.
 Example: Convert 13₁₀ to binary (base-2).
o 13 % 2 = 1, n = 13 // 2 = 6
o 6 % 2 = 0, n = 6 // 2 = 3
o 3 % 2 = 1, n = 3 // 2 = 1
o 1 % 2 = 1, n = 1 // 2 = 0 (Stop)
o Reading remainders backwards: 1101₂. ∴ 13₁₀ = 1101₂.