# algorithms's questions - English 1answer

6.184 algorithms questions.

### How to determine seed collision probability in a PRNG?

I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds ...

I am looking for some suggestions on what algorithm to be used for the below task assignment problem. There are multiple projects. Each project has multiple tasks for each week. Duration of each task ...

### 2 Prove complexity bound without reduction?

The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the ...

### -1 An 'increasing Edge' in a network flow

We are given a network flow, as well as a max flow in the network. An edge would be called $increasing \space edge$ if increasing its capacity in an arbitrary positive number, would also increase the ...

### 1 Undirected graph find minimal wight sum so every cycle has at least one weighted edge included

1 answers, 53 views algorithms graphs
I am given weighted undirected and non-planar graph G=(V,E). I don't understand much about complex graph and how to work with them. So any tips will help. For example like this I don't know how to ...

### 1 Time interval correction for step detection algorithm

I am currently going over this paper, and in fact have already tried to implement it: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4634483/ [1] Paper looks at the amplitude of the step and the time ...

### 2 Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on a ...

### 1 Shortest path tree from each vertex implies a unique MST?

Given a connected, undirected graph G, edge-weighted (positive), prove that If G has a spanning tree T which, for each vertex r in G, is a shortest path tree from r, then G has a unique MST. I know ...

### Merge Leaf labeled trees

I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to ...

### How to restore a broken minimal spanning tree?

We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be ...

### 4 Dynamic programming: speed of top down vs bottom up approaches

1 answers, 778 views algorithms dynamic-programming
I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. ...

### 3 Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...

### 1 Calculate the minimum absolute difference between the maximum and minimum number from the triplet of 3 arrays

1 answers, 35 views algorithms arrays
Question is: Calculate the minimum absolute difference between the maximum and minimum number from the triplet a, b, c such that a, b, c belongs arrays A, B, C respectively. There is another ...

### 5 Can any constant-time operation be applied N times in O(log(N)) time?

2 answers, 551 views algorithms complexity-theory
Suppose f is a constant-time function. Is it always possible to apply it n times in O(log(n))...

### 32 The math behind converting from any base to any base without going through base 10?

6 answers, 38.430 views algorithms arithmetic number-formats
I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still ...

### 9 How to solve an arrangement problem at the Archive Nationale of France using graph theory?

3 answers, 864 views algorithms graphs optimization packing
Good evening! I'm actually doing an internship at the Archives Nationales of France and I encountered a situation I wanted to solve using graphs... I. The dusty situation We want to optimize the ...

### Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

1 answers, 34 views algorithms data-structures counting

### Fibonacci Heap / Binomial Heap - Decrease Key

1 answers, 200 views algorithms data-structures heaps
I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out. Decrease Key is a function that almost all min heaps have (vice versa with ...

### -3 knapsack problem

i have a question for the knapsack problem that i am totally not able to comprehend properly. I know how to knapsack works with the 0-1 approach and fractional. kindly can i be helped with this ...

### 1 Dijkstra Partitioning Algorithm : Special Case

I have been exploring Dikstra partitioning Algorithm. Below are my given:R = Red W = White B = BlueI have this unpartitioned array. ...

### 1 Online set filling with redistributions

Edited: Suppose we have 4 sets $A, B, C, D$ which can can hold a maximum of two elements, each. Now, elements ($E_i$) arrive serially with properties such as: ...

### 89 BIT: What is the intuition behind a binary indexed tree and how was it thought about?

2 answers, 24.928 views algorithms binary-trees trees
A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...

### 6 Correctness of Strongly Connected Components algorithm for a directed graph

2 answers, 2.421 views algorithms graphs graph-traversal
I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$....

### 8 Maximum subset pairwise not divisible by $K$

3 answers, 4.473 views algorithms efficiency
I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$. I tried to solve this problem, but I have found the ...

### 1 Proof of correctness of reversal algorithm for array rotation?

1 answers, 31 views algorithms arrays
We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for d = 2, the resultant rotated array is {3, 4, 5, 6, 7, 1, 2}. ...

### 1 Printing all paths of a tree and sorting the weight of edges

Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time. To solve this ...

### 3 Interval tree: find all intervals containing a given interval

2 answers, 526 views algorithms search-trees intervals
Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(min(n,(k + 1) log n))$ where $k$...

### 6 Sorting a list of strings in lexicographic order of sorted strings

1 answers, 1.872 views algorithms sorting strings
Let $A$ be a collection of strings over the alphabet $\{0,\ldots,m-1\}$ that in total contain $n$ symbols. Your task is to sort each of the strings internally, and then sort the resulting strings ...

### -1 Shell sort vs quick sort, which is better?

0 answers, 46 views algorithms sorting quicksort
Referring to this website : Toptal This website is confusing me, on clicking on play all, website starts to play animations of all available algorithms sorting the given arrays, which shows shell ...