Foundations of Algorithmic Design
In computer science, an algorithm is a step-by-step procedure for solving a problem. To design efficient
software, we must understand how to measure an algorithm’s performance and which strategy
(paradigm) is best suited for a specific type of problem.
1. Algorithm Complexity and Big O Notation
Algorithm complexity is the measure of the resources (time and memory) required by an algorithm as
the input size increases. We use Big O notation to describe the upper bound of an algorithm’s growth
rate.
Time Complexity: How the execution time increases with input size n .
Space Complexity: How much extra memory is required as n grows.
Common complexity classes include:
O(1) (Constant): Time remains the same regardless of n (e.g., accessing an array element).
O(logn) (Logarithmic): Time increases slowly (e.g., Binary Search).
O(n) (Linear): Time increases proportionally to n (e.g., finding the maximum in a list).
2
O(n ) (Quadratic): Time increases with the square of n (e.g., Nested loops).
n
O(2 ) (Exponential): Time doubles with each addition to n (e.g., Recursive Fibonacci).
2. Algorithmic Paradigms
When faced with a complex problem, we choose a design strategy based on the problem’s structure.
A. The Greedy Method
The Greedy method makes the locally optimal choice at each step with the hope of finding a global
optimum. It never reconsiders its decisions.
Characteristics: Simple, fast, but does not always find the best solution.
Example: The Fractional Knapsack Problem. If you want to fill a bag with items to maximize
value, a greedy approach takes the item with the highest value-to-weight ratio first.
# Simple Greedy Example: Coin Change (for specific denominations)
def greedy_coin_change(amount, coins):
[Link](reverse=True)
result = []
for coin in coins:
while amount >= coin:
amount -= coin
[Link](coin)
return result
B. Dynamic Programming (DP)
Dynamic Programming is used when a problem can be broken down into overlapping subproblems. It
stores the results of these subproblems (a technique called memoization) to avoid redundant
calculations.
Requirements:
Optimal Substructure: The optimal solution to the problem contains optimal solutions to
subproblems.
Overlapping Subproblems: The same subproblems are solved multiple times.
Example: The 0/1 Knapsack Problem. Unlike the fractional version, you cannot break items. DP
tracks the maximum value for every possible weight capacity.
DP [i][w]=max(DP [i −1][w ], valuei +DP [i−1][w − weighti ])
C. Backtracking
Backtracking is a refined brute-force approach. It builds a solution incrementally and “backs up”
(backtracks) as soon as it determines that the current path cannot lead to a valid solution.
Strategy: It uses a State-Space Tree and performs a Depth-First Search (DFS).
Example: The N-Queens Problem. Placing N queens on an N ×N chessboard such that no two
queens attack each other. If a queen placement leads to a conflict, the algorithm removes it and
tries the next position.
D. Branch-and-Bound (B&B)
Branch-and-Bound is typically used for optimization problems. It is similar to backtracking but uses a
“bounding function” to prune branches that cannot possibly yield a better solution than the one already
found.
Difference from Backtracking: While backtracking explores any valid path, B&B uses a cost
estimate to prioritize the most promising paths (often using Breadth-First Search or Best-First
Search).
Example: The Traveling Salesman Problem (TSP). Finding the shortest route that visits all cities
and returns to the start.
3. The Memory Model
To write efficient code, we must understand how the computer manages memory during execution.
The Stack:
Used for static memory allocation and function execution.
Follows Last-In-First-Out (LIFO).
Stores local variables and function call “frames.”
Very fast but limited in size.
The Heap:
Used for dynamic memory allocation.
Objects and data structures (like Linked Lists) are stored here.
Managed by the programmer (in C/C++) or by a Garbage Collector (in Python/Java).
Larger but slower to access than the stack.
4. Linked Lists
A Linked List is a linear data structure where elements are not stored in contiguous memory locations.
Instead, each element (called a Node) contains a pointer or reference to the next node.
Structure of a Node:
Data: The value stored.
Next: A reference to the next node in the sequence.
Advantages:
1. Dynamic size (can grow or shrink easily).
2. Efficient insertion and deletion (O(1) if the position is known).
Disadvantages:
1. No random access (must traverse from the head, O(n)).
2. Extra memory for pointers.
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def insert_at_beginning(self, new_data):
new_node = Node(new_data)
new_node.next = [Link]
[Link] = new_node
5. Summary Comparison
Technique Approach Best For Key Feature
Greedy Local Best Efficiency Irrevocable decisions
DP Subproblems Optimization Memoization
Backtracking DFS Feasibility State-space pruning
Branch-and-Bound BFS/Best-FS Optimization Bounding functions
Understanding these foundations allows a developer to look at a problem and immediately recognize
whether it requires the “memory” of Dynamic Programming or the “exploration” of Backtracking.