Unearthing Data Structures & Algorithms: The Essentials Guide - Part 2
Embarking on the next leg of our journey through the landscape of data structures and algorithms, we delve into the heart of efficient problem-solving. As we bid farewell to the initial segment of this two-part series, remember that these structures form the bedrock of elegant solutions. While the terrain may appear challenging, with consistent practice and guidance, you'll unlock their potential.
Your continued readership is valued, and I'm thrilled to have you accompany us on this exploration. With that said let's jump right back to continue from where we left off.
Greedy Algorithms
A greedy algorithm aims to make the optimal choice at each step without considering the future steps. It focuses on finding the globally optimal solution locally, without looking ahead. This approach makes it fast but may not always result in the globally optimal solution. Greedy algorithms are used for various problems, including some well-known algorithms like Dijkstra's Algorithm, Kruskal's algorithm, A* algorithm, and Huffman trees.
To delve deeper into this vast topic, I recommend watching this informative video: Greedy Algorithms Explained for a more detailed explanation.
To create a greedy algorithm, you need to follow the principle of choosing the optimal choice at each moment in time. For example, when counting change, you start with the highest denomination and work backward to select the coins that fit the change amount.
Here's a summary of the key points for this algo:
Greedy algorithms make locally optimal choices without considering future steps.
Greedy algorithms aim to find the globally optimal solution using this local approach.
Greedy algorithms are faster than alternatives like Divide and conquer and Dynamic Programming.
Some popular algorithms that use the greedy approach include Dijkstra's Algorithm, Kruskal's algorithm, A*, Prim's algorithm, and Huffman trees.
To create a greedy algorithm, follow the property of choosing the optimal choice at that exact moment in time.
The example of counting change demonstrates how a greedy algorithm works by starting with the highest denomination and working backward.
Remember that the runtime of a greedy algorithm is often dominated by the loops involved, making it O(n^2) in some cases. In situations where greedy algorithms fail to find the globally optimal solution, alternatives like Dynamic Programming may be necessary.
A* (A Star) algorithm in JavaScript
A* can be considered a kind of greedy algorithm, but it's a "smart" or "informed" greedy algorithm. It's a bit more sophisticated than traditional greedy algorithms because it combines greedy principles with information from a heuristic function.
In a traditional greedy algorithm, you always choose the locally optimal choice at each step without considering the bigger picture. A* is "greedy" in the sense that it focuses on the most promising path based on the heuristic estimate. It selects the next node to explore based on the sum of the cost to reach that node from the start and the estimated cost to reach the goal from that node.
So, while A* makes locally optimal choices, it uses heuristics to make those choices smarter and more informed. It's designed to efficiently find the optimal path by prioritizing nodes that are likely to lead to the goal.
In summary, A* is a kind of "greedy" algorithm, but it's enhanced by heuristics to make more intelligent decisions, which often leads to finding the optimal path more efficiently.
// Define a class representing a node in the A* algorithm
class Node {
constructor(x, y) {
this.x = x; // X coordinate of the node
this.y = y; // Y coordinate of the node
this.g = 0; // Cost from start node to this node
this.h = 0; // Heuristic (estimated cost from this node to the goal)
this.f = 0; // Total cost (f = g + h)
this.parent = null; // Parent node for tracing the path
}
}
// A* algorithm function to find the shortest path on a grid
function astar(grid, start, end) {
const openSet = []; // Set of nodes to be evaluated
const closedSet = []; // Set of nodes already evaluated
openSet.push(start); // Add the start node to the openSet
// Continue processing nodes until the openSet is empty
while (openSet.length > 0) {
let current = openSet[0]; // Select the node with the lowest f value
let currentIndex = 0;
// Find the node with the lowest f value in the openSet
openSet.forEach((node, index) => {
if (node.f < current.f) {
current = node;
currentIndex = index;
}
});
// Remove the current node from the openSet
openSet.splice(currentIndex, 1);
// Add the current node to the closedSet
closedSet.push(current);
// If we reached the end, reconstruct the path and return it
if (current === end) {
const path = [];
let temp = current;
while (temp) {
path.push([temp.x, temp.y]);
temp = temp.parent;
}
return path.reverse();
}
// Define the possible neighboring nodes (adjust for your grid structure)
const neighbors = [];
const { x, y } = current;
if (grid[x - 1] && grid[x - 1][y]) neighbors.push(grid[x - 1][y]);
if (grid[x + 1] && grid[x + 1][y]) neighbors.push(grid[x + 1][y]);
if (grid[x][y - 1]) neighbors.push(grid[x][y - 1]);
if (grid[x][y + 1]) neighbors.push(grid[x][y + 1]);
// Evaluate neighbors
neighbors.forEach((neighbor) => {
if (!closedSet.includes(neighbor)) {
const tempG = current.g + 1; // Assuming that the cost to move to a neighboring node is 1
if (!openSet.includes(neighbor) || tempG < neighbor.g) {
// Update the neighbor's values
neighbor.g = tempG;
neighbor.h = heuristic(neighbor, end); // You need to define the heuristic function
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
// Add the neighbor to the openSet if not already present
if (!openSet.includes(neighbor)) openSet.push(neighbor);
}
}
});
}
// If no path is found
return null;
}
// Heuristic function for estimating the cost between two nodes
function heuristic(nodeA, nodeB) {
// You need to define your heuristic function here (e.g., Manhattan distance)
return Math.abs(nodeA.x - nodeB.x) + Math.abs(nodeA.y - nodeB.y);
}
// Example usage:
const gridSizeX = 5;
const gridSizeY = 5;
const grid = new Array(gridSizeX);
// Initialize the grid with nodes
for (let i = 0; i < gridSizeX; i++) {
grid[i] = new Array(gridSizeY);
for (let j = 0; j < gridSizeY; j++) {
grid[i][j] = new Node(i, j);
}
}
// Define start and end nodes
const startNode = grid[0][0];
const endNode = grid[4][4];
// Find the path using A* algorithm
const path = astar(grid, startNode, endNode);
// Output the result
if (path) {
console.log("Path found:", path);
} else {
console.log("No path found.");
}
Divide and Conquer
Closest Pair of Points:
The Closest Pair of Points algorithm aims to identify the two points in a given set that are closest to each other based on the Euclidean distance. In this context, picture a canvas adorned with scattered points, each uniquely characterized by its x and y coordinates. Here's a brief overview:
Sorting the Stage: The algorithm commences with an orchestration of order. The points take their positions on a plane, lined up by their x-coordinates.
Divide and Conquer: The algorithm carefully divides the ensemble into two halves along the vertical axis. Recursively, the algorithm finds the closest pair of points in each half. This involves calculating the distances between points and considering only those within a certain range from the dividing line.
Combine: With the closest pairs identified in each half, the algorithm turns its attention to the dividing line. This involves comparing the distances of points in one half to the other half within a certain distance of the dividing line. The final result is the pair of points with the minimum distance found during the divide, conquer, and combine steps.
// A structure to represent a Point in 2D plane
class Point {
constructor(x, y) {
this.x = x;
this.y = y;
}
}
// Needed to sort array of points
// according to X coordinate
function compareX(a, b) {
var p1 = a, p2 = b;
return (p1.x - p2.x);
}
// Needed to sort array of points according to Y coordinate
function compareY(a, b) {
var p1 = a, p2 = b;
return (p1.y - p2.y);
}
// A utility function to find the
// distance between two points
function dist(p1, p2) {
return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
}
// A Brute Force method to return the
// smallest distance between two points
// in P[] of size n
function bruteForce(P, n) {
var min = Number.POSITIVE_INFINITY;
for (var i = 0; i < n; ++i) {
for (var j = i + 1; j < n; ++j) {
if (dist(P[i], P[j]) < min) {
min = dist(P[i], P[j]);
}
}
}
return min;
}
// A utility function to find the
// distance between the closest points of
// strip of given size. All points in
// strip[] are sorted according to
// y coordinate. They all have an upper
// bound on minimum distance as d.
// Note that this method seems to be
// a O(n^2) method, but it's a O(n)
// method as the inner loop runs at most 6 times
function stripClosest(strip, size, d) {
var min = d; // Initialize the minimum distance as d
strip.sort(compareY);
// Pick all points one by one and try the next points till the difference
// between y coordinates is smaller than d.
// This is a proven fact that this loop runs at most 6 times
for (var i = 0; i < size; ++i) {
for (var j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j) {
if (dist(strip[i], strip[j]) < min) {
min = dist(strip[i], strip[j]);
}
}
}
return min;
}
// A recursive function to find the
// smallest distance. The array P contains
// all points sorted according to x coordinate
function closestUtil(P, n) {
// If there are 2 or 3 points, then use brute force
if (n <= 3) {
return bruteForce(P, n);
}
// Find the middle point
var mid = Math.floor(n / 2);
var midPoint = P[mid];
// Consider the vertical line passing
// through the middle point calculate
// the smallest distance dl on left
// of middle point and dr on right side
var dl = closestUtil(P, mid);
var dr = closestUtil(P.slice(mid), n - mid);
// Find the smaller of two distances
var d = Math.min(dl, dr);
// Build an array strip[] that contains
// points close (closer than d)
// to the line passing through the middle point
var strip = [];
var j = 0;
for (var i = 0; i < n; i++) {
if (Math.abs(P[i].x - midPoint.x) < d) {
strip[j] = P[i];
j++;
}
}
// Find the closest points in strip.
// Return the minimum of d and closest
// distance is strip[]
return Math.min(d, stripClosest(strip, j, d));
}
// The main function that finds the smallest distance
// This method mainly uses closestUtil()
function closest(P, n) {
P.sort(compareX);
// Use recursive function closestUtil()
// to find the smallest distance
return closestUtil(P, n);
}
// Driver code
var P = [new Point(2, 3), new Point(12, 30), new Point(40, 50),
new Point(5, 1), new Point(12, 10), new Point(3, 4)];
var n = P.length;
console.log(`The smallest distance is ${closest(P, n)}`);
// This is code is contributed by Prasad Kandekar(prasad264)
Backtracking
Backtracking is a general algorithm for finding all (or some) solutions to computational problems, particularly constraint satisfaction problems. It incrementally builds candidates for solutions and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.
Here are the key components and steps involved in a backtracking algorithm:
Decision Space:
The problem is decomposed into a set of decisions to be made.
The decisions are usually represented in the form of choices at each stage.
Recursive Approach:
Backtracking typically uses a recursive approach to explore all possible choices.
At each decision point, the algorithm explores one choice and moves to the next decision point.
Base Case:
There is a base case that defines when a candidate solution is complete.
If the current path leads to a solution, the algorithm stops recursion and considers the current path as a valid solution.
Backtrack:
If, at any point, the algorithm determines that the current path cannot lead to a valid solution, it "backtracks" to the previous decision point.
It undoes the choice made at the current decision point and explores other choices.
Pruning:
Sometimes, certain paths in the decision space can be eliminated without further exploration.
Pruning involves skipping unnecessary branches, reducing the search space and improving efficiency.
Backtracking is commonly used to solve problems that can be broken down into a series of decisions, each with multiple choices. Examples include solving puzzles like N-Queens, Sudoku, generating permutations or combinations, and solving constraint satisfaction problems.
The N-Queens Problem:
The N-Queens problem is a classic problem that can be solved using backtracking. The decision space involves placing queens on a chessboard such that no two queens attack each other. The backtracking algorithm would try placing queens on the board one by one, backtracking whenever a placement violates the constraints, until a valid placement for all queens is found or all possibilities are explored. In essence, The goal is to place N queens on an NxN chessboard in such a way that no queen can attack any other queen.
// Function to solve the N-Queens problem
var solveNQueens = function (n) {
var res = []; // Array to store the solutions
if (n === 1 || n >= 4) dfs(res, [], n, 0); // Call the depth-first search (dfs) function if n is 1 or greater than or equal to 4
return res; // Return the array of solutions
};
// Depth-first search function
var dfs = function (res, points, n, index) {
for (var i = index; i < n; i++) {
if (points.length !== i) return; // Return if the length of points is not equal to i
for (var j = 0; j < n; j++) {
if (isValid(points, [i, j])) { // Check if placing a queen at [i, j] is valid
points.push([i, j]); // Place the queen
dfs(res, points, n, i + 1); // Recursively call dfs for the next row
if (points.length === n) res.push(buildRes(points)); // If all queens are placed, build and push the result
points.pop(); // Backtrack by removing the last queen placement
}
}
}
};
// Function to build the result format from the queen placements
var buildRes = function (points) {
var res = [];
var n = points.length;
for (var i = 0; i < n; i++) {
res[i] = "";
for (var j = 0; j < n; j++) {
res[i] += points[i][1] === j ? "Q" : "."; // Construct the row with "Q" at queen positions and "." elsewhere
}
}
return res; // Return the formatted result
};
// Function to check if placing a queen at newPoint is valid
var isValid = function (oldPoints, newPoint) {
var len = oldPoints.length;
for (var i = 0; i < len; i++) {
if (oldPoints[i][0] === newPoint[0] || oldPoints[i][1] === newPoint[1])
return false; // Check for conflicts in the same row or column
if (
Math.abs(
(oldPoints[i][0] - newPoint[0]) / (oldPoints[i][1] - newPoint[1])
) === 1
)
return false; // Check for conflicts diagonally
}
return true; // If no conflicts found, the placement is valid
};
Randomized Algorithm
Randomized QuickSort:
A variation of Quicksort algorithm where the pivot is chosen randomly.
// Function to generate a random integer within a given range [min, max] function randomInt(min, max) { return Math.floor(Math.random() * (max - min + 1)) + min; } // Function to swap elements at positions i and j in an array function swap(arr, i, j) { const temp = arr[i]; // Store the value at position i arr[i] = arr[j]; // Assign the value at position j to position i arr[j] = temp; // Assign the stored value to position j } // Function to perform the partition step in the quicksort algorithm function partition(arr, low, high) { const pivotIndex = randomInt(low, high); // Choose a random pivot index const pivotValue = arr[pivotIndex]; // Get the value of the pivot element swap(arr, pivotIndex, high); // Move the pivot element to the end let partitionIndex = low; // Initialize the partition index // Iterate through the array and rearrange elements based on the pivot for (let i = low; i < high; i++) { if (arr[i] < pivotValue) { swap(arr, i, partitionIndex); // Swap elements smaller than the pivot partitionIndex++; } } swap(arr, partitionIndex, high); // Move the pivot element to its final position return partitionIndex; // Return the index where the array is partitioned } // Function to implement the quicksort algorithm function quickSort(arr, low, high) { if (low < high) { const pivotIndex = partition(arr, low, high); // Get the partition index quickSort(arr, low, pivotIndex - 1); // Recursively sort the left subarray quickSort(arr, pivotIndex + 1, high); // Recursively sort the right subarray } } // Example usage: const arrayToSort = [9, 3, 7, 1, 5, 6, 8, 2, 4]; console.log("Original array:", arrayToSort); quickSort(arrayToSort, 0, arrayToSort.length - 1); console.log("Sorted array:", arrayToSort);
In this implementation, randomInt is a helper function that generates a random integer between min and max, inclusive. The swap function is used to swap elements in the array. The partition function picks a random pivot element, places it at the end of the array, and rearranges the array so that all elements less than the pivot are on the left side, and all elements greater than or equal to the pivot are on the right side.
The quickSort function recursively calls itself on the left and right subarrays until the entire array is sorted.
Summary
Greedy algorithms:
Greedy algorithms are used to solve optimization problems by making the locally optimal choice at each step with the hope of finding a global optimum.
It works by assigning shorter codes to more frequently occurring symbols.
Divide and Conquer:
Divide and Conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm breaks down a problem into sub-problems of the same or related type, until these become simple enough to be solved directly.
Merge sort is a sorting algorithm that uses the divide and conquer technique.
It works by dividing the input array into smaller subarrays, sorting them, and then merging them back together.
Backtracking:
Backtracking is a general algorithmic technique that considers systematically searching every possible combination and abandons a particular path as soon as it determines that it cannot be part of the solution.
The N-Queens problem is a classic problem that can be solved using backtracking.
The goal is to place N queens on an NxN chessboard in such a way that no queen can attack any other queen.
Conclusion
Data structures are the building blocks of efficient algorithms and problem-solving in computer science. While they might appear complex initially, with practice and the right guidance, you'll soon find yourself embracing their power and using it to create elegant and efficient solutions.
So, why wait? Start your data structure journey today and unlock the true potential of your coding skills. Remember, it's not just about mastering algorithms; it's about becoming a better problem solver and a skilled software engineer. Happy coding!
Acknowledgments
Sites used for visualizations:
Visualgo - Visualgo website
Heap Visualization by Ben Frederickson - Heap Visualization by Ben Frederickson
Pathfinding Visualizer by Clement Mihailescu - Pathfinding Visualizer by Clement Mihailescu
CSVISTool - CSVISTool website
Algorithms Visualization by cs.usfca.edu - Algorithms Visualization by cs.usfca.edu
A (A-Star) Pathfinding Algorithm Visualization on a Real Map* - A* (A-Star) Pathfinding Algorithm Visualization on a Real Map by ones and zeros
