Finding minimal degree for a B-Tree

We are given 44,000,000 elements. We want to store them in a B-Tree so that his height is 5 (no more than 5).
We are asked: “What is the minimal t we can choose?”

($ t$ is the minimal degree, in each vertex that is not the root we have at least $ t-1$ keys but no more than $ 2t-1$ )

We have a debate whether the minimal $ t$ for the minimal height is $ 10$ or $ 30$ :

Some calculated as so: $ 5 = \log_t(22,000,000)$
which gives us $ t \approx 29.4$ and so $ t = 30$

However then a some good questions were asked whether we know the inserting order or not, if we know then it may be $ t=10$ and if we do not it may be $ t=30$

The TA answered that while we show that we can insert all the elements under the constraints, it is valid, the height should not be more than $ 5$ . Given we know all the elements and now you create the tree, your task is to show how to build a B-Tree (the exact calculation for the minimal $ t$ )

We are stuck from here, we do not know which way is correct.
Thank you!

Number of minimal perfect hash functions that are order preserving- why is it true?

Suppose we have a universe of $ u=|U|$ elements. We called a set of $ H$ function $ (U,m)$ order-preserving minimal perfect hash family (OPMPHF) if for every subset $ M\subset U$ of size $ m$ has at least one function $ h\in H$ which is an over preserving minimal prefect hash. It is shown in [1,2] that for every
$ (U,m)$ -OPMPHF $ H$ obeys:

$ $ H=m! \cdot {u \choose m}/(\frac{u}{m})^m $ $

Thus, the program length for any order preserving minimal perfect hash function should contain at least $ \log_2 |H|$ bits.

In partiular, if $ m=3,u=8$ , we have that $ |H|\geq 17.7$ .

However, I think I can create as set of $ |H|=6$ functions for such family. For every $ 2\leq i\leq 7$ we define $ f_i(x)$ to be equal $ 1$ if $ x<i$ , equal $ 2$ if $ x=i$ and equal $ 3$ if $ x\geq i$ . Every function $ f_i$ is order-preserving, and for each set $ M$ with second element $ i$ has a perfect function $ f_i$ .

Do I miss something in my analysis?

[1]- http://160592857366.free.fr/joe/ebooks/ShareData/Optimal%20algorithms%20for%20minimal%20perfect%20hashing.pdf [2]-K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984

MST with possibly minimal diameter

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph is undirected (just like in Christofides algorithm). The point is, the problem I am working on requires me to find the MST with possibly lowest diameter (the number of nodes on the longest path between any two leaf nodes, equivalently, for the purpose of measuring the diameter one can treat all the edges of the MST as if they had the weight equal to 1).

I know that Boruvka’s, Prim’s and Kruskal’s algorithm can be used to find some MST, but can I influence them somehow to prefer the shortest (in the terms of the diameter) trees possible?

If the answer to the question above is negative, are there any algorithms or methods which either yield MST with some bounds on the tree diameter or, at least, are there any known methods of obtaining a bound on MST diameter for a given graph?

algorithm that finds minimal vertex cover of a given vertex

i am looking for a simple algorithm that gets as an input an undirected graph and a vertex in the graph and outputs the minimal vertex cover that v belongs to.

not sure on how to do it correctly, here’s my attempt:

for a given undirected graph $ G=(V,E)$ and a vertex $ v \in G$

1)$ edges \leftarrow \emptyset $

2)remove adjacent edges to given vertex v(given in the input)

3)while there are edges in graph G:

3.1)$ edges \leftarrow {u,v}$

3.2)$ G\:\leftarrow \:G\:\:\ \:\:\left\{u,v\right\}$ (doesn’t let me mark it correctly, but i meant remove {u,v} from G. doesn’t give me to write \ correctly

3.3)return |x|+1 (including v we got from the input)

how to make it better? would appreciate seeing better algorithms for this and explanations/insights so i can learn

thank you for your efforts

Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold

Let $ A$ be a an $ n\times m$ real valued matrix. The problem is to find the minimal subset $ I$ of rows (if there is any) such that the sum of each column $ j$ over the corresponding rows exceeds some threshold $ t_j$ , i.e. $ \sum_{i\in I}A[i,j]>t_j$ for all $ j\in\{1,\dots m\}$ .

Or, stated as optimization problem:

