7 Steps to Programming a Problem

Programming is not just about writing lines of code; it's about solving problems efficiently and effectively. Whether you're a seasoned developer or just starting out on your coding journey, mastering the art of programming requires a structured approach. Here are 7 practical steps to help you become a proficient programmer:

Step 1: Work an Example

Before we jump into solving a problem, we need to really understand it. It's like trying to explain something you don't get yourself! So, let's start by working through a specific example. We'll keep it simple by looking at how to find where two rectangles overlap.

Getting What the Problem's About:

First things first, let's get what we're dealing with. We're asked to find the part where two rectangles meet. Oh, and by the way, these rectangles are either standing up or lying down.

Picking an Example:

Choosing a good example to work on is key. It needs to be easy enough to handle but still show us what's going on.

Example Time:

Imagine we've got two rectangles. One's painted yellow and goes from (-4,1) to (8,6), and the other's blue, stretching from (1,-1) to (4,7). Our job? To find where they both overlap, shown in green from (1,1) to (4,6).

Getting Hands-On:

Drawing helps a lot. We can see where the rectangles are and where they overlap. Even though coloring them isn't really part of the deal, it helps us understand.

Making Sense of the Picture:

Looking at our drawing, we can easily spot where the green area is—the part where the rectangles meet. But to write code for this, we need to get into the math behind it.

Doing the Math:

To write a program, we need to know the rules. In this case, it's about figuring out how rectangles intersect and coming up with a clear way to find that intersection.

More Examples, Maybe?:

Sometimes, the answer is so obvious that it's hard to explain how we got there. Working through a few more examples can help us understand better and see if there are any tricky situations we need to think about.

Step 2: Write Down What You Just Did:

To find the intersection of the two rectangles:

1. Identify the coordinates of the bottom left and top right corners of each rectangle.

- Rectangle 1: Bottom left (-2, 1), Top right (6, 3)

- Rectangle 2: Bottom left (-1, -1), Top right (4, 4)

2. Create a new rectangle representing the overlap.

- Determine the left coordinate as the maximum of the left coordinates of both rectangles (max(-2, -1) = -1).

- Determine the bottom coordinate as the maximum of the bottom coordinates of both rectangles (max(1, -1) = 1).

- Determine the right coordinate as the minimum of the right coordinates of both rectangles (min(6, 4) = 4).

- Determine the top coordinate as the minimum of the top coordinates of both rectangles (min(3, 4) = 3).

3. The resulting rectangle represents the intersection:

- Left: -1

- Bottom: 1

- Right: 4

- Top: 3

By following these steps, we find the intersection of the two rectangles. This process ensures clarity and precision in our approach to solving the specific instance of the problem.

Step 3: Generalizing The Values:

Generalizing Repetitions: Identifying repetitions in an algorithm is crucial for generalization. Repetitions typically involve performing similar steps multiple times, often with slight variations in values or conditions. By recognizing these patterns, we can make our algorithm more concise and adaptable to different scenarios.

For instance, let's reconsider the problem of printing a right triangle of stars, where the height and base are both N:

Given an integer N (>0), print a right triangle of *s, with height N and base N.

Following Step 2, we observed the repetition in the printing process:

1. Print 1 star
2. Print a newline
3. Print 2 stars
4. Print a newline
5. Print 3 stars
6. Print a newline
7. Print 4 stars
8. Print a newline
9. Print 5 stars
10. Print a newline

This sequence demonstrates a clear repetition: printing 'i' stars followed by a newline, where 'i' ranges from 1 to N. Generalizing this pattern, we arrive at the following algorithm:

Count (call it i) from 1 to N (inclusive)
  Print i stars
  Print a newline        

In this generalized algorithm, 'N' represents the height of the triangle, and 'i' iterates from 1 to N, controlling the number of stars printed on each line.

Generalizing Conditional Behavior: In some cases, certain steps in an algorithm are conditionally executed based on specific criteria. Identifying these conditions and their associated actions is essential for making the algorithm more adaptable to different scenarios.

For example, consider a problem where we find the sum of a list of numbers:

Given a list of numbers, find their sum.

In Step 2, we observed the process of adding each number to the running total:

1. Add 3 + 5 (= 8)
2. Add 8 + 42 (= 50)
3. Add 50 + 11 (= 61)
4. Your answer is 61

Upon scrutiny, we recognize that the steps involve adding each number to a running total, starting from an initial value of 0. Generalizing this process leads us to the following algorithm:

Set previous_total = 0
Count (call it i) from 1 to the total number of items
  Add (the ith number) to previous_total
Your answer is previous_total
        

