In this tutorial, you'll build your own spam email classifier from scratch using the Naive Bayes algorithm. By the end, you'll have a working model that achieves over 97% accuracy—and you'll understand exactly how it works under the hood.

This project was inspired by the Python Machine Learning Workbook for Beginners by AI Publishing, which offers excellent hands-on ML projects for those starting their journey. (Note: I have no affiliation with the authors — I simply found it a useful resource.)

Table of Contents

• Prerequisites

• Why Naive Bayes for Spam Detection?

• How to Set Up Your Environment

• How to Load and Explore the Dataset

• How to Visualize the Data Distribution

• How to Analyze Word Patterns with Word Clouds

• Preprocessing the Text Data

• How to Convert Text to Numerical Features

• How to Train the Naive Bayes Classifier

• How to Evaluate Model Performance

• Testing on Individual Emails

• Key Takeaways

What You'll Learn

• How email spam filters actually work

• The intuition behind the Naïve Bayes algorithm

• Text preprocessing techniques for machine learning

• How to evaluate classification models

• Building a complete spam detection pipeline in Python

Prerequisites

You should have basic familiarity with Python and some understanding of fundamental machine learning concepts. Don't worry if you're still learning—I'll explain everything as we go.

Why Naive Bayes for Spam Detection?

Before we dive into code, let's understand why Naive Bayes is particularly well-suited for this task.

Imagine you receive an email containing words like "free," "winner," "click here," and "limited time offer." Your brain immediately flags this as suspicious. The Naive Bayes algorithm does something similar—it calculates the probability that an email is spam based on the words it contains.

The algorithm is called "naive" because it makes a simplifying assumption: it treats each word as independent of every other word. In reality, word combinations matter (think "free trial" vs. "free money"), but this simplification works remarkably well in practice.

Why Choose Naive Bayes?

• Speed: It trains incredibly fast, even on large datasets

• Efficiency: Requires minimal training data to produce reliable results

• Simplicity: Easy to implement and interpret

• Performance: Despite its simplicity, it often outperforms more complex algorithms for text classification

Limitations to keep in mind:

• The independence assumption means it can't capture relationships between words

• If a word appears in the test data but never appeared in training, the algorithm assigns it zero probability (though there are ways to handle this)

Now let's build our spam detector.

How to Set Up Your Environment

First, install the required libraries. Open your terminal or run this in a Jupyter notebook cell:

%pip install regex wordcloud numpy pandas seaborn matplotlib scikit-learn

Here's a quick summary of what each library does:

• regex / re — for cleaning text using pattern matching

• wordcloud — for visualizing which words appear most frequently

• numpy and pandas — for data loading and manipulation

• seaborn and matplotlib — for charts and visualizations

• scikit-learn — provides the Naive Bayes classifier, vectorizer, and evaluation tools

Once installation is complete, import everything at the top of your script or notebook. Grouping all imports at the top is a Python best practice — it makes dependencies easy to spot at a glance.

# Data manipulation and analysis
import pandas as pd
import numpy as np

# Data visualization
import seaborn as sns
import matplotlib.pyplot as plt

# Natural language processing
import nltk
import re
from nltk.corpus import stopwords

# Machine learning
from sklearn.naive_bayes import MultinomialNB
from sklearn.model_selection import train_test_split
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics import classification_report, confusion_matrix, accuracy_score

# Word cloud visualization
from wordcloud import WordCloud

How to Load and Explore the Dataset

We'll use a dataset of labeled emails. You can download it from Kaggle or use any similar email dataset with text and spam columns.

Use pandas' read_csv() function to load the dataset from a CSV file into a DataFrame — a table-like structure that makes it easy to inspect and manipulate data. The head() method then displays the first 5 rows so you can confirm the data loaded correctly and understand its structure.

message_dataset = pd.read_csv('emails.csv')
message_dataset.head()

Output:

Next, call shape on the DataFrame to check its dimensions — this returns a tuple of (rows, columns) and is a quick way to confirm you loaded the full dataset without truncation.

# Get the dimensions of our dataset (rows, columns)
message_dataset.shape

Output:

(5728, 2)

The dataset contains 5,728 emails with two columns: text (the email content) and spam (1 for spam, 0 for legitimate emails).

How to Visualize the Data Distribution

Before training any model, it's crucial to understand your data. Let's see how spam and legitimate emails are distributed.

value_counts() tallies how many emails belong to each class (spam vs. legitimate). Chaining .plot(kind="pie") on the result converts those counts directly into a pie chart. The autopct="%1.0f%%" argument tells matplotlib to label each slice with its percentage, rounded to the nearest whole number.

plt.rcParams["figure.figsize"] = [8, 10]
message_dataset.spam.value_counts().plot(kind="pie", autopct="%1.0f%%")

Output:

You'll see that approximately 24% of emails in the dataset are spam, while 76% are legitimate. This is a moderately imbalanced dataset, which we'll keep in mind when evaluating our model.

How to Analyze Word Patterns with Word Clouds

Word clouds provide an intuitive visualization of the most frequent words in a text corpus. Words that appear more often are rendered larger. Let's create separate word clouds for spam and legitimate emails to identify distinguishing patterns.

First, we need to remove stop words — common words like "the," "is," and "at" that appear everywhere and carry no meaningful signal for classification. NLTK's stopwords.words("english") returns a pre-built list of these words. The apply() method runs a function across every row in the column, and the lambda inside it splits each email into individual words, filters out any stop words, then rejoins the remaining words into a clean string.

stop = stopwords.words("english")

message_dataset["text_without_sw"] = message_dataset["text"].apply(
    lambda x: "".join([item for item in x.split() if item not in stop])
)

Now let's visualize the spam emails. We filter the DataFrame to rows where spam == 1, join all that text into a single large string, and pass it to WordCloud().generate(). The imshow() function renders the resulting image, and axis("off") hides the x/y axes since they're not meaningful for an image display.

message_dataset_spam = message_dataset[message_dataset["spam"] == 1]

plt.rcParams["figure.figsize"] = [8, 10]
text = ' '.join(message_dataset_spam['text_without_sw'])
wordcloud2 = WordCloud().generate(text)

plt.imshow(wordcloud2)
plt.axis("off")
plt.show()

Output:

Now do the same for legitimate emails by filtering to rows where spam == 0:

message_dataset_ham = message_dataset[message_dataset["spam"] == 0]

plt.rcParams["figure.figsize"] = [8, 10]
text = ' '.join(message_dataset_ham['text_without_sw'])
wordcloud2 = WordCloud().generate(text)

plt.imshow(wordcloud2)
plt.axis("off")
plt.show()

Output:

Key observations:

• Spam emails frequently contain promotional language: "free," "money," "offer," "click," "please"

• Legitimate emails contain more conversational and work-related terms: "company," "time," "thanks"

You'll also notice the word "enron" appearing prominently in the legitimate emails cloud. This is because the non-spam emails in this dataset are drawn from the publicly available Enron email corpus — a large collection of real internal emails from Enron Corporation that was released during their 2001 fraud investigation. It has since become one of the most widely used benchmark datasets in NLP research, which is why "enron" shows up so frequently as a word in legitimate email content.

These patterns give us confidence that word-based classification will work well.

How to Preprocess the Text Data

Raw text needs cleaning before machine learning algorithms can process it effectively. Let's first separate our features from our labels. In ML terminology, X holds the inputs (the email text we use to make predictions) and y holds the target labels (1 for spam, 0 for legitimate).

X = message_dataset["text"]
y = message_dataset["spam"]

Now we'll define a function to clean the text. The re.sub() function from Python's built-in re module performs pattern-based substitution using regular expressions. We call it three times in sequence:

1. re.sub('[^a-zA-Z]', ' ', doc) — replaces anything that isn't a letter (numbers, punctuation, symbols) with a space. This strips noise that doesn't help with classification.

2. re.sub(r'\s+[a-zA-Z]\s+', ' ', document) — removes isolated single characters (like "I" or "a" left behind after removing punctuation) by matching any single letter surrounded by whitespace.

3. re.sub(r'\s+', ' ', document) — collapses multiple consecutive spaces into a single space, tidying up any extra gaps created by the previous two steps.

def clean_text(doc):
    document = re.sub('[^a-zA-Z]', ' ', doc)
    document = re.sub(r'\s+[a-zA-Z]\s+', ' ', document)
    document = re.sub(r'\s+', ' ', document)
    return document

Apply this cleaning function to every email in the dataset. We first convert the pandas Series to a plain Python list using list(), then loop through each email, clean it, and collect the results in X_sentences.

# Create an empty list to store cleaned emails
X_sentences = []

# Convert the pandas Series to a list for iteration
reviews = list(X)

# Clean each email and add it to our list
for rev in reviews:
    X_sentences.append(clean_text(rev))

How to Convert Text to Numerical Features

Machine learning algorithms work with numbers, not text. We need to transform our cleaned text into a numerical representation.

TF-IDF (Term Frequency-Inverse Document Frequency) is a great choice for this. It assigns each word a score that reflects how important it is to a particular document relative to the entire dataset. A word that appears often in one email but rarely across all emails gets a high score — meaning it's distinctive and likely meaningful. Common words that appear everywhere get a lower score.

TfidfVectorizer from scikit-learn handles this transformation. The parameters we set control what gets included:

• max_features=2500 — only keeps the 2,500 most frequent words, discarding rare ones that don't generalize well

• min_df=5 — ignores words that appear in fewer than 5 emails (too rare to be useful)

• max_df=0.7 — ignores words that appear in more than 70% of all emails (too common to be distinctive)

• stop_words=stopwords.words('english') — removes common English words like "the" and "is"

fit_transform() does two things in one step: it learns the vocabulary from our text (fit), then converts each email into a numerical vector based on that vocabulary (transform). Calling .toarray() on the result converts the sparse matrix output — which stores only non-zero values for efficiency — into a regular dense NumPy array that scikit-learn classifiers expect.

vectorizer = TfidfVectorizer(
    max_features=2500,
    min_df=5,
    max_df=0.7,
    stop_words=stopwords.words('english')
)

X = vectorizer.fit_transform(X_sentences).toarray()

Each email is now represented as a vector of 2,500 numbers, where each number is the TF-IDF score for a specific word.

How to Train the Naive Bayes Classifier

Now comes the exciting part — training our model! First, split the data into training and test sets using train_test_split(). This function randomly shuffles and divides both X and y simultaneously, keeping labels aligned with their corresponding emails. Setting test_size=0.20 reserves 20% of the data for testing. Setting random_state=42 seeds the random number generator so you get the same split every time you run the code, making your results reproducible.

X_train, X_test, y_train, y_test = train_test_split(
    X, y,
    test_size=0.20,
    random_state=42
)

Now train the Multinomial Naive Bayes classifier. We use MultinomialNB specifically because it's designed for features that represent counts or frequencies — exactly what TF-IDF scores are. Calling fit(X_train, y_train) trains the model by having it calculate the probability of each word appearing in spam versus legitimate emails across the training set. Those probability tables are what the model uses later to classify new emails.

spam_detector = MultinomialNB()
spam_detector.fit(X_train, y_train)

That's it! The Naive Bayes algorithm is remarkably fast—training completes in milliseconds even with thousands of emails.

How to Evaluate Model Performance

Let's see how well our spam detector performs on emails it has never seen before. The predict() method takes the test set features and returns a predicted label (0 or 1) for each email, based on the probability tables the model learned during training.

y_pred = spam_detector.predict(X_test)

Now evaluate the predictions using three different tools from scikit-learn's metrics module:

• confusion_matrix() — produces a 2×2 grid comparing actual vs. predicted labels, showing exactly where the model gets things right and wrong

• classification_report() — prints precision, recall, and F1-score for each class, giving a more complete picture than accuracy alone

• accuracy_score() — returns the overall percentage of correct predictions

print(confusion_matrix(y_test, y_pred))
print(classification_report(y_test, y_pred))
print(accuracy_score(y_test, y_pred))

Output:

[[849   7]
 [ 18 272]]

              precision    recall  f1-score   support

           0       0.98      0.99      0.99       856
           1       0.97      0.94      0.96       290

    accuracy                           0.98      1146
   macro avg       0.98      0.96      0.97      1146
weighted avg       0.98      0.98      0.98      1146

0.9781849912739965

Our model achieves 97.82% accuracy! Let's break down what the confusion matrix tells us:

• 849: Legitimate emails correctly identified as legitimate (True Negatives)

• 7: Legitimate emails incorrectly marked as spam (False Positives)

• 18: Spam emails that slipped through as legitimate (False Negatives)

• 272: Spam emails correctly caught (True Positives)

The classification report shows:

• For legitimate emails (class 0): 98% precision, 99% recall

• For spam emails (class 1): 97% precision, 94% recall

These numbers are impressive, especially considering the simplicity of our approach.

How to Test on Individual Emails

Let's verify our model works by testing it on a specific email. We'll first print the cleaned text at index 56 and its actual label to see what we're working with. Then we'll ask the model to predict it.

print(X_sentences[56])
print(y[56])

Output:

Subject localized software all languages available hello we would like to offer localized software versions german french spanish uk and many others aii iisted software is available for immediate downioad no need to wait week for cd deiivery just few exampies norton lnternet security pro windows xp professionai with sp fuil version corei draw graphics suite dreamweaver mx homesite inciudinq macromedia studio mx just browse our site and find any software you need in your native ianguaqe best reqards kayieen 
1

This is clearly a spam email trying to sell pirated software. The actual label is 1 (spam). Now pass this single email through the same pipeline — first transforming it into a TF-IDF vector using the already-fitted vectorizer, then calling predict() on the result. It's important to use the same vectorizer that was fitted on the training data, so the word-to-index mapping is consistent.

print(spam_detector.predict(vectorizer.transform([X_sentences[56]])))

Output:

[1]

The model correctly identifies this promotional email as spam.

Key Takeaways

1. Naive Bayes is powerful for text classification despite its simplifying assumptions. For spam detection, it achieves excellent accuracy with minimal computational cost.

2. Text preprocessing matters. Removing noise (special characters, numbers, extra spaces) helps the algorithm focus on meaningful patterns.

3. TF-IDF captures word importance effectively. It gives higher weight to distinctive words that help differentiate spam from legitimate emails.

4. Always evaluate with multiple metrics. Accuracy alone can be misleading, especially with imbalanced datasets. Precision, recall, and F1-score give a complete picture.

5. Start simple. Before reaching for complex deep learning models, try classical algorithms like Naïve Bayes. They're interpretable, fast, and often surprisingly effective.

Next Steps

Want to improve this spam detector further? Here are some ideas:

• Experiment with different vectorizers: Try CountVectorizer or word embeddings (Word2Vec, GloVe)

• Handle class imbalance: Use techniques like SMOTE or adjust class weights

• Feature engineering: Add features like email length, number of links, or sender domain

• Try other algorithms: Compare with SVM, Random Forest, or gradient boosting

• Deploy the model: Build a simple API using Flask or FastAPI

Conclusion

You've built a spam email classifier that achieves over 97% accuracy using the Naïve Bayes algorithm. Along the way, you learned about text preprocessing, feature extraction with TF-IDF, and model evaluation techniques.

The beauty of this approach is its simplicity. With just a few dozen lines of code, you've created something that actually works—and now you understand the principles behind commercial spam filters.

Feel free to experiment with the code, try different parameters, and see how the results change. That's the best way to deepen your understanding.

References

• Python Machine Learning Workbook for Beginners: 10 Machine Learning Projects Explained from Scratch by AI Publishing

This Algorithm Analysis Deep Dive course is taught by Computer Science Professor Dr. Qiang Hao. It goes beyond surface-level rules to help you understand the core mathematical reasoning behind performance.

Here are a list of the key sections in the course:

• Introduction to time complexity

• Time complexity analysis of insertion sort

• Asymptotic analysis

• Divide and conquer - Recurrence tree method

• Divide and conquer - Master theorem

• Probabilistic analysis - Quicksort

• Probabilistic analysis - Average case and expected value

• Heaps and heapsort

• Hashtables

• Binary search trees

• Amortized analysis

This course is designed to connect the dots between the code you write and the theory behind it. And you can get all the course materials, like quizzes, assignments, and solutions, from the companion GitHub repository to follow along and test your knowledge.

Watch the full course on the freeCodeCamp.org YouTube channel (6-hour watch).

We just published a comprehensive course on the freeCodeCamp.org channel about data structures and algorithms. This course will help you prepare for coding interviews and strengthen your foundational programming skills. Sheldon Chi developed this course.

Sheldon will break down the most essential data structures and algorithmic patterns. This course will help you build your intuition for efficiency and help you recognize which patterns to apply and how to avoid brute force solutions. And each concept is taught step by step, with practical code walkthroughs and tips for common pitfalls.

Here is the full list of sections in this course:

• Array

• String

• Set

• Control Flow & Looping

• Big O Notation

• Hashmap

• Hashmap practice problems

• Two Pointers

• Two Pointers practice problems

• Sliding Window

• Sliding Window practice problems

• Binary Search

• Binary Search practice problems

• Breadth-First Search (BFS) on Trees

• BFS on Graphs

• BFS practice problems

• Depth-First Search (DFS)

• DFS on Graphs

• DFS practice problems

• Backtracking

• Backtracking practice problems

• Priority Queue/heap

• Priority Queue/heap practice problems

Watch the full course on the freeCodeCamp.org YouTube channel (1-hour course).

In this hands-on tutorial, you will learn how to implement queues in TypeScript using linked lists.

Here’s what we’ll cover

• Prerequisites

• Getting started

• What are Queues?

• What are Linked Lists?

• What is a Simple Queue?

• What is a Circular Queue?

• What is a Double Ended Queue?

• What is a Priority Queue?

• When to Use Queues (and When to Avoid Them)

• Conclusion

Prerequisites

1. TypeScript: You need to know TypeScript basics, such as interfaces, types, and classes.

2. Algorithm fundamentals: You need a basic understanding of data structures and algorithms. For example, you should be comfortable analyzing time and space complexity using Big-O notation.

3. Linked Lists Data Structure: It's important to have a solid understanding of linked lists before starting this tutorial. I wrote a detailed linked list tutorial that you can use to learn about this data structure.

Getting Started

To get started with this tutorial, you’ll use a playground project that’s designed to help you implement queues and follow each step hands-on.

Clone the project from the GitHub repository and code along with the tutorial.

The project structure is as follows:

.
├── index.ts
├── examples
│   ├── 01-linked-list.ts
│   ├── 02-simple-queue.ts
│   ├── 03-circular-queue.ts
│   ├── 04-double-ended-queue.ts
│   └── 05-priority-queue.ts
└── playground
    ├── 01-linked-list.ts
    ├── 02-simple-queue.ts
    ├── 03-circular-queue.ts
    ├── 04-double-ended-queue.ts
    └── 05-priority-queue.ts

Throughout the tutorial, you will use the playground directory to implement and test your code.

The examples directory contains the final version of each implementation. If you get stuck, you can look at these solutions as a last resort!

What Are Queues?

