On the other hand
Once upon a time, in a futuristic city known as Cybertopia, there lived a brilliant scientist named Dr. Ethan. Dr. Ethan was renowned for his groundbreaking work in the field of computer algorithms. His ability to design and analyze algorithms propelled him to the forefront of technological advancement.
One day, Dr. Ethan embarked on an ambitious project to develop a revolutionary algorithmic technology that would push the boundaries of human capabilities. He called it the Ouroboros Algorithm, inspired by the ancient symbol of a serpent eating its own tail, representing infinity and continuous renewal.
The Ouroboros Algorithm was unlike anything the world had ever seen. It possessed the power of recursion, allowing it to break down complex problems into smaller, more manageable subproblems. This recursion would enable the algorithm to analyze and solve challenges beyond the limitations of human cognition .
As Dr. Ethan refined and tested the Ouroboros Algorithm, he discovered its remarkable ability to employ a technique known as divide and conquer. Just like a master strategist, the algorithm would divide complex tasks into smaller, more manageable parts, conquer each part separately, and then combine the solutions to produce an optimal outcome.
However, Dr. Ethan realized that for the Ouroboros Algorithm to reach its full potential, it needed balance. Drawing inspiration from the ancient philosophy of yin and yang, Dr. Ethan introduced the concept of balancing algorithms. He designed the algorithm to dynamically adapt to changing input, ensuring that it would always maintain equilibrium and efficiency in its computations.
With each iteration of the algorithm’s development, Dr. Ethan pushed the boundaries of what was possible in the realm of computer algorithms. He was determined to create an algorithmic masterpiece that could solve the most complex of problems.
Finally, after years of dedication and relentless pursuit of perfection, the Ouroboros Algorithm was complete. Dr. Ethan presented it to the world, and the impact was immediate and profound.
The Ouroboros Algorithm revolutionized industries and transformed society. Its recursive nature and ability to divide and conquer allowed it to solve previously unsolvable puzzles, accelerating scientific breakthroughs, and pushing the limits of human knowledge. The algorithm’s balancing capability ensured that it could adapt to any circumstance , making it an invaluable tool across various fields.
In the years that followed, the Ouroboros Algorithm became the backbone of Cybertopia’s technological advancements. From medical diagnosis to prediction of natural disasters, from optimizing transportation routes to creating personalized education plans, Ouroboros Algorithm became the go-to solution for complex problems.
As Dr. Ethan looked upon the sea of possibilities that the algorithm had unlocked, he couldn’t help but feel a sense of awe and wonder. The merging of science and imagination had given birth to a technological marvel that surpassed all expectations.
And so, the story of Dr. Ethan and the Ouroboros Algorithm would be etched into the annals of history, forever reminding humanity of the power of algorithmic design and analysis. It was a testament to human ingenuity and the endless possibilities that lie ahead in the realm of technology.
Abstract
In algorithm design, we often need to consider how to use the optimal method to solve problems and achieve high efficiency and scalability in practical applications. It may also be an iterative way to optimize the algorithm and continuously approximate the results.
Recursion
Recursion is an algorithmic technique that solves problems through repeated application of itself. In a recursive algorithm, the problem is broken down into smaller sub-problems and these sub-problems are solved by repeatedly calling itself. Recursive algorithms usually include a base case (i.e. the end-of-recursion condition) to avoid infinite recursion. Recursion is widely used in many algorithms, such as calculating Fibonacci numbers, traversing binary trees, etc.
Examples of Fibonacci Sequence
public class Fibonacci {<!-- -->
public static int fibonacci(int n) {<!-- -->
if (n <= 1) {<!-- -->
return n;
} else {<!-- -->
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
public static void main(String[] args) {<!-- -->
int n = 6;
System.out.println("The " + n + "th number of the Fibonacci sequence is: " + fibonacci(n));
}
}
In the above code, the fibonacci method accepts an integer n as a parameter, and if n is less than or equal to 1, it returns n directly. Otherwise, it recursively calls the fibonacci method to calculate the nth Fibonacci number, which is the sum of the previous two Fibonacci numbers, and returns the result.
When we call fibonacci(6), the program recursively evaluates fibonacci(5) and fibonacci(4), then recursively evaluates fibonacci(4) and fibonacci(3), and so on until the end of recursion condition is reached. Finally, we get the sixth number in the Fibonacci sequence, which is 8.
Recursive algorithms can simplify problem descriptions and solution ideas, making the code more concise and readable. However, recursive algorithms also have some potential problems. For example, too deep a recursion level may lead to stack overflow and repeated calculations. Therefore, when designing a recursive algorithm, we need to set the recursion end conditions reasonably and ensure that the time complexity and space complexity of the algorithm are controllable.
Divide and Conquer
Divide and conquer is an algorithmic technique that divides a problem into smaller sub-problems and solves the original problem by solving these sub-problems. In the divide-and-conquer approach, the problem is divided into multiple sub-problems that are relatively small in size but have similar structures. After the subproblems are solved independently, their solutions are combined into the solution of the original problem. Divide-and-conquer methods typically use recursion to solve sub-problems and a merge strategy to integrate the solutions to the sub-problems into a solution to the original problem. Common divide-and-conquer algorithms include merge sort and quick sort.
Merge sort example
public class MergeSort {<!-- -->
public void mergeSort(int[] arr, int left, int right) {<!-- -->
if (left < right) {<!-- -->
int mid = (left + right) / 2;
mergeSort(arr, left, mid); // Sort the left half recursively
mergeSort(arr, mid + 1, right); // Sort the right half recursively
merge(arr, left, mid, right); // Merge the left and right ordered subarrays
}
}
public void merge(int[] arr, int left, int mid, int right) {<!-- -->
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; + + i) {<!-- -->
L[i] = arr[left + i];
}
for (int j = 0; j < n2; + + j) {<!-- -->
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 & amp; & amp; j < n2) {<!-- -->
if (L[i] <= R[j]) {<!-- -->
arr[k] = L[i];
i + + ;
} else {<!-- -->
arr[k] = R[j];
j + + ;
}
k++;
}
while (i < n1) {<!-- -->
arr[k] = L[i];
i + + ;
k++;
}
while (j < n2) {<!-- -->
arr[k] = R[j];
j + + ;
k++;
}
}
public static void main(String[] args) {<!-- -->
int[] arr = {<!-- --> 12, 11, 13, 5, 6, 7 };
int n = arr.length;
MergeSort mergeSort = new MergeSort();
mergeSort.mergeSort(arr, 0, n - 1);
System.out.println("Sorted array:");
for (int i = 0; i < n; + + i) {<!-- -->
System.out.print(arr[i] + " ");
}
}
}
The above code implements the merge sort algorithm. The specific steps are as follows:
- In the
mergeSortmethod, first determine whether the incoming array range is valid. Ifleftis smaller thanright, perform the following operations: - Divide the array into left and right halves and recursively call the
mergeSortmethod to sort the left half; - Recursively call the
mergeSortmethod to sort the right half; - Finally, call the
mergemethod to merge the left and right sorted subarrays into one sorted array. - In the
mergemethod, first calculate the sizes of the left and right subarrays, and create auxiliary arraysLandRto store the elements of the subarrays. - Then, the elements of the left subarray are copied into the
Larray, and the elements of the right subarray are copied into theRarray. - Set three pointers
i,jandkto point toLandRand the beginning of the original arrayarr. - In the loop, compare the values of
L[i]andR[j]and put the smaller value into the original arrayarr[k]and move the corresponding pointer. - If all the elements of one subarray have been put into the original array, then the remaining elements of the other subarray are put into the original array in sequence.
Balance
Balance: In some algorithms, balance is a key design principle. Balance can refer to the balance of a data structure (such as balancing a binary tree), or it can refer to the load balancing of an algorithm (such as task distribution). A balanced design can improve algorithm performance and scalability. For example, a balanced binary search tree can guarantee a worst-case search time complexity of O(log n), while an unbalanced binary search tree may result in linear time complexity.
AVL tree example
import java.util.*;
public class AVLTree {<!-- -->
private Node root;
private class Node {<!-- -->
int key, height;
Node left, right;
Node(int key) {<!-- -->
this.key = key;
this.height = 1;
}
}
private int height(Node node) {<!-- -->
if (node == null)
return 0;
return node.height;
}
private int balanceFactor(Node node) {<!-- -->
if (node == null)
return 0;
return height(node.left) - height(node.right);
}
private Node leftRotate(Node node) {<!-- -->
Node newRoot = node.right;
node.right = newRoot.left;
newRoot.left = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
private Node rightRotate(Node node) {<!-- -->
Node newRoot = node.left;
node.left = newRoot.right;
newRoot.right = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
private void updateHeight(Node node) {<!-- -->
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
public void insert(int key) {<!-- -->
this.root = insertNode(root, key);
}
private Node insertNode(Node node, int key) {<!-- -->
if (node == null)
return new Node(key);
if (key < node.key) {<!-- -->
node.left = insertNode(node.left, key);
} else if (key > node.key) {<!-- -->
node.right = insertNode(node.right, key);
} else {<!-- -->
// Duplicate keys not allowed in AVL tree
return node;
}
updateHeight(node);
int balance = balanceFactor(node);
if (balance > 1) {<!-- -->
if (key < node.left.key) {<!-- -->
return rightRotate(node);
} else if (key > node.left.key) {<!-- -->
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
if (balance < -1) {<!-- -->
if (key > node.right.key) {<!-- -->
return leftRotate(node);
} else if (key < node.right.key) {<!-- -->
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
public boolean search(int key) {<!-- -->
return searchNode(root, key);
}
private boolean searchNode(Node node, int key) {<!-- -->
if (node == null)
return false;
if (key == node.key)
return true;
if (key < node.key) {<!-- -->
return searchNode(node.left, key);
} else {<!-- -->
return searchNode(node.right, key);
}
}
public static void main(String[] args) {<!-- -->
AVLTree tree = new AVLTree();
//Insert nodes
tree.insert(6);
tree.insert(3);
tree.insert(9);
tree.insert(2);
tree.insert(5);
// Search for a key
System.out.println(tree.search(3)); // prints true
System.out.println(tree.search(7)); // prints false
}
}
The AVLTree class implements the insertion and search operations of AVL trees. During the insertion operation, the balance factor is used to determine whether a left or right rotation is required to maintain the balance of the tree. The search operation finds the target value by recursively comparing the keys of the nodes.
Through the self-balancing property of the AVL tree, it is able to maintain a search time complexity of O(log n) in the average case and a time complexity of O(log n) even in the worst case. This makes the AVL tree an efficient data structure for storing and searching large amounts of data.
Dynamic programming
Dynamic Programming: Dynamic programming is an algorithmic technique used for optimization problem solving. It solves the optimal solution step by step by dividing the problem into overlapping sub-problems with optimal substructures. Dynamic programming usually uses a table to store intermediate results to avoid double calculations. By using dynamic programming, some problems with overlapping subproblems can be effectively solved, such as the longest common subsequence, knapsack problem, etc.
public class Knapsack {<!-- -->
public static int knapSack(int capacity, int[] weights, int[] values, int n) {<!-- -->
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 0; i <= n; i + + ) {<!-- -->
for (int j = 0; j <= capacity; j + + ) {<!-- -->
if (i == 0 || j == 0) {<!-- -->
dp[i][j] = 0;
} else if (weights[i - 1] <= j) {<!-- -->
dp[i][j] = Math.max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
} else {<!-- -->
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {<!-- -->
int capacity = 7;
int[] weights = {<!-- -->1, 3, 4, 5};
int[] values = {<!-- -->1, 4, 5, 7};
int n = weights.length;
int maxVal = knapSack(capacity, weights, values, n);
System.out.println("Maximum value that can be obtained is: " + maxVal);
}
}
The knapSack method uses a two-dimensional array dp to store the optimal solution to the sub-problem. The outer loop i represents the number of items considered, and the inner loop j represents the current backpack capacity. According to the optimal solution of the sub-problem, we can make a choice: if the weight of the current item is less than or equal to the backpack capacity, you can choose to put it into the backpack, so the optimal solution can be by choosing the optimal value of the current item and the remaining capacity Solved. If the weight of the current item exceeds the backpack capacity, then we do not choose to put it into the backpack, and the optimal solution is equal to the optimal solution of the previous sub-problem.
Ultimately, dp[n][capacity] represents the maximum value that can be obtained considering n items and a given backpack capacity.
Topological sorting
Topological sorting is a sorting algorithm for directed acyclic graph (DAG), which sorts the nodes in the graph according to their sequential relationship. In topological sorting, if there is an edge from node A to node B, then node A must be sorted before node B. Topological sorting can be applied to tasks scheduling, dependency analysis and other fields.
Examples
import java.util.*;
public class TopologicalSort {<!-- -->
public static List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {<!-- -->
List<Integer> order = new ArrayList<>();
// 1. Build adjacency list
List<List<Integer>> adjacencyList = new ArrayList<>();
for (int i = 0; i < numCourses; i + + ) {<!-- -->
adjacencyList.add(new ArrayList<>());
}
for (int[] prerequisite : prerequisites) {<!-- -->
int course = prerequisite[0];
int prerequisiteCourse = prerequisite[1];
adjacencyList.get(prerequisiteCourse).add(course);
}
// 2. Calculate the in-degree of each node
int[] inDegree = new int[numCourses];
for (List<Integer> prerequisitesList : adjacencyList) {<!-- -->
for (int course : prerequisitesList) {<!-- -->
inDegree[course] + + ;
}
}
// 3. Add nodes with indegree 0 to the sorting results
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i + + ) {<!-- -->
if (inDegree[i] == 0) {<!-- -->
queue.offer(i);
}
}
// 4. Remove nodes with indegree 0 and their associated edges in order of topological sorting.
while (!queue.isEmpty()) {<!-- -->
int course = queue.poll();
order.add(course);
for (int prerequisiteCourse : adjacencyList.get(course)) {<!-- -->
inDegree[prerequisiteCourse]--;
if (inDegree[prerequisiteCourse] == 0) {<!-- -->
queue.offer(prerequisiteCourse);
}
}
}
// 5. Determine whether there is a cycle
if (order.size() != numCourses) {<!-- -->
return new ArrayList<>();
}
return order;
}
public static void main(String[] args) {<!-- -->
int numCourses = 4;
int[][] prerequisites = {<!-- -->{<!-- -->1, 0}, {<!-- -->2, 0}, {<!-- -->3 , 1}, {<!-- -->3, 2}};
List<Integer> order = topologicalSort(numCourses, prerequisites);
System.out.println("Topological sorting results:");
for (int course : order) {<!-- -->
System.out.print(course + " ");
}
}
}
We first build an adjacency list to represent the directed graph, and then use an array to record the in-degree of each node. We enqueue the nodes with indegree 0 and process the nodes in the queue sequentially. For each node, we reduce the in-degree of its associated node by 1, and if it is reduced to 0, we enqueue it. Finally, we determine whether the number of nodes in the sorting result is equal to the total number of nodes to determine whether a cycle exists.
Stabilizing marriage issues
The stable marriage problem refers to how to find a stable set of marriage pairs in a marriage market, given each person’s preference list for everyone else, in which no two people would be willing to leave their spouses and form a pair with someone else. This problem was raised by American economists Goldberg and Ricken (Gale and Shapley) in 1962, and has been widely studied and applied.
The classic algorithm for solving the stable marriage problem is the Gale-Shapley algorithm, also known as the Deferred Acceptance Algorithm. The idea of this algorithm is to continuously perform pairing and crossover selection until the final pairing of everyone is found.
Examples
import java.util.*;
class StableMarriage {<!-- -->
public static void main(String[] args) {<!-- -->
int[][] menPreferences = {<!-- --> {<!-- -->1, 0, 3, 2},
{<!-- -->1, 2, 3, 0},
{<!-- -->2, 0, 3, 1},
{<!-- -->0, 1, 2, 3} };
int[][] womenPreferences = {<!-- --> {<!-- -->0, 1, 2, 3},
{<!-- -->1, 0, 2, 3},
{<!-- -->2, 1, 3, 0},
{<!-- -->3, 2, 1, 0} };
int n = menPreferences.length;
int[] womenPartners = new int[n];
boolean[] menEngaged = new boolean[n];
stableMarriage(menPreferences, womenPreferences, womenPartners, menEngaged, n);
System.out.println("Stable marriages:");
for (int i = 0; i < n; i + + ) {<!-- -->
System.out.println("Man " + i + " is engaged to Woman " + womenPartners[i]);
}
}
static void stableMarriage(int[][] menPreferences, int[][] womenPreferences, int[] womenPartners,
boolean[] menEngaged, int n) {<!-- -->
int freeMen = n;
while (freeMen > 0) {<!-- -->
int man;
for (man = 0; man < n; man + + ) {<!-- -->
if (!menEngaged[man]) {<!-- -->
break;
}
}
for (int i = 0; i < n & amp; & amp; !menEngaged[man]; i + + ) {<!-- -->
int woman = menPreferences[man][i];
if (womenPartners[woman - n] == -1) {<!-- -->
womenPartners[woman - n] = man;
menEngaged[man] = true;
freeMen--;
} else {<!-- -->
int currentPartner = womenPartners[woman - n];
if (isPreferable(womenPreferences, woman, man, currentPartner)) {<!-- -->
womenPartners[woman - n] = man;
menEngaged[man] = true;
menEngaged[currentPartner] = false;
}
}
}
}
}
static boolean isPreferable(int[][] womenPreferences, int woman, int man, int currentPartner) {<!-- -->
int n = womenPreferences.length;
for (int i = 0; i < n; i + + ) {<!-- -->
if (womenPreferences[woman][i] == man) {<!-- -->
return true;
}
if (womenPreferences[woman][i] == currentPartner) {<!-- -->
return false;
}
}
return false;
}
}
We created a StableMarriage class and defined the male and female preference lists in the main method. The stableMarriage method finds stable marriage pairs by implementing the Gale-Shapley algorithm. According to the algorithm, we select one of the men who does not have a mate and then try to match the women one by one until a match is found. If the woman already has a spouse, the preference list is used to decide whether to change her current spouse. Finally, we output the results for stable marriage pairs.
Can the problem algorithm generalize well?
Marriage stability issues often involve two groups of people, such as men and women, or employers and job seekers. Everyone ranks everyone else based on their own preferences, and different people may have different rankings of preferences. The goal of the stable marriage problem is to find a set of pairs such that no two people can leave their spouses and form a pair with someone else, that is, no better match exists.
To solve this problem, Gale and Shapley proposed an algorithm called the deferred acceptance algorithm. This algorithm finds stable marriage pairs in an iterative manner. Specific steps are as follows:
- Each man first chooses the person he likes best, and offers himself to the other as a candidate;
- Each person chooses the most satisfactory one among the current candidates and deletes the others from the pool of candidates;
- If a man is chosen from more than one candidate, he chooses the one he likes best and eliminates the others from the pool of candidates;
- Repeat steps 2 and 3 until no one is selected by more than one candidate.
The marriage stability algorithm ensures that the final pairing is stable. That is, no two people can leave their spouse and form a pair with someone else. This is because at every step of the algorithm, everyone chooses the one they are most comfortable with, and at least one candidate chooses them.
Hanoi Tower
The Tower of Hanoi is a classic recursive problem that involves moving a set of dishes from one tower base to another. Specifically, we have three towers, labeled A, B, and C. Initially, all the dishes are placed on tower A, stacked in order from largest to smallest. And our goal is to move these dishes to tower C, by using tower B.
java example
public class HanoiTower {<!-- -->
public static void main(String[] args) {<!-- -->
int numOfDisks = 3;
solveHanoiTower(numOfDisks, 'A', 'B', 'C');
}
public static void solveHanoiTower(int n, char source, char auxiliary, char target) {<!-- -->
if (n == 1) {<!-- -->
System.out.println("Move disk 1 from " + source + " to " + target);
return;
}
solveHanoiTower(n - 1, source, target, auxiliary);
System.out.println("Move disk " + n + " from " + source + " to " + target);
solveHanoiTower(n - 1, auxiliary, source, target);
}
}
In the above code, the solveHanoiTower method receives four parameters: n represents the number of dishes to be moved, source represents the starting tower, auxiliary represents the auxiliary tower, and target represents the target tower. When there is only one disc, just move it directly from the starting tower to the target tower. For multiple discs, first move the first n-1 discs from the starting tower to the auxiliary tower, then move the largest disc from the starting tower to the target tower, and finally move the n-1 discs on the auxiliary tower. -1 dish is moved to the target tower, achieved through recursive calls.