The Nearest Neighbour Algorithm is one of the foundational concepts in Data Warehousing and Mining (DWM). It is used to analyse a graph or dataset and classify its nodes into two groups based on a given threshold distance. A node is placed in the close neighbourhood (K1) if it is within the threshold, and in the far neighbourhood (K2) if it exceeds it.
In this post we walk through a well-commented C++ implementation that reads an adjacency matrix of 5 vertices, accepts a starting vertex and a distance threshold, and partitions all connected vertices into the two neighbourhood sets K1 and K2.
What is the Nearest Neighbour Algorithm?
Given a graph represented as an adjacency matrix where adjMatrix[i][j] stores the distance (edge weight) between vertex i and vertex j, the algorithm works as follows for a chosen source vertex s:
Read the distance from s to every other vertex from the adjacency matrix row corresponding to s.
For each vertex v: if the distance is greater than 0 (there is an edge) and less than or equal to the threshold, add v to K1.
If the distance exceeds the threshold, add v to K2.
Also print all direct connections along with their distances.
A value of 0 on the diagonal represents the distance from a vertex to itself (no self-loops). A large value like 99 is typically used to represent no direct connection (infinity).
The K-Nearest Neighbors (KNN) algorithm is one of the simplest and most intuitive supervised machine learning algorithms. It classifies a new data point based on the majority class among its K closest neighbors in the training dataset. There is no explicit training phase — the algorithm memorizes the entire dataset and makes decisions at prediction time, which is why it is also called a lazy learner.
In this post, we will walk through a C++ implementation of the KNN algorithm that classifies a person’s height as short, medium, or tall using a small training set of 12 records. We cover the algorithm step by step and explain the output in detail.
What is the KNN Algorithm?
KNN works on a very simple principle: similar things exist in close proximity. Given an unlabeled data point, the algorithm:
Calculates the distance between the new point and every point in the training dataset.
Sorts all training points by distance (ascending).
Picks the K nearest points (the threshold).
Assigns the class that appears most frequently among those K neighbors.
This program uses a single feature — height — and the distance metric is the simple absolute difference (Manhattan distance in 1D). Gender is stored in the dataset but is not used as a feature for classification in this implementation.
Apriori is a cornerstone algorithm in association rule mining, widely used in market basket analysis (e.g., identifying which items are frequently bought together in stores). The algorithm’s power lies in its ability to uncover hidden patterns in large transactional datasets.
What Does the Apriori Algorithm Do?
The Apriori algorithm is used for discovering frequent itemsets—groups of items that appear together in a dataset with frequency above a specified threshold (called minimum support). These itemsets form the basis for generating association rules—for example, “if someone buys bread and butter, there’s a good chance they’ll also buy jam.”
A Finite State Machine (FSM) can determine whether a decimal integer is divisible by 3 without performing any division. The key insight is that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. We can track the running digit-sum modulo 3 as we process each digit, mapping perfectly onto a 3-state FSM: State 0 (remainder 0), State 1 (remainder 1), and State 2 (remainder 2). After processing all digits, the machine is in State 0 if and only if the number is divisible by 3. The FSM also prints a state trace as it processes each digit.
A Finite State Machine (FSM) can be designed to recognise strings that end with a specific suffix. In this post, we build a 4-state FSM that accepts strings over the alphabet {a, b} which end with the suffix ‘abb’. Unlike the “contains” variant, here only the final state of the machine matters — the string is accepted if and only if the last three characters form ‘abb’. The FSM also prints a state trace showing each transition as it processes the input.
A Finite State Machine (FSM) can efficiently detect whether a given string contains a specific pattern as a substring. In this post, we design an FSM with four states to check whether a string over the alphabet {a, b} contains the substring ‘abb’. The FSM uses a transition table to move between states as characters are read, and rejects the string once it finds ‘abb’. The machine enters a trap state upon detecting ‘abb’ and stays there regardless of further input.
A Turing Machine is the most powerful model of computation, capable of simulating any algorithm. While the well-formedness of parentheses is typically solved with a stack, this post models it using the Turing Machine approach: we iteratively scan the tape (string) for the innermost matching pair (), replace them with a marker character, and repeat until either all characters are markers (accepted) or an unmatched symbol remains (rejected). This technique directly mirrors how a Turing Machine’s read/write head manipulates tape symbols.