Let $ A\in\mathbb{R}^{n\times m}, t\in\mathbb{R}^m$ . Now solve \begin{align}\min_{\xi\in\{0,1\}^n}&\sum_{i=1}^n\xi_i\\text{s.t.}&\,A^\top\xi>t\,.\end{align}

Actually, i would need a solution only for $ m=2$ , but the general might be interesting too.

What preventive measures can be taken to get over this scenario with minimal data loss

I am SQL server dba and came across weird scenario our cluster which had 10 nodes 5 primary 5 secondary each nodes had SQL role…. example Ams1pd11 to Ams1pd15 are primary.. and Ams3 side from pd11 to of 15 was secondary… in this scenario whole cluster behaved abnormally going 2 nodes down and all nodes availability groups were inaccessible leading to multicustomer outage.

Explanation of the real-time scenario as it started when I was in shift….

Ams1pd12 got down which was hosting primary server A So automatically the role A was failed over on best possible node and he choose Ams1pd11.

But Ams1pd11 already had one role on it e.g B Now Ams1pd11 was hosting both A and B as Ams1pd12 got down

As both primary roles were on one node it was a risk so to balance I failed over B node to one of secondary node Ams3 side.. now it was balanced and I was just about to investigate on Ams1pd12 why it got down and all…

But suddenly Ams1pd11 node also went down and the role was not failed over and stucked over there…

So now 2 nodes out of 10 were down and one role was stuck so the customers on that role were impacted….

We were troubleshooting with Microsoft for same and noticed that other nodes were showing up by the availability group for alll the nodes were stuck and they were not opening and stucked in expanding state….

So this way all the nodes on that cluster were impacted and as due to this our backups stopped.. There was data loss…

The one stucked role and customer on that node faced only 15 mins data loss as the service was down fr us and them too at the same time, but

The nodes which were showing up and AG groups were inaccessible weird thing was for the already logged in users they were able to change modify the data… It was only refusing new connections… But old connection were still active…

So if issue started and backup stopped at 7 am most of the customers were able to access the database till 6pm so there was 11 hours of data loss….

And it took lot of efforts to restore databases manually… Those online nodes were easy to recover as we just had to attach the dbs as we migrated data and log files bt for stucked role databases we had to manually recover them.

Please suggest the strategies which will be best to be followed in this type of disaster how we can obtain speedy recovery.

minimal distance of a self correcting code

i wonder: how can i find minimal distance of a self correcting code in following situation: if we know that a code can fix every 3 errors(if not more than 3 errors, the word is recovered) and can detect every 5 errors(if between 3 and 5 errors, the algorithm will report that the error can not be fixed), how can we find its minimal distance?

i know that a code that fixes(hamming distance properties) $ i$ number of errors costs a length of $ 2i+1$ , and for detection of $ i$ errors it costs a length of $ i+1$ . so the minimal length in this scenario is $ (2(3)+1)+(5+1)$ or should it be the larger of the two? but if it’s the larger of the two, then the number 7 seems problematic in this case and seems that it is not suffice.

what is the correct minimal hamming distance here?

c# – Setup specific mousewheel rules and timer with reset function to control a value with minimal user input

My main issue here is to distinguish a first and a second stage when moving a mousewheel up and down.
How could I put the following together for a mousewheel solution in plain c#?
I have a value that controls the opacity level of an object and it could be a value between 1 – 255.
I started with a simple mousewheel setup so that each time the wheel jumps to its next spot upwards or downwards, another value returns a 1 or -1. What I need is moving the wheel up or down 1 time will start a timer event that changes the opacity value to the minimum or maximum value depending on wheel movement direction by adding/subtracting 1 to the current value every 1ms. For up direction, stop value increase only when the wheel was moved to the next spot upwards or when the value is 255. For down direction, stop value decrease only when the wheel was moved to the next spot downwards or when the value is 1.

Find the minimal tank capacity to be able to travel from any city to any other

There are $ n$ cities in the country. The car can go from any city $ u$ to city $ v$ , On this road it spends $ w_{u,v} > 0$ fuel. At the same $ w_{u,v}$ can differ from $ w_{v, u}$ . The task is to find the minimal tank capacity to be able to travel from any city to any other (possibly with refuels) in $ O(n^2\log n)$ .