## shortest path algorithm – why backtrack from the end node instead of starting from the starting node?

I was watching a dynamic programming video by Erik Demaine . He says here https://youtu.be/OQ5jsbhAv_M?t=2133 , finding the shortest path by guessing the node after the starting node is not the right approach, and instead should guess the node before the last node. I didn’t understand his explanation. Can someone explain better why find the path backwards? It seems to me that you should get the same answer either way and both approaches are equally good.

Posted on Categories proxies

## algorithm to find shortest path connecting EVERY node

I have received a problem to solve and I am not sure what algorithm to use.

TLDR; Find the shortest path to get to every node in a undirected graph The problem states that one must visit every station in the shanghai metro in the shortest path possible. Interchange Stations (‘edges’) can be reused and you can start / stop anywhere.

I have created a lookup table that shows connected stations as well as the distance to travel (not shown)

"Xinzhuang": [   "Waihuan Rd." : 1 ], "Waihuan Rd.": [   "Xinzhuang": 2.2,   "Lianhua Rd.": 3 ], "Lianhua Rd.": [   "Waihuan Rd.": 4,   "Jinjiang Park": 5, ], "Jinjiang Park": [   "Lianhua Rd.": 9.1,   "South Railway Station": 10.3 ], "South Railway Station": [   "Jinjiang Park": 4.1,   "Caobao Rd.": 1.1,   "Shilong Rd.": 2.5 ], ... 

I found this leetcode problem but it did not mention any specific algorithm and since it was O(2^N * N) I wondered if there was a faster method than BFS.

https://leetcode.com/problems/shortest-path-visiting-all-nodes/solution/

Since my graph is so big, I was going to reduce the lines with a single path to a single node.

What algorithm can I use that will work in Polynomial time, OR has the least time complexity?

Posted on Categories proxies

## Number of graphs that satisfies the property that edge weight is maximum of node values on which the edge is incident

I have an undirected weighted graph without multi edges. All the edge weights are whole numbers and known. I want to know in how many ways node values(node values are also whole numbers) can be assigned to the nodes such that the graph satisfies the condition that for every edge its edge weight is exactly equal to maximum of two node values this edge is incident on.

Posted on Categories proxies

## Building Suffix Array from Suffix Tree. Inorder visit when node has more than two children

From the notes:

It is not difficult to observe that the suffix array $$\texttt{SA}$$ of the text $$\texttt{T}$$ can be obtained from its suffix tree $$\texttt{ST}$$ by performing an in-order visit: each time a leaf is encountered, the suffix-index stored in this leaf is written into the suffix array $$\texttt{SA}$$; each time an internal node u is encountered, its associated value is written into the array $$\texttt{lcp}$$.

How do you do the inorder visit when a node has more than two children?

Let’s say you visit the leftmost child, then the node, then the other leftmost child. Then do you visit again the node?

SA in an array of pointer to suffixes, ordered lexicographically.

lcp contains the longest common prefix between two consecutive suffixes $$\text{suff}_{SA[i]} \text{ and } \text{suff}_{SA[i+1]}$$.

The $represents a char that’s smaller than every other char. The value associated to each node is the length of the prefix spelled so far. The leaves represents indices of suffixes. If T = banana$ , the leaf 3 represents nana$(T[3,7]) In the image there’s what is supposed to be a suffix tree, but I think there’s an error since the edges should be sorted according to their label and the leaf 7 with the edge labeled "$ " should be the leftmost leaf and edge. When simulating the algorithm, first you visit the node 7 ( using the fixed version of the tree ), then the root, so you have

SA = [7, ...] lcp = [0, ...] 

Then let’s say you keep going on with an inorder visit of u. When you go back to the root, do you insert the value 0 again in the lcp? Or do you do it just the first time you visited the root?

In other words, do I visit child-root-child-root… or child-root-child-child…

Posted on Categories proxies

## What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?

The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of nodes in the tree?

Posted on Categories proxies

## how to send prime and generator of diffie hell-men to client over network node js?