In this generalized algorithm, 'previous_total' represents the running sum, which accumulates the values of the numbers in the list. The loop iterates over each item in the list, adding it to the running total.

Generalization Is Iterative: Generalizing an algorithm is an iterative process that involves refining and expanding its scope over multiple iterations. Each iteration may reveal new patterns or opportunities for abstraction, leading to a more versatile and efficient algorithm. By iteratively refining our algorithms, we can create solutions that are adaptable to a wide range of inputs and conditions.

Step 4: Test Your Algorithm:

Testing your algorithm is crucial to ensure its correctness and robustness across different scenarios. By applying your algorithm to various test cases, you can verify its behavior and identify any potential flaws or mis-generalizations. Here are some guidelines to effectively test your algorithm:

1. Qualitatively Different Test Cases:

Test your algorithm on instances of the problem that differ qualitatively from those used during its design phase. For example, in the case of our rectangle problem, consider testing with rectangles that overlap in different ways or have varying dimensions. This helps uncover any biases or assumptions in the algorithm that might limit its applicability.

2. Corner Cases:

Explore corner cases where the algorithm might behave differently. For instance, if your algorithm processes a list of items, test it with an empty list, a list containing only one item, and large or small lists. For algorithms involving counting or iteration, test with boundary values like zero or one to assess how the algorithm handles extreme cases.

3. Statement Coverage:

Strive to achieve statement coverage by ensuring that each line of your algorithm is executed at least once during testing. This involves designing test cases that exercise all branches and conditions in the algorithm. By systematically covering different execution paths, you can verify the correctness of each component and identify any unreachable or untested code segments.

4. Examination of Oddities:

Review your algorithm for any peculiar behaviors or edge cases that might lead to unexpected outcomes. For instance, if your algorithm consistently produces a certain output regardless of input, or if it never returns a specific value despite being a plausible result, investigate these anomalies. Consider whether there are test cases where the expected answer differs from the algorithm's output, highlighting potential deficiencies in its logic.

By following these guidelines and conducting thorough testing, you can validate the correctness and reliability of your algorithm before proceeding to implementation. Testing serves as a critical step in the development process, helping to uncover errors, refine the algorithm, and ensure its effectiveness across diverse scenarios.

Step 5: Translation To Code:

Translating your algorithm into code involves converting each step of the algorithm into executable instructions. Here's how you can proceed with the translation process:

1. Function Declaration: Start by declaring the function you are writing, including its name, parameters, and return type. If necessary, define any custom data structures or helper functions that the main function will use. So here we first define a struct ( or you can make a class) of rectangle and define some functions to be used like minimum, maximum function to return the min or max between 2 values and intersection function to return the rectangle which overlaps

struct rect_tag {
  float left;
  float bottom;
  float top;
  float right;
};
typedef struct rect_tag rect_t;

float minimum(float f1, float f2);
float maximum(float f1, float f2);
rect_t intersection(rect_t r1, rect_t r2);
        

2. Translating Algorithm Components: Translate each step of your algorithm into corresponding code statements. Pay attention to loops, conditional statements, mathematical computations, variable assignments, and return statements.

float minimum(float f1, float f2) {
  if (f1 < f2) {
    return f1;
  }
  else {
    return f2;
  }
}

float maximum(float f1, float f2) {
  if (f1 > f2) {
    return f1;
  }
  else {
    return f2;
  }
}

rect_t intersection(rect_t r1, rect_t r2) {
  rect_t ans;
  ans.left = maximum(r1.left, r2.left);
  ans.bottom = maximum(r1.bottom, r2.bottom);
  ans.right = minimum(r1.right, r2.right);
  ans.top = minimum(r1.top, r2.top);
  return ans;
}
        

3. Top-down Design and Composability: As you write your code, follow the principles of top-down design and composability. Break down complex tasks into smaller, manageable functions, and compose them together to build the overall functionality of your program. This approach promotes code readability, maintainability, and scalability.

By systematically translating your algorithm into code and adhering to best practices in programming, you can create well-structured, reliable software solutions that effectively solve the problem at hand.

Seems Solved right? but what if the given rectangles are not overlapping? That brings us to our next 2 steps.

Step 6: Design Test Cases:

Now that you have generalized your algorithm, it's crucial to design comprehensive test cases to validate its correctness and robustness. Observing that we were able to contemplate good test cases for our hypothetical problem without going through Steps 1–5, you can actually come up with a set of black-box tests for a problem before you start working on it. Some programmers advocate a test-first development approach. One advantage is that if you have a comprehensive test suite written before you start, you are unlikely to skip testing after you implement your code. Another advantage is that by thinking about your corner cases in advance, you are less likely to make mistakes in developing and implementing your algorithm.

