Algorithms and problem solving are fundamental concepts in programming. An algorithm is a step-by-step procedure or formula for solving a problem. Problem-solving in programming involves understanding the problem, devising an algorithm to solve it, and then translating that algorithm into code.
In this explanation, we'll cover the following:
An algorithm is a well-defined, step-by-step procedure or set of instructions designed to perform a specific task or solve a specific problem. Algorithms can be implemented in any programming language.
For example, an algorithm to add two numbers can be as simple as:
A good algorithm must possess the following characteristics:
Problem-solving in programming involves several stages, which can be broken down as follows:
Clarify the problem: Ensure that you understand the problem requirements and constraints.
Identify input and output: What inputs does the program require? What output should it generate?
For example:
For the sum of numbers problem, the algorithm could look like this:
sum initialized to 0.sum.sum.There are several types of algorithms, and the choice of algorithm often depends on the problem at hand. Here are some basic types:
Sorting algorithms are used to arrange data in a specific order (ascending or descending). Common sorting algorithms include:
Bubble Sort: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. It’s simple but inefficient for large datasets.
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
Merge Sort: A more efficient algorithm that divides the list into halves, sorts each half recursively, and then merges the sorted halves. It has a better performance than bubble sort.
Search algorithms are used to find an element in a collection of data. Common search algorithms include:
Linear Search: This algorithm sequentially checks each element of the list until the desired element is found.
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Found, return index
}
}
return -1; // Not found
}
Binary Search: An efficient search algorithm used on sorted arrays. It repeatedly divides the search interval in half.
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid; // Found, return index
}
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Not found
}
A recursive algorithm solves a problem by calling itself with a smaller problem size. Recursion can be more elegant but requires careful handling of the base case to avoid infinite recursion.
Example: Factorial Calculation
The factorial of a number n (denoted as n!) is the product of all positive integers up to n.
int factorial(int n) {
if (n == 0) {
return 1; // Base case
}
return n * factorial(n - 1); // Recursive case
}
A greedy algorithm makes the locally optimal choice at each step, with the hope of finding the global optimum. It works well for problems where local optimums lead to a global optimum, but may not work for all types of problems.
Example: Coin Change Problem
The problem is to make change for a given amount using the least number of coins, assuming you have an unlimited supply of coins of certain denominations (like 1, 5, and 10).
A greedy approach would choose the largest coin that does not exceed the remaining amount and keep making this choice until the amount is reduced to zero.
Here are some problem-solving techniques commonly used in algorithm design:
Example: Merge Sort (already mentioned) is a divide-and-conquer algorithm.
Example: Fibonacci Sequence calculation using dynamic programming:
int fibonacci(int n) {
int fib[n+1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
return fib[n];
}
Example: N-Queens Problem (placing N queens on a chessboard such that no two queens threaten each other) is a classic backtracking problem.
Example: Linear Search (checking every item in a list one by one) is a brute force technique.
Open this section to load past papers