A queue is a data structure that manages items in a first-in, first-out (FIFO) order, where the first item added is the first removed.

For example, imagine a printer handling jobs. If you send three documents to print, the printer processes them in the order they arrive. The first document prints first, then the second, and finally the third.

In programming, queues help manage tasks that need to happen in order, such as:

• A web server queues incoming requests to process them one by one.

• A chat app queues messages to send them in the order they’re typed.

• A navigation app queues locations to explore a map level by level. (Breadth-First Search)

There are four types of queues in a data structure:

• Simple Queue: Adds items to the back and removes them from the front in first-in, first-out (FIFO) order.

• Circular Queue: It is similar to a simple queue, except the last element is connected to the first.

• Double-Ended Queue (Deque): Allows adding or removing items from both front and back, like a bus stop line where people join or leave either end.

• Priority Queue: Processes items based on priority, not arrival order. Like a delivery app processes VIP orders before regular ones.

Each of these queues has a set of operations for managing their items. In this tutorial, you will learn about the following common and widely used operations:

• enqueue: Adds an item to the back of the queue, like a new customer joining the end of a ticket line.

• dequeue: Removes and returns the item at the front of the queue.

• getFront: Looks at the item at the front without removing it, like checking who’s first in line.

• getRear: Looks at the item at the back without removing it, like seeing who’s last in line.

• isEmpty: Checks if the queue has no items.

• isFull: Checks if the queue has reached its maximum size.

• peek: Same as getFront, views the front item without removing it, like a quick glance at the first task.

• size: Returns the number of items in the queue, like counting how many people are in line.

Now that you know about queues and their main operations, let's get into the actual implementation and see how it looks in code.

There are a few different ways to implement queues, but in this tutorial, you will learn about linked list-based queues, which use a linked list to create the queues.

First, let's briefly learn about the linked list data structure and then move on to the queue implementation.

What Are Linked Lists?

A linked list is a method of storing a collection of items where each item, known as a "node," contains two parts: the actual data and a reference (or pointer) to the next item in the list.

Unlike arrays, where all items are stored next to each other in memory, linked lists connect nodes using these references, like a chain.

Linked lists are used to implement queues because they allow efficient insertion at the end and removal from the front, which are the two main operations of a queue.

In a linked list-based queue, you can add a new node at the tail and remove one from the head in constant time (O(1)) without needing to shift elements, as you would in an array.

In this tutorial, you are going to use a specific type of linked list called Circular Doubly Linked List.

A circular doubly linked list is a type of linked list where each node connects to both the next and previous nodes, and the last node loops back to the first one to form a circle.

This means you can move through the list in both directions and never hit a dead end. This makes it easy to go forward or backward through nodes and helps avoid special cases like handling null at the ends.

In a circular doubly linked list, everything is connected in a loop, which simplifies certain queue operations and keeps things efficient.

You can learn more about circular linked lists in my Linked Lists Handbook.

For this tutorial, I’ve already added a circular doubly linked list in src/playground/01-linked-list.ts:

// 📁 src/playground/01-linked-list.ts

/**
 * Node for doubly linked list
 */
export class NodeItem<T> {
  value: T;
  next: NodeItem<T> | null = null;
  prev: NodeItem<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

/**
 * Circular Doubly Linked List
 */
export class LinkedList<T> {
  private head: NodeItem<T> | null = null;
  private tail: NodeItem<T> | null = null;
  private currentSize: number = 0;

  /**
   * Add a new node to the front of the list
   * @param value The value to add
   */
  prepend(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.head!.prev = newNode;
      this.tail!.next = newNode;
      this.head = newNode;
    }
    this.currentSize++;
  }

  /**
   * Add a new node to the back of the list
   * @param value The value to add
   */
  append(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.head!.prev = newNode;
      this.tail = newNode;
    }
    this.currentSize++;
  }

  /**
   * Remove and return the value from the front of the list
   * @returns The value at the head or undefined if empty
   */
  deleteHead(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.head!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head!.next;
      this.head!.prev = this.tail;
      this.tail!.next = this.head;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Remove and return the value from the back of the list
   * @returns The value at the tail or undefined if empty
   */
  deleteTail(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.tail!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail!.prev;
      this.tail!.next = this.head;
      this.head!.prev = this.tail;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Get the value at the front without removing it
   * @returns The value at the head or undefined if empty
   */
  getHead(): T | undefined {
    return this.head?.value;
  }

  /**
   * Get the value at the back without removing it
   * @returns The value at the tail or undefined if empty
   */
  getTail(): T | undefined {
    return this.tail?.value;
  }

  /**
   * Check if the list is empty
   * @returns True if the list is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.currentSize === 0;
  }

  /**
   * Get the current size of the list
   * @returns The number of nodes in the list
   */
  size(): number {
    return this.currentSize;
  }
}

In this module, you have a circular doubly linked list with 8 different methods that will make it easier to build queues later in the tutorial:

• prepend: Adds a new value to the front of the list.

• append: Adds a new value to the end of the list.

• deleteHead: Removes and returns the value at the front.

• deleteTail: Removes and returns the value at the end.

• getHead: Returns the front value without removing it.

• getTail: Returns the end value without removing it.

• isEmpty: Checks whether the list has no items.

• size: Returns the number of items currently in the list.

Now that your linked list is ready, let's begin creating your first queue!

What is a Simple Queue?

A Simple Queue follows the basic FIFO rule: you’ll to add items to the back and remove them from the front.

It’s like a line of customers at a ticket counter, where the first person in line buys a ticket first.

To get started, open src/playground/02-simple-queue.ts, where you will find the placeholder for the Simple Queue with its methods:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  ...methods
}

At the core of this SimpleQueue class, you're using a circular doubly linked list to store the items, and optionally allowing a maximum size limit to control how big the queue can grow.

• private list: LinkedList<T> is where the queue's data is stored. Instead of a simple array, you're using a custom linked list, which makes it efficient to add or remove items from either end. The linked list manages the data structure and allows you to focus on how the queue works.

• private maxSize is an optional limit for how many items the queue can hold. If not provided, the queue can grow as large as needed.

• Then, the constructor method that runs when you create a new queue. It creates a new, empty linked list to hold the queue items.

Now, let's implement the queue methods.

Open your code editor and update src/playground/02-simple-queue.ts with the following code:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

As you can see, the linked list greatly simplifies your queue implementation because it acts as the engine behind your queue.

Here's how your Simple Queue works:

• isEmpty(): This method checks whether the queue contains any items. It calls the isEmpty() method on the linked list, which internally checks if the current size of the list is zero. If the list has no nodes, it returns true, indicating that the queue is empty. This is a basic utility method often used before attempting to dequeue or inspect the queue.

• isFull(): This method determines whether the queue has reached its capacity. It compares the current size of the linked list (via the size() method) to the optional maxSize value. If maxSize is defined and the size is equal to or greater than that limit, it returns true, indicating that no more items can be added. This is useful to prevent overflow in bounded queues.

• size(): This method returns the number of items currently stored in the queue. It directly calls the size() method of the linked list, which tracks how many nodes are present. This allows you to monitor queue usage and remaining capacity.

• enqueue(): This method adds a new item to the end (rear) of the queue. It first checks whether the queue is full by calling the isFull() method. If it is, the method throws an error. Otherwise, it appends the new item to the internal linked list using the append() method, which adds the new node to the tail of the circular doubly linked list.

• dequeue(): This method removes and returns the item at the front of the queue. It calls the deleteHead() method of the linked list, which removes the head node and updates the links of the surrounding nodes to maintain the circular structure. If the queue is empty, it returns undefined.

• getFront(): This method returns the value at the front of the queue without removing it. It uses the getHead() method of the linked list to retrieve the value of the head node. This operation does not modify the queue and is useful for previewing the next item to be dequeued.

• getRear(): This method returns the value at the rear of the queue without removing it. It uses the getTail() method of the linked list, which returns the value of the tail node. This helps you inspect the most recently added item without altering the queue.

• peek(): This method is an alias for getFront(). It returns the item at the front of the queue without removing it. Internally, it calls getFront() to get the head value. This is often used in queue APIs to check the next item in line.

You’ve just implemented your first queue in TypeScript. To make sure that your implementation works correctly, run the following command in your terminal at the root of the project:

npm run test:file 02

If any of the tests fail, use the final example from src/examples/02-simple-queue.ts to debug the issue, and then run the tests again.

If all tests pass, you can proceed to the next section, where you'll implement a Circular Queue.

What is a Circular Queue?

A CircularQueue is a fixed-size queue where the last position connects back to the first. This allows you to reuse space after removing items.

Imagine a buffet line with a limited number of plates: when someone takes a plate from the front, a new one is added at the back, using the same space again.

The CircularQueue is quite similar to the SimpleQueue, but it has a few unique differences.

Let’s modify src/playground/03-circular-queue.ts and add the following code:

// 📁 src/playground/03-circular-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Circular Queue implemented with a circular doubly linked list
 */
export class CircularQueue<T> {
  private list: LinkedList<T>;
  private maxSize: number;