Practical Tips for Designing Test Cases

Writing good test cases requires a lot of thought, as you need to consider a wide variety of things that can go wrong. Here are some suggestions to guide your thinking, as well as important lessons:

Testing Error Cases

1. Invalid Inputs: Test how your algorithm handles invalid inputs. For example, if your algorithm expects a positive integer, test it with zero, negative integers, and non-integer values.
2. Boundary Conditions: Test the boundaries of the input domain. If your algorithm processes a range of values, ensure you test the smallest and largest possible values within this range.

Testing Valid Inputs

1. Requirements Interpretation: Think carefully about the requirements, and consider whether something could be misinterpreted, easily mis-implemented, or have variations that could seem correct. For instance, if your algorithm works with sequences of decreasing numbers, test it with a sequence like 7 6 6 5 4 to check how it handles equal numbers.
2. Type Considerations: Consider what would happen if the programmer used the wrong type in a particular place. For example, using a 32-bit integer when a 64-bit integer is required, or using an integer type when a floating-point type is needed.
3. Off-by-One Errors: Consider any off-by-one errors the programmer might have made. If the algorithm involves counting, check what happens if the count starts or ends one position off. If it involves numerical comparison, see what happens if < and <= (or > and >=) are mixed up.

Specific Examples for Thought

1. Equal Number Sequences: Suppose your algorithm determines the number of even numbers in a sequence. A good test case for an off-by-one error might involve sequences where the last element's inclusion or exclusion changes the result:
2. Bad Test Case: Sequence 1: 2 3 5 6 9 8Sequence 2: 1 4 2 8 7 6Both correct and buggy algorithms may report Sequence 2 having more even numbers.
3. Good Test Case: Sequence 1: 2 3 5 6 9 8Sequence 2: 1 4 2 8 7 3A correct algorithm will report a tie (3 each), while a buggy one might still report Sequence 2 as having more even numbers.

Covering All Major Categories of Inputs

1. Numerical Inputs: Ensure you cover negative, zero, and positive numbers. Testing with one is also a good idea.
2. Sequences of Data: Your tests should include an empty sequence, a single-element sequence, and a sequence with many elements.
3. Characters: Test with lowercase letters, uppercase letters, digits, punctuation, spaces, and non-printable characters.

Problem-Specific Categories

1. Prime Numbers: If your function deals with prime numbers, ensure you test with both prime and composite numbers.
2. Combining Data Categories: If dealing with a sequence of numbers, test all combinations: Empty list, Single-element list with 0, Single-element list with a negative number, Single-element list with a positive number, Multiple-element list covering negative, zero, and positive numbers

Comprehensive Coverage

1. All Possible Answers: If your algorithm gives a set of possible answers (e.g., true/false, values from an enum, a specific set of strings), ensure your test cases cover each possible answer at least once.
2. Conditions and Answers: If your algorithm gives different answers based on input conditions (e.g., a numeric input leading to yes/no answers), test combinations like negative number yielding yes, negative number yielding no, positive number yielding yes, positive number yielding no, and zero.

White Box Testing

White box testing, also known as clear box or glass box testing, involves examining the internal structure of the code to devise test cases. Unlike black box testing, which focuses on the input-output behavior without regard to internal implementation, white box testing leverages knowledge of the code's inner workings to ensure thorough testing. A critical aspect of white box testing is test coverage—a measure of how well your test cases cover different behaviors of your code.

While white box and black box testing are different, they are not mutually exclusive but rather complementary. One might start by forming a set of black box test cases, implement the algorithm, and then create additional test cases to achieve the desired level of test coverage.

Consider the following example function:

int aFunction(int a, int b, int c) {
  int answer = 0;
  if (a < b) {
    answer = b - a;
  }
  if (b < c) {
    answer = answer * (b - c);
  } else {
    answer = answer + 42;
  }
  return answer;
}
        

We will discuss three levels of test coverage using this example: statement coverage, decision coverage, and path coverage.

Statement Coverage

Statement coverage means that every statement in the function is executed at least once. For instance, if we only use the test case with a=1, b=2, and c=3, we do not achieve full statement coverage because line 10 (the body of the else clause) is not executed. This lack of coverage indicates that our test cases do not fully exercise the function's behaviors.

Although statement coverage is a minimal starting point, it often falls short. For example, it does not ensure that we have tested cases where a < b evaluates to false, meaning we have not tested the scenario where we do not enter the first if statement (line 4).

Decision Coverage

A stronger level of coverage is decision coverage, which requires that all possible outcomes of decisions (boolean tests) are exercised. For every boolean test, you need a test case where the expression evaluates to true and another where it evaluates to false. For a switch/case statement, you need at least one test case per choice in the case statement plus one for the default case, even if it is implicit.

