Problem Solving &
Algorithms
Unlock the power of computational thinking and efficient programming.
Chapter 1
What is Problem Solving?
Problem-solving is the systematic process of identifying, analyzing, and developing a step-by-step method (algorithm) to solve a
problem. It's the bedrock of analytical thinking and the foundation for algorithm development, programming, and computational
thinking.
As Pascal Schneider describes, it's about applying knowledge, skills, and strategies to achieve a solution through logical steps.
Understand the Problem Plan a Solution
Clearly define what needs to be solved. Strategize the approach and design the algorithm.
Implement & Test Refine & Maintain
Execute the plan and verify its correctness. Improve and adapt the solution over time.
Defining Algorithms
An algorithm is a finite, well-defined sequence of step-by-step instructions designed to solve a specific problem or perform a
particular task.
According to Thomas Cormen, a good algorithm must be precise, unambiguous, logically ordered, and must terminate with a
correct result.
Think of it like a recipe. To cook a new dish, you follow a set of
instructions. If you follow the recipe perfectly, you get a
delicious dish. Similarly, if an algorithm is followed correctly, it
will produce the expected output.
Chapter 2
Key Characteristics of an Algorithm
For an algorithm to be effective, it must possess several fundamental characteristics that ensure its reliability and usability.
01 02 03
Input Output Definiteness (Unambiguity)
Algorithms require data to operate, like Every algorithm must yield at least one Each step must be clear, certain, and
fuel for a machine. While most need input result that provides the solution to the precise. Instructions should be
(numbers, letters), some can produce problem. The output must match the unambiguous to avoid multiple
output without explicit initial input (e.g., a expected format; for instance, if you input interpretations or incorrect results. For
"Welcome" page). names, you should get names as output, example, "use the spoon labeled 10ml" is
not numbers. definite, unlike "use the large spoon."
04 05
Finiteness Effectiveness
An algorithm must always terminate after a finite number of Each step must be sufficiently basic, simple, and executable.
steps. It cannot run indefinitely, preventing infinite loops and The steps must be practical, theoretically doable, and lead to a
ensuring that a solution (or a statement of no solution) is correct solution within finite time and resources.
eventually reached.
Designing for Success: Algorithm Evaluation
Criteria
Designing an algorithm isn't just about creating instructions; it's about crafting the best possible solution, balancing multiple
critical factors.
1 2 3
Correctness Efficiency (Time & Space) Readability & Simplicity
The absolute foundation. A correct How fast does it run, and how much Code is read more often than written.
algorithm always produces the memory does it need? Even correct Simple, well-commented, and logical
required output for every legal input, algorithms can vary wildly in their solutions are easier to implement,
satisfying all problem constraints. resource consumption. debug, and maintain over time.
In mission-critical systems, formal verification (mathematical proofs) is used to guarantee algorithmic behavior, eliminating
hidden bugs.
Chapter 3
Common Types of Algorithms
Different problems call for different approaches. Here are some of the most common algorithmic strategies.
Brute Force Backtracking
Tries all possible solutions exhaustively until the correct one is A trial-and-error method that explores potential solutions and
found. Simple but can be inefficient for large datasets (e.g., undoes choices when they lead to an incorrect outcome (e.g.,
Linear Search). solving mazes, N-Queens).
Dynamic Programming Greedy Algorithm
Stores and reuses intermediate results to avoid redundant Makes locally optimal choices at each step, hoping to find a
computations, enhancing efficiency for complex problems (e.g., global optimum. Not always guaranteed to find the best overall
Fibonacci sequence). solution (e.g., Kruskal's algorithm).
Divide and Conquer Randomized Algorithm
Breaks complex problems into smaller subproblems, solves Utilizes randomness in its steps to achieve a solution, often
them independently, and then combines their solutions (e.g., when an approximate or probabilistic answer is sufficient (e.g.,
Merge Sort, Quick Sort). Randomized Quick Sort).
Chapter 4
The Algorithm Design Process
A structured approach ensures robust and effective solutions.
Problem Definition
Clearly understand the problem, objectives, and
constraints.
Requirement Analysis
Identify functional (what it does) and non-functional
(how well it does it) requirements.
Identify Inputs & Outputs
List all data received and results produced for
traceability.
Choose Strategy
Select the best algorithmic approach for the problem
type.
Develop Algorithm
Write logical, unambiguous steps in natural language or
pseudocode.
Correctness & Validation
Verify logic with sample inputs and edge cases.
Analyze Performance
Evaluate time and space complexity using Big-O
notation.
Implementation
Convert the algorithm into executable code.
Testing & Debugging
Thoroughly test with various inputs; fix errors.
Optimization
Refine for efficiency and reduced resource usage.
Documentation
Clearly explain how it works, theory, examples, and
performance analysis.
Algorithm Showdown: Search Methods
Comparing two fundamental search algorithms.
Linear Search Binary Search
Approach: Checks every item in the list sequentially from Approach: Finds the midpoint of a sorted list, determines
start to finish. which half the target must be in, and repeatedly halves the
search space.
Time Complexity: O(N) - time grows linearly with list size.
Time Complexity: O(log N) - much faster for large lists.
Best Case: O(1) - item is the very first element.
Best Case: O(1) - item is in the center.
Required Condition: None (works on any list).
Required Condition: List MUST be sorted.
Sorting Algorithms: Bubble Sort vs. Merge Sort
Understanding the differences between two common sorting techniques.
Bubble Sort Merge Sort
Approach: Repeatedly steps through the list, compares Approach: A classic "Divide and Conquer" algorithm. It divides
adjacent elements, and swaps them if they are in the wrong the list into smaller halves until each piece is a single element,
order, causing larger elements to "bubble up." then repeatedly merges the smaller sorted lists.
Time Complexity: O(N²) in the worst case, making it Time Complexity: O(N log N) in all cases, making it much
inefficient for large lists. more efficient for larger datasets.
Best Case: O(N) when the list is already sorted. Worst Case: O(N log N).
Required Condition: None. Required Condition: None.
Algorithmic Efficiency: Mastering Time & Space
Beyond just working, efficient algorithms are crucial for applications to be responsive and scalable, especially with large datasets.
Time Complexity Space Complexity
Measures how an algorithm's execution time grows as the Measures the amount of memory (temporary variables, data
input size (N) increases. It's about predictable scaling, not structures, recursion stack) an algorithm needs as the input
raw speed in seconds. size (N) grows.
Big-O Notation: The Growth Rating
Big-O notation describes the worst-case scenario for an algorithm's performance, indicating how resource usage scales with input
size.
Linear Growth (O(N)) Quadratic Growth (O(N²)) Logarithmic Growth (O(log
Time or space grows directly in Time or space grows with the N))
proportion to the input size. square of the input size. Doubling Resource needs grow very slowly.
Doubling input doubles operations. input quadruples operations. A Doubling input adds only a tiny,
Good! disaster for large data! constant amount of operations.
Example: Searching an unsorted Example: Nested loops Superhero speed!
list item by item. comparing every item to every Example: Binary search on a
other item. sorted list, repeatedly halving
the search space.
The Time-Space Trade-off: Often, you can make an algorithm faster by using more memory (e.g., caching results) or conserve
memory by taking more time (recomputing values instead of storing them).
Case Study: Electricity Billing System Algorithm
A practical application of algorithmic design.
1. Problem Definition 2. Input / Output & Specification
Design an algorithm to calculate a customer's electricity Inputs: Customer Name, ID, Previous Meter Reading
bill based on previous and current meter readings, a fixed (PMR), Current Meter Reading (CMR), Tariff Rate (¦20),
tariff rate per unit, and additional service charges. The Service Charge (¦500), Meter Maintenance (¦200).
system must compute units consumed, the basic bill, and Outputs: Customer Name, ID, PMR, CMR, Units
the total payable amount, then display all results. Consumed, Basic Bill, Total Amount Payable.
Process: Read details, compute Units = CMR - PMR,
calculate Basic Bill = Units * Rate, then Total Bill =
Basic Bill + Fixed Charges, and finally, display
everything.
Algorithm Electricity_Billing_System
START
// Step 1: Input customer details
READ Customer_Name
READ Customer_ID
READ PMR
READ CMR
// Step 2: Input tariff and fixed charges
READ Rate ± 20
READ Service_Charge ± 500
READ Meter_Maintenance ± 200
// Step 3: Calculate units consumed
Units ± CMR - PMR
// Step 4: Calculate basic bill
Basic_Bill ± Units * Rate
// Step 5: Calculate total bill
Total_Bill± Basic_Bill + Service_Charge + Meter_Maintenance
// Step 6: Display results
PRINT "Customer Name: ", Customer_Name
PRINT "Customer ID: ", Customer_ID
PRINT "Previous Meter Reading: ", PMR
PRINT "Current Meter Reading: ", CMR
PRINT "Units Consumed: ", Units
PRINT "Tariff Rate: ¦", Rate, " per unit"
PRINT "Basic Bill: ¦", Basic_Bill
PRINT "Service Charge: ¦", Service_Charge
PRINT "Meter Maintenance: ¦", Meter_Maintenance
PRINT "Total Amount Payable: ¦", Total_Bill
END