Module 10: Problem Solving Basics

Learning Objectives

By the end of this module, you will be able to:

• Understand the fundamentals of problem solving.
• Learn how to design algorithms.
• Create and understand flowcharts.
• Analyze time and space complexity.
• Understand Big O notation.
• Perform dry runs to debug programs.
• Solve common programming problems using logical thinking.
• Improve coding skills through practice problems.

Introduction

Programming is not just about writing code. The real skill lies in solving problems efficiently.

Every software application, game, website, or operating system is built by solving thousands of small and large problems.

A good programmer follows a structured approach:

1. Understand the problem.
2. Design a solution.
3. Analyze its efficiency.
4. Write the code.
5. Test and improve it.

This module focuses on developing your problem-solving mindset, which is the foundation of Data Structures and Algorithms (DSA).

What is Problem Solving?

Problem solving is the process of finding the most effective solution to a given problem.

Instead of immediately writing code, you should:

• Understand the input.
• Identify the expected output.
• Think about different approaches.
• Choose the best solution.
• Implement and test it.

Example:

Problem:

Find the largest number among three numbers.

Instead of coding immediately, first think:

• Compare the first and second numbers.
• Compare the larger value with the third.
• Print the largest value.

This logical thinking is called problem solving.

Steps to Solve Any Programming Problem

A systematic approach makes coding easier and reduces errors.

Step 1: Understand the Problem

Read the problem carefully.

Ask yourself:

• What is the input?
• What is the expected output?
• Are there any constraints?
• What are the edge cases?

Example:

Input

textCopy
110 20

Output

textCopy
130

Step 2: Design the Algorithm

Before coding, write the solution in simple steps.

Step 3: Draw a Flowchart (Optional)

Visualize the program flow.

Step 4: Write the Code

Convert the algorithm into a programming language such as C.

Step 5: Test with Different Inputs

Always test:

• Normal cases
• Boundary cases
• Invalid cases

What is an Algorithm?

An algorithm is a finite sequence of well-defined steps used to solve a problem.

Characteristics of a good algorithm:

• Clearly defined steps
• Finite number of steps
• Produces correct output
• Efficient
• Easy to understand

Example Algorithm

Problem

Find the sum of two numbers.

Algorithm

textCopy
1Step 1: Start
2Step 2: Read two numbers
3Step 3: Add the numbers
4Step 4: Display the result
5Step 5: Stop

C Program

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int a, b;
6
7    scanf("%d %d", &a, &b);
8
9    printf("Sum = %d", a + b);
10
11    return 0;
12}

Characteristics of a Good Algorithm

A good algorithm should have:

• Correctness
• Simplicity
• Efficiency
• Scalability
• Finite execution
• Well-defined input and output

What is a Flowchart?

A flowchart is a graphical representation of an algorithm.

Instead of writing text, symbols represent program steps.

Flowcharts help in:

• Planning programs
• Understanding logic
• Finding mistakes before coding
• Explaining solutions to others

Common Flowchart Symbols

Example Flowchart

Problem: Find whether a number is even or odd.

textCopy
1           Start
2              │
3              ▼
4        Read Number
5              │
6              ▼
7      Number % 2 == 0?
8         /           \
9       Yes            No
10       │              │
11       ▼              ▼
12 Print Even     Print Odd
13       │              │
14       └──────┬───────┘
15              ▼
16             End

Dry Run

A dry run means manually executing a program step by step without running it on a computer.

Dry runs help you:

• Find logical errors
• Understand loops
• Debug algorithms
• Improve programming skills

Example

cCopy
1int sum = 0;
2
3for(int i = 1; i <= 5; i++)
4{
5    sum += i;
6}

Dry Run Table

Final Output

textCopy
115

Time Complexity

Time complexity measures how the running time of an algorithm grows as the input size increases.

It does not measure actual execution time in seconds.

Example:

Finding the maximum element in an array of n elements requires checking each element once.

textCopy
1Operations ≈ n

Time Complexity

textCopy
1O(n)

Why Time Complexity Matters

Imagine two algorithms:

Algorithm A

textCopy
1100 operations

Algorithm B

textCopy
11,000,000 operations

For small inputs, both may seem fast.

For large inputs:

• Algorithm A remains efficient.
• Algorithm B becomes slow.

Efficient algorithms are essential for real-world applications.

Common Time Complexities

Space Complexity

Space complexity measures how much extra memory an algorithm uses.

Example:

cCopy
1int numbers[100];

Memory usage grows with the number of elements.

Space Complexity

textCopy
1O(n)

Examples

Constant Space

cCopy
1int sum = 0;

Extra memory remains constant.