I am using crypto module of node js for exchanging key using diffie-hellman algorithm.

server.js

const crypto = require("crypto");  const alice = crypto.createDiffieHellman(512);  const aliceKey = alice.generateKeys(); 

client.js

const bob = crypto.createDiffieHellman(alice.getPrime(), alice.getGenerator());  const bobKey = bob.generateKeys();  const aliceSecret = alice.computeSecret(bobKey);  const bobSecret = bob.computeSecret(aliceKey); 

The above example is taken from node.js documentation as shown the client uses servers prime number for generating the prime number.

my question is how should I securely send the prime number and the other parameter to client over internet? are there any other alternatives?

and another question is that I am generating keys using generate keys function but I have already generated private-key.pem and public-cert.pem file. can I use those if yes then how?, if no then what is difference between those keys?

Posted on Categories proxies

## How to install node modules for external evaluation?

I was hoping for some extra clarity configuring additional modules for use in external evaluation, since there’s no mention of this in the the nodejs workflow.

It seems mathematica looks only at ~/.node_modules, so is it sufficient to simply generate a soft link?

cd ~; ln -s node_modules .node_modules 

In decreasing importance, here are some specific sub-questions:

1. I prefer using yarn to manage required installations, do I have to use npm?
2. Do npm installs need to be global or user?
3. Does the fe or kernel need to be restarted; or evaluators re-registered after install or removal?

Knowing that any specific functionalities or modules will definitely not work (e.g. no browser …) would help, and any pro-tips from Javascript developers would be appreciated. For example, would it be possible to add a 'package.json' file for a notebook and isolate dependencies? I really don’t want these mma configuration steps to interfere with my existing node-js work.

Posted on Categories cheapest proxies

## Insert a node in a binary search tree

The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $$z.p = y$$ instruction does. wouldn’t the algorithm work without it?

abr_insert(T, z) //z is the node that must be inserted     {             y = NULL;             x = T.root;             while(x != NULL)             {                     y  = x;                     if(z.key < x.key)                             x = x.left;                     else                             x = x.right;             }             z.p = y; //here is the instruction that I don't understand             if(y = NULL)                 T.root = z;             else if(z.key < y,key)                     y.left = z;             else                     y.right = z;     } 

## How do we find the predecessor and the successor of a node in a B-Tree?

How can we find the predecessor and the successor of a node in a B-Tree? I mention that the search, delete and insert function are like in the article on geeksforgeeks. How can we use the getPred and getSucc functions from this article : https://www.geeksforgeeks.org/delete-operation-in-b-tree/ ? BTree t(3); // we create a B tree that has degree 3 t.Insert(6); t.Insert(5); t.Insert(4); t.Insert(3); t.Insert(2); t.Insert(1); t.Insert(0); t.Insert(-1); t.Insert(-2); Let`s say we insert these keys into the B-Tree. I tried like that : treeNode* x = t.Search(3); // find the node that contains the key 3 // x->findKey(3) returns the position in the node where the key 3 appears cout << x->getPredecessor(x->findKey(3)); // that doesn’t work – How can I solve this problem? Thank you very much!

Posted on Categories proxies

## Observation regarding finding predecessor(or successor) of a node in a Binary Search Tree(BST)

I have some propositions regarding BSTs , please can someone confirm whether they are true or false:

Situation :

1.Suppose we have a node $$n_1$$ with a value $$val_1$$ i.e $$n_1(val_1)$$

2.We wish to find the predecessor node of $$n_1$$ , with respect to inline traversal (That is the node $$n_2(val_2)$$ with $$val_2$$ being the greatest number $$val_2 < val_1$$)

3.Assume for simplicity that the BST dosen’t have any repetition

Proposition 1: Let $$n_1$$ have two children .Then $$n_2$$ has atmost one child i.e the number of children of $$n_2$$ can’t be two

Proposition 2: Let $$n_1$$ have only one child and $$n_1$$ is not root ,then also $$n_2$$ has atmost one child.

Please ascertain whether these propositions are true , but if false can someone provide a counter example ?

Posted on Categories proxies