  /**
   * @param maxSize Required maximum size of the circular queue
   */
  constructor(maxSize: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Circular queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

This may look very similar to a SimpleQueue, but there are a few key differences:

• Constructor Difference: Unlike the SimpleQueue, the CircularQueue requires a maxSize parameter during instantiation. This enforces a strict upper limit on how many elements can be in the queue at once.

  In contrast, SimpleQueue treats maxSize as optional and allows unbounded queues. By making the size mandatory, CircularQueue is better suited for fixed-size buffer scenarios where memory or resource control is important (for example, in real-time systems or caching).

• enqueue(): This method is almost identical to the one in SimpleQueue, but the key difference lies in the design intent. In CircularQueue, throwing an error when the queue is full is part of the contract and it assumes that you’re managing a fixed buffer.

  The circular nature comes into play conceptually: once full, no more data can enter unless older entries are removed, which mimics a circular overwrite mechanism (though this specific implementation doesn’t auto-overwrite).

• isFull(): This method behaves the same as in SimpleQueue when a maxSize is set, but in CircularQueue, it’s always applicable because maxSize is required. The consistent presence of a size limit makes the queue predictable and ideal for bounded use cases like streaming data and rate-limited processing.

Now, let's test the implementation to see if it works:

npm run test:file 03

If any of the tests fail, use the final /examples directory to debug the issue.

If the tests pass, you'll be ready to move on to the next section, where you will learn about double-ended queues.

What is a Double Ended Queue?

A double-ended queue (deque) lets you add or remove items from both the front and the back.

It’s like a line at a bus stop where people can join or leave from either end.

Let’s modify src/playground/04-double-ended-queue.ts and add the following code:

// 📁 src/playground/04-double-ended-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Double-Ended Queue (Deque) implemented with a circular doubly linked list
 */
export class Deque<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the deque
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the front of the deque
   * @param item The element to add
   */
  enqueueFront(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.prepend(item);
  }

  /**
   * Add an element to the rear of the deque
   * @param item The element to add
   */
  enqueueRear(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the deque
   * @returns The element at the front or undefined if empty
   */
  dequeueFront(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Remove and return the element from the rear of the deque
   * @returns The element at the rear or undefined if empty
   */
  dequeueRear(): T | undefined {
    return this.list.deleteTail();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the deque is empty
   * @returns True if the deque is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the deque is full
   * @returns True if the deque is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the deque
   * @returns The number of elements in the deque
   */
  size(): number {
    return this.list.size();
  }
}

Now, let's go through the methods:

• enqueueFront(): This method allows adding an element to the front of the deque, unlike in SimpleQueue or CircularQueue which only support adding to the rear. Internally, it uses list.prepend(item) to insert the item at the head.

  This operation makes the deque suitable for use cases where elements need to be pushed and popped from both ends, like in undo/redo systems or task schedulers.

• enqueueRear(): This behaves similarly to SimpleQueue’s enqueue, adding elements to the rear using list.append(item).

  The distinction in Deque is that this is just one of two symmetric operations and it gives you full double-ended control.

• dequeueFront(): This removes and returns the element from the front of the deque using list.deleteHead().

  While similar to the dequeue method in queues, the naming here is explicit to clarify that it's operating on the front and can be paired with a rear counterpart.

• dequeueRear(): This is a unique feature to deques, it removes and returns the element at the rear using list.deleteTail(). This complements dequeueFront() and enables LIFO (stack-like) behavior if needed.

• Constructor Difference: Like SimpleQueue, the Deque accepts an optional maxSize. This allows for flexible configurations.

  You can have unbounded deques when maxSize is not provided, or fixed-size deques when constraints are important. This is in contrast to CircularQueue, which requires a max size.

Once you have completed the implementation, run the following command to test the module:

npm run test:file 04

Now, you're ready to move on to the last section of the tutorial, where you'll learn about the Priority Queue.

What is a Priority Queue?

A priority queue processes items based on their priority, not their order of arrival.

Higher-priority items are removed first, like an emergency room where patients with severe conditions are treated before others.

Let’s modify src/playground/05-priority-queue.ts:

// 📁 src/playground/05-priority-queue.ts

import { LinkedList, NodeItem } from "./01-linked-list";

/**
 * Interface for an element with priority
 */
interface PriorityItem<T> {
  value: T;
  priority: number;
}

/**
 * Priority Queue implemented with a circular doubly linked list
 */
export class PriorityQueue<T> {
  private list: LinkedList<PriorityItem<T>>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the priority queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<PriorityItem<T>>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the queue based on its priority
   * Higher priority numbers are dequeued first
   * @param value The value to add
   * @param priority The priority of the value (higher number = higher priority)
   */
  enqueue(value: T, priority: number): void {
    if (this.isFull()) {
      throw new Error("Priority queue is full");
    }

    const newItem: PriorityItem<T> = { value, priority };
    if (this.isEmpty()) {
      this.list.prepend(newItem);
      return;
    }

    let current = this.list["head"];
    let count = 0;
    while (
      current &&
      current.value.priority >= priority &&
      count < this.size()
    ) {
      current = current.next;
      count++;
    }

    if (count === this.size()) {
      this.list.append(newItem);
    } else {
      const newNode = new NodeItem(newItem);
      newNode.next = current;
      newNode.prev = current!.prev;
      if (current!.prev) {
        current!.prev.next = newNode;
      } else {
        this.list["head"] = newNode;
      }
      current!.prev = newNode;
      if (current === this.list["head"]) {
        this.list["head"] = newNode;
      }
      this.list["tail"]!.next = this.list["head"];
      this.list["head"]!.prev = this.list["tail"];
      this.list["currentSize"]++;
    }
  }

  /**
   * Remove and return the element with the highest priority from the queue
   * @returns The value with the highest priority or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead()?.value;
  }

  /**
   * Get the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead()?.value;
  }

  /**
   * Get the element with the lowest priority without removing it
   * @returns The value at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail()?.value;
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

Let's understand how the methods work within a Priority Queue:

• enqueue(): This method inserts a new element into the queue based on its priority. Unlike other queue types where order is based on insertion time, PriorityQueue uses a sorting mechanism where elements with higher priority values are placed closer to the front.

  The method traverses the linked list from the head, searching for the correct position where the new item should be inserted so that the list remains sorted in descending priority order.

  It manually adjusts the prev and next pointers to keep the circular doubly linked list intact. This sorting during insertion ensures quick access to the highest priority element later.

• dequeue(): This method removes and returns the element with the highest priority, which is always positioned at the front of the list.

  Internally, it calls deleteHead() and then returns the value from the PriorityItem<T> node. Because items are sorted during insertion, this operation is always efficient and retrieves the correct item.

• getFront(): This retrieves the value at the front of the queue without removing it. Since the list is sorted in descending priority, this value always represents the highest priority item.

• getRear(): This returns the value at the rear of the queue, which is the item with the lowest priority. It accesses the last element in the list using getTail() and extracts the value.

• isEmpty(): This checks whether the queue contains any elements by delegating to the linked list’s isEmpty() method.

• isFull(): This checks whether the queue has reached its maximum allowed size. It compares the current size with maxSize if it's defined.

• peek(): This is functionally equivalent to getFront(). It provides a clearer semantic name when users want to examine the highest-priority element without removing it.

• size(): This returns the total number of items currently in the priority queue. It's useful for monitoring capacity or debugging.

• Key Differences: The priority queue differs from other queue types by enforcing order during insertion based on a numeric priority.

  This enables constant-time access to the highest priority element but introduces linear-time insertion complexity due to the need to find the correct place for each new element.

  It supports advanced scheduling and load balancing use cases where task urgency or importance matters more than arrival time.

Once you’re done with the implementation, run the following command to test your code:

npm run test:file 05

That’s it, congratulations!

You have successfully completed the tutorial and learned about queues and their different variations. Great job!

Before reaching conclusions, let’s briefly learn about where to use queues and where to avoid them. We’ll also discuss the bottlenecks and issues that queues may create if not used correctly and in the right place.

When to Use Queues (and When to Avoid Them)

Queues are ideal in scenarios where tasks or data must be processed in the exact order they arrive, such as in job scheduling and event handling systems.

For example, when multiple print jobs are sent to a printer, a queue can make sure each document is printed in the order it was submitted.

Similarly, queues are used in operating systems for managing tasks in thread pools or CPU scheduling (for example, Round Robin), where order is crucial.

Queues are also heavily used in asynchronous communication systems such as message brokers like RabbitMQ and Kafka.

In these systems, producers and consumers operate independently: a producer pushes messages into the queue, and a consumer processes them later.

This pattern is extremely useful in microservices architecture or serverless environments, where different parts of a system need to remain loosely coupled and highly scalable.

Similarly, in real-time systems like video streaming or sensor data ingestion, queues help buffer incoming data to avoid data loss and allow for smooth downstream processing.

When to Avoid Queues

Queues are not well-suited for problems that require random access to elements, complex search operations, or sorting.

Since queues typically allow insertion at one end and removal from the other, they’re inefficient for use cases where you frequently need to access elements in the middle or search through all items.

An array, tree, or hash map would serve better in such cases.

Using queues inappropriately can introduce unnecessary complexity and hidden bottlenecks.

For instance, blindly placing a queue between every microservice might decouple components but also make debugging and failure handling more difficult.

Over-queuing can also lead to backpressure problems where queues grow uncontrollably under high load which will increase latency or even crashing the system if not managed properly.

So you should use queues deliberately: when order, buffering, or async processing is required.

Conclusion

Queues are a basic data structure that work well when you need order and async processing.

Queues are useful for handling tasks, streaming data, or coordinating services, and making sure things run smoothly and efficiently.

But they aren't suitable for every problem. It's important to understand their pros and cons to use them correctly and avoid unnecessary complexity.

Thanks for following along with this tutorial. You can follow me on X, where I share more useful tips on data structures and web development.

Happy coding!

In this article, we'll explore the concept of binary exponentiation, understand how it works, and implement it in code.

What is Binary Exponentiation?

Binary exponentiation is a method to compute \(a^n\) (a raised to the power of n) using only multiplications, instead of the naïve \(O(n)\) multiplications.

This significant improvement in efficiency makes it possible to calculate extremely large powers quickly, even when dealing with modular arithmetic.

How Binary Exponentiation Works

The key idea behind binary exponentiation is to break down the exponent into its binary representation and use the properties of exponents to simplify the calculation.

Let's break it down step by step:

1. Convert the exponent n to its binary representation.

2. Initialize the result as 1 and the base as a.

3. Iterate through each bit of the binary representation of n from right to left: (a). If the current bit is 1, multiply the result by the current base. (b). Square the base (multiply it by itself).

4. Return the final result.

For example, let's calculate \(3^{13}\):

1. Convert 13 to binary: \(13_{10} = 1101_2\)

2. Initialize result = 1, base = 3

3. Iterate through the bits:

   • Bit 1: result = \(1 *3 = 3\), base = \(3 *3 = 9\)

   • Bit 0: result = 3, base = \(9 * 9 = 81\)

   • Bit 1: result = \(3 *81 = 243\), base = \(81 *81 = 6561\)

   • Bit 1: result = \(243 * 6561 = 1,594,323\)

Thus, \(3^{13}=1,594,323.\)

Why Binary Exponentiation is Efficient

The efficiency of binary exponentiation comes from two main factors:

1. Reduced number of multiplications: Instead of performing n-1 multiplications as in the naïve approach, we only perform \(O(log n)\) multiplications. This is because we're essentially breaking down the problem into smaller subproblems based on the binary representation of the exponent.

2. Reuse of previous calculations: By squaring the base at each step, we're reusing the results of previous calculations, which significantly reduces the overall number of operations needed.

To illustrate this efficiency, consider calculating \(a^{1000000}\). The naïve approach would require 999,999 multiplications, while binary exponentiation would only require about 20 multiplications (as \(\log_2(1000000) \approx 20\)).

Algorithm Implementation

Let's implement the binary exponentiation algorithm in Python:

def binary_exponentiation(base, exponent):
    result = 1
    while exponent > 0:
        # If the current bit is 1, multiply the result by the current base
        if exponent & 1:
            result *= base
        # Square the base
        base *= base
        # Move to the next bit
        exponent >>= 1
    return result

# Example usage
print(binary_exponentiation(3, 13))  # Output: 1594323

Let's break down the algorithm:

1. We initialize result to 1, which is the identity for multiplication.

2. We use a while loop to iterate until the exponent becomes 0.

3. We check if the least significant bit of the exponent is 1 using the bitwise AND operator &. If it is, we multiply the result by the current base.

4. We square the base by multiplying it by itself.

5. We use the right shift operator >>= to move to the next bit of the exponent.

6. Finally, we return the result.

Time Complexity Analysis

The time complexity of binary exponentiation is \(O(log n)\), where n is the exponent. This is because:

1. The number of bits in the binary representation of n is \(\lfloor \log_2 n\rfloor + 1\).

2. We perform at most two multiplications per bit (one for squaring the base, and potentially one for updating the result).

Therefore, the total number of multiplications is at most \(2(\lfloor \log_2 n \rfloor + 1)\), which simplifies to \(O(\log n)\).

Example Problems and Solutions

Let's look at some algorithmic problems that you can solve efficiently using binary exponentiation, along with detailed explanations of the solutions and how we arrived at using binary exponentiation.

Problem 1: Modular Exponentiation

Problem: Calculate \(3^{1000000} \bmod 1000000007\).

Approach:

1. We recognize that this problem involves a very large exponent (1000000), which would be impractical to compute using naïve exponentiation.

2. We also notice that we need to find the result modulo a large prime number (1000000007).

3. This combination of a large exponent and modular arithmetic is a clear indicator that we should use modular binary exponentiation.

Solution: We'll modify our binary exponentiation function to include modular arithmetic:

def mod_binary_exponentiation(base, exponent, mod):
    result = 1
    base %= mod
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent >>= 1
    return result

print(mod_binary_exponentiation(3, 1000000, 1000000007))  # Output: 624098969

Explanation:

1. We initialize result to 1 and set base to base % mod to handle cases where the initial base is larger than the modulus.

2. The main loop works similarly to the original binary exponentiation algorithm, but with two key differences:

   a. When updating result, we perform (result * base) % mod. This ensures that result never exceeds mod, preventing integer overflow and maintaining the correct modular result.

   b. When squaring base, we perform (base * base) % mod for the same reason.

3. The bitwise operations (exponent & 1 and exponent >>= 1) work exactly as in the original algorithm, allowing us to process the binary representation of the exponent efficiently.

4. By applying the modulo operation at each step, we ensure that all intermediate results remain within the range [0, mod-1]. This is possible because of the properties of modular arithmetic:

   $$(a⋅b)modm=((amodm)⋅(bmodm))modm$$

This problem would be impossible to solve with naïve exponentiation due to the huge result, but modular binary exponentiation makes it tractable by keeping all intermediate results manageable.

Problem 2: Matrix Exponentiation

Problem: Given a 2x2 matrix A, calculate An where n = 1000000.

Approach:

1. We observe that we need to raise a matrix to a very large power (1000000).

2. Matrix multiplication is associative, which allows us to use the same principle as binary exponentiation for numbers.

3. We recognize that this is a perfect scenario for applying binary exponentiation to matrices.

Solution: We can use binary exponentiation on matrices. Here's a Python implementation with explanations:

import numpy as np

def matrix_multiply(A, B, mod):
    return np.array([[(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod, (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
                     [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod, (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod]])

def matrix_power(A, n, mod):
    result = np.eye(2, dtype=int)
    while n > 0:
        if n & 1:
            result = matrix_multiply(result, A, mod)
        A = matrix_multiply(A, A, mod)
        n >>= 1
    return result

A = np.array([[1, 1], [1, 0]])
n = 1000000
mod = 1000000007

result = matrix_power(A, n, mod)
print(result)  # Output: [[690749268 297612485]
                #         [297612485 393136783]]

Explanation:

1. matrix_multiply(A, B, mod):

   • This function performs matrix multiplication of two 2x2 matrices, A and B.

   • Each element of the resulting matrix is computed using the standard matrix multiplication formula, followed by a modulo operation to keep the values manageable.

2. matrix_power(A, n, mod):

   • This function implements binary exponentiation for matrices.

   • We start with result as the 2x2 identity matrix (created using np.eye(2, dtype=int)).

   • The main loop follows the same pattern as scalar binary exponentiation: a. If the current bit of n is 1, we multiply result by the current A. b. We square A (by multiplying it with itself). c. We right-shift n to move to the next bit.

   • All matrix multiplications are done using our matrix_multiply function, which incorporates modular arithmetic.

This matrix exponentiation technique is particularly powerful for solving linear recurrence relations in logarithmic time, as demonstrated here with the Fibonacci sequence.

Practice Problems

Here are some problems for you to solve using binary exponentiation:

1. Modular Exponentiation: Calculate \(7^{1234567} \bmod 1000000009\). (Hint: Use the mod_binary_exponentiation function from Problem 1 in the examples.)

2. Last Digit: Find the last digit of . (Hint: Observe the pattern of last digits of powers of 2 and use binary exponentiation with modulo 10.)

3. Power Tower: Calculate the last 3 digits of \(2^{2^{20}}\). (Hint: Use the property of modular arithmetic that \(a^b \bmod m = a^{b \bmod \phi(m)} \bmod m\) where \(\phi\) is Euler's totient function. You'll need to calculate \(2^{20} \bmod \phi(1000)\) first.)

4. Matrix Chains: Given a 2x2 matrix A = [[1, 2], [3, 4]], calculate the last two digits of the sum of all elements in \(A^{1000000}\). (Hint: Use matrix exponentiation as in Problem 2 from the examples, but only keep track of the last two digits of each element. You'll need to sum the elements after the final exponentiation.)

5. Fibonacci Sequence: Find the 1000000th Fibonacci number modulo 1000000007. (Hint: Use the matrix form of the Fibonacci sequence ([[1, 1], [1, 0]]) and apply matrix exponentiation as shown in Problem 2 of the examples.)

Conclusion

Binary exponentiation is a powerful technique that can be applied to a wide range of problems involving large exponents. As we've seen in the example and practice problems, it's particularly useful in modular arithmetic, matrix operations, and solving recurrence relations.

By practicing these problems, you'll gain a deeper understanding of how to apply binary exponentiation in various scenarios. Remember, the key is to recognize when a problem involves raising something to a large power, whether it's a number, a matrix, or even a more complex structure.

If you found this explanation of Binary Exponentiation algorithm helpful, you might also enjoy more in-depth programming tutorials and concepts I cover on my blog.

In my Lisp interpreter, the brackets could be mixed like this:

(let [(x 10])
  [+ x x)]

The above code is an example of an S-Expression where we have tokens, a sequence of characters with meaning (like name let or number 10), and brackets/parentheses. However, the code is not valid because it mixes pairs of parentheses and brackets.

(let [(x 10)]
  [+ x x])

This is the proper Lisp syntax (if brackets are supported), where opening parentheses always match closing parenthesis and opening brackets always match closing brackets.

In this article, I'll show you how you can detect if the input is the second valid S-Expression and not the first invalid S-Expression.

We will also handle cases like this:

(define foo 10))))

In the code above, you see invalid syntax with more closing than opening parentheses.

So in simple terms, we will detect if pairs of opening and closing characters like (), [], and {} match inside the string like "[foo () {bar}]".

The solution to this problem can be useful when implementing a Lisp parser, but you can also use it for different purposes (like some kind of validation or part of a math expression evaluator). It's also a good exercise.

NOTE: to understand this article and code, you don't need to know anything about Lisp. But if you want some more context, you can read this article: What is Lisp and Scheme?

Pairing with the Stack Data Structure

You may think that the simplest way to solve this problem is using Regular Expressions (RegExp). It may be possible to use Regex for simple cases, but soon it will get too complex and have more problems than it solves.

Actually, the easiest way of pairing opening and closing characters is using the stack. Stack is the simplest data structure. We have two basic operations: push, for adding an item to the stack, and pop, for removing an item.

This works similarly to a stack of books. The last item that you put onto the stack will be the first one that you take out.

You can read more about this data structure from this article: Data Structures 101: Stacks.

With a stack, it's easier to process (parse) the characters, which have a beginning and end, like XML tags or simple parentheses.

For example, say we have this XML code:

<element><item><sub-item>text</sub-item></item></element>

When we use the stack, the last tag we open (inner <sub-item> for example) will always be the first we need to close (if the XML is valid).

So if we use the stack, we can push the item <sub-item> when we open it, and when we need to close it we can pop it from the stack. We only need to make sure that the last item on the stack (which is always the opening tag) matches the closing one.

We will have exact same logic with parentheses.

Note that if we have XML self-closing tags, we can skip them since they are open and automatically closed.

Arrays in JavaScript have both methods (push and pop), so they can be used as a Stack. But it's more convenient to create an abstraction in the form of a class, so we can add additional methods like top() and is_empty() that are easier to read.

But even if we didn't add new methods, it's always better to create abstractions like this, because it makes the code simpler and easier to read.

Most developers know common data structures and will immediately recognize them and not need to think about them. The most important thing with programming is forgetting not related stuff that are required at any given moment. The human memory is limited and can only hold about 4±1 items at the same time. You can read more about short-term memory on Wikipedia.

class Stack {
    #data;
    constructor() {
        // creating new empty array as hiden property
        this.#data = [];
    }
    push(item) {
        // push method just use native Array::push()
        // and add the item at the end of the array
        this.#data.push(item);
    }
    len() {
        // size of the Stack
        return this.#data.length;
    }
    top() {
        // sice the items are added at the end
        // the top of the stack is the last item
        return this.#data[this.len() - 1];
    }
    pop() {
        // pop is similar to push and use native Array::pop()
        // it removes and returns the last item in array
        return this.#data.pop();
    }
    is_empty() {
        // this comment shortcut !0 is true
        // since 0 can is coerced to false
        return !this.len();
    }
}

The above code uses ES6 (ES2015) class and ES2022 private
properties.

The Parentheses Matching Algorithm

Now I will describe the algorithm (steps) needed to parse the parentheses.

We need a loop that will go through each token – and it's best if all other tokens are removed before processing.

When we have an opening parenthesis, we need to push that element into the stack. When we have a closing parenthesis, we need to check if the last element on the stack matches the one we are processing.

If the element is matching, we remove it from the stack. If not, it means that we have messed up parentheses, and we need to throw an exception.

When we have a closing bracket, but there is nothing on the stack, we also need to throw an exception, because there is no opening parenthesis that matches the closing one we have.

After checking all the characters (tokens), if something is left of the stack, it means that we didn't close all the parentheses. But this case is ok, because the user may be in the process of writing. So in this case, we return false, not an exception.

If the stack is empty, we return true. This means that we have a complete expression. If this was an S-Expression, we could use the parser to process it, and we would not need to worry about invalid results (of course if the parser was correct).

The Source Code

function balanced(str) {
    // pairs of matching characters
    const maching_pairs = {
        '[': ']',
        '(': ')',
        '{': '}'
    };
    const open_tokens = Object.keys(maching_pairs);
    const brackets = Object.values(maching_pairs).concat(open_tokens);
    // we filter out what is not our matching characters
    const tokens = tokenize(str).filter(token => {
        return brackets.includes(token);
    });
    const stack = new Stack();
    for (const token of tokens) {
        if (open_tokens.includes(token)) {
            stack.push(token);
        } else if (!stack.is_empty()) {
             // there are matching characters on the stack
            const last = stack.top();
            // the last opening character needs to match
            // the closing bracket we have
            const closing_token = maching_pairs[last];
            if (token === closing_token) {
                stack.pop();
            } else {
                // the character don't match
                throw new Error(`Syntax error: missing closing ${closing_token}`);
            }
        } else {
            // this case when we have closing token but no opening one,
            // becauase the stack is empty
            throw new Error(`Syntax error: not matched closing ${token}`);
        }
    }
    return stack.is_empty();
}

The above code was implemented as part of my S-Expression parser, but the only thing I've used from that article is a function tokenize() that splits the string into tokens (where a token is a single object like number 123 or a string "hello"). If you want to process just the characters, you can use str.split(''), so the tokens would be an array of characters.

The code is much simpler than the S-Expression parser because we don't need to process all the tokens. But when we use the tokenize() function from the above article, we will be able to test input like this:

(this "))))")

The full source code (including the tokenize() function) can be found on GitHub.

Summary

You shouldn't even start processing expressions that have opening and closing characters with regular expressions. On StackOverflow there is this famous answer to this question:

RegEx match open tags except XHTML self-contained tags

Matching parentheses presents exactly the same problem, as parsing HTML. As you can see from the above code, ⁣it's a simpler problem to solve if we use the stack.

It's possible that we could write a Regular Expression that would check if the sequence of characters has matching parentheses. But it would soon get complicated if we had strings as tokens (sequence of characters), as with S-Expressions, and parentheses inside those stings should be ignored. It turns out that the solution is rather simple if we use the proper tools.

Personally, I love Regular Expressions, but you always need to decide if they're the right tool for the job.

NOTE: This article was based on an article in the Polish blog Głównie JavaScript (ang. Mostly JavaScript), with a title: Jak parować nawiasy lub inne znaki w
JavaScript?

If you like this article, you may want to follow me on Social Media: (Twitter/X and/or LinkedIn). You can also check my personal website and my new blog.

However, when it comes to sorting custom objects, such as instances of user-defined classes, the built-in sorting methods fall short. These methods don't know how to order objects based on custom criteria. This is where Java's Comparable and Comparator interfaces come into play, allowing developers to define and implement custom sorting logic tailored to specific requirements.

In this blog post, we'll explore how to use the Comparable and Comparator interfaces to sort custom objects in Java. I'll provide examples to illustrate the differences and use cases for each approach, helping you master custom sorting in your Java applications.

Table of Contents

• Sorting Methods for Primitive Types
• How to Use the Comparable Interface
• How to Use the Comparator Interface
• Comparable vs Comparator
• Wrapping Up

Sorting Methods for Primitive Types

Java provides a variety of built-in sorting methods that make it easy to sort primitive data types. These methods are highly optimized and efficient, allowing you to sort arrays and collections with minimal code. For primitive types, such as integers, floating-point numbers, and characters, the Arrays.sort() method is commonly used.

How to Use the Arrays.sort() Method

The Arrays.sort() method sorts the specified array into ascending numerical order. This method uses a dual-pivot quicksort algorithm, which is faster and more efficient for most data sets.

Let's look at an example of sorting an array of integers and characters using Arrays.sort():

package tutorial;

import java.util.Arrays;

public class PrimitiveSorting {
    public static void main(String[] args) {
        int[] numbers = { 5, 3, 8, 2, 1 };
        System.out.println("Original array: " + Arrays.toString(numbers));

        Arrays.sort(numbers);
        System.out.println("Sorted array: " + Arrays.toString(numbers));

        char[] characters = { 'o', 'i', 'e', 'u', 'a' };
        System.out.println("Original array: " + Arrays.toString(characters));

        Arrays.sort(characters);
        System.out.println("Sorted array: " + Arrays.toString(characters));
    }
}

Output:

Original array: [5, 3, 8, 2, 1]
Sorted array: [1, 2, 3, 5, 8]
Original array: [o, i, e, u, a]
Sorted array: [a, e, i, o, u]

How to Use the Collections.sort() Method

The Collections.sort() method is used to sort collections such as ArrayList. This method is also based on the natural ordering of the elements or a custom comparator.

package tutorial;

import java.util.ArrayList;
import java.util.Collections;

public class CollectionsSorting {
    public static void main(String[] args) {
        ArrayList<String> wordsList = new ArrayList<>();
        wordsList.add("banana");
        wordsList.add("apple");
        wordsList.add("cherry");
        wordsList.add("date");
        System.out.println("Original list: " + wordsList);

        Collections.sort(wordsList);
        System.out.println("Sorted list: " + wordsList);
    }
}

Output:

Original list: [banana, apple, cherry, date]
Sorted list: [apple, banana, cherry, date]

Limitations with Custom Classes

While Java's built-in sorting methods, such as Arrays.sort() and Collections.sort(), are powerful and efficient for sorting primitive types and objects with natural ordering (like String), they fall short when it comes to sorting custom objects. These methods do not inherently know how to order user-defined objects because there is no natural way for them to compare these objects.

For example, consider a simple Person class that has name, age, and weight attributes:

package tutorial;

public class Person {
    String name;
    int age;
    double weight;

    public Person(String name, int age, double weight) {
        this.name = name;
        this.age = age;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + ", weight=" + weight + " kgs]";
    }
}

If we try to sort a list of Person objects using Arrays.sort() or Collections.sort(), we will encounter a compilation error because these methods do not know how to compare Person objects:

package tutorial;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CustomClassSorting {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>(Arrays.asList(
                new Person("Alice", 30, 65.5),
                new Person("Bob", 25, 75.0),
                new Person("Charlie", 35, 80.0)
        ));
        System.out.println("Original people list: " + people);

        Collections.sort(people);
        System.out.println("Sorted people list: " + people);
    }
}

Compilation Error:

java: no suitable method found for sort(java.util.List<tutorial.Person>)
    method java.util.Collections.<T>sort(java.util.List<T>) is not applicable
      (inference variable T has incompatible bounds
        equality constraints: tutorial.Person
        lower bounds: java.lang.Comparable<? super T>)
    method java.util.Collections.<T>sort(java.util.List<T>,java.util.Comparator<? super T>) is not applicable
      (cannot infer type-variable(s) T
        (actual and formal argument lists differ in length))

The error occurs because the Person class does not implement the Comparable interface, and there is no way for the sorting method to know how to compare two Person objects.

To sort custom objects like Person, we need to provide a way to compare these objects. Java offers two main approaches to achieve this:

1. Implementing the Comparable Interface: This allows a class to define its natural ordering by implementing the compareTo method.
2. Using the Comparator Interface: This allows us to create separate classes or lambda expressions to define multiple ways of comparing objects.

We will explore both approaches in the upcoming sections, starting with the Comparable interface.

How to Use the Comparable Interface

Java provides a Comparable interface to define a natural ordering for objects of a user-defined class. By implementing the Comparable interface, a class can provide a single natural ordering that can be used to sort its instances. This is particularly useful when you need a default way to compare and sort objects.

Overview

The Comparable interface contains a single method, compareTo(), which compares the current object with the specified object for order. The method returns:

• A negative integer if the current object is less than the specified object.
• Zero if the current object is equal to the specified object.
• A positive integer if the current object is greater than the specified object.

How Comparable Allows for a Single Natural Ordering of Objects

By implementing the Comparable interface, a class can ensure that its objects have a natural ordering. This allows the objects to be sorted using methods like Arrays.sort() or Collections.sort() without the need for a separate comparator.

Let's implement the Comparable interface in a new PersonV2 class, comparing by age.

package tutorial;

public class PersonV2 implements Comparable<PersonV2> {
    String name;
    int age;
    double weight;

    public PersonV2(String name, int age, double weight) {
        this.name = name;
        this.age = age;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "PersonV2 [name=" + name + ", age=" + age + ", weight=" + weight + " kgs]";
    }

    @Override
    public int compareTo(PersonV2 other) {
        return this.age - other.age;
    }
}

In this implementation, the compareTo() method compares the age attribute of the current PersonV2 object with the age attribute of the specified PersonV2 object by subtracting one age from the other. By using the expression this.age - other.age, we’re effectively implementing this logic as follows:

• If this.age is less than other.age, the result will be negative.
• If this.age is equal to other.age, the result will be zero.
• If this.age is greater than other.age, the result will be positive.

Note: We can also use Integer.compare(this.age, other.age) instead of performing the arithmetic operation manually.

Now that the PersonV2 class implements the Comparable interface, we can sort a list of PersonV2 objects using Collections.sort():

package tutorial;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CustomClassSortingV2 {
    public static void main(String[] args) {
        List<PersonV2> people = new ArrayList<>(Arrays.asList(
                new PersonV2("Alice", 30, 65.5),
                new PersonV2("Bob", 25, 75.0),
                new PersonV2("Charlie", 35, 80.0)
        ));
        System.out.println("Original people list: " + people);

        Collections.sort(people);
        System.out.println("Sorted people list: " + people);
    }
}

Output:

Original people list: [PersonV2 [name=Alice, age=30, weight=65.5 kgs], PersonV2 [name=Bob, age=25, weight=75.0 kgs], PersonV2 [name=Charlie, age=35, weight=80.0 kgs]]
Sorted people list: [PersonV2 [name=Bob, age=25, weight=75.0 kgs], PersonV2 [name=Alice, age=30, weight=65.5 kgs], PersonV2 [name=Charlie, age=35, weight=80.0 kgs]]

In this example, the PersonV2 objects are sorted in ascending order of age using the Collections.sort() method, which relies on the natural ordering defined by the compareTo() method in the PersonV2 class.

Limitations of Comparable

While the Comparable interface provides a way to define a natural ordering for objects, it has several limitations that can restrict its use in practical applications. Understanding these limitations can help us determine when to use other mechanisms, such as the Comparator interface, to achieve more flexible sorting.

• Single Natural Ordering: The primary limitation of Comparable is that it allows only one natural ordering for the objects of a class. When you implement Comparable, you define a single way to compare objects, which is used whenever the objects are sorted or compared. This can be restrictive if you need to sort objects in multiple ways.
• Inflexibility: If you need to sort objects by different attributes or in different orders, you will have to modify the class or create new implementations of Comparable. This inflexibility can lead to a proliferation of comparison methods and can make the code harder to maintain.
• Non-Adaptable: Once a class implements Comparable, the natural ordering is fixed and cannot be easily changed. For instance, if your PersonV2 class initially sorts by age but later you need to sort by weight or name, you have to either change the compareTo() method or create a new version of the class.

This is where the Comparator interface comes into play. To define multiple ways of comparing objects, we can use the Comparator interface, which we will explore in the next section.

How to Use the Comparator Interface

The Comparator interface in Java provides a way to define multiple ways of comparing and sorting objects. Unlike the Comparable interface, which allows only a single natural ordering, Comparator is designed to offer flexibility by allowing multiple sorting strategies. This makes it particularly useful for scenarios where objects need to be sorted in different ways.

Overview

The Comparator interface defines a single method, compare(), which compares two objects and returns:

• A negative integer if the first object is less than the second object.
• Zero if the first object is equal to the second object.
• A positive integer if the first object is greater than the second object.

This method provides a way to define custom ordering for objects without modifying the class itself.

How Comparator Allows for Multiple Ways of Ordering Objects

The Comparator interface allows you to create multiple Comparator instances, each defining a different ordering for objects. This flexibility means that you can sort objects by various attributes or in different orders without altering the object's class.

Let's implement multiple Comparator instances for the Person class. We'll define comparators for sorting by name, by age, and by weight. First, we need to update the Person class to include getters and ensure that attributes are accessible.

package tutorial;

public class Person {
    String name;
    int age;
    double weight;

    public Person(String name, int age, double weight) {
        this.name = name;
        this.age = age;
        this.weight = weight;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public double getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + ", weight=" + weight + " kgs]";
    }
}

Comparator by Name

This comparator sorts Person objects alphabetically by their name.

package tutorial.comparator;

import tutorial.Person;

import java.util.Comparator;

public class PersonNameComparator implements Comparator<Person> {

    @Override
    public int compare(Person p1, Person p2) {
        return p1.getName().compareTo(p2.getName());
    }
}

Comparator by Age

This comparator sorts Person objects by their age, in ascending order.

package tutorial.comparator;

import tutorial.Person;

import java.util.Comparator;

public class PersonAgeComparator implements Comparator<Person> {

    @Override
    public int compare(Person p1, Person p2) {
        return p1.getAge() - p2.getAge();
    }
}

Comparator by Weight

This comparator sorts Person objects by their weight, in ascending order.

package tutorial.comparator;

import tutorial.Person;

import java.util.Comparator;

public class PersonWeightComparator implements Comparator<Person> {

    @Override
    public int compare(Person p1, Person p2) {
        return (int) (p1.getWeight() - p2.getWeight());
    }
}

Now, here’s how you can use these Comparator instances to sort a list of Person objects:

package tutorial;

import tutorial.comparator.PersonAgeComparator;
import tutorial.comparator.PersonNameComparator;
import tutorial.comparator.PersonWeightComparator;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CustomClassSortingV3 {
    public static void main(String[] args) {
        List<Person> people = new ArrayList<>(Arrays.asList(
                new Person("Alice", 30, 65.5),
                new Person("Bob", 25, 75.0),
                new Person("Charlie", 35, 80.0)
        ));
        System.out.println("Original people list: " + people);

        Collections.sort(people, new PersonNameComparator());
        System.out.println("Sorted people list by name: " + people);

        Collections.sort(people, new PersonAgeComparator());
        System.out.println("Sorted people list by age: " + people);

        Collections.sort(people, new PersonWeightComparator());
        System.out.println("Sorted people list by weight: " + people);
    }
}

Output:

Original people list: [Person [name=Alice, age=30, weight=65.5 kgs], Person [name=Bob, age=25, weight=75.0 kgs], Person [name=Charlie, age=35, weight=80.0 kgs]]
Sorted people list by name: [Person [name=Alice, age=30, weight=65.5 kgs], Person [name=Bob, age=25, weight=75.0 kgs], Person [name=Charlie, age=35, weight=80.0 kgs]]
Sorted people list by age: [Person [name=Bob, age=25, weight=75.0 kgs], Person [name=Alice, age=30, weight=65.5 kgs], Person [name=Charlie, age=35, weight=80.0 kgs]]
Sorted people list by weight: [Person [name=Alice, age=30, weight=65.5 kgs], Person [name=Bob, age=25, weight=75.0 kgs], Person [name=Charlie, age=35, weight=80.0 kgs]]

In this example, the Comparator instances allow sorting the Person objects by different attributes: name, age, and weight. This demonstrates how the Comparator interface enables flexible and versatile sorting strategies for a class.

Comparable vs Comparator

When sorting objects in Java, you have two primary options: the Comparable and Comparator interfaces. Understanding the differences between these two interfaces can help you choose the right approach for your needs. Please note that this is also a very important interview question.

Comparison

Here’s a table comparing and contrasting the Comparable and Comparator interfaces in Java:

Benefits and Drawbacks of Each Approach

Comparable Operator

Benefits:

• Simplicity: Provides a default sorting order that is easy to implement and use.
• Built-in: The natural ordering is part of the class itself, so it is always available and used by default in sorting methods.

Drawbacks:

• Single Ordering: Can only define one way to compare objects. If different sorting orders are needed, the class must be modified or additional Comparator instances must be used.
• Class Modification: Requires altering the class to implement Comparable, which might not be feasible if the class is part of a library or if its natural ordering is not clear.

Comparator

Benefits:

• Flexibility: Allows for multiple sorting orders and criteria, which can be defined externally and used as needed.
• Non-invasive: Does not require modification of the class itself, making it suitable for classes you do not control or when you need different sorting options.

Drawbacks:

• Complexity: Requires creating and managing multiple Comparator instances, which can add complexity to the code.
• Overhead: Might introduce additional overhead if many comparators are used, especially if they are created on the fly.

In summary, Comparable is best used when a class has a natural ordering that makes sense for most use cases.

Comparator, on the other hand, provides flexibility for sorting by multiple criteria and is useful when the class does not have a natural ordering or when different sorting orders are needed.

Choosing between Comparable and Comparator depends on your specific sorting needs and whether you need a single default order or multiple flexible sorting options.

Wrapping Up

Understanding and utilizing both Comparable and Comparator can significantly enhance your ability to manage and manipulate object collections in Java. By applying these concepts, you can create more flexible and powerful sorting mechanisms.

To solidify your understanding, try implementing both Comparable and Comparator in real-world scenarios. Experiment with different classes and sorting criteria to see how each approach works in practice.

Links to Official Java Documentation:

• Java Comparable Interface
• Java Comparator Interface

These techniques have not only enabled a wide range of image processing techniques such as noise reduction, sharpening, and dynamic-range extension, but have also enabled many techniques used in compute vision such as edge detection, object detection, and so on.

Multi-scale analysis is one of the newer techniques (relatively speaking) that has been adopted in a wide range of applications, especially in the astronomical image and data processing applications. This technique, which is based on Wavelet transform, allows us to divide our data into multiple signals, that all add up to make the final signal.

We can then perform our processing or analysis work on this individual sub-signals, allowing us to do targeted operations that do not affect other sub-signals.

In this tutorial, we'll first be exploring what the technique is all about, through the lens of a particular algorithm for performing multi-scale analysis on images. We'll then move on to looking at how we can implement what we discussed in the first part in Rust programming language and recreate the examples you see in the first half of the article.

Before You Read:

Prerequisites for Part 1:

The technique described is derived from the concept of "Wavelet Transforms". You don't need to know everything about it, but a very basic understanding will help you grasp the material better.

Since the article focuses on image processing and analysis, a basic understanding of how pixels work in digital format is helpful, but not mandatory.

Prerequisites for Part 2:

Here, we focus on implementing the algorithm using the Rust programming language, without going much into the details of the language itself. So being comfortable writing Rust programs, and comfortable reading crate documentations is required.

If this is not you, you can still read Part 1 and learn the technique, and then maybe you'll want to then try it out in a language of your choice. If you're not familiar with Rust, I highly encourage you to learn the basics. Here's an interactive Rust course that can get you started.

Table Of Contents

1. Part 1: Understanding Multi-Scale Processing Technique And Algorithm
   1. What is multi-scale image processing
   2. The À Trous Wavelet Transform
   3. Scaling Functions
   4. Convolution Pixels At Each Scale
   5. Handling Boundary Conditions
   6. Computing Maximum Possible Scales For Any Given Image
   7. Closing Notes
2. Part 2: How to Implement À Trous Tranform in Rust
   1. Prerequisites
   2. The À Trous Transform
   3. Iterators And The À Trous Transform
   4. Convolution
   5. Implementing the Iterator
   6. Recomposition
   7. Using The À Trous Transform
   8. Further Reading
3. Wrapping Up

Part 1: Understanding the Multi-Scale Processing Technique and Algorithm

So what do we mean when we talk about multi-scale processing or analysis of some data? Well, we usually mean breaking down the input data into multiple signals, each representing a particular scale of information.

Scale, when talking about image analysis, simply refers to the size of structures that we are looking at at any given time. It ignores everything else that's either smaller or larger than the current scale.

What is multi-scale image processing?

For images, "scales" generally refer to the size in pixels of various structures or details in the image. You'll be able to get an intuitive understanding by looking at the following example:

Messier 33, AKA Triangulum Galaxy

Assuming our naïve understanding is correct, we can derive images of at-least the following 3 scales:

• Very small structures, usually the size of a single pixel. This layer, when separated from the rest of the image, will only contain the noise and some sharp stars for the most part.
• Small structures, usually a few pixels in size. This layer, when separated, will contain all of the stars and the very fine details in the galaxy arms.
• Large and very large scale structures, usually 100s of pixels in size. This layer, when separated, will contain the general size and shape of the galaxy at the center.

Now the question becomes, why do we need to do all of this in the first place?

The answer is simple: it allows us to make targeted enhancements and changes to an image.

For example, noise reduction on the overall image will usually result in a loss of sharpness in the galaxy. But since we have broken our image down into multiple scales, we can easily apply noise reduction to only the first few layers, as most of the random noise that is easy to remove resides only in lower scale layers.

We then re-combine the noise-reduced low-scale layers with unmodified large-scale ones, and we have an output that gives us noise reduction without a loss in quality.

Another peculiar thing about noise is that it's almost always present in just one of these layers, making noise reduction process both easy and non-destructive.

If you're more of a visual learner, let's see this in practice using the image we used above. We're gonna be working with the following grayscale version of that image, where I've also added random gaussian noise:

Messier 33 AKA Triangulum Galaxy, Converted to grayscale and with added Gaussian noise

Performing scale-based layer separation on this image, we get the following results. Note that the results are rescaled to a range where they can be viewed as an image for representational purpose. The actual transform produces pixel values that don't make sense when looked at independently, but all of the techniques and calculations described in this tutorial can still be safely applied without rescale. The recomposition process automatically gives us back the correct range:

9-level À Trous Decomposition. From top-left to bottom-right, we have images at the following pixel scales: 1, 2 4, 8, 16, 32, 64, 128, 256 (powers of 2)

1. The first and second layers contain the noise and stars. In this particular example, noise is mixed in with the stars. But using the first and second layers, we can easily target areas that are not present in the second layer, as we can be sure that those are where the noise is present in the first layer.
2. With the third layer, we still see the residue luminance from stars. But if you look closely, we also see very faintly the arms of the galaxy starting to appear.
3. From the fourth layer onwards, we see the galaxy at varying scales and detail levels, completely without the stars. We start with the finer details (relatively small scale details) and increasingly move on to larger and larger scale samples. By the end, we only see a vague shape where the galaxy used to be.

From here on, we can selectively apply noise reduction to the first two layers. Then we can recombine all of the layers to create the following image that has very little noise while preserving the same amount of details in the stars and the galaxy arms:

Messier 33 AKA Triangulum Galaxy, result of recombining all layers but with noise reduction applied to the pixel scale 1 & 2 layers

In its most basic form, multi-scale analysis involves breaking up your source image, commonly referred to as the "signal", into multiple "signals" – each containing the data for a particular scale in the source signal.

Scale, when talking about image signal here, refers to the distance between adjacent pixels that we take when creating the layer from the source image.

In practice, this technique is used as the one of the first steps in all kinds of astronomical data analysis and image processing.

As an example, you can use the technique to detect locations of stars while ignoring larger structures much more easily than would be possible otherwise.

The À Trous Wavelet Transform

All of what I've showed you previously, and all of what you're going to see in this tutorial, was achieved with wavelet decomposition and recomposition using the à trous algorithm for discreet wavelet transforms.

This algorithm has been used throughout the years for various applications. But it's become particularly important recently in astronomical image processing applications, where different objects and signals in an image can be completely separated based on structural scales.

Here's how the algorithm works:

1. We start with the source image input and number of levels to decompose into n.
2. For each level n:
   • We convolve the image with our scaling function (we'll see what this is in a bit), where adjacent pixels are considered to be 2ⁿ units apart from each other, giving us the result result_n. This is where the "À Trous" name comes from, which literally translates to "with holes".
   • The layer output output_n is then computed using input - result_n.
   • We then update input to equal result_n. This is also known as residue data which serves as the source data for next layer.
3. Repeat the above steps for all levels.
4. In the end, we have 9 wavelet layers, and 1 residue layer. All 10 layers are required for the recomposition.

For a more mathematical approach to understanding this algorithm, I encourage you to read about the à trous algorithm here.

The recomposition process is very straightforward: we just need to add all 10 layers together. We can chose to apply positive or negative bias to any of the layers, which is a factor by which to multiply the layer pixel values during recomposition. You can use it either to enhance or diminish the characteristics of that particular layer.

Scaling Functions

Scaling functions are specific convolution kernels that help us better represent data at a particular scale based on our use case. There are 3 most commonly used scaling functions, which are shown below:

The images above show the 3 most commonly used scaling functions in the À Trous algorithm, visualised using 3rd level decomposition of the triangulum galaxy image used previously:

• B3 Spline is a very smooth kernel. It is mostly used in isolation of large scale structures. If we wanted to sharpen our galaxy, we would have used this kernel.
• Low-scale is a very sharply peaked kernel, and is best at working with small scale structures.
• Linear interpolation kernel gives us the best of both worlds, and hence is used when we need to work with both small scale and large scale structures. This is what we have used in all of our previous examples.

Convolution Pixels At Each Scale

I mentioned in the algorithm that at each scale, the pixels in the image are considered to be 2ⁿ units apart. Let's try to grasp a better understanding of this using the following visualisation:

Consider the following 8px by 8px image. Each pixel is labeled 1 through 64, which is their index.

A representational pixel grid of a 8x8px image

We're going to focus on a convolution operation of one of the center pixels only for this example, let's say pixel number 28.

Scale 0: At scale 0, the value of 2ⁿ becomes 1. This means that for convolution, we'll consider pixels that are 1 unit apart from our target center pixel. These pixels are highlighted below:

8x8px grid with pixels that are involved in convolution for pixel number 28 highlighted at scale 0

Scale 1: This is where things get interesting. At scale 1, the value of 2ⁿ becomes 2. This means that for convolution, we'll jump directly to pixels that are 2 locations apart from the target pixel:

8x8px grid with pixels that are involved in convolution for pixel number 28 highlighted at scale 1

As you can see, we've created "holes" in our computation of the value of the target pixel by skipping 2ⁿ - 1 adjacent pixels and selecting the 2ⁿth pixel. This is the basis of the algorithm.

This process is repeated for every pixel in the image, just like a regular convolution process. And each time, we consider increasing distances between pixels for computation of final values at increasing scales.

Let's look at just one more scale.

Scale 2: This is where things get even more interesting. At scale 2 the value of 2ⁿ becomes 4. This means that for convolution, we'll jump directly to pixels that are 4 locations apart from the target pixel:

8x8px grid with pixels that are involved in convolution for pixel number 28 highlighted at scale 2

Wait what? Why are we choosing pixels 1, 4, 8, 25, & 57? 1 & 4 are only 3 locations apart, 25 is only 2 locations apart, and 8 & 57 are not even diagonally aligned with the target pixel. What's going on?

Handling Boundary Conditions

As we've mentioned that this process is executed for all of the pixels in an image, we also need to consider cases where the pixel locations for convolution lie outside of the image.

This is not a concept unique to this algorithm. During convolution, this is referred to as a boundary condition or handling boundary pixels. There are various techniques for dealing with this, and all of them involve virtually extending the image in order to make it seem like we're not encountering the boundary at all.

Some of the techniques are:

• Extending as much as needed by copying the value of the last row/column
• Mirroring the image on all edges and corners
• Wrapping the image around the edges.

In our example, we're employing the "mirroring" technique. When implementing such an algorithm, we don't need to actually create an extended image. Any boundary handling is implementable using just basic mathematical formulae.

Our extended image, with the correct pixels selected for scale 2, is as follows:

Source image extended on all edges and corners using the mirroring technique. All of the faded regions represent extended areas.

Again, the extension is only logical and is completely computed using formulae, as opposed to actually extending the source image and then checking. We can easily see that with the mirrored images in place, our basic rule of picking pixels that are 2ⁿ locations apart is still followed.

Computing Maximum Possible Scales for Any Given Image

If you think about it carefully, you'll see that the maximum layers an image can be decomposed into can be calculated by computing the log₂ of the image width or height (whichever is lower) and throwing away the fractional part.

In our 5x5 image, log₂(5) ~= 2.32. If we throw away the fractional part, that leaves us with 2 layers. Similarly, for a 1000x1000px image, log₂1000 ~= 9.96, which means we can decompose a 1000x1000 px image into a maximum of 9 layers. It simply implies that our "holes" cannot be larger than the width or height.

Even with the mirroring extension we used above, if the holes are larger than the width of the image, they'll still end up outside of the extended regions, specially for corner or boundary pixels, making it impossible to perform convolution at that scale.

Closing Notes

Thinking about the examples and visualisations a bit more, you can clearly see how and why this algorithm works, and how it's able to separate out structures in an image based on their sizes. The increasing hole sizes make it so that only structures larger than the hole itself are retained for any given layer.

A big advantage of using this algorithm is the computational cost. Since this doesn't involve Fourier or Wavelet transforms, the computational cost is quite low, relatively speaking. The memory cost, however, is indeed higher. But more often than not that is a good tradeoff.

Another advantage of this algorithm when comparing it to other discreet wavelet transform algorithms is that the size of source image is preserved throughout the entire process. There's no decimation or upscaling happening here, making this algorithm one of the easiest ones to understand and implement.

The algorithm is used in almost all of the astronomical image processing softwares such as PixInsight, Siril, and many others.

This algorithm is also known by other names such as Stationary Wavelet Transform and Starlet Transform.

Part 2: How to Implement À Trous Tranform in Rust

Now I'm going to show you how you can implement this algorithm in Rust.

For the purposes of this tutorial, I'm going to assume that you're pretty familiar with Rust and its basic concepts, such as data-types, iterators, and traits and are comfortable writing programs that use these concepts.

I'm also going to assume that you have an understanding of what convolution and convolution kernels mean in this context.

Prerequisites

We're going to need a couple of dependencies. Before we get to that, let's quickly create a new project:

cargo new --lib atrous-rs
cd atrous-rs

Now let's all of the dependencies we need. We actually only need 2:

cargo add image ndarray

image is a Rust library we'll use to work with images of all of the standard formats and encodings. It also helps us convert between various formats, and provides easy access to pixel data as buffers.

ndarray is a Rust library that helps you you create, manipulate, and work with 2D, 3D, or N-Dimensional arrays. We can use nested Vectors, but using a project like ndarray is better in this case because we need to perform a lot of operations on both individual values as well as their neighbours. Not only is it much easier to do with ndarray, but they also have performance optimisations built in for many operations and CPU types.

Although I'll be covering the basic functions/traits/methods/data-types we use from these crates, I'm not going to go into too much detail for them. I encourage you to read the docs instead.

We're actually going to jump straight to algorithm implementation, and come back later to see how we can use it.

The À Trous Transform

Create a new file that will hold our implementation. Let's name it transform.rs.

Start with adding the following struct, that will hold the information we need to perform the transform:

// transform.rs

use ndarray::Array2;

pub struct ATrousTransform {
    input: Array2<f32>, // `Array2<f32>` is a 2D array where each value is of type `f32`. This will hold our pixel data for input image.
    levels: usize, // The number of levels or scales to decompose the image into
    current_level: usize, // Current level that we need to generate. This holds the state of our iterator.
    width: usize, // Width of input image
    height: usize, // Height of input image
}

We also need a way to create this struct easily. In our case, we want to be able to create it from the input image directly. Also, input image can be of any of the supported format and encoding, but we want a consistent color-type to implement the calculations, so we'll also need to convert the image to our expected format.

It's helpful to extract all of this logic away using the "constructor" pattern in Rust. Let's implement that:

// transform.rs

use image::GenericImageView;

impl ATrousTransform {
    pub fn new(input: &image::DynamicImage, levels: usize) -> Self {
        let (width, height) = input.dimensions();
        let (width, height) = (width as usize, height as usize);

        // Create a new 2D array with proper size for each dimension to hold all of our input's pixel data. Method `zeros` takes a "shape" parameter, which is a tuple of (rows_count, columns_count).
        let mut data = Array2::<f32>::zeros((height, width));

        // Convert the image to be a grayscale image where each pixel value is of type `f32`. Loop over all pixels in the input image along with its 2D location.
        for (x, y, pixel) in input.to_luma32f().enumerate_pixels() {
            // Put the pixel value at appropriate location in our data array. The `[[]]` syntax is used to provide a 2-dimensional index such as `[[row_index, col_index]]`
            data[[y as usize, x as usize]] = pixel.0[0];
        }

        Self {
            input: data,
            levels,
            current_level: 0,
            width,
            height
        }
    }
}

This takes care of converting the image to grayscale and converting the pixel values to f32. If you're not already aware, for images with floating-point pixel values, the values are always normalized. This means that they are always between 0 and 1 – 0 representing black and 1 representing white.

Iterators and the À Trous Transform

Before we continue, let's think about the algorithm for a second. We need to be able to generate images at increasing scales, until we hit the maximum number of levels we need.

We want the consumer of our library to have access to all of these scales, and be able to manipulate them and also easily recombine once they're done. They need to be able to filter layers to ignore structures at certain scales, manipulate or "map" them to change their characteristics, perform operations on them, or even store each image if they so need.

This sounds an awful lot like Iterators! Iterators give us methods like filter, skip, take, map, for_each, and so on, all of which are exactly all we need to work with our layers before recomposition.

One added advantage of Iterators is that it allows you to finish processing each layer all the way through before you move on to the next one. If you're unsure why this is, I suggest reading more about processing a series of items with Iterators in Rust.

We're going implement the Iterator trait for our ATrousTransform type which should produce a wavelet layer as output for each iteration.

We're going to be implementing the inner-most parts of the algorithm first, and build out from there. So we first need a way to convolve an input data buffer with the scaling function while making sure that adjacent pixels are 2ⁿ locations apart, which is the first step in our loop.

Convolution

We need to define our convolution kernel before we can do anything else. Create a new file kernel.rs and add it to lib.rs with the following contents:

// kernel.rs

#[derive(Copy, Clone)]
pub struct LinearInterpolationKernel {
    values: [[f32; 3]; 3]
}

impl Default for LinearInterpolationKernel {
    fn default() -> Self {
        Self {
            values: [
                [1. / 16., 1. / 8., 1. / 16.],
                [1. / 8., 1. / 4., 1. / 8.],
                [1. / 16., 1. / 8., 1. / 16.],
            ]
        }
    }
}

We define it using a struct instead of a constant array of arrays because we need to define some tiny helpful methods on it related to index handling. We'll come back to that later.

Create another file convolve.rs. This is where all of the code for handling convolution for individual pixels will go. We'll define a Convolution trait that will define methods needed to perform the convolution on every pixel in current layer.

// convolve.rs

pub trait Convolution {
    fn compute_pixel_index(
        &self,
        distance: usize,
        kernel_index: [isize; 2],
        target_pixel_index: [usize; 2]
    ) -> [usize; 2];

    fn compute_convoluted_pixel(
        &self, 
        distance: usize, 
        index: [usize; 2]
    ) -> f32;
}

You may ask why we need a trait here instead of a simple impl block. We are only working with Grayscale images in this article, but you may want to extend it to implement it for RGB or other color modes as well.

Now, you need to implement this trait for your ATrousTransform struct:

// convolve.rs

impl Convolution for ATrousTransform {
    fn compute_pixel_index(
        &self, 
        distance: usize, 
        kernel_index: [isize; 2], 
        target_pixel_index: [usize; 2]
    ) -> [usize; 2] {
        let [kernel_index_x, kernel_index_y] = kernel_index;

        // Compute the actual distance of adjacent pixel
        // by multiplying their relative position with the
        // size of the hole.
        let x_distance = kernel_index_x * distance as isize;
        let y_distance = kernel_index_y * distance as isize;

        let [x, y] = target_pixel_index;

        // Compute the index of adjacent pixel in the 2D
        // image based on the index of current pixel.
        let mut x = x as isize + x_distance;
        let mut y = y as isize + y_distance;

        // If x index is out of bounds, consider x to be
        // the nearest boundary location
        if x < 0 {
            x = 0;
        } else if x > self.width as isize - 1 {
            x = self.width as isize - 1;
        }

        // If y index is out of bounds, consider y to be
        // the nearest boundary location
        if y < 0 {
            y = 0;
        } else if y > self.height as isize - 1 {
            y = self.height as isize - 1;
        }

        // The final 2D index of pixel.
        [y as usize, x as usize]
    }

    fn compute_convoluted_pixel(
        &self, 
        distance: usize, 
        [x, y]: [usize; 2]
    ) -> f32 {
        // Create new variable to hold the result of convolution
        // for current pixel.
        let mut pixels_sum = 0.0;

        let kernel = LinearInterpolationKernel::default();

        // Iterate over relative position of pixels from the center
        // pixel to perform convolution with. In other words, 
        // these are the indexes of neighbouring pixels from the
        // center pixel.
        for kernel_index_x in -1..=1 {
            for kernel_index_y in -1..=1 {
                // Get the computed pixel location that maps to
                // the current position in kernel
                let pixel_index = self.compute_pixel_index(
                    distance,
                    [kernel_index_x, kernel_index_y],
                    [x, y]
                );

                // Get the multiplicative factor (kernel value) for 
                // this relative location from the kernel.
                let kernel_value = kernel.value_from_relative_index(
                    kernel_index_x,
                    kernel_index_y
                );

                // Multiply the pixel value with kernel scaling
                // factor and add it to the pixel sum.
                pixels_sum += kernel_value * self.input[pixel_index];
            }
        }

        // Return the value of computed pixel from convolution process.
        pixels_sum
    }
}

We need to do computations to figure out each pixel's location based on the relative position in the kernel from the center pixel as well as ensure that the "hole size" is also being taken into consideration for the final pixel index. As you might notice, you also want to handle the boundary conditions when computing indexes.

I encourage to take your time here and go through the code and the comments.

Implementing the Iterator

It's finally time to implement the Iterator trait for your ATrousTransform:

// transform.rs

impl Iterator for ATrousTransform {
    // Our output is an image as well as the current level for each
    // iteration. The current level is an `Option` to represent the
    // final residue layer after the intermediary layers have been
    // generated.
    type Item = (Array2::<f32>, Option<usize>);

    fn next(&mut self) -> Option<Self::Item> {
        let pixel_scale = self.current_level;
        self.current_level += 1;

        // We've already generated all the layers. Return None to 
        // exit the iterator.
        if pixel_scale > self.levels {
            return None;
        }

        // We've generated all intermediary layers, return the 
        // residue layer.
        if pixel_scale == self.levels {
            return Some((self.input.clone(), None))
        }

        let (width, height) = (self.width, self.height);

        // Distance between adjacent pixels for convolution (also 
        // referred to as size of "hole").
        let distance = 2_usize.pow(pixel_scale as u32);

        // Create new buffer to hold the computed data for this layer.
        let mut current_data = Array2::<f32>::zeros((height, width));

        // Iterate over each pixel location in the 2D image
        for x in 0..width {
            for y in 0..height {
                // Set the current pixel in current layer to
                // the result of convolution on the current
                // pixel in input data.
                current_data[[y, x]] = self.compute_convoluted_pixel(
                    distance, 
                    [x, y]
                );
            }
        }

        // Create current layer by subtracting currently computed pixels 
        // from previous layer
        let final_data = self.input.clone() - &current_data;

        // Set the input layer to equal the current computed layer so 
        // that it can be used as the "previous layer" in next iteration.
        // This is also our residue data for each layer.
        self.input = current_data;

        // Return the current layer data as well as current level information.
        Some((final_data, Some(self.current_level)))
    }
}

I'm going to point out that there's a lot of potential for optimizing for performance here, but that's out of the scope of this article.

We'll finally look at how we can take all of these layers and reconstruct our input image.

Recomposition

As I've said previously, reconstructing an image that was decomposed with the A Trous transform is as simple as summing all of the layers together.

We're going to define a trait for this. Why we need a trait here should be clear once you look at the implementation.

Create a new file recompose.rs with the following contents:

// recompose.rs

use image::{DynamicImage, ImageBuffer, Luma};
use ndarray::Array2;

pub trait RecomposableLayers: Iterator<Item = (Array2<f32>, Option<usize>)> {
    fn recompose_into_image(
        self,
        width: usize,
        height: usize,
    ) -> DynamicImage
        where
            Self: Sized,
    {
        // Create a result buffer to hold the pixel data for our output image.
        let mut result = Array2::<f32>::zeros((height, width));

        // For each layer, add the layer data to current value of result buffer.
        for layer in self {
            result += &layer.0;
        }

        // Compute min and max pixel intensity values in the final data so that
        // we can perform a "rescale", which normalizes all pixel values to be
        // between the range of 0 & 1, as is expected by float 32 images.
        let min_pixel = result.iter().copied().reduce(f32::min).unwrap();
        let max_pixel = result.iter().copied().reduce(f32::max).unwrap();

        // Create a new `ImageBuffer`, which is a type provided by `image` crate to
        // serve as buffer for pixel data of an image. Here, we're creating a new
        // `Luma` ImageBuffer with pixel value of type `u16`. Luma just refers to
        // grayscale.
        let mut result_img: ImageBuffer<Luma<u16>, Vec<u16>> =
            ImageBuffer::new(width as u32, height as u32);

        // Pre-compute the denominator for scaling computation so that we don't
        // repeat this unnecessarily for every iteration.
        let rescale_ratio = max_pixel - min_pixel;

        // Iterate over all pixels in the `ImageBuffer` and fill it based on data
        // from the `result` buffer after rescaling the value.
        for (x, y, pixel) in result_img.enumerate_pixels_mut() {
            let intensity = result[(y as usize, x as usize)];

            *pixel =
                Luma([((intensity - min_pixel) / rescale_ratio * u16::MAX as f32) as u16]);
        }

        // Convert the `ImageBuffer` into `DynamicImage` and return it
        DynamicImage::ImageLuma16(result_img)
    }
}

// Implement this trait for anything that implements the Iterator trait
// with the given item type
impl<T> RecomposableLayers for T where T: Iterator<Item = (Array2<f32>, Option<usize>)> {}

If you haven't noticed, since we implement this trait for a generic, this will work with any iterator, such as Filter, Map, and so on. If you didn't use a trait here, you'll have had to implement the same thing again and again for every built-in iterator type, and your code wouldn't have worked with 3rd party types.

Using the À Trous Transform

After all of that, it's finally time to reproduce the processing that I showed you for the galaxy image with lots of noise. Create a new file main.rs with the following contents:

use image::{DynamicImage, ImageBuffer, Luma};
use atrous::recompose::RecomposableLayers;
use atrous::transform::ATrousTransform;

fn main() {
    // Open our noisy image
    let image = image::open("m33-noise-lum.jpg").unwrap();

    // Create a new instance of the transform with 9 layers
    let transform = ATrousTransform::new(&image, 9);

    // Map over each layer
    transform.map(|(mut buffer, pixel_scale)| {
        // Create a new image buffer to hold the pixel data. This
        // will be populated from the raw buffer for this layer.
        let mut new_buffer =
            ImageBuffer::<Luma<u16>, Vec<u16>>::new(buffer.ncols() as u32, buffer.nrows() as u32);

        // Iterate over all pixels of the `ImageBuffer` to populate it. We also
        // convert from `f32` pixels to `u16` pixels.
        for (x, y, pixel) in new_buffer.enumerate_pixels_mut() {
            *pixel = Luma([(buffer[[y as usize, x as usize]] * u16::MAX as f32) as u16])
        }

        // If the present layer is a small scale layer (< 3), 
        // perform noise reduction
        if pixel_scale.is_some_and(|scale| scale < 3) {
            let mut image = DynamicImage::ImageLuma16(new_buffer).to_luma8();

            // Bilateral filter is a de-noising filter. Apply it to the image.
            image = imageproc::filter::bilateral_filter(&image, 10, 10., 3.);

            // Modify the raw buffer to contain the updated pixel values after
            // filtering.
            for (x, y, pixel) in image.enumerate_pixels() {
                buffer[[y as usize, x as usize]] = pixel.0[0] as f32 / u8::MAX as f32;
            }

            // Return the updated buffer.
            (buffer, pixel_scale)
        } else {
            // Return the unmodified buffer for larger scale layers.
            (buffer, pixel_scale)
        }
    })
        // Call the recomposition method on iterator
        .recompose_into_image(image.width() as usize, image.height() as usize)
        // Convert output to 8-bit grayscale image
        .to_luma8()
        // Save it to jpg file
        .save("noise-reduced.jpg")
        .unwrap()
}

You also need to add a new dependency, imageproc, which provides useful image processing implementations on top of the image crate.

cargo add imageproc

To make this work, we also need to modify our Cargo.toml to explicitly define both binary and library targets:

// Cargo.toml

[package]
name = "atrous-rs"
version = "0.1.0"
edition = "2021"

[[bin]]
name = "atrous"
path = "src/main.rs"

[lib]
name = "atrous"
path = "src/lib.rs"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
image = "0.25.1"
imageproc = "0.24.0"
ndarray = "0.15.6"

You may download the test image from here. Move it to the root directory of your project, and run cargo run --release. Once it finishes, you should have a new file noise-reduced.jpg as the output of our process.

And there we have it.

Further Reading

These are some of the resources that were very helpful to me when I was learning about this algorithm and how to use it. I highly encourage anyone who wants a more technical understanding of the algorithm to check these out.

• The à trous algorithm
• The À Trous Discrete Wavelet Transform In PixInsight
• Astronomical Image and Data Analysis by Jean-Luc Starck and Fionn Murtagh
• Sparse Image and Signal Processing: Wavelets and Related Geometric Multiscale Analysis by J.L. Starck, F. Murtagh, and J. Fadili

In addition, I've created a Rust library for working with À Trous transform. It closely matches with what I've showed you here, but has some additional features already, and will have even more.

Things such as handling RGB images and working with all the 3 different kernels is already implemented. It also has better logic for handling boundary conditions, where it uses the image folding technique.

I'm also soon going to be working on performance improvements for the same.

If you want to learn more, or contribute to the library, feel free to do so. The repository can be found here: https://github.com/anshap1719/image-dwt

Wrapping Up

I hope you enjoyed the journey so far. If image processing techniques or their implementation in Rust is something that interests you, then stay tuned for more as these are the topics I love writing about.

Also, feel free to contact me if you have any questions or opinions on this topic.

Enjoying my work?

Consider buying me a coffee to support my work!

Till next time, happy coding and wishing you clear skies!

We just posted a course on the freeCodeCamp Community YouTube channel that will equip you with the essential skills to excel in Leetcode-style coding challenges. Mukhtar from Coding Monkey developed this course.

The course begins with an introduction that sets the stage for what you're about to learn. It emphasizes the significance of algorithms in coding interviews and how mastering them can be a game-changer for your career. The course is structured to transform your approach to problem-solving, enabling you to tackle Leetcode problems with newfound confidence.

Here are some of the algorithms and challenges you will learn about:

Reverse String & Integers

Learn how to manipulate strings and integers by reversing them. This section teaches the fundamental techniques for reversing data types, a common task in coding interviews that tests your understanding of strings and number manipulation.

Palindrome

A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward. This section covers the strategies to determine whether a given input is a palindrome, showcasing your ability to work with strings and logic.

Max Char

Identify the most frequently occurring character in a string. This algorithm is crucial for understanding character mapping and frequency analysis, which are pivotal in many coding challenges.

Array Chunking

Learn to divide an array into chunks of a specified size, a vital skill for data manipulation and organization in coding tasks.

Title Case

Transform the casing of strings to title case, where the first letter of each word is capitalized. This section hones your string manipulation skills and attention to detail.

Anagrams

Discover how to check if two strings are anagrams of each other, meaning they contain the same characters in a different order. This algorithm tests your ability to analyze and rearrange data.

Count Vowels

Counting vowels in a string is a fundamental task that reinforces your understanding of string traversal and character comparison.

Fizz Buzz

A classic problem that combines numbers and strings. You'll learn to output "Fizz," "Buzz," or "FizzBuzz" based on a number's divisibility, sharpening your logical thinking and control flow mastery.

Steps String Pattern

Create a step-like pattern using strings, a unique challenge that enhances your understanding of nested loops and string manipulation.

Pyramid String Pattern

Build a pyramid with strings. This algorithm takes your loop skills further, challenging you to create a visually structured output.

Spiral Matrix

As a bonus, the course offers a section on creating a spiral matrix, an advanced challenge that will test your array manipulation and pattern recognition skills.

This course is an excellent opportunity to refine your algorithmic thinking and prepare for those daunting coding interviews. Watch the full course on the freeCodeCamp.org YouTube channel (2-hour watch).

In this tutorial, you'll learn the following:

• Constant and linear time complexity.
• Why use a hash map?
• Things to consider when writing hash functions.
• How to solve the Two Sum problem in PHP and JavaScript.

What is Constant Time Complexity - O(1)?

O(1) indicates that the running time of an algorithm is constant, regardless of the input size.

This implies that the algorithm's performance isn't dependent on the size of the input. An example is accessing an index of an array.

<?php

function constantTimeAlgorithm($arr) 
{

    echo $arr[0] . PHP_EOL;
}

Here is a non-code example to illustrate the concept of constant time complexity:

Imagine sending a file through an airline to your friend, and the airline has a policy where they charge based on the weight of the package.

Now, whether your file weighs 2 grams or 20 kilograms, the airline's processing time remains constant. This means that the time it takes for the airline to handle your package doesn't depend on the weight of the file – it's always the same.

In other words, the processing time is constant irrespective of the size of the file.

What is Linear Time Complexity - O(n)?

O(n) indicates that the running time of an algorithm grows linearly with the size of the input.

The performance of the algorithm is directly proportional to the input size. An example is traversing a for loop and printing elements.

<?php

function linearTimeAlgorithm($arr) 
{
    foreach ($arr as $element) {
        echo $element . PHP_EOL;
    }
}

Here's a non-code example to illustrate the concept of linear time complexity:

Consider using an electronic transfer service to send a file to your friend. In this scenario, the time it takes to transfer the file increases linearly with the size of the file.

For instance, if it takes 1 minutes to transfer a 100 MB file, it would take approximately 100 minutes to transfer a 10 GB file using the same service.

This linear relationship between the size of the file and the time it takes to transfer it reflects linear time complexity. The time taken to transfer the file increases proportionally or linearly with the size of the input or file.

Why use a Hash Map?

Illustration of how a hash map works

A hash map is a concrete implementation of the abstract data type known as an associative array.

In a hash map, keys are hashed to determine the index where the corresponding values will be stored, allowing for efficient retrieval and storage of key-value pairs.

This implementation typically provides fast access times for operations like insertion, deletion, and lookup of values based on their associated keys.

In languages like PHP or JavaScript, when you use an associative array, you are essentially using a hash map. Their associative arrays are implemented using hash tables behind the scenes.

You can use strings, integers, or other data types as keys, and the language's internal hashing mechanism efficiently maps these keys to their corresponding values. Additionally, JavaScript provides the Map object for more advanced hash map functionalities.

Time and Space Complexity for Hash Map

The time and space complexity for a hash map (or hash table) is not necessarily O(n) for all operations. The typical and desired time complexity for basic operations like insertion, lookup, and deletion in a well-designed hash map is O(1) on average.

Here's a breakdown of time and space complexity for a hash map:

Time Complexity:

Average Case:

• Insertion (average): O(1)
• Lookup (average): O(1)
• Deletion (average): O(1)

Worst Case:

• Insertion (worst): O(n), where n is the size of the hash map. This occurs when there are many hash collisions, leading to linear probing or other collision resolution strategies that may involve traversing the entire hash map.
• Lookup and Deletion (worst): O(n), for the same reason as insertion.

Space Complexity:

• The space complexity is typically O(n). Where n is the number of key-value pairs stored in the hash map. Each key-value pair occupies constant space, and the space required grows linearly with the number of elements.

In algorithm analysis, the notation O(1) and O(n) represent the upper bounds on the time complexity of an algorithm, where n is the size of the input.

Operations

1. Insertion: The key-value pair is hashed, and the resulting index is used to store the value in the corresponding slot. If a collision occurs, the collision resolution strategy is applied.
2. Deletion: The key is hashed to find the index, and the item at that index is removed. Collision resolution may be necessary.
3. Lookup: The key is hashed to find the index, and the value at that index is returned. Collision resolution may be applied if needed.

Things to consider When Creating Hash Tables

When creating hash tables, there are several important considerations to ensure efficiency, including fast computation of hash codes and effective collision resolution strategies.

Fast Computation

Hash codes should be computed quickly to ensure efficient insertion, lookup, and deletion operations. A good hash function contributes to the speed of hash code computation.

Avoid collision

A collision happens when two or more keys produce the same hash code. In other words, multiple keys map to the same array index.

How to Handle Collisions

Hash maps use collision resolution techniques to deal with collisions. Common strategies include:

Chaining

To manage several values with the same hash code, chaining involves storing a linked list or other data structure at each array index. If a collision occurs, the new key-value pair is appended to the linked list at the relevant index.

Open addressing

When a collision happens in a hash table, a technique called open addressing is employed to resolve it by searching for the next open space.

All it does is search the array for the next empty slot where the key-value combination can be placed. Methods including double hashing, quadratic probing, and linear probing are applied.

Linear Probing: In linear probing, the algorithm moves linearly to the next index in the array in order to find the next open slot when a collision occurs.

Quadratic Probing: In this method, an algorithm employs a quadratic function to find the next slot that becomes available.

Double Hashing: In double hashing, the algorithm calculates the step size between probes using a secondary hash function.

In order to reduce the possibility of collisions, a good hash function should generate distinct hash codes for various inputs. By making sure the hash codes are evenly distributed throughout the range of potential values, collisions can be prevented.

How to Solve the Two Sum Problem

Two sum problem

The Two Sum problem involves finding all pairs of elements in an array that sum up to a specific target value. Now let's look at the problem statement.

Problem statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Example 1:

Input: nums = [3,2,4, 8], target = 12

Output: [2, 3]

Example 2:

Input: nums = [5,5], target = 10

Output: [0,1]

Solution

To solve the Two Sum problem, we can use a hash table. The idea is to traverse the nums array and, for each element, check if the complement (the difference between the target and the current element) is already in the hash table. If it is, we have found a pair of indices whose elements add up to the target.

Here are the steps to follow:

1. To hold the elements and their respective indices, create an empty hash table upon initialization.
2. Go over the array of nums.
3. Do the complement calculation (target - current element) for each element.
4. Verify if the complement has already been added to the hash table. If yes, return the current index and the index stored in the hash table for the complement.
5. If the complement is not in the hash table, store the current element and its index in the hash table.
6. If no such pair is found during the traversal, it implies that there is no solution.

PHP Code Solution

<?php

function twoSum($nums, $target) {
    $hashTable = [];

    foreach ($nums as $i => $num) {
        $complement = $target - $num;

        if (array_key_exists($complement, $hashTable)) {

            // Found the pair, return the indices
            return [$hashTable[$complement], $i];
        }

        // Store the current element in the hash table
        $hashTable[$num] = $i;
    }

    // No solution found
    return [];
}

// Example usage:
$nums = [2, 7, 11, 5, 15, 30];
$target = 12;
$result = twoSum($nums, $target);

echo "Indices of the two numbers: [" . implode(", ", $result) . "]";

JavaScript Code Solution using map Function

function twoSum(nums, target) {
    const hashTable = new Map();

    for (const [index, num] of nums.entries()) {
        const complement = target - num;

        // Check if the complement is in the Map
        if (hashTable.has(complement)) {

            // Found the pair, return the indices
            return [hashTable.get(complement), index];
        }

        // Store the current number and its index in the Map
        hashTable.set(num, index);
    }

    // No solution found
    return [];
}

// Example usage:
const nums = [2, 7, 11, 5, 15, 30];
const target = 12;
const result = twoSum(nums, target);

console.log(`Indices of the two numbers that add up to ${target}: [${result.join(', ')}]`);

This approach has a time complexity of O(n) because we iterate through the array once. The space complexity is also O(n) due to the storage of elements in the hash map.

Resources

1. Hash table From Wikipedia
2. Hash maps in Python

Conclusion

In this article, you learned about hash maps, things to consider when writing hash functions and a real world problem that involves solving the Two Sum problem.

Keep learning, and Happy Coding!

You can find me on LinkedIn and Twitter.

During this process, I came across the Sliding Window technique. I found this algorithm to be very interesting, so I wanted to share my learnings with the community.

This tutorial will be useful for you if you're preparing for competitive programming interviews. So, let's get started.

What is the Sliding Window Technique?

The sliding window technique is an algorithmic approach used in computer science and signal processing. It involves selecting a fixed-size subset, or "window," from a larger dataset and moving this window through the dataset in a step-wise fashion.

The window slides over the data, typically one element at a time, and performs some operation on the elements within the window at each step.

Are you confused? Let me elaborate on this technique with an example.

Sliding Window example

Assume you're practicing for competitive programming and you encounter the following problem:

"Find the maximum sum of sub-array of size k with the time complexity of O(N).

Array = [1, 2, 6, 2, 4, 1], k = 3"

If you're not familiar with the concept of time complexity, here's a quick definition:

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.

And here's a course if you'd like to learn more.

Back to our problem. Basically, we have to find the sub-array of size 3, whose sum is the maximum (largest number). Here's a pictorial view of how we can go about solving this:

Find sum of sub-array of size k

Manual solution

Let's solve it manually. From the above image, let's find the sum of each of the sub-arrays of size 3.

• Sum of 1st sub-array = 1 + 2 + 6 = 9
• Sum of 2nd sub-array = 2 + 6 + 2 = 10
• Sum of 3rd sub-array = 6 + 2 + 4 = 12
• Sum of 4th sub-array = 2 + 4 + 1 = 7

The maximum (biggest) number among 9, 10, 12, and 7 is 12 – or the 3rd sub-array. That is our solution.

Code solution

Alright, let's wear our programming shoes and try to solve this using code.

Here's my solution to the problem:

Here's a quick walk through of the above code.

I'm defining the input array and window size at the bottom, and calling the method findMaxSumOfSequence with these parameters.

Initially I'm doing a validation if the input array size is more than the window size, else the calculation is not possible, so return null.

I'm assuming the maximum sum to be negative infinity.

I iterate over the array, and for each item in the array, I iterate for next k items, find their sum, and assign the current window sum to maximum sum variable if the current window sum is more than existing maximum sum. Finally, return the maximum sum.

Let's try to run the code.

Find maximum sum of a sub-array of size k

Here we go. We got the right answer.

But, the problem does not stop here. If you look at the problem carefully, we have to find the solution in O(N) time complexity.

So, you might wonder what's the time complexity of the above solution. Well, the time complexity of the above solution is O(N*k). This means, we're iterating k times for each item in the array (nested for-loop).

O(N) time complexity basically describes that you have to find the maximum value by iterating over the given array only once.

Using the Sliding Window technique

How do we solve this with one iteration? Here's where sliding window technique comes into play. Let's take a look at the pictorial representation of our solution once again:

Sliding window technique

Here, you may notice that the window slides over the array. It's initially covering the indices 0, 1, and 2 in the 1st sub-array. For the next sub-array, it slides one-position to the right, eliminating 0th index to the left and adding the 3rd index to the right. So, now it covers the 1, 2, and 3 in the 2nd sub-array...and so on.

The calculation goes this way for the sub-arrays:

• 1st sub-array = 1 + 2 + 6 = 9
• 2nd sub-array = 9 (sum of 1st sub-array) - 1 + 2 = 10

Let's take a look at this carefully. We find the sum of 1st sub-array to be 9. To calculate the sum of 2nd sub-array, we subtract the number that's going out (1 at 0th index) and add the number that's coming in (2 at 3rd index).

• 3rd sub-array = 10 (sum of 2nd sub-array) - 2 + 4 = 12
• 4th sub-array = 12 (sum of 3rd sub-array) - 6 + 1 = 7

This is the sliding window technique. Following this technique, we'll able to find the sum of maximum sub-array in a single iteration.

How to implement Sliding Window in code

Alright, let's put on our coding shoes again and try to implement this.

Let's try to understand the above code. I made some changes to the findMaxSumOfSequence method. I introduced start and end variables which describe the window block.

In this implementation, we have 2 loops but they're not nested. This is because, in the first loop, we have to find the sum of the 1st window. The second loop will subtract and add items from the result of the first loop.

From the above example, the first loop will iterate over the first k items (3) which are 1, 2, and 6. I calculate the sum and store them in the maxSum and windowSum variables.

In the next loop, I'm iterating over each item in the array. For each item, I'm subtracting the previous number and adding the next number, and updating the result in the windowSum variable. I compare the windowSum and maxSum variables and update the maxSum variable if the windowSum is larger. Then I move the window to the next sub-array by incrementing the start and end variables. Finally, I return the maximum sum.

Here's the output of the above code:

Find maximum sum of a sub-array of size k using sliding window technique

With this implementation, we have satisfied the problem's requirement by iterating over the array only once and finding the maximum sum of a sub-array (with O(N) time complexity).

Applications of the Sliding Window Technique

The Sliding Window Technique is versatile and finds applications in various domains.

Array and String Manipulation: In array or string processing, a sliding window can be used to efficiently perform operations such as finding subarrays or substrings that satisfy certain conditions.

Data Compression: Sliding window compression algorithms, like LZ77 and its variants, use a window to find repeated patterns in the input data and replace them with references to previous occurrences.

Image Processing: In image processing, a sliding window can be employed for tasks such as feature extraction, object detection, or image segmentation.

Signal Processing: Time-series data can be analyzed using a sliding window to capture local patterns, trends, or anomalies.

Network Protocols: Sliding window protocols are used in computer networks for reliable and efficient data transmission. The sender and receiver maintain a window of allowable sequence numbers to manage the flow of data.

Conclusion

Hope you now have a clear idea of how the Sliding Window Technique works after seeing these examples. I would recommend that you try to solve some other problems with this technique to get familiar with it. Trying to find the minimum sum of the sub-array of size k on your own using this technique would be a helpful exercise.

As I mentioned earlier, I'm actively looking to switch my job. If you have a good position available in your organization, please refer me.

Hope you enjoyed reading this article. If you wish to learn more about techniques to crack competitive programming interviews, subscribe to my newsletter by visiting my site which also has a consolidated list of all my blogs.

K-means clustering is a basic but powerful tool in data science. It has changed the way we look at and understand large datasets.

In this article, we’ll learn about what K-means clustering is, how it works, what it’s used for, and some problems it might have. This guide is helpful and easy to understand, whether you’re learning about data science or just interested in it.

Basics of Clustering

Clustering is a way to put similar data points into groups. It helps us find patterns and shapes in data, which is very useful in areas like marketing and biology.

It’s a type of ‘unsupervised learning’, meaning the data forms its own groups without us knowing the answers beforehand.

There are many types of clustering methods like Hierarchical, Density-based, Distribution-based, and Partitioning methods. K-means falls into the category of “partitioning methods”.

What is K-Means Clustering?

K-means clustering is a way to split data into groups, or ‘clusters’.

Image of graphs depicting data points before and after k-means clustering

We decide how many groups we want, called ‘K’. The aim is to make items in each group as similar as possible while making the groups different from each other.

K-means usually makes groups that are about the same size. This is different from hierarchical clustering, which can make groups of different sizes.

How the K-means Algorithm Works

K-means is popular because it’s a simple yet smart way of clustering data. Here’s how it works.

A cluster is a group of data points that are grouped together because they are similar. You will choose a number, k, which is the number of central points, called centroids, that you want in your data.

A centroid is a central spot that stands in the middle of a cluster. Each data point is placed into one of these clusters. This is done by minimizing the total distance within each cluster.

In simple terms, the K-means algorithm picks k centroids, and then assigns each data point to the closest cluster. The goal is to keep these central points, or centroids, as close together as possible.

Here, the term ‘means’ in K-means is about finding the average or the centroid of the data.

Here is a step by step approach:

1. Pick the Number of Groups (K): First, decide how many groups you want, called ‘K’. You can choose this based on what you know or use methods like the elbow method.
2. Start with Centroids: Choose K points from your data randomly as starting points, called centroids.
3. Group Data Points: Put each point in your data into the nearest group, based on how close it is to the centroids.
4. Update Centroids: Change each group’s centre point to the average of all the points in that group.
5. Keep Going Until It’s Just Right: Repeat steps 3 and 4 until the groups don’t change any more.

Picking the right number for K is important. If you have too many groups, it might get too complicated. If you have too few, it might be too simple.

If you want to see how this works in code, here is a simple example:

from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
import numpy as np

# Step 1: Generate random data
np.random.seed(0)
x = -2 * np.random.rand(100, 2)  # Generate random points around (-2, -2)
x1 = 1 + 2 * np.random.rand(50, 2)  # Generate random points around (3, 3)
x[50:100, :] = x1  # Combine the two sets of points

# Step 2: Visualize the data (unclustered)
plt.scatter(x[:, 0], x[:, 1], s=50, c='b')
plt.xlabel('X Axis')
plt.ylabel('Y Axis')
plt.show()

# Step 3: Apply KMeans clustering
kmeans = KMeans(n_clusters=2)  # Initialize KMeans with 2 clusters
kmeans.fit(x)  # Fit the model to the data

# Step 4: Get the coordinates of the cluster centers and the cluster labels
centroids = kmeans.cluster_centers_  # Centroids of the clusters
labels = kmeans.labels_  # Labels of each point

# Step 5: Visualize the clustered data
plt.scatter(x[:, 0], x[:, 1], s=50, c=labels, cmap='viridis')  # Plot data points with cluster color
plt.scatter(centroids[:, 0], centroids[:, 1], s=200, c='red', marker='*')  # Plot centroids
plt.xlabel('X Axis')
plt.ylabel('Y Axis')
plt.title('K-Means Clustering')
plt.show()

Here is the final result after clustering.

K-means clustering

Where Do We Use K-Means Clustering?

K-means clustering is used in many areas. Let’s look at a few of them:

Market Segmentation

K-means clustering is a tool businesses use to learn about their customers. It groups customers by purchases, interests, or location.

It is useful in retail and e-commerce for making smart marketing strategies along with recommending similar products products. A good example is Amazon’s suggestions of related items after you make a purchase.

This method makes customer service and product promotion more effective. It helps businesses tailor their offerings to different customer needs, improving sales and customer satisfaction.

Image Compression and Processing

The K-means algorithm is important for working with digital images, especially when it comes to making them smaller. It does this by by grouping similar colours together and replacing them with a single colour.

When there are fewer colours, the image file becomes smaller, which saves storage space and makes it easier to send and use the image. This process doesn’t just make the image file smaller – it also makes the image simpler for computers to analyze.

This colour reduction is helpful in areas like medical imaging. Doctors often use detailed scans like MRIs to diagnose and treat illnesses. These scans show lots of tiny details, and sometimes there’s too much information. By using K-means to simplify the image, doctors can more easily see the important parts.

Document Clustering for Information Retrieval

K-means clustering can help manage piles of online information. It works by putting similar documents into groups. This is useful for search engines, digital libraries and other large scale document databases.

Imagine an online library with millions of articles. K-means can help by sorting these articles into related clusters. This can help search engines search for relevant content quickly instead of going through every single article in the database.

When you’re looking for something specific, K-means makes it easier and faster to find.

Anomaly Detection in Network Security

In network security, K-means clustering is like a smart guard. It helps security teams by spotting unusual patterns in data traffic that could be signs of threats.

Here’s how it works: Normally, data in a network has a regular pattern. K-means looks at all this data and groups it based on these patterns. But sometimes, something strange pops up — like unexpected spikes in traffic or odd data movements. These could be clues to security risks, like hacking attempts.

K-means is great at quickly finding these odd patterns. It flags data that doesn’t fit into usual groups. Security teams can then check these flags to see if they’re real dangers. This quick spotting is crucial because in network security, responding fast can prevent a lot of damage.

Genome research

K-means clustering is a useful tool in gene research, especially for medical studies. It sorts genes into groups that act similarly and helps to understand genes better.

This grouping is valuable in personalized medicine which looks at a person’s unique genes to decide on the best treatment. K-means helps by showing which genes are alike. This way, doctors can understand the treatments that will work well for someone based on their genes.

So, K-means is not just about grouping genes. It’s a key part of making medicine that’s just right for each person. It helps doctors choose treatments that match a person’s genetic details, which is a big step forward in healthcare.

Conclusion

K-means clustering is a powerful method for uncovering patterns in data. By grouping similar items, it helps in making data-driven decisions in various fields.

While it has its limitations, its ease of use and effectiveness make it a go-to method for exploratory data analysis. Whether you’re a seasoned data scientist or a curious beginner, delving into k-means clustering can open up new perspectives and insights into your data.

Thanks for reading this article. You can learn more at https://manishmshiva.com.

You can always run a sequential search—scanning the array from the beginning to the end—on the array. But if the array is sorted, running the binary search algorithm is much more efficient.

Let's learn how binary search works, its time complexity, and code a simple implementation in Python.

How Does Linear Search Work?

We'll start our discussion with linear or sequential search.

Suppose we have an unsorted sequence of numbers nums. Given this nums array, you should check if the target is present in nums. You don’t have information about whether nums is sorted.

So the only way you can do this is to scan the array in a linear fashion, starting at the first element—until you find a match.

You can loop through the entire array to check if the element at index i matches the target. Once you find a match, you can break out of the loop.

Notice that in the worst case, you’ll have to scan the entire array and be lucky enough to find a match at the last index. Or you’ll have exhausted the array—without finding a match—indicating that the element is not present in the array.

Suppose the array has n elements. Because you have to scan the entire array—in the worst case—the linear search algorithm has a time complexity of O(n).

Here's an example:

Linear Search Example | Image by the author

But when you do not know anything about the sequence, this is the best you can do. So linear or sequential search is the best you can do when searching through unsorted sequences.

How Linear Search Works in Python

The function linear_search takes in an array nums and a target to search for. It then loops through the array sequentially to check if target is present in nums:

def linear_search(nums,target):
  for num in nums:
    if num == target:
      return True
  return False

Here are a couple of sample outputs:

nums = [14,21,27,30,36,2,5,7,11]
target = 27

print(linear_search(nums,target))
# Output: True

target = 100
print(linear_search(nums,target))
# Output: False

How Does Binary Search Work?

Now consider the nums sequence with n elements sorted in ascending order. For any valid index k, the following holds True for the element a_k at index k:

The elements at indices 0, 1, 2, …, (k-1) are all less than or equal to a_k. And all elements at indices (k+1) to (n-1) are greater than or equal to a_k.

With this information, you no longer need to run a linear scan. You can do it much faster with binary search.

We’re given a sorted array nums and a target. Let mid denote the middle-most index of the array and nums[mid] denote the element at the middle index. Here’s how the binary search algorithm works:

• Check if nums[mid] is equal to the target. If so, we’ve already found a match—in the very first step—and the search terminates.
• If nums[mid] > target, you only need to search the left half of the array. Even when you search through the left subarray you can use the same binary search algorithm.
• If nums[mid] < target, you can ignore all the elements up to the middle element and only consider the right half of the array.

Notice that we have a recurrence relation here. First, we start by running the binary search algorithm on the array with n elements. If we don't find the target in the very first step, we run binary search on the subarray of size at most n/2 elements.

If we end up with an empty array or an array with one element that is not the target, we conclude that the target does not exist in the nums array.

Binary Search Example | Image by the author

How to Implement Binary Search in Python

Here's a recursive implementation of binary search in Python:

def binary_search(nums,target,low,high):
  if low > high:
    return False
  else:
    mid = (low + high)//2
    if nums[mid] == target:
      return True
    elif nums[mid] < target:
      return binary_search(nums,target,mid+1,high)
    else:
      return binary_search(nums,target,low,mid-1)

With a few sample runs of the binary_search function:

nums = [2,5,7,11,14,21,27,30,36]
target = 27

print(binary_search(nums,target,0,len(nums)-1))
# Output: True

target = 38
print(binary_search(nums,target,0,len(nums)-1))
# Output: False

What Is the Time Complexity of Binary Search?

In binary search, we know that the search space is reduced by half at each step and this guides us in computing the time complexity.

For an array with n elements, we check if the middle-most element matches the target. If so, we return True and terminate the search.

But if the middle element does not match the target, we perform binary search on a subarray of size at most n/2. In the next step, we have to search through an array of size at most n/4. And we continue this recursively until we can make a decision in a constant time (when the subarray is empty).

At step k, we need to search through an array of size at most n/(2^k). And we need to find the smallest such k for which we have no subarray to search through.

Mathematically:

The time complexity of binary search is, therefore, O(logn). This is much more efficient than the linear time O(n), especially for large values of n.

For example, if the array has 1000 elements. 2^(10) = 1024. While the binary search algorithm will terminate in around 10 steps, linear search will take a thousand steps in the worst case.

Wrapping Up

And that's a wrap. I hope you found this introduction to binary search helpful! You’ll often run into questions involving binary search in coding interviews.

If you’re preparing for coding interviews, check out 10 Common Coding Interview Questions [Solved] on freeCodeCamp’s YouTube channel.

In computer science, a greedy algorithm is an algorithm that finds a solution to problems in the shortest time possible. It picks the path that seems optimal at the moment without regard for the overall optimization of the solution that would be formed.

Edsger Dijkstra, a computer scientist and mathematician who wanted to calculate a minimum spanning tree, introduced the term "Greedy algorithm". Prim and Kruskal came up with optimization techniques for minimizing cost of graphs.

Many Greedy algorithms were developed to solve graph problems. A graph is a structure made up of edges and vertices.

Diagram of a simple graph

Greedy vs Not Greedy Algorithms

An algorithm is greedy when the path picked is regarded as the best option based on a specific criterion without considering future consequences. But it typically evaluates feasibility before making a final decision. The correctness of the solution depends on the problem and criteria used.

Example: A graph has various weights and you are to determine the maximum value in the tree. You'd start by searching each node and checking its weight to see if it is the largest value.

There are two approaches to solving this problem: greedy approach or not greedy.

Example graph

This graph consists of different weights and we need to find the maximum value. We'll apply the two approaches on the graph to get the solution.

Greedy Approach

In the images below, a graph has different numbers in its vertices and the algorithm is meant to select the vertex with the largest number.

Starting from vertex 6, then it's faced with two decisions – which is bigger, 3 or 4? The algorithm picks 4, and then is faced with another decision – which is bigger, 14 or 11. It selects 14, and the algorithm ends.

On the other hand there is a vertex labeled 20 but it is attached to vertex 3 which greedy does not consider as the best choice. It is important to select appropriate criteria for making each immediate decision.

The sample graph showing the greedy approach

Not Greedy Approach

The “not greedy” approach checks all options before arriving at a final solution, unlike the "greedy approach" which stops once it gets its results.

Starting from vertex 6, then it's faced with two decisions – which is bigger, 3 or 4? The algorithm picks 4, and then is faced with another decision – which is bigger, 14 or 11. It selects 14 and keeps it aside.

Then it runs the process again, starting from vertex 6. It selects the vertex with 3 and checks it. 20 is attached to the vertex 3 and the process stops. Now it compares the two results – 20 and 14. 20 is bigger, so it selects the vertex (3) that carries the largest number and the process ends.

This approach considers many possibilities in finding the better solution.

The sample graph showing the non-greedy approach

Characteristics of a Greedy Algorithm

• The algorithm solves its problem by finding an optimal solution. This solution can be a maximum or minimum value. It makes choices based on the best option available.

• The algorithm is fast and efficient with time complexity of O(n log n) or O(n). Therefore applied in solving large-scale problems.

• The search for optimal solution is done without repetition – the algorithm runs once.

• It is straightforward and easy to implement.

How to Use Greedy Algorithms

Before applying a greedy algorithm to a problem, you need to ask two questions:

• Do you need the best option at the moment from the problem?

• Do you need an optimal solution (either minimum or maximum value)?

If your answer to these questions is "Yes", then a greedy algorithm is a good choice to solve your problem.

Procedure

Let’s assume you have a problem with a set of numbers and you need to find the minimum value.

You start of by defining the constraint, which in this case is finding the minimum value. Then each number will be scanned and checked on each constraint which serves as a condition to be fulfilled. If the condition is true, the number(s) is selected and returned as the final solution.

Here's a flowchart representation of this process:

Flow chart showing the process for solving a problem using greedy algorithms

Greedy Algorithm Examples

Problem 1 : Activity Selection Problem

This problem contains a set of activities or tasks that need to be completed. Each one has a start and finish time. The algorithm finds the maximum number of activities that can be done in a given time without them overlapping.

Approach to the Problem

• We have a list of activities. Each has a start time and finish time.

• First, we sort the activities and start time in ascending order using the finish time of each.

• Then we start by picking the first activity. We create a new list to store the selected activity.

• To choose the next activity, we compare the finish time of the last activity to the start time of the next activity. If the start time of the next activity is greater than the finish time of the last activity, it can be selected. If not we skip this and check the next one.

• This process is repeated until all activities are checked. The final solution is a list containing the activities that can be done.

The table below shows a list of activities as well as starting and finish times.

The first step is to sort the finish time in ascending order and arrange the activities with respect to the result.

After sorting the activities, we select the first activity and store it in the selected activity list. In our example, the first activity is “Homework”.

Moving to the next activity, we check the finish time of “Homework” (5) which was the last activity selected and the starting time of “Term paper” (4). To pick an activity, the starting time of the next activity must be greater than or equal to the finish time. (4) is less than (5), so we skip the activity and move to the next.

The next activity “Presentation” has a starting time of (6) and it is greater than the finish time (5) of “Homework”. So we select it and add it to our list of selected activities.

For the next activity, we do the same checking. Finish time of “Presentation” is (10), starting time of “Volleyball practice ” is (10). We see that the starting time is equal to the finish time which satisfies one of the conditions, so we select it and add it to our list of selected activities.

Continuing to the next activity, the finish time of “Volleyball” practice is (12) and the starting time of “Biology lecture” is (13). We see the starting time is greater than the finish time so we select it.

For our last activity, the starting time for “Hangout” is (7) and the finishing time of our last activity “Biology lecture” is (14), 7 is less than 14, so we cannot select the activity. Since we are at the end of our activity list, the process ends.

Our final result is the list of selected activities that we can do without time overlapping: {Homework, Presentation, Volleyball practice, Biology lecture}.

Code Implementation of the Example

The variable <data> stores the starting times of each activity, the finish time of each activity, and the list of tasks (or activities) to be performed.

The variable <selected_activity> is an empty list that will store the selected activities that can be performed.

<start_position> shows the position the first activity which is index “0”. This will be our starting point.

data = {
  "start_time": [2 , 6 , 4 , 10 , 13 , 7],
  "finish_time": [5 , 10 , 8 , 12 , 14 , 15],
  "activity": ["Homework" , "Presentation" , "Term paper" , "Volleyball practice" , "Biology lecture" , "Hangout"]
}

selected_activity =[]
start_position = 0

Here's a dataframe table showing the original data:

Original Info

   start_time  finish_time             activity
0           2            5             Homework
1           6           10         Presentation
2           4            8           Term paper
3          10           12  Volleyball practice
4          13           14      Biology lecture
5           7           15              Hangout

Then we sort the finish time in ascending order and rearrange the start time and activity in respect to it. We target the variables by using the keys in the dictionary.

tem = 0
for i in range(0 , len(data['finish_time'])):
   for j in range(0 , len(data['finish_time'])):
       if data['finish_time'][i] < data['finish_time'][j]:
           tem = data['activity'][i] , data['finish_time'][i] , data['start_time'][i]
           data['activity'][i] , data['finish_time'][i] , data['start_time'][i] = data['activity'][j] , data['finish_time'][j] , data['start_time'][j]
           data['activity'][j] , data['finish_time'][j] , data['start_time'][j] = tem

In the code above, we intialized <tem> to zero. We are not using the inbuilt method to sort the finish time. We are using two loops to arrange it in ascending order. <i> and <j> represent the indexes and check if values of the <data['finish_time'][i]> is less than <data['finish_time'][j]>.

If the condition is true, <tem> stores the values of the elements in the <i> position and swaps the corresponding element.

Now we print the final result, here's what we get:

print("Start time: " , data['start_time'])
print("Finish time: " , data['finish_time'])
print("Activity: " , data['activity'])

# Results before sorting
# Start time:  [2, 6, 4, 10, 13, 7]
# Finish time:  [5, 10, 8, 12, 14, 15]
# Activity:  ['Homework', 'Presentation', 'Term paper', 'Volleyball practice', 'Biology lecture', 'Hangout']


# Results after sorting
# Start time:  [2, 4, 6, 10, 13, 7]
# Finish time:  [5, 8, 10, 12, 14, 15]
# Activity:  ['Homework', 'Term paper', 'Presentation', 'Volleyball practice', 'Biology lecture', 'Hangout']

And here's a dataframe table showing the sorted data:

Sorted Info with respect to finish_time

   start_time  finish_time             activity
0       2            5             Homework
1       4            8           Term paper
2       6           10         Presentation
3          10           12       Volleyball practice
4          13           14         Biology lecture
5       7           15          Hangout

After sorting the activities, we start by selecting the first activity, which is “Homework”. It has a starting index of “0” so we use the <start_position> to target the activity and append it to the empty list.

selected_activity.append(data['activity'][start_position])

The condition for selecting an activity is that the start time of the next activity selected is greater than the finish time of the previous activity. If the condition is true, the selected activity is added to the <selected_activity> list.

for pos in range(len(data['finish_time'])):
   if data['start_time'][pos] >= data['finish_time'][start_position]:
       selected_activity.append(data['activity'][pos])
       start_position = pos

print(f"The student can work on the following activities: {selected_activity}")

# Results
# The student can work on the following activities: ['Homework', 'Presentation', 'Volleyball practice', 'Biology lecture']

Here's what it looks like all together:

data = {
  "start_time": [2 , 6 , 4 , 10 , 13 , 7],
  "finish_time": [5 , 10 , 8 , 12 , 14 , 15],
  "activity": ["Homework" , "Presentation" , "Term paper" , "Volleyball practice" , "Biology lecture" , "Hangout"]
}

selected_activity =[]
start_position = 0
# sorting the items in ascending order with respect to finish time
tem = 0
for i in range(0 , len(data['finish_time'])):
   for j in range(0 , len(data['finish_time'])):
       if data['finish_time'][i] < data['finish_time'][j]:
           tem = data['activity'][i] , data['finish_time'][i] , data['start_time'][i]
           data['activity'][i] , data['finish_time'][i] , data['start_time'][i] = data['activity'][j] , data['finish_time'][j] , data['start_time'][j]
           data['activity'][j] , data['finish_time'][j] , data['start_time'][j] = tem

# by default, the first activity is inserted in the list of activities to be selected.

selected_activity.append(data['activity'][start_position])
for pos in range(len(data['finish_time'])):
   if data['start_time'][pos] >= data['finish_time'][start_position]:
       selected_activity.append(data['activity'][pos])
       start_position = pos

print(f"The student can work on the following activities: {selected_activity}")
# Results
# The student can work on the following activities: ['Homework', 'Presentation', 'Volleyball practice', 'Biology lecture']

Problem 2: Fractional Knapsack Problem

A knapsack has a maximum weight, and it can only accommodate a certain set of items. These items have a weight and a value.

The aim is to fill the knapsack with the items that have the highest total values and do not exceed the maximum weight capacity.

Approach to the Problem

There are two elements to consider: the knapsack and the items. The knapsack has a maximum weight and carries some items with a high value.

Scenario: In a jewelry store, there are items made of gold, silver, and wood. The costliest item is gold followed by silver and then wood. If a jewerly thief comes to the store, they take gold because they will make the most profit.

The thief has a bag (knapsack) that they can put those items in. But there is a limit to what the thief can carry because these items can get heavy. The idea is to pick the item the makes the highest profit and fits in the bag (knapsack) without exceeding its maximum weight.

• The first step is to find the value to weight ratio of all items to know what fraction each one occupies.

• We then sort these ratios in descending order (from highest to lowest ). This way we can pick the ratios with the highest number first knowing that we will make a profit.

• When we pick the highest ratio, we find the corresponding weight and add it to the knapsack. There are conditions to be checked.

Condition 1: If the item added has a lesser weight than the maximum weight of the knapsack, more items are added until the sum of all the items in the bag are the same as the maximum weight of the knapsack.

Condition 2: If the sum of the items’ weight in the bag is more than the maximum capacity of the knapsack, we find the fraction of the last item added. To find the fraction, we do the following:

• We find the sum of the remaining weights of the items in the knapsack. They must be less than the maximum capacity.

• We find the difference between the maximum capacity of the knapsack and the sum of the remaining weights of the items and divide by the weight of the last item to be added.

Fraction =  (maximum capacity of the knapsack - sum of remaining weights) / weight of last item to be added

To add the weight of the last item to the knapsack, we multiply the fraction by the weight.

Weight_added = weight of last item to be added  * fraction

When we sum up the weights of all the items it will be equal to the knapsack's maximum weight.

Practical Example:

Let's say that the maximum capacity of the knapsack is 17, and there are three items available. The first item is gold, the second item is silver, and third item is wood.

• Weight of gold is 10, the weight of silver is 6, and the weight of wood is 2

• the value (profit) of gold is 40, the value (profit) of silver is 30, and the value (profit) of wood is 6.

• Ratio of gold= value/weight = 40/10 = 4

• Ratio of silver = value/weight=30/6 = 5

• Ratio of wood = value/weight = 6/2 = 3

• Arranging the ratios in descending: 5, 4, 3.

• The largest ratio is 5 and we match it to the corresponding weight “6”. It points to silver.

• We put silver in the knapsack first and compare it to the maximum weight which is 17. 6 is less than 17 so we have to add another item. Going back to the ratios, the second largest is “4” and it corresponds to the weight of “10” which points to gold.

• Now, we put gold in the knapsack, add the weight of the silver and gold, and compare it with the knapsack weight. (6 + 10 = 16). Checking it against the maximum weight, we see that it is less. So we can take another item. We go back to the list of ratios and take the 3rd largest which is “3” and it corresponds to “2” which points to wood.

• When we add wood in the knapsack, the total weight is (6 +10+2 = 18) but that is greater than our maximum weight which is 17. We take out the wood from the knapsack and we are left with gold and silver. The total sum of the two is 16 and the maximum capacity is 17. So we need a weight of 1 to make it equal. Now we apply condition 2 discussed above to find the fraction of wood to fit in the knapsack.

Explanation of filling the remaining space in the backpack with a fractional piece of wood

Now the knapsack is filled.

Code Implementation of the Example

The variable <data> stores the weights of each item and the profits. The variable <maximum_capacity> stores the maximum weight of the knapsack. <selected_wt> is intialized at 0, and it will store the selected weights to be put in the knapsack. Lastly, <max_profit> is intialized as 0, it will store the values of the selected weight.

data = {
    "weight": [10 , 6 , 2],
    "profit":[40 , 30 ,6]
}
max_weight = 17
selected_wt = 0
max_profit = 0

Then we calculate the ratio of the profit to the weight. Ratio = profit/weight:

ratio = [int(data['profit'][i] / data['weight'][i]) for i in range(len(data['profit']))]

Now that we have the ratio, we arrange the elements in descending order, from biggest to smallest. Then the items in weight and profit are arranged according to the positions of the sorted ratio.

for i in range(len(ratio)):
    for j in range(i + 1 , len(ratio)):
        if ratio[i] < ratio[j]:
            ratio[i] , ratio[j] = ratio[j] , ratio[i]
            data['weight'][i] , data['weight'][j] = data['weight'][j] , data['weight'][i]
            data['profit'][i] , data['profit'][j] = data['profit'][j] , data['profit'][i]

After the weight and profit are sorted, we start choosing the items and checking the condition. We loop through the length of ratio to target the index of each item in the list. Note: all items in ratio are arranged from biggest to smallest, so the first item is the maximum value and the last item is the minimum value.

for i in range(len(ratio)):

The first item we select has the highest ratio amongst the rest and it is in index 0. Now that the first weight is selected weight, we check if it is less than maximum weight. If it is, we add items till the total weight is equal to the weight of the knapsack. The second item we select has the second highest ratio amongst the rest and it is in index 1, the arrangement is that order of selection.

For every selected weight, we add it to the selected_wt variable and their corresponding profits to the max_profit variable.

if selected_wt + data['weight'][i] <= max_weight:
          selected_wt += data['weight'][i]
          max_profit += data['profit'][i]

When the sum of the selected weights in the knapsack exceeds the maximum weight, we find the fraction of the weight of the last item added to make the total selected weights be equal to the maximum weight. We do this by finding the difference between the max_weight and the sum of the selected weights divided by the weight of the last item added.

The final profit made from the fraction carried is added to the max_profit variable. Then we return the max_profit as the final result.

      else:
          frac_wt = (max_weight - selected_wt) / data['weight'][i]
          frac_value = data['profit'][i] * frac_wt
          max_profit += frac_value
          selected_wt += (max_weight - selected_wt)
print(max_profit)

Bringing it all together:

data = {
    "weight": [10 , 6 , 2],
    "profit":[40 , 30 ,6]
}
max_weight = 17
selected_wt = 0
max_profit = 0

# finds ratio
ratio = [int(data['profit'][i] / data['weight'][i]) for i in range(len(data['profit']))]

# sort ratio in descending order, rearranges weight and profit in order of the sorted ratio
for i in range(len(ratio)):
    for j in range(i + 1 , len(ratio)):
        if ratio[i] < ratio[j]:
            ratio[i] , ratio[j] = ratio[j] , ratio[i]
            data['weight'][i] , data['weight'][j] = data['weight'][j] , data['weight'][i]
            data['profit'][i] , data['profit'][j] = data['profit'][j] , data['profit'][i]


# checks if selected weight with the highest ratio is less than the maximum weight, if so it adds it to knapsack and stores the profit, select the next item.
# else the sum of the selected weights is more than max weight, finds fraction

for i in range(len(ratio)):
    if selected_wt + data['weight'][i] <= max_weight:
          selected_wt += data['weight'][i]
          max_profit += data['profit'][i]
    else:
          frac_wt = (max_weight - selected_wt) / data['weight'][i]
          frac_value = data['profit'][i] * frac_wt
          max_profit += frac_value
          selected_wt += (max_weight - selected_wt)

print(f"The maximum profit that can be made from each item is: {round(max_profit , 2)} euros")
# Result
# The maximum profit that can be made from each item is: 73.0 euros

Applications of Greedy Algorithms

There are various applications of greedy algorithms. Some of them are:

• [Minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree#:~:text=A%20minimum%20spanning%20tree%20(MST,minimum%20possible%20total%20edge%20weight.) is without any cycles and with the minimum possible total edge weight. This tree is derived from a connected undirected graph with weights.

• Dijkstra’s shortest path is a search algorithm that finds the shortest path between a vertex and other vertices in a weighted graph.

• Travelling salesman problem involves finding the shortest route that visits different places only once and returns to the starting point

• Huffman coding assigns shorter code to frequently occurring symbols and longer code to less occurring symbols. It is used to encode data efficiently.

Advantages of Using a Greedy Algorithm

Greedy algorithms are quite straight forward to implement and easy to understand. They are also very efficient and have a lower complexity time of O(N * logN).

They're useful in solving optimization problems, returning a maximum or minimum value.

Disadvantages/Limitations of Using a Greedy Algorithm

Even though greedy algorithms are straightforward and helpful in optimization problems, they don't offer the best solutions at all times.

Also greedy algos only run once, so they don't check the correctness of the result produced.

Conclusion

Greedy algorithms are a straightforward approach to solving optimization problems, returning a minimum or maximum value.

This article explained some examples of greedy algorithms and the approach to tackling each problem. By understanding how a greedy algorithm problems works you can better understand dynamic programming. If you have any questions feel free to reach out to me on Twitter💙.

The Euclidean Algorithm is a well-known and efficient method for finding the greatest common divisor (GCD) of two integers. The GCD is the largest number that can divide both integers without leaving a remainder.

The algorithm is named after the ancient Greek mathematician Euclid, who presented it in his book "Elements" around 300 BCE.

You can use this algorithm to solve Diophantine equations, to tackle the shortest-vector problem which is the foundation of lattice-based cryptography, and also to detect common patterns of pixels in images. This is, among other things, applied to optimize rendering processes and detect different objects in images.

How Does the Euclidean Algorithm Work?

Here's a step-by-step explanation of how the Euclidean Algorithm works:

Start with two positive integers, a and b, where a >= b. If a < b, simply swap their values. Note that this is meant for a convenient mathematical demonstration, as the implementation also works for a < b.

Divide a by b and find the remainder, r (use the modulo operation, represented as a % b). If r is 0, the GCD is b, and the algorithm terminates.

If r is not 0, set a to b and b to r. Then, repeat step 2.

The algorithm continues to iterate until the remainder is 0. At that point, the last non-zero remainder is the GCD of the original two numbers.

The Euclidean Algorithm works because the GCD of two numbers remains unchanged when the larger number is replaced by its remainder when divided by the smaller number.

Example of Euclidean Algorithm

Here's an example to illustrate the algorithm:

Let's find the GCD of 30 and 9:

a = 30, b = 9

Calculate the remainder: r = a % b = 30 % 9 = 3 (since 3 is not 0, continue to step 3)

Update the values: a = 9, b = 3

Calculate the new remainder: r = a % b = 9 % 3 = 0 (r is now 0)

The GCD of 30 and 9 is 3.

Why Does the Euclidean Algorithm Work?

The greatest common divisor of two integers is the largest positive integer that divides both of them without leaving a remainder. So the algorithm is based on the following key property:

If a and b are two integers, then the GCD of a and b is the same as the GCD of b and a % b, where % represents the modulo operator (the remainder after division).

Mathematically, the key property of the algorithm can be justified using the division algorithm:

Let a and b be two positive integers, such that a >= b. We can write the division algorithm as:

a = bq + r, where q is the quotient and r is the remainder.

Now, let d be a common divisor of a and b. Then, a = d * m1 and b = d * m2 for some integers m1 and m2. We can rewrite the division algorithm as:

d * m1 = (d * m2) * q + r.

Rearranging the equation, we get:

r = d * (m1 - m2 * q).

Since d is a factor of both a and b, and r can also be written as a multiple of d, we can conclude that d is also a divisor of r. This means that the GCD of a and b is also a divisor of r. So, we can replace b with r and keep finding the GCD using this algorithm until b becomes 0.

The Euclidean Algorithm is particularly useful due to its efficiency and simplicity, making it easy to implement in computer algorithms and programming languages.

Let's see some different ways to implement it in Go:

Recursive Implementation of the Euclidean Algorithm in Go

This implementation of the Euclidean Algorithm in Golang is a recursive version that finds the GCD of two integers. Let's go through it step by step:

The function is defined as GCD(a, b int) int. It takes two integer inputs, a and b, and returns an integer output.

The base case of the recursion is checked with if b == 0. If b is 0, the function returns the value of a as the GCD.

If b is not 0, a temporary variable tmp is created and assigned the value of a. This temporary variable is used to store the value of a before updating its value in the next step.

The values of a and b are updated as follows:

• a is assigned the current value of b.
• b is assigned the value of the remainder when tmp (the previous value of a) is divided by the new value of a (which was b before the update).

The function calls itself recursively with the updated values of a and b as input, return GCD(a, b).

The algorithm continues to call itself recursively until the base case is reached, that is b becomes 0. At this point, the function returns the GCD, which is the value of a.

// Recursive approach:
func GCD(a, b int) int {
    if b == 0 {
        return a
    }
    tmp := a
    a = b
    b = tmp % a
    return GCD(a, b)
}

For example, let's say we want to find the GCD of 56 and 48:

First call: GCD(56, 48)

• Since b (48) is not 0, update a and b:
• a becomes 48
• b becomes 56 % 48 = 8
• The function calls itself with the new values: GCD(48, 8)

Second call: GCD(48, 8)

• Since b (8) is not 0, update a and b:
• a becomes 8
• b becomes 48 % 8 = 0
• The function calls itself with the new values: GCD(8, 0)

Third call: GCD(8, 0)

• Now, b (0) is 0, so the function returns a (8) as the GCD.

Iterative Implementation of the Euclidean Algorithm in Go

This implementation of the Euclidean Algorithm in Golang is an iterative version using a loop to find the GCD of two integers. Let's go through the code step by step:

The function is defined as GCD(a, b int) int. It takes two integer inputs, a and b, and returns an integer output.

A loop is used to iterate as long as b is not equal to 0. The loop condition is b != 0. Note that this for loop construction in Go is essentially a while loop in many other languages.

Inside the loop, the values of a and b are updated simultaneously using a tuple assignment: a, b = b, a%b. This line does the following:

• a is assigned the current value of b.
• b is assigned the value of the remainder when a is divided by b.

When the loop exits (that is, b becomes 0), the value of a is returned as the GCD.

The algorithm iterates until the remainder (b) is 0, at which point the GCD is the last non-zero remainder, which is the value of a.

func GCD(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

For example, let's say we want to find the GCD of 100 and 64:

Initialize a as 100 and b as 64. Check the loop condition: b (64) is not 0.

Inside the loop, update a and b:

• a becomes 64
• b becomes 100 % 64 = 36
  Check the loop condition again: b (36) is not 0.

Inside the loop, update a and b:

• a becomes 36
• b becomes 64 % 36 = 28
  Check the loop condition again: b (28) is not 0.

Inside the loop, update a and b:

• a becomes 28
• b becomes 36 % 28 = 8
  Check the loop condition again: b (8) is not 0.

Inside the loop, update a and b:

• a becomes 8
• b becomes 28 % 8 = 4
  Check the loop condition again: b (4) is not 0.

Inside the loop, update a and b:

• a becomes 4
• b becomes 8 % 4 = 0
  Check the loop condition again: Now, b (0) is 0, so the loop exits.

The function returns the value of a (4) as the GCD.

Testing the Solutions

These tests were created by Jon Calhoun in his free Go Algorithms course. Assuming you defined your GCD function in a file named gcd.go, place these tests in a file named gcd_test.go. Read below to see how the tests will work:

The function TestGCD is defined, taking a single parameter t *testing.T. The *testing.T is a pointer to a testing.T object that provides methods for reporting test failures and logging additional information.

An array of anonymous structs is defined, called tests. Each struct has three fields: a, b, and want. These structs represent test cases, where a and b are input values for the GCD function, and want is the expected result (correct GCD).

Several test cases are defined in the tests array, covering different scenarios.

A for loop iterates through the tests array. In each iteration, a single test case (struct) is assigned to the variable tc.

The t.Run function is called to run a subtest for the current test case. The first argument is a formatted string that describes the test case (using the input values tc.a and tc.b). The second argument is an anonymous function that takes a *testing.T parameter, similar to the main test function.

Inside the subtest function, the GCD function is called with the input values tc.a and tc.b, and the result is assigned to the got variable.

The got result is compared to the expected result tc.want. If they are not equal, the t.Fatalf function is called to report the test failure and provide an error message with the incorrect result and the expected result.

This test function helps ensure that the GCD function works correctly for various input values and edge cases. Running this test function with the go test command will execute all the test cases and report any failures, which can help identify potential issues with the GCD function implementation.

import (
    "fmt"
    "testing"
)

func TestGCD(t *testing.T) {
    tests := []struct {
        a, b int
        want int
    }{
        {10, 5, 5},
        {25, 5, 5},
        {30, 15, 15},
        {30, 9, 3},
        {100, 9, 1},
        {
            2 * 2 * 3 * 3 * 5,
            2 * 3 * 5 * 7 * 13,
            2 * 3 * 5,
        }, {
            2 * 2 * 3 * 3 * 13,
            2 * 3 * 5 * 7 * 13,
            2 * 3 * 13,
        }, {
            2 * 3 * 5 * 7 * 11 * 13 * 17 * 19,
            3 * 3 * 7 * 7 * 11 * 11 * 17 * 17,
            3 * 7 * 11 * 17,
        },
    }
    for _, tc := range tests {
        t.Run(fmt.Sprintf("(%v,%v)", tc.a, tc.b), func(t *testing.T) {
            got := GCD(tc.a, tc.b)
            if got != tc.want {
                t.Fatalf("GCD() = %v; want %v", got, tc.want)
            }
        })
    }
}

Run the tests, creating different cases as you wish:

go test -v # verbose flag

Conclusion

Hope you had a good time learning about the Euclidean algorithm and its implementation in Go.

If you are interested in how these clever tricks work, take a look at the field of Number Theory in mathematics, which is particularly focused on the properties of integers, especially involving prime numbers.