Complexity

textCopy
1O(1)

Linear Space

cCopy
1int arr[n];

Memory grows with n.

Complexity

textCopy
1O(n)

Big O Notation

Big O notation describes the upper bound (worst-case growth) of an algorithm.

It focuses on how performance changes as the input size increases.

O(1) — Constant Time

Example

cCopy
1printf("%d", arr[3]);

Regardless of array size, accessing one index takes constant time.

O(n) — Linear Time

Example

cCopy
1for(int i = 0; i < n; i++)
2{
3    printf("%d", arr[i]);
4}

The loop runs n times.

O(n²) — Quadratic Time

Example

cCopy
1for(int i = 0; i < n; i++)
2{
3    for(int j = 0; j < n; j++)
4    {
5        printf("*");
6    }
7}

Nested loops execute approximately n × n times.

O(log n) — Logarithmic Time

Example:

Binary Search repeatedly divides the search space by half.

textCopy
11024
2↓
3
4512
5↓
6
7256
8↓
9
10128
11↓
12
1364
14↓
15
16...
17↓
18
191

Very efficient for sorted data.

How to Analyze Complexity

Single Loop

cCopy
1for(int i = 0; i < n; i++)

Complexity

textCopy
1O(n)

Nested Loops

cCopy
1for(int i = 0; i < n; i++)
2{
3    for(int j = 0; j < n; j++)
4    {
5
6    }
7}

Complexity

textCopy
1O(n²)

Consecutive Loops

cCopy
1for(int i = 0; i < n; i++)
2{
3
4}
5
6for(int i = 0; i < n; i++)
7{
8
9}

Complexity

textCopy
1O(n)

Not O(2n) because constants are ignored in Big O notation.

Practice Problem 1: Number Problems

Check Prime Number

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int n, isPrime = 1;
6
7    printf("Enter a number: ");
8    scanf("%d", &n);
9
10    if(n <= 1)
11        isPrime = 0;
12
13    for(int i = 2; i * i <= n && isPrime; i++)
14    {
15        if(n % i == 0)
16            isPrime = 0;
17    }
18
19    if(isPrime)
20        printf("Prime Number");
21    else
22        printf("Not a Prime Number");
23
24    return 0;
25}

Time Complexity

textCopy
1O(√n)

Practice Problem 2: Pattern Problems

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int n;
6
7    printf("Enter rows: ");
8    scanf("%d", &n);
9
10    for(int i = 1; i <= n; i++)
11    {
12        for(int j = 1; j <= i; j++)
13        {
14            printf("* ");
15        }
16
17        printf("\n");
18    }
19
20    return 0;
21}

Output

textCopy
1*
2* *
3* * *
4* * * *
5* * * * *

Time Complexity

textCopy
1O(n²)

Practice Problem 3: Mathematical Problems

Factorial

cCopy
1#include <stdio.h>
2
3int main()
4{
5    int n;
6    long long factorial = 1;
7
8    printf("Enter a number: ");
9    scanf("%d", &n);
10
11    for(int i = 1; i <= n; i++)
12    {
13        factorial *= i;
14    }
15
16    printf("Factorial = %lld", factorial);
17
18    return 0;
19}

Time Complexity

textCopy
1O(n)

Tips to Improve Problem-Solving Skills

• Understand the problem before coding.
• Solve the problem manually with sample inputs.
• Break large problems into smaller tasks.
• Write algorithms before implementing them.
• Perform dry runs to validate your logic.
• Start with a simple solution, then optimize it.
• Practice coding problems consistently.

Common Mistakes to Avoid

• Writing code without understanding the problem.
• Ignoring edge cases such as empty input or zero.
• Skipping dry runs.
• Focusing only on making the code work instead of making it efficient.
• Choosing overly complex solutions for simple problems.
• Not analyzing time and space complexity.

Best Practices

• Think first, code second.
• Write clear and simple algorithms.
• Use meaningful variable names.
• Test your solution with multiple inputs.
• Analyze the complexity of every solution.
• Optimize only after ensuring correctness.
• Keep your code readable and modular.

Module Summary

In this module, you learned:

• The importance of problem-solving in programming.
• How to design algorithms and visualize them using flowcharts.
• How to perform dry runs to verify program logic.
• The concepts of time complexity, space complexity, and Big O notation.
• How to analyze the efficiency of common programming constructs.
• How to solve number, pattern, and mathematical problems using logical thinking.

After completing this module, you'll be ready to learn Searching Algorithms, where you'll study Linear Search and Binary Search, compare their performance using Big O analysis, and understand how efficient searching forms the basis of many advanced data structures and algorithms.