Alien Dictionary: 

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you. 

You are given a list of strings words from the alien language's dictionary, where the strings in words are  

sorted lexicographically 

 by the rules of this new language. 

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them. 

  

Example 1: 

Input: words = ["wrt","wrf","er","ett","rftt"] 

Output: "wertf" 

Example 2: 

Input: words = ["z","x"] 

Output: "zx" 

Example 3: 

Input: words = ["z","x","z"] 

Output: "" 

Explanation: The order is invalid, so return "". 

  

Constraints: 

• 1 <= words.length <= 100 

• 1 <= words[i].length <= 100 

• words[i] consists of only lowercase English letters. 

 

class Solution { 

    public String alienOrder(String[] words) { 

        StringBuilder sb = new StringBuilder(); 

        if (words == null || words.length == 0) { return sb.toString(); } 

 

        Character after = null; 

        for (int i = 0; i < words.length; i++) { 

            for (int j = 0; j < words[i].length(); j++) { 

                if ( i > 0 ) { 

                    int match = 0; 

                    while (match < words[i-1].length() &&  

                            match < words[i].length() &&  

                            words[i-1].charAt(match) == words[i].charAt(match)) 

                    { 

                        after = words[i-1].charAt(match); 

                        match++; 

                    } 

                    if (match != 0 && match < words[i-1].length()) { 

                        after = words[i-1].charAt(match); 

                    } 

                    if (match == 0){ 

                        after = words[i-1].charAt(match); 

                    } 

                    int afterIndex = after != null ? sb.indexOf(String.valueOf(after)) : -1; 

                    int index = sb.indexOf(String.valueOf(words[i].charAt(match))); 

                    if (index != -1 && afterIndex != -1 && index < afterIndex) { 

                        return ""; 

                    } 

                } 

 

                int afterIndex = after != null ? sb.indexOf(String.valueOf(after)) : -1; 

                int index = sb.indexOf(String.valueOf(words[i].charAt(j))); 

                if (index == -1) { 

                    System.out.println(sb.toString()); 

                    sb.insert(afterIndex+1, String.valueOf(words[i].charAt(j))); 

                } 

 

                after = words[i].charAt(j); 

            } 

        } 

 

        return sb.toString(); 

    } 

} 

 

 As a collective graph of drones based on distances as edges, there will be optimization problems for the tighter formation while maintaining minimum inter-drone distance. This can be done with the help of a cost function that helps to minimize the error between the current and the optimal position which is not a predesignated one but an iterative transition state that is determined by a steepest gradient descent. This method is illustrated as follows: 

#! /usr/bin/python 
''' 
Steepest gradient descent method: 
f(x) = 1/2 x-transpose A x - b-transpose x + c 
f'(x) = A x - b 
A = [ 3 2 ] b = [ 2 ] c = 0 
      [ 2 6 ]       [ -8 ] 
''' 
def steepest_gradient_descent(A, b, c, x, maxIteration, epsilon): 
i = 0 
residual = b - Ax # residual is what keeps it from being 0 
delta = scalar(transpose(residual, 2, 1), residual) # scalar is dot-product 
delta-0 = delta # initial delta 
while ((i < maxIteration) && (delta > (epsilon^2)*delta-0)): # epsilon is tolerance threshold 
    q = scalar (A, residual) 
    alpha = delta / scalar(transpose(residual, 2, 1), q) 
    x = x + scalar(alpha, residual) 
    if i % 50 == 0: # 50 is arbitrary, sqrt(n) for large n 
        residual = b - scalar(A, x) # recalculate residual to remove 
    else: # accumulated floating point error 
        residual = residual - scalar(alpha, q) 
    delta = scalar(transpose(residual, 2, 1), residual) 
    i = i + 1 
``` 
x = [ 2 ] 
      [ -2 ] 
``` 
def transpose(m, r, c): 
     r = [[0 for i in range(c)] for j in range(r)] 
     for i in range(c): 
         for j in range(r): 
              r [i][j] = m [j][i] 
     return r 

 Communication graph for UAV swarm

The graphs for task assignments and the graphs for communication with the drones in the UAV swarm are different and serve different purposes. The mesh network for communication is designed to provide an efficient and reliable network for UAVs. The minimum spanning tree (MST) ensures that all drones are connected with minimal total distance, optimizing the overall efficiency of the network. The distances are Euclidean in a three dimensional co-ordinate system between pairs of drones in a graph of drone distances. The MST is a foundational structure optimizing the costs and improving the efficiency of communication. With a frequent iteration of updating positions of each drone, recalculating inter-drone distances between pairs, and constructing the MST, the UAV swarm can respond faster and better to meet critical operational requirements such as collision avoidance.

To construct the MST, we use Prim’s MST

This is a greedy algorithm that maintains a set A of edges which grows until it covers the graph. While most generic MST do that, in the case of Prim, the set A is a tree.

MST-Prim

// this grows a tree

A = null

for each vertex v in G, initialize the key and the parent

Initialize a min-priority queue Q with vertices

while the Queue is not empty

       extract the vertex with the minimum edge distance connecting it to the tree

       for each adjacencies v of this vertex u

              set the key to the weight(u,v) and parent

Reference: previous article: https://1drv.ms/w/c/d609fb70e39b65c8/EdbLDbqLUR5NtKTXdv1w67EBaI6PS9lHF255VJaaICDSxw?e=Ij6GOH