To visualize decision coverage, consider a control flow graph (CFG). A CFG is a directed graph whose nodes are basic blocks (sequences of statements executed in an all-or-nothing manner), and edges represent possible control flows (arrows) between them.

Here is the control flow graph for our example function:

[Start] -> [answer = 0; if (a < b)] -> [answer = b - a]
                           |             |
                           v             v
                          [if (b < c)] -> [answer = answer * (b - c)]
                           |             |
                           v             v
                          [answer = answer + 42] -> [return answer]
        

Decision coverage means covering every edge in this graph. For instance, if a < b is true, we take the left edge from the first block. If false, we take the right edge. Similarly, the second decision (if b < c) also has true and false paths. To achieve decision coverage, we need to test cases where each decision point evaluates to both true and false. Example test cases to achieve decision coverage might be:

• a=1, b=2, c=3 (covers a < b true, b < c true)
• a=5, b=2, c=1 (covers a < b false, b < c false)
• a=1, b=5, c=3 (covers a < b true, b < c false)

Path Coverage

Path coverage requires that all possible paths through the control flow graph are tested. Each unique path from the start to the end of the function represents a sequence of execution steps.

The paths through our example function are:

1. a < b true, b < c true
2. a < b true, b < c false
3. a < b false, b < c true
4. a < b false, b < c false

Each path needs to be covered by at least one test case. Here is a possible set of test cases to achieve path coverage:

• a=1, b=2, c=3 (Path 1)
• a=1, b=5, c=3 (Path 2)
• a=5, b=2, c=3 (Path 3)
• a=5, b=2, c=1 (Path 4)

Choosing the Right Level of Coverage

Why are there multiple levels of test coverage, and how do you pick the right level? Higher levels of coverage give more confidence in the code's correctness but require more test cases. For a simple function, a few test cases might suffice, but for complex code, achieving path coverage could involve an exponential number of test cases.

The choice of coverage level depends on the context:

• Preliminary Testing: If testing by hand, statement coverage may be sufficient as a preliminary check.
• Critical Software: For critical software, aim for higher coverage levels, such as decision or path coverage, to ensure thorough testing.

Step 7: Debugging the Scientific Method

The process of debugging can be effectively approached using the scientific method, a systematic way of observing, hypothesizing, and experimenting. Here is a structured approach to debugging using this method:

1. Observe a Phenomenon:
2. Ask a Question:
3. Gather Information and Apply Knowledge:
4. Form a Hypothesis:
5. Test the Hypothesis:
6. Accept or Reject the Hypothesis:

Practical Example

Consider you have a function that processes a list of numbers and returns the maximum value. However, it crashes when the list contains negative numbers. Here’s how you could debug it using the scientific method:

1. Observe a Phenomenon:
2. Ask a Question:
3. Gather Information and Apply Knowledge:
4. Form a Hypothesis:
5. Test the Hypothesis:
6. Accept or Reject the Hypothesis:

Remember the overlapping rectangle problem? What can be a good test case for it? What if the rectangle are not overlapping? how will you fix it? You can follow the Step 6 > Step 7 and Step 5 to fix it, can you do it? Don't read article further and really try to use the steps we learnt before looking at the solution below.

Here's the final solution.

rect_t* intersection(rect_t r1, rect_t r2) {
  rect_t* ans = (rect_t*)malloc(sizeof(rect_t));
  ans->left = maximum(r1.left, r2.left);
  ans->bottom = maximum(r1.bottom, r2.bottom);
  ans->right = minimum(r1.right, r2.right);
  ans->top = minimum(r1.top, r2.top);

  // Check if the rectangles do not overlap
  if (ans->left >= ans->right || ans->bottom >= ans->top) {
    free(ans);
    return NULL;
  }
  return ans;
}

int main() {
  rect_t r1 = { -2.0, 1.0, 3.0, 6.0 };
  rect_t r2 = { -1.0, -1.0, 4.0, 4.0 };
  rect_t* result = intersection(r1, r2);
  if (result == NULL) {
    printf("The rectangles do not overlap.\n");
  } else {
    printf("Intersection: left=%f, bottom=%f, right=%f, top=%f\n", result->left, result->bottom, result->right, result->top);
    free(result);
  }
  return 0;
}
        

I learnt it from my course for into to C specialization from Duke university, and if you are early in your career, I'd invite you to watch this course.

Hope these 7 steps help you write better code in an easier way with a systemized approach.

Feel free to connect with me for more advice and articles on anything Computers and Software.

#Algorithms #DataStructures #Coding #Programming #SoftwareDevelopment