texts: What is beta and k parameter in Incremental Decision Tree

texts:
I have read this paper https://arxiv.org/pdf/1803.03674v1.pdf for outlier detection problem with real data (online training)
In this paper, the authors used Incremental Decision Tree to build subspaces (nodes in tree) by 2-mean method. The problem is in the algorithm 2 (build tree in paper), the condition (line 22): if t = beta power k. with t is the round observations (maybe each round we observe one sample) the splitting is performed.
The question is: What is beta and k? I spent a lot of time thinking about this. In the experiment you can see the authors plot chart describe splitting space process. At round 5, 11, 40? These are t (in my understanding) 5 can't be a result of any number power any number.
Thanks you.


texts: Set which is easy to sample, but difficult to sample from its complement

texts:
Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\frac{2}{3}$  members of $S$ of size $n$ (for all $n$).  $A$ does not have to be uniform.

Is there a set $S$ such that there exists an efficient algorithm $A$ such that for all $n$, $A$ generates at least $\frac{2}{3}$ members of $S$ (of size $n$), but any efficient algorithm for $S^C$ can only generate at most $\frac{1}{3}$ elements from $S^C$ of size $n$ (under complexity asuumptions)?


texts: Should planar Euclidean graphs be planar straight-line graphs?

texts:
An Euclidean graph, by definition is

  A weighted graph in which the weights are equal to the Euclidean
  lengths of the edges in a specified embedding

and a graph is called planar if

  it can be drawn in a plane without graph edges crossing

lastly, a planar straight-line graph (PSLG) is

  embedding of a planar graph in the plane such that its edges are mapped into straight line segments.

By these three definitions, I cannot conclude that if an Euclidean planar graph should be a PSLG or not.
For instance, given an Euclidean non-planar graph:

I can convert this graph into an Euclidean planar graph

by sticking with the definitions. Given the definitions above, the former one is a non planar straght-line graph whereas the latter one is a planar graph. Assume that the length of each edge is preserved. Then is the latter one still an Euclidean graph?


texts: Would time travel be useful for optimization?

texts:
Let's say we have circuitry that can send pieces of data to the past state of the program through literal time travel. Said time travel takes 1-5 clock cycles (I cannot assume the nature of time travel so I am giving slight lee-way) and sends one byte to some byte in the past programs memory along with a check bit to some other location so that the time travel can be detected. The general purpose would be for the program to basically run once and then essentially bootstrap paradoxing the original calculation, thereby in essence only taking the amount of time it took to send the data back to the program's past state.

Would it actually be realistic for a user level  or utility program to use this as a fast/cheap way to optimize a program? My guess is that it is only good for extremely complex calculations such as prime number searches, framebuffer generations for 3D graphics, etc. but I cannot be entirely sure.

Assuming this were in the C language, the syntax for code to be bootstrapped would look like this (in case one wishes to write examples of cases they find contradictory)

bootstrap (<checkbit to see if time travel has occurred>)
{
    <code to process and create the original data>

    send: <list of addresses to be sent back separated by commas>
    to: <list of addresses of where the data should be sent to separated by commas>
}

Assume energy/radiation/side effects of time travel are irrelevant. This assumes that it is literally as easy to time travel as it is to run an adding circuit. Also, assume that people have worked out all the "bugs" from the system. The circuit works correctly without fail.

I apologize if this is the wrong stack exchange site. I wish to speak scientifically regarding this in a real theoretical sense and this seemed like the more theoretical CS stack exchange site.


texts: What is an array of arrays called when all arrays have the same size?

texts:
If I have an array a of arrays, in many languages they may have different size. Is there a word for an array of arrays where all the arrays have the same length?

Edit:
An array of arrays may have the following form:

[
  [ 1, 2, 3 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2 ]
]

But in order to convert this to a matrix you would have to assume some default value or trim the arrays. The following array of arrays is possible to convert into a matrix without any asumptions or trimming as all arrays have same length.

[
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
]

Is there some name or classifier for a matrix of this kind?


texts: set with maximum sum consisting of mutually co-prime numbers

texts:
Definitions. Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and mutually co-prime. Then find the maximum sum the set $S$ can have.
Example. Let $n=10$, then the maximum sum $S$ can have is $30$ corresponding to $S=\{1,5,7,8,9\}$.

What I tried. I tried to implement the following greedy algorithm.

First I divide primes $\le n$ into $3$ lists: $list_1$ containing primes $\le \lfloor \sqrt{n} \rfloor$, $\; list_2$ containing primes in range $\big( \lfloor \sqrt(n) \rfloor,\lfloor \frac{n}{2} \rfloor \big )$ and finally $list_3$ containing prime in the range $\big[\lfloor \frac{n}{2} \rfloor+1,n \big ]$.
Next I define a function $largest(a,b,n)$, which returns the largest number of the form $a*b^{r}$ less than equal to $n$.
If there exist two numbers $l_1 \in list_1$ and $l_2 \in list_2$ such that $diff = largest(l_2,l_1,n)-( largest(1,l_1,n) + l_2 ) > 0$, I chose the pair $(l_1,l_2)$ such that $diff$ is maximised. I delete $l_1$ from $list_1$, $l_2$ from $list_2$ and append $largest(l_2,l_1,n)$ in $list_2$ and repeat step $3$. If no such pair $(l_1,l_2)$ exists such that $diff>0$, I go to step $4$.
I don't change anything in $list_3$.
In the end $ \{1\} \cup \{ l_1^r \;  | \;l_1 \; \in list_1 \text{ and } largest(1,l_1,n)=r \} \cup list_2 \cup list_3$ is my desired set $S$ and I report the sum of it's elements.

Running example of my algorithm. If $n=30$,

#list_1 = {2,3,5}
#list_2 = {7,11,13}
#list_3 = {17,19,23,29}

#The first time step 3 is evaluated I get l_1 = 2 and l_2 = 7 ..
#.. as  diff = ( 28 - ( 16 + 7 ) ) = 5 > 0 and diff is maximised
# so I delete 2 from list_1 and 7 from list_2 and append 28 in list_2

#When step 3 is evaluated again no such pair (l_1,l_2) is found

#So our desired list becomes S={1,27,25,11,13,28,17,19,23,29} with sum 193.

But my algorithm only seems to give correct for few simple cases only. Plus I am not able to prove/disprove or modify any of my assumptions .Now I am hopelessly stuck at the problem and I am not making any progress. But I still believe that some greedy algorithm is at work here.

PS: The question is from project Euler max-sum co-prime set. I would really appreciate just some hint or new direction to think.


texts: Undergrad resources for identifying regular languages with Myhill-Nerode matrices

texts:
I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure properties of regular languages, the pumping lemma etc, to show that a language is or is not regular, all of our proofs and examples for identifying regular languages use the Myhill-Nerode theorem and boolean matrices as defined below.

Let $L = \{w_1, w_2, ...\}$ be a set of words over some alphabet $\Sigma$ and let $T_L$ be a matrix with entries $t_{ij}$ where

$$ t_{ij} =
\left\{
 \begin{array}{ll}
  1  & \mbox{if } w_iw_j \in L \\
  0  & \mbox{otherwise}
 \end{array}
\right.
$$

Then by Myhill-Nerode, L is non-regular iff all rows of $T_L$ are distinct.

Correction: Then by Myhill-Nerode, $L$ is non-regular iff $T_L$ has an infinite number of distinct rows.

My question is, are there any readily available books, papers, or lecture notes that lean heavily on this technique and are appropriate for undergrads?


texts:
What is the minimal number of DFA states required to recognize binary numbers (encoded MSB to LSB) which are divisible by 6 and 8?

For divisibility by $6$ we required $6$ states.

For divisibility by $8$ we require $4$ states.

So in total, we need $6 \times 4$ states = $24$ states.

Am I correct? Can we do it with fewer states?


texts: Lower bound on distinct element heapsort

texts:
I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS:

Exercise 6.4-5
Show that when all elements are distinct, the best-case running time of heapsort is $\Omega(n\text{log}(n))$.

I've been thinking over this for about a day or so, and so far I've tried working with finding the time it takes run heapsort through just the leaves of a heap (I've been focusing on full heaps with $n = 2^h - 1$ elements), but couldn't draw any conclusions except for the minimum and 2nd-minimum elements, so that hasn't really gotten anywhere.

Does anyone have any hints as to how to proceed? Please don't post solutions to the problem, just hints/potential directions to proceed.

Any help is much appreciated!


texts:
Is this regular or not
L = {w1w^R | w ∈ {0,1}*
(where for any word w ∈ {0,1})*, w^R denotes the reverse of w)


texts: Is it possible to entangle more than 2 qubits? If so, is it useful?

texts:
With 2 qubits, there are 4 ways to entangle the qubits - the four maximally entangled two-qubit Bell states, of which one is $1/\sqrt{2}(|00\rangle + |11\rangle)$.

Is it possible to entangle more than two qubits together?  If so, is there any practical use to doing so?


texts: Regular Expressions with at least 2 0's and at most 1

texts:
I think the answer should be:

$(1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon)$

But I am not sure if this is the right answer. Can someone explain the correct answer?
And if it is correct how can I shorten this up?

Also what is the nfa for the regular expression:
∅*

i have one more problem:  i can't surely understand the meaning of Σ* symbol. As far as I understand it should be (0+1)* if Σ = (0, 1) and (a+b+c)* if
Σ = (a,b,c) and so on. Please someone clarify this.


texts: How to find the accuracy of a set partitioning?

texts:
Suppose that there are $k$ sets $S_1, S_2, S_3, \dots, S_k$.

The numbers $N = \{1, 2, \dots,n\}$ are distributed into these sets equally.

Say that we partition $N$ into $m$ sets $P_1, P_2, \dots, P_m$.

The problem is to find how accurate is our partitioning.
However, the accuracy is not finding the exact same sets, but putting the same elements into the same set.
For instance:

$S_1 = \{1,2,3,4,5,6\}$
$S_2 = \{7,8,9,10,11,12\}$
$S_3 = \{13,14,15,16,17,18\}$

and

$P_1 = \{1,2\}$
$P_2 = \{3,4,5\}$
$P_3 = \{6,7,8,9\}$
$P_4 = \{10,11,12\}$
$P_5 = \{13,14,15,16\}$
$P_6 = \{17\}$
$P_7 = \{18\}$

This partitioning is almost accurate because if we were to put $6$ into $P_2$ instead of $P_3$, then none of the sets would contain elements those do not belong to the same set in the original sets.

However,
$P_1 = \{1,2,3,4,5,6,7,8,9\}$
$P_2 = \{10,11,12,13,14,15,16,17,18\}$

is a very inaccurate partitioning because half of the elements in each set is from a different set.

My questions are:
1. Is there a name for this problem?
2. Is this problem NP-Hard?
3. How can I define a metric for the accuracy of the partitioning?
4. How can I find how accurate a partitioning is?


texts: What is an easy-to-implement linear or non-quadratic suffix array construction algorithm?

texts: The algorithm described here in "Linear Work Suffix Array Construction" (2006) has compact C++ code that is too abstract for me to follow. Is that still the current easy-to-implement linear algorithm? If no, please point out that other algorithm. If yes, are there any other easier to follow reference implementations?


texts:
Is there a way for two programs or computer nodes to communicate with each other without knowing each others APIs? Or is there a least a reasonable approach to make them talk in some settings?
Let a messaging protocol be fixed for every communicating program. For the sake of example let it be based on prolog queries. Then every program will have a database representing all of its current knowledge.
If one program is a compiler and the other one is a linker, then we have an example: the linker needs the code and associated function names to be able to do its job, so it sends query function(Name, Instructions). to the compiler. Every compiler should be able to respond to that query because it should have the knowledge required. However, the compiler's data that is requested by the linker may not be stored under the name function, because that name could not be present in the compiler's database at all, or it could stand for something else.
Continuing with this example until the end.
Unique identifier could be used instead of function, but that would be an overkill, because, in that case, every compiler and linker would need to know about that unique identifier, which is equivalent to knowing the API.
Much better would be to have a method to interactively connect the linker's function with compier's equivalent name (or combination of different names).
People learn new names with little effort. For example, by looking up their definitions. If linker could define function (in terms of simpler names?) then that would be perfect. If there is a nice way to make such definitions, I want to know it.
I was also thinking about solving this based on test cases. The idea is that linker could have an example source file and a query + the result of that query (so, a test case) for each of its requests. Then compiler could use those test cases by compiling the sources and trying to reproduce query results by using its own queries (brute forcing in the worst case), which would likely give a correspondence between linker queries and compiler queries. But that approach is bad because of at least one reason - test cases are not compilable by every compiler. So if a linker has test cases in C, then both gcc and clang would be able to speak with the linker, but rust compiler would not be.
Any suggestions or references to existing studies are appreciated! Thanks in advance.


texts: Algorithmic challenge: generate a list of random non overlapping squares

texts:
For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap.
So the challenge is simply: given a two dimensional area $a$ (topLeft: int, topRight: int, width: int, height:int), a number of squares required $n$ and a size for each square $s$: generate a list $L$ of $|L|=n$ squares in $a$ where the following condition holds.
$$\forall q,r \in L , q \neq r \implies \textrm{no_overlap}(q,r) \land \textrm{inside}(q,a)  $$
where no_overlap is a function that checks if square $q$ and $r$ do not overlap given the size $s$ and inside(q,a) checks if square $q$ is completely inside the area $a$.
I tried coming up with a solution myself but the only thing I can find is to brute force generating a square, check if there is overlap and if not ,add it to $L$. But as one might see, this algorithm could theoretically run forever. I would need something which is guaranteed to work in a finite time and preferably be of a complexity of at most $\mathcal{O}(n^2)$. So I thought to myself, maybe I could share this with other people around the world and see what clever ideas they have in mind. I most certainly find it an interesing theoretical question to ask. The practical reason is for a Unity 3D (game) project I am making.
EDIT:
This would be a possible solution graphically illustrated for $n=7$


texts:
A language is in $\mathsf{Almost\text{-}PSPACE}$ if there is a (deterministic) $\mathsf{PSPACE}$ Turing machine with an oracle $A$ that accepts the language with probability $1$ when the oracle language is chosen uniformly at random [1,2]. (That is, the language accepted by the oracle is determined by tossing a fair coin for each possible string.)

I can't understand the difference between $\mathsf{Almost\text{-}PSPACE}$ and $\mathsf{IPP^A}$.

Is it possible that $\mathsf{P} = \mathsf{PSPACE} \subsetneq \mathsf{Almost\text{-}PSPACE}$? Or, maybe it is already known that $\mathsf{P} \subsetneq \mathsf{Almost\text{-}PSPACE}$? Or it will imply that $\mathsf{P} = \mathsf{Almost\text{-}P} = \mathsf{Almost\text{-}PSPACE}$?

[1] Complexity Zoo.
[2] C.H. Bennett and J. Gill, Relative to a random oracle $A$, $\mathsf{P}\neq\mathsf{NP}\neq\mathsf{co\text{-}NP}$ with probability $1$. SIAM Journal on Computing, 10(1):96–113, 1981. (Paywalled PDF.)


texts: Why use joint trees in Graphical Models?

texts:
I am wondering why some methods transform the underlying graphical model (Bayesian Network for example) to a junction tree¹? What are the advantages?  Also what are the limitations?

I believe it's for computational purposes. If that's the case under what circumstances it is not recommended to transform the underlying DAG to joint-trees?

Edit: speaking about graphical models in general (whether they are probabilistic or not), is there some guidelines when to transform them i.e. decompose them?

1 Junction trees are also known as tree decomposition.


texts:
I'm new to Optimization and aproximation problems

I would like to know if the following statements are true or false and why :

If the optimization problem $K$ admits a PTAS then $K$ admits an approximation algorithm with
approximation ratio 2.
If there is an FPTAS for MIN-TSP then $P = NP$


texts: "Print 'em all game" for Turing machines

texts:
Suppose that we have a tape restricted to $n$ cells on binaryalphabet $\Sigma = \{0,1\}$ and initially filled with zeroes.

We want to build a Turing machine $M_n$ (or better a Linear Bounded Automata) that "prints" all the $2^n$ numbers on the tape, i.e. for all $x \in [0..2^{n-1}]$ there is a time $t_x$ during the computation in which the tape content is exactly $x$. Note that we can build an "optimized" Turing machine for every $n$.

At every step the head must move left or right.

  What is the minimum number of steps $T(n)$ required?

We can easily see that $2^n-1 \leq T(n) \leq n 2^n$.

But how much can we "optimize" it?

For example for $n=3$ there is an optimal $2^n-1$ sequence:

t0:  >0 0 0
t1:   1>0 0
t2:   1 1>0
t3:   1>1 1
t4:  >1 0 1
t5:   0>0 1
t6:   0 1>1
t7:   0>1 0


texts: Improving success probability for one sided error algorithms

texts:
Suppose I have a probabilistic Turing machine for a language such that
$$ x \in A \implies \Pr(M \text{ accepts } x) \ge \frac{1}{n}$$
$$ x \notin A \implies \Pr(M \text{ accepts } x) = 0$$
I want to show that the above language is in $\mathsf{RP}$. In particular, I need a probabilistic Turing machine $N$ such that
$$ x \in A \implies \Pr(N \text{ accepts } x) \ge 1 - \frac{1}{2^n}$$ where $n = |x|$.

I tried to construct $N$ such that it runs $M$ multiple times (say $t$ times) and accepts if at least one of the runs accepts. This preserves the one-sided error but I'm not sure if it runs in polynomial time.

I showed that $x \in A \implies \Pr(N \text{ accepts } x) \ge 1 - (1 - \frac{1}{n})^t$.

Now, to show that it is in $\mathsf{RP}$,

$$1 - (1 - \frac{1}{n})^t \ge 1 - \frac{1}{2^n}$$
$$ (1-\frac{1}{n})^t \le \frac{1}{2^n} $$

I am basically stuck at this point and unable to show an upper bound for $t$. I know that it suffices to show that $t$ is polynomial in $n$ but I am not able to prove it. How do I show that $N$ is indeed a polynomial time machine? Or maybe this is not the right approach?


texts: Is there an algorithm that provably exists although we don't know what it is?

texts:
In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it.

I am looking for similar results in computer science. In particular: is there a problem that we can prove it is decidable without showing an algorithm for it? I.e. we know that it can be solved by an algorithm, but we don't know what the algorithm looks like?


texts: What is a sticky bit in computer architecture?

texts:
I am reading about a counter implementation in RISC Architecture. The specification reads,

  Sticky overflow bit is set when the counter wraps through zero.

I can infer that the overflow bit is set when the counter reaches maximum value(all 1's) and another increment makes it 0(all 0's). What is the meaning of the sticky overflow bit?


texts: NP-hardness for one-dimensional facility location problem with entrance fee for each customer

texts:
We have $n$ customers, $(x_1, \dots, x_n)$, sorted on the read line. For convenience, we also use $x_i$ to denote its coordinate on the line. We need to locate $m$ facilities on the real line. We note that these facilities can be located anywhere on the real line. Each facility $j\in [m]$ is associated with an entrance fee $f_j$, such as the ticket money for a swimming pool. Given a location profile $(y_1, \dots, y_m)\in \mathcal{R}^m$ for the facilities($(y_1, \dots, y_m)$ is not necessarily ordered), the cost for customer $i$ at facility $j$ is $c_{ij} = |x_i- y_j|+f_j$, which can be understood as the aggregate money of the travelling cost and the entrance fee when you taxi to a swimming pool and purchase a ticket to swim inside. And the customer will always choose the facility so as to minimize her cost.
Our goal is to find a location profile $(y_1, \dots, y_m)$ for the given $m$ facilities such that the total minimum cost
$$\sum_{i\in [n]}\min_{j\in [m]}c_{ij}$$
is minimized.
An easy but critical obserbation is that there is an optimal solution where each facility is located in the median agent of the continuous region of agents it serves. If we have identical entrance fees, we only need to find the optimal $m$ continuous partitions, which can be solved by dynamic programming in $O(mn^2)$. For the general case, similar DP algortihm runs in $O(2^mn^2)$. The algorithm, however, is exponential in $m$ and only makes sense after we've proved the problem is NP-hard. Another observation which may be helpful is that for if we have known the optimal $m$ continuous partitions, we just assign the facility of the $k$-th smallest entrance fee to the partition of the $k$-th most customers.
So is this problem NP-hard?  Or is there an algorithm running in polynomial time?
Update
Below is the detailed DP algorithms for the special case where all entrance fees are identical and the general case:

For the spcial case, denote by $M(i,j,k)$ the minimum total cost when customer $i$ is in the $k$-th partition and customer $j$ the right boundary of this partition. Depending on whether or not customer $i-1$ is still in the $k$-partition, we derive the following transition function:
$$M(i,j,k)=  \min\{M(i-1,j,k), M(i-1,i-1,k-1)+c(i,j)\}$$
where $c(i,j)$ is the minimum total cost of partition $[i,j]$, i.e., total cost for these customers when exact one facility is located in the median of $[i,j]$.
Obvious, this DP runs in $O(mn^2)$.

For the general case, the key difference is that we have to decide which facility is located in the rightmost partition since now facilities are heterogeneous. Similarly we denote by $M(i,j,F)$ the minimum total cost when customer $i$ is in the rightmost partiton, customer $j$ is the right boundary of this partition and $F$ is the set of facilities to be located. Similarly again, we can derive the following transition function:
$$M(i,j,F)=  \min\{M(i-1,j,F), \\ \min_{s\in F}\{M(i-1,i-1,F\setminus\{s\})+c^{\prime}(i,j,f_s)\}\}$$
where $c^{\prime}(i,j,f_s)$ is the total cost of $[i,j]$ when a facility with entrance fee $f_s$ is locate in the median of $[i,j]$.
This DP runs in $O(2^mn^2)$


texts:
Consider the following language:
$$ L_1=\{uu^rv \mid u,v\in\{0,1\}^+\}.$$
that means that neither $u$ nor $v$ can be $\varepsilon$. As usual $u^r$ refers to $u$ reflected.

I think that this language is not regular, but i am not sure. Any ideas?


texts: Time Complexity of a Naive Solution to Merge K Sorted Arrays

texts:
There is a leetcode question about merging k sorted arrays. I would like to be able to explain the time complexity of the following naive solution:

function mergexsSortedArrays(xs) {
  if (xs === null || xs.length === 0) {
    return [];
  }

  let l1 = xs[0];

  for (let i = 1; i < xs.length; i++) {
    let l2 = xs[i];

    l1 = merge(l1, l2);
  }

  return l1;
}

/*
This is simply for completeness; the relevant code is above
/*
function merge(l1, l2) {
  const ans = [];

  let l1HeadIdx = 0;
  let l2HeadIdx = 0;

  while (l1HeadIdx < l1.length && l2HeadIdx < l2.length) {
    if (l1[l1HeadIdx] < l2[l2HeadIdx]) {
      ans.push(l1[l1HeadIdx]);
      l1HeadIdx++;
    } else {
      ans.push(l2[l2HeadIdx]);
      l2HeadIdx++;
    }
  }

  while (l1HeadIdx < l1.length) {
    ans.push(l1[l1HeadIdx]);
    l1HeadIdx++;
  }

  while (l2HeadIdx < l2.length) {
    ans.push(l2[l2HeadIdx]);
    l2HeadIdx++;
  }

  return ans;
}

Let's say that k is the number of elements in the input array. To simplify the math, we will assume that each sorted array has length n.

Within the for loop, we are running the merge algorithm. On the first iteration, l1 will have length n and l2 will have length n, so the merge algorithm will be do 2n work. In the second iteration, l1 will be 2n and l2 will be n, so merge will do 3n work. As our result, the amount of work that is being done in our for loop will be 2n + 3n + 4n ... (k - 1) n. If we expand this work a bit, it would be n + 2n + 3n ... k(n), and this can be re-written as n * (1 + 2 + 3 ... k); the inner sum has a closed-form formula of [k * (k + 1)] / 2, which is essentially an O(k^2), and then we add the n to get a final time complexity of O(n(k^2)).

Is this correct? Or have I gone off the rails?


texts: In cache-oblivious algorithms, how is recursive reduction of data performed?

texts:
From wikipedia:

"Typically, a cache-oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into cache, regardless of the cache size."

(Is this recursive subdivision manual, or automated? Assuming automated...)

In what way must one produce code in order for it to be suitable for reduction to a cache-oblivious form? Does this rely on the specific implementation of recursive reduction applicable in one's given case?

Another way of putting the question is, would I need to write my code in a special way in order for some automated parser to run through the code and optimise it for cache-oblivious access?

P.S. I'm trying to get a handle on how to approach writing code for practical optimisation using the methods noted in the literature.


texts: Justification behind this heuristic in SMA*+

texts:
I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA*+). In short, the authors propose a limited-memory version of A* where we cull nodes if we are out of memory, to re-expand them later on.

To do this they choose the worst node to cull. And they propose a heuristic to maximize to choose what is considered the worst node:

  For example, a culling heuristic based on the ratio between f-cost and depth, given as $c(n) = f(n) / \ln(d(n) + e)$, where $e$
  is Euler’s number, can improve performance on problems
  with many similar f-costs, if we can reasonably assume that the goal has a high depth.

A quick reminder, $f(n) = g(n) + h(n)$ where $g(n)$ is the cost to reach node $n$ and $h(n)$ is the heuristic to estimate the distance from $n$ to the goal node. $d(n)$ is the depth of the node.

The authors don't further elaborate on this. Is there some logical justification I'm missing for the formula $c(n)$, in particular the natural logarithm and adding $e$ to $d(n)$?


texts: Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

texts:
Let $L$ be a language, and consider the following relation $\equiv_L$ on strings:
$s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$.
This is an equivalence relation.
Let $I(L)$ be the number of equivalence classes of $\equiv_L$
(a) Suppose $L$ is a language and $I(L)$ is finite. Construct a DFA recognizing $L$ that has
exactly $I(L)$ states.
(b) Consider the language $L = \{www : w \in \{a,b\}^*\}$. Show that $L$ is not regular by giving
infinitely many pairwise inequivalent elements. [which is something proven to work earlier]

Now, for (a) I think I got a reasonable solution, for (b) I don't feel so sure.
For part (a) I describe an algorithm which first creates a start state for the DFA and labels it $\bar\varepsilon$, i.e. the $\equiv_L$-equivalence class of $\varepsilon$. Second, for each letter $a$ in the input alphabet a new state $\bar a$ is created and a transition from $\bar\varepsilon$ to $\bar a$ is labelled $a$. Then all the states with the same label are merged in a single state, and the transitions are adjusted as a consequence. Hence, this procedure just carried on $\bar\varepsilon$ is iterated to each state just added. The algorithm stops when an iteration does not add any new state or transition.
Do you think that the writer wanted me to use this much information about $\equiv_L$-equivalence classes or there is a neater solution?
For part (b), I believe that all the words generated by $ab^*$ are pairwise not $\equiv_L$-equivalent, with that $L$. Am I not sure I can justify it further than this, but is there another simpler example?
Thank you for any help, this is a rather long question.


texts: What Do These Symbols Mean in Repetitive Rule Application and How Are They Applied Practically?

texts: Frequently in cs blogs and books I see this notation, =>* and =>+ but I am not sure how it is being applied in a production rule and it's significance. What exactly does it represent, and can you show an example of it being applied.


texts: If M is recognizing L in polynomial time, is it also deciding it in polynomial time?

texts:
Assume that a given turing machine $M$ accepts words in the language
  in $n^k$ or less steps, but words that aren't in the language
  are rejected in unknown number of steps (the machine might even loop).

  $k$ is unknown.

  Is $L(M)\in P$?

Well, obviously $L(M)$ is recognized in polynomial time. The question is whether it's possible to decide $L(M)$ in polynomial time.

It seems to me that the answer is no, but I can't figure a way to prove it.


texts: Evaluating functions related by Mobius inversion formula

texts:
Problem

Consider two functions $f: \mathbb{N} \rightarrow \mathbb{N}$ and $g: \mathbb{N} \rightarrow \mathbb{N}$ such that $f(k) = \sum_{d | k} g(d)$ for all $k \in \mathbb{N}$.  So, the questions are:

Let's say $f(k)$ is known for $k \in \{ 1, 2, \dots, n \}$. How to evaluate $g(k)$ for all $k \in \{ 1, 2, \dots, n \}$ within time $\mathcal{O}(n \log n)$?
Let's say $g(k)$ is known for $k \in \{ 1, 2, \dots, n \}$. How to evaluate $f(k)$ for all $k \in \{ 1, 2, \dots, n \}$ within time $\mathcal{O}(n \log n)$?

My approach

I've noticed that $f(k) = \sum_{d | k} g(d)$ brings to mind Mobius inversion formula, that states the following:

$$ \forall k \in \mathbb{N} \quad f(k) = \sum_{d | k} g(d) \Rightarrow g(k) = \sum_{d | k} f\left( \frac{k}{d} \right) \mu(d), $$

where $\mu$ is the Mobius function. I understand how to do the evaluation from the questions by pre-factorizing all the numbers $1, 2, \dots, n$, but then it doesn't work within desired $\mathcal{O}(n \log n)$ time. How can one do that faster than by factorization?


texts: how to solve this quality distance problem for wheelchair user

texts:
I want to ask how to solve this problem..
in this graph we have vertex and edge with two value the quality and distance..
there are 3 path in this graph
1->2->6   distance is 10..
1->4->6   distance is 9..
1->3->5->-6  distance is 18..

my concern here is the quality of road,, 1 is the best road quality 2 is for average 3 is the worst..

the source is the 1 and to destination will be the 6..

1->2->6 the quality from 1 to 2 vertex is 1 but 2 to 6 is 2 so the quality of path will be 2..

1->4->6 the quality are 1 and 3 so it will be road quality 3..

1->3->5->6 all got 1 so it will be quality 1..

1->3->5->6 even if the distance is is 18 but it has 1 quality or the best quality of road then this will be the best path.. if they have the same quality then the dijktras algorithm will compute the shortest path because thEY have the same quality..
i already have code for dijkstra in php because i will be using php my problem is how to code or modify this algorithm.. thank you for the answer.. GOd bless.


texts: What is the algorithmic complexity of this?

texts:
I'm practicing leet code questions and want to understand more fully how to determine Big O notation. What is the algorithmic complexity of my solution to the following problem?

O(n^2) ? For every item in n I could loop an additional n[i] times. Or is it O(n) ?

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Input: [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

var canJump = function(nums) {

  let validIndices = {};
  for(let i = nums.length - 1; i >= 0; i--) {
    let currentNum = nums[i];
    if(currentNum + i >= nums.length - 1) {
      validIndices[i] = true;
    } else {
      while(currentNum > 0) {
        if(validIndices[i + currentNum]) {
          validIndices[i] = true;
        }
        currentNum--;
      }
    }
  }

  return !!validIndices[0];
};


texts: Finidng edges of convexhull from rectangles

texts:
Green Boxes = rectangles
red dots = edge points
red lines = to be generated from convex hull algorithm

I have a problem with creating the convex hull algorithm.
I want to select or collect all the edges from these rectangles and draw convex hull around through these edges (See red dots from the Image).
To make my algorithm more efficient, I don't know how to deselect or eliminate the points (X black points) inside all rectangles.

Could someone give me a solution for this?

Thanks in advance


texts: Sliding window protocol, calculation of sequence number bits

texts:
I am preparing for my exams and was solving problems regarding Sliding Window Protocol and I came across these questions..

  A 1000km long cable operates a 1MBPS. Propagation delay is 10 microsec/km. If frame size is 1kB, then how many bits are required for sequence number?
  A) 3 B) 4 C) 5 D) 6

I got the ans as C option as follows,

propagation time is 10 microsec/km
so, for 1000 km it is 10*1000 microsec, ie 10 milisec
then RTT will be 20 milisec

in 10^3 milisec 8*10^6 bits
so, in 20 milisec X bits;

X = 20*(8*10^6)/10^3 = 160*10^3 bits

now, 1 frame is of size 1kB ie 8000 bits
so total number of frames will be 20. this will be a window size.

hence, to represent 20 frames uniquely we need 5 bits.

the ans was correct as per the answer key.. and then I came across this one..

  Frames of 1000 bits are sent over a 10^6 bps duplex link between two hosts. The propagation time is
  25ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

  What is the minimum number of bits (l) that will be required to represent the sequence numbers distinctly?
  Assume that no time gap needs to be given between transmission of two frames.

  (A) l=2 (B) l=3 (C) l=4 (D) l=5

as per the earlier one I solved this one like follows,

propagation time is 25 ms
then RTT will be 50 ms

in 10^3 ms 10^6 bits
so, in 50 ms X bits;

X = 50*(10^6)/10^3 = 50*10^3 bits

now, 1 frame is of size 1kb ie 1000 bits
so total number of frames will be 50. this will be a window size.

hence, to represent 50 frames uniquely we need 6 bits.

and 6 is not even in the option. Answer key is using same solution but taking propagation time not RTT. and their answer is 5 bits. I am totally confused, which one is correct?


texts: Find the $k$-th lexicographically smallest hamiltonian circuit

texts:
Let's say we have given unweighted directed graph with $N$ nodes and $M$ edges, and we want to find the $K$-th hamiltonian circuit, ordered in lexicographical order.

For example, if we have complete graph with $4$ nodes, and $12$ edges. The smallest hamiltonian circuit is $1 - 2 - 3 - 4$, the second one is $1 - 2 - 4 - 3$. Since finding hamiltonian circuit is NP Hard, what is the best complexity we can get this algorithm at?

Hamiltonian circuit is path that visits each node exactly once.

For the purpose of the problem, the circuit should begin in node $1$

What I think

If we have adjacent list of nodes connected to node $1$, sorted, then the permutations numbered from $[1, x]$ will pass in the first node, the on the second node the permutations numbered $[x, y]$ will pass the second node, etc..

Now our task is actually to find the $x, y...$ And we can solve for the second node (that we called from node $1$) for each of nodes adjacent to it, but this leads us to time complexity of $O(N!)$. Can we do it faster?


texts: Heuristic algorithm for the minimum weighted s-t cut with linear running time

texts: To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving this problem as a separation sub-problem inside a branch and cut algorithm, so I don't always need the optimal solution. Is there a heuristic/approximation/randomized algorithm for the min s-t cut problem with better time complexity?


texts: How to prune branches in a branch-and-bound solution for Flow Shop Scheduling?

texts:
I am implementing a Branch-and-Bound algorithm to find the optimal solution for the Flowshop Scheduling Problem, but I am stuck on the optimization phase, here is a rundown of the problem and what I go so far.

(I am sorry for my English, not a native speaker...)

The Problem

There are n tasks that must be run through two different machines, $m_1$ and $m_2$, where each tasks has different durations in each machine, minimize the sum of the finishing time of each task on $m_2$.

$\min c^* = \sum_{i=0}^{n} f_{2i}$

Where

$f_{ij}$ = the finishing time of task j on machine i

$d_{ij}$ = the duration of task j on machine i

With the constraint that each task can only be run in $m_2$ after it's done running on $m_1$.

What I have so far

I nailed down the basics of BnB, I can compute a dual bound for any node (a value that is no greater than the optimal solution from that node onwards). Then for each node, I generate all of it's children by appending one of the tasks that are not yet scheduled to the end of the task list, for each child I compute the dual bound and each one of them that has a dual bound greater than the greatest up to now its put on a priority queue. This solves the problem, every time I find a node with a dual bound that's better than the one I have, I am zeroing in the optimal solution, and each node that produces a dual bound that doesn't add any information for me is not explored (ie, bounds that are lower than the current optimal, since it doesn't help to narrow the possible value for the real optimal)

What I need

Now I need to add pruning by using the primal bound, in this case the primal bound for a node is any viable solution that's a child of that node, this yields a value that's certainly greater than or equal to the optimal, the reasoning here is: if I pick a feasible solution that's not the optimal, then by definition, its cost must be greater than the optimal, otherwise I picked the optimal solution, but it's value is, by definition, no less than the optimal

This is where I need help, is this the correct way to bound the optimal value? I only expand nodes in which the dual bound (an estimative of the lowest value I can achieve from that node) are between the best dual and primal bound so far in the tree? Can I ignore any nodes where the dual bound is outside this range? I can't seem to get my code right, but that's because I am unsure whats the correct line of thought here.


texts:
I'm confused between 2 XOR gate symbols, they have a minor difference but I'd still like to know if they truly are identical.

One looks like -

The other, like

Notice, how for one of them the input lines are connected all the way and for the other, it's not. Are they both identical, as I suspect or is there something I'm not aware about?


texts: The sum of all integers less than n with a zero

texts:
For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703

In this problem, n is smaller than $10^{18}$ , and the algorithm should finish within 1 second.


texts: Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$

texts:
I would like some help for the computation theory.
There is a PDA that accepts the language $\{0^n 1^a 2^b \mid n = a+b\}$, so how can I express it into context free grammar? Any help would be appreciated!
That's what I was trying, I am not sure if it is correct or not
S -> 0SA | 0SB | empty
A -> 1
B -> 2


texts: Find a strategy to evade hungry lions on the real line for the longest time

texts:
This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.

You are placed on the real line, and there also are $K$ lions on the real line, which are currently sleeping. You are given the wake up time of each lion. You can walk past a lion as long as it is sleeping. As soon as any lion wakes up, it starts walking towards you to eat you. Both you and the lions can walk at a maximum speed of 1m/s.

Given your starting position and the starting positions and wake up times of the lions, find the maximum time you can stay alive (can be infinite), and the strategy you should follow.


texts:
A popular mobile game, DiscoZoo, is about "rescuing" animals from a 5x5 grid of cells. Each animal represents a unique pattern (some have 3 cells, some have 4). The object is that, given this 5x5 grid, find all (or as many as possible) of the given animals within 10 turns, where the pattern of animals can be at any place within the grid (but cannot be rotated, change size, etc. - only translated such that all the coordinates of each animal are valid, and there is only one animal per square). We can only "get" an animal if we can successfully find each of the squares of that animal within the number of turns left; otherwise, we do not.

Here is an example. The sheep has a pattern of 4 horizontal adjacent squares, so clearly the squares (5, 2) (indexing from 1 and as (row, col)) and (5, 5) will be a sheep (and thus get the sheep). For the rabbit, it has a pattern of 4 vertical adjacent squares, so the squares (2, 1) and (4, 1) will be the rabbit. For the cow, it has a pattern of 3 horizontal adjacent squares, and since square (4, 2) was selected (and no animal placed there), the only square left for the cow is (4, 5). This is assuming that we do have attempts left (but there aren't any for this example).

More formally, we are given a 2D array $a[1..n][1..n]$, and $m$ animals $A_1,...A_m$ such that $A_i$ has value $p_i$. In the grid are the values of the $p_i$'s (in their respective positions) and all the rest are 0. Each cell either has 0 or one non-zero value (i.e., only one animal). However, none of the values are given to us at the start. Once we "select" a cell, that cell's value is revealed to us. Our objective is to find all or the maximum possible number of non-zero cells in the grid within $g$ turns.

What is the complexity of this problem in general?

Edit: after some thinking about the problem, let's restrict ourselves to having $m$ copies of the same animal $A$, and let that animal be a 2x2 square (i.e., occupies coordinates $(x, y), (x+1, y), (x, y+1), (x+1, y+1)$). What is the complexity of this version of the problem?

Even if we restrict further by looking at 1x1 squares, this is equivalent to finding nonzero elements in the matrix - it is trivially solvable in $\Theta(n^2)$ time, but can we do better?


texts: Virtual Memory vs Cache for block identification

texts: Both are based on the principle of locality. Then why virtual memory uses table lookup while cache memory uses associative memory for block identification?


texts:
I have a question from Introduction to Algorithms by CLRS,

When we say "the running time is $O(n^2),$" we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any values of $n$, no matter what particular input of size $n$ is chosen, the running time on the input is bounded from above by the value of $f(n)$.

What do the authors mean by saying there exists a function that is $O(n^2)$? Do they mean that this function is from the set $O(n^2)$? Is the last part which I highlighted correct? I think it must be "... from above by $O(n^2)$." I appreciate your answers.


texts: Growing multiples of variable combinations

texts:
I need to find growing combinations of variables a, b, c etc. I don't know names of math things in English well, so my description of the problem will be in pseudocode. This is for a programming problem, but I want to understand the underlying mathematics. I would highly appreciate proper names of techniques used so I can look them up further.

Lets say we have a list of variables

L (a, b, c)

And one single variable l which is the maximum desired count of a single variable from L.

I need to find every combination of elements from L multiplied by numbers from 0 to l.

So, for l = 3 I expect the following result:

1a0b0c
0a1b0c
0a0b1c
1a1b0c
1a0b1c

... and so on until ...

3a3b3c


texts: Why some rules in Elementary Cellular Automata halt and others don't?

texts:
I was looking over stephen wolfram's work mainly about Elementary Cellular Automata, i see that for all rules with N steps {i.e 200 steps} they show the same pattern {i,e rule 90 running on 20 steps and 100 steps are the same, like Here}.

Unlike rule 110 which shows different behavior when N = 20, 100 or 200, i know that it is universal but does that mean if a cellular automaton structure does not halt {continue to show different pattern when changing N steps} does that means it is always universal ?


texts: Split a graph into 2 components with known distribution?

texts:
I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there is a >10% difference difference, the split is simply not considered valid.) Additionally, I want to be able to calculate the chance that $G$ is split into these two components by this method.

I have solved the problem if we do not care about the size of components.  Simply create a uniformly random spanning tree of $G$, and randomly remove one of it's edges, breaking it into two components $A,B$. Then, calculate the number spanning trees in each component, and and multiply by the number of edges between $A$ and $B$, $e(A,B)$. This gets how many spanning trees can possibly yield $G$. In any spanning tree, each edge gives a different split, and there are always $(n-1)$ possible edges we can remove. So: $$p(A,B) = t(A)t(B)e(A,B) \frac{1}{t(A \cup B)(n-1)}$$

(The last part is not really necessary because it stays constant, as I only need something which is proportional to the probability.)

I'm looking for an algorithm which can practically be done upon relatively small graphs, with order of roughly 50 vertices. The method must have non-zero probabilities for a large number of splits (hopefully all, but a partial result would still be great). Additionally, it must have a reasonable chance of giving a good split. (for example, I could use the method above, and every once in a while, a randomly chose edge will split the tree well, but I'm hoping to do better)

I have an additional method for my harder problem, which perhaps could be improved:

Let $m$ be the smallest weight of a vertex in $G$, and $W$ be the sum of all the vertex weights in $G$. Choose two vertices $v_a$ and $v_b$ in $G$. Say we are looking for split in which $v_a$ is in component $A$ and $v_b$ is in $B$. Let $x$ be a random integer in the range of $.45\frac{W}{m} < x < .55\frac{W}{m}$. Then, we look for a split such that the $\left \lfloor \frac{W_a}{m} \right \rfloor = x$, where $W_A$ is the summed weight of the vertices in $A$. In any given tree, there is at most one edge which satisfies these conditions. Proof: consider the path from $v_a$ to $v_b$, we must remove an edge from this path to split these two into different components. As you go down this path, $W_A$ changes by at least $m$. So, the number of possible edges is constant like before, except now it is one rather than $(n-1)$. With $X$ being the number of possible values of $x$ in $A \cup B$, we get:

$$ p(A,B) = t(A)t(B)e(A,B)\frac{1}{t(A \cup B)X}$$

This is assuming that $v_a$ and $v_b$ and chosen deterministically, if you want it to be random, that can be accounted for too if desired. However, the issue is that the probability of a split having $\left \lfloor \frac{W_a}{m} \right \rfloor = x$ is quite low in my graphs, as $W$ is 200 times large than $m$. This restriction makes the chance of a good edge go from 60% to 3.5%. Perhaps there is a way to better way to choose $x$ based on the structure of $G$, or just a better way entirely to do this.


texts: Can I speed up Insertion Sort by using a tree for finding insertion positions?

texts:
I want to implement an insertionSort-algorithm. Let's say I have these pseudocode.

function insertionSort(F)
  for i <- 1 to n - 1 do
    j  <- findInsertPosition(F, i, 0, i - 1)
    insert(F, i, j)
  end for
end function

Now I want to implement the findInsertPosition function. Say I give this function my list, which is an array, and change this array into a tree, so that I can search iteratively in this tree for my element.

Would my complexity for the whole code be still maintained in $O(n \log n)$?


texts: Adding the requirement of linear time on infinitely many inputs into the class $P$

texts:
Is the following problem computable in polynomial time?

Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$)

Output: $<M_2>$, encoding of a determinstic TM that runs in polynomial time ($L(M_2)\in P$), and satisfies:

$L(M_1)=L(M_2)$ (they decide the same language)
$\forall n\exists w\in\{0,1\}^n : \text {Time} (M_2,w)=n$ (there exists an input of any length on which the TM runs in linear time)


texts: Conditions to apply Source Coding Theorem

texts:
I was wondering what are the conditions to apply source coding theorem (SCT).

1. Is it applied only to uniform-length coding, what about variable-length coding, does it also satisfy SCT?

I was asking because in my lecture, SCT is only discussed in uniform coding section.

2. Is the result of SCT for uniquely decodable coding or is it for lossless coding?

In Wikipedia SCT, it's said $f$ is unique decodable code, then we have SCT. In my lecture, it gives me an impression that SCT is generally applied to all lossless coding.


texts: How to express a structure of a 5-colorable graph in logic

texts:
A graph can be expressed as an structure $G = <A,R>$ satisfying the axioms
$ \forall xy R(x,y) \rightarrow R(y,x)$ and $ \forall x \lnot R(x,x)$.

How to extend the structure and/or axioms to express a 5 colourable graph?


texts: Algorithm that finds minimum distance travelled while reordering a set of boxes with a forklift

texts:
Question:  There are n+1 loading docks. a permutation of boxes 1->n is placed on the first n. there is a fork that can move one box to an empty location at a time.   Give an algorithm to sort then boxes with minimum distance travelled.

Answers:

Case A:  If distance travelled includes distance traveled by the fork without a box, then it is also an algorithm to minimize number of operations and can be done in-place. So, In-place quick-sort or heap-sort.

Case B:  If distance travelled only includes that done with a box, then  the following heuristic algorithm comes to my head

empty dock = N
for(index = N-1,...0)
   if(dock[index] == index) continue;

   if(dock[N] == index) move dock[N] to index
   else
      search for dock, X, s.t dock[X] == index
           move dock[index] to dock[empty dock] (initially dock[N])
           move dock[X] to dock[index]
           if(dock[empty dock] == X) move dock[empty dock] to dock[X]
           else empty dock = X

Basic idea is that this minimizes the distance travelled to move a box to its final location.  But I don't know if this leads to global minimum since there is also the temporary storage of the displaced box (Starting from N-1 tries to minimize the temporary movement of displaced box but I don't know if this always holds as the algorithm continues).

I don't have the mathematical background to prove it is minimizes distance. Is there some well known algorithm that this problem maps to or is there a mathematical way to come up with algorithm the leads to minimum?


texts: Subset sum exponential solution - how does the sorting work?

texts:
The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements.  You then generate all the subsets for each list (each having $2^{N/2}$ subsets).  It then states...

"Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time $O(2^{N/2}N)$. However, given a sorted list of sums for k elements, the list can be expanded to two sorted lists with the introduction of a (k + 1)st element, and these two sorted lists can be merged in time $O(2^{k})$."

Can someone illustrate/explain this part of the algorithm?


texts: How do you compute and compare the delays between a (4:2) compressor and (3,2) counter carry save tree?

texts:
My question: How is Table 6.8 shown below computed for different operands? For example, for 3 operands how did they compute:

Number of levels using (3,2) = 1

Number of levels using (4;2) = 1

Equivalent delay: 1.5

Or how about for 9 operands how did they compute:

Number of levels using (3,2) = 4

Number of levels using (4;2) = 3

Equivalent Delay: 4.5

The textbook also points out that the equivalent delay of a (4;2) compressor carry save tree with 9 operands (4.5) is bigger than that of a carry save tree using (3,2) counters.  Why is that?

What are the general conditions when one is bigger than the other?

The following is an image of a (4:2) compressor taken from this book.

The truth table provided for this compressor is:

where $a=b=c=1$ and $d=e=f=0$.  I think these constants are used to generalize the circuit.

  An adder tree that uses (4;2) compressors will have a more regular
  struc-ture and may have a lower delay than an ordinary CSA tree made
  of (3,2) counters. Table 6.8 compares the delays of carry-save trees
  using either (3,2) counters or (4;2) compressors. Since the delay of a
  (4;2) compressor is 1.5 times that of a (3,2) counter, the number of
  levels of (4;2) compressors in column 3 is multiplied by 1.5 to yield
  the equivalent delay in column 4. Note that the equivalent delay of a
  carry save tree using (4;2) compressors (column 4) is not always
  smaller than that of a carry save tree using (3,2) counters (column
  2). For example, for nine partial products, (3,2) counters will yield
  a carry save tree with an overall lower delay. Various other counters
  and compressors can be employed in the implementation of the addition
  tree for the partial product accumulation; for example, (7,3) counters

Please look at the bold face sentence above:


texts:
I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing to me:

Suppose we number the probabilistic Turing machines and define the probabilistic halting function $h_p(x)$ to be 1 if machine $x$ halts on input of $x$ with probability at least 1/2 and 0 if machine $x$ halts on input of $x$ with probability less than 1/2. Show that there is no probabilistic Turing machine which can output $h_p(x)$ with probability of correctness strictly greater than 1/2 for all $x$.

I'm sure we're supposed to assume that there is a probabilistic Turing machine that does this, and then show that we can solve the deterministic halting problem using this machine, thus obtaining a contradiction. I don't have a clue how to go from this probabilistic Turing machine to a deterministic one, though.


texts: Find a subgraph whose edge weights sum to at least the number of nodes

texts:
Given a graph G = (V,E)
  every edge is assigned a real number Xe $\in$ [0,1]

  The sum of x variables for all edges is equal to the number of edges -1 : $\sum x_V = |V|-1$

  For a subset S $\subset$ V let us denote by $E_{(S)}$ the set of all edges with both endpoints in the subset S.

  Give a polynomial time algorithm that takes as an input graph G and numbers $X_e$ for e $\in$ E, and either finds a subset S such that

  $\sum_{e \in E(s)} X_e  > |S|-1 $

  or says that no such set S exists.

Analysis of its correctness and its running time.

Any suggestion please ?

---------------------------- IDEAS

min-cut project selection
min-cut baseball elimination
dynamic programming

I was trying to build a list of dictionaries, storing for each node, the sum of the edges of every subgraph in which it is.

work in progress..


texts:
I am trying to find all mother vertex in a directed graph.

A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

My Approach:

Do DFS on each vertex and check if all the vertex are reached on each start node.
Time complexity : O(V*(V+E)).

I am looking for any better solutions with better complexity.

Any help would be appreciated.


texts: Turing reducibility implies mapping reducibility

texts:
The question is whether the following statement is true or false:

$A \leq_T B \implies A \leq_m B$

I know that if $A \leq_T B$ then there is an oracle which can decide A relative to B. I know that this is not enough to say that there is a computable function from A to B that can satisfy the reduction.

I don't know how to word this in the proper way or if what I'm saying is enough to say that the statement is false. How would I go about showing this?

EDIT: This is not a homework problem per se, I'm reviewing for a test.
Where $\leq_T$ is Turing reducibility, and $\leq_m$ is mapping reducibility.


texts: Why does the following Backus-Naur form reflect the following syntax diagram?

texts:
The definition of the variable

< number>::=< digit > | < digit >< number >

where < digit >  is defined as

< digit > ::= 1|2|3|4|5

Apparently reflects the following syntax diagram

Please explain why this is the case. I am particularly confused with the clause after the vertical OR line (i.e. < digit >< number >) and whether it has something to do with the fact that number can consist of many digits.


texts:
Consider the DFA, M=({1, 2, 3, 4, 5, 6}, {a, b}, 1, {2, 5}, δ), whose δ is specified below.

I calculated the following and got unmarked states (5,2) and (6,3)

(6,3) looks okay but there is something wrong with (5,2).It is not deterministic so where did I go wrong?


texts: Programming languages and Model of computations

texts:
I am learning about model of computation and I found this wikipedia entry that categorises and outlines various model of computation.
Now I want to know the programming languages that builds on these models.
I am aware that functional programming languages are built upon lambda calculus, and that imperative programming is more or less as a result of Turing machine model. But I do not know about the other models and if any programming language have been designed based on them.
Anyone knows if there are languages that builds on model of computation listed on the wikipedia entry?


texts: design of self-loops and final states in fsm

texts:
I am learning about automata and finite state machines. Consider the following automaton, that accepts the word 'ab', does not have to be infinite, just once:

alphabet: 'a','b'
states: 1,2, 3 (3 is the final state and 1 is the initial state)

transitions:

state 1, symbol a, state 2
state 2, symbol b, state 3

First part of my questions:

Question 1. Is it required to add self-loops at 1 for 'b', and a self-loop for 'a' at 2?

Question 2. What about at state 3(final)? Should I add self-loops for 'a' and 'b'?

I basically need to know, how to design my final state. So that even if my alphabet was expanded (say a, b, c), and I have a 'dump' state, with the following transitions:

state 1, symbol a, state 2
state 1, symbol b or c, state dump

state 2, symbol b, state 3
state 2 symbol a or c, state dump

Question 3. Now from final state 3, should I add a transition to dump state, with symbol values a,b,c ???

Your assistance is much appreciated.


texts:
(The question is an extension of this unanswered question on stackoverflow)

If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in a DAG instead of a tree that is even more compact.

However, if we have a set of sets (i.e. the order does not matter), there are a lot of possible tries that represent the same set of elements.
An example can be found in the stackoverflow question I linked above.

Edit: For example, assume that we are given the following sets of integers.

{1,2,3,4,5}
{1,2,6,7}
{1,2,4,7}
{1,3,5,7}

Two possible representations are shown below (trie on the left, DAG on the right)

My questions are:

  How hard is the problem of finding an optimal (i.e minimal) such trie?
  Are there any fast algorithms for solving this problem?
  If not, are there any fast algorithms that find "good" tries?
  What about the DAG case?

In the scenario I have in mind there is an additional constraint that no set is a subset of another set.

Any link/paper that is even slightly relevant to any of the questions is helpful.


texts: How to test if my implementation of tree/graph data structures are correct?

texts:
I've recently implemented RB tree, B-Tree and vEB tree. I was wondering however if there's any rule of thumb for testing if my implementation are actually correct.

Is there any reference that can tell how to develop proper test cases for such data structures?

Besides from mathematical techniques maybe.

What about graph in general?


texts:
I am having a hard time understanding maths behind a 1x1 convolution and how is it actually performed.

Assuming that I have a 6x6x32 input to my 1x1xK convolution layer similar to the one presented in this video and shown below. I understand that I would take a 1x1x32 slice from the input ( blue in the image below), but what operation would I actually perform?

Do I just take one value, let's say at [1,1,1] of yellow and multiply each value in the input slice with this value, or do I multiply each value from the slice with the corresponding value in the 1x1x32 part.

Also what is meant by #filters? Doesn't it need to match 32 in a given example?


texts:
I have a set of $n$ objects $\{1,2,\ldots,n\}$ where object $i$ has weight $w(i)$ and we have a capacity $W$. I would like to pick a subset $S=\{a_1,\ldots,a_m\}\subseteq \{1,2,\ldots,n\}$ of the objects in order to minimize $$\sum_{j=0}^m(a_{j+1}-a_{j}-1),$$ (assuming that $a_0=0$ and $a_{m+1}=n+1$) while respecting the capacity, i.e., $$\sum_{j=1}^mw(a_j)\leq W.$$

The objective is like the sum of gaps between chosen objects.

Is this problem NP-hard or can we find a polynomial time algorithm?


texts: Regex for bit strings with at least two zeros but no consecutive zeros

texts:
This is what I have:

$$(1^*011^*011^*)^*\,.$$

But I don't think this is accounting for an odd number of zeros, like "$10101010101111$". I think I have the right expression that satisfies no 2 consecutive zeros and even number of zeros. Can someone help? Thanks!


texts:
Suppose we have algorithm that is $\Theta(n(t+n^{1/t}))$, where $t>0$ is some parameter. How to select $t$ such that the running time has a minimum rate of growth?

Source: Combinatorial Optimization by Korte and Vygen (I am going through this book by myself but sadly there are no available solutions anywhere online, it seems).

I am not very proficient with math, but my assumption is that I  need to look for $t$ s.t. the second derivative of $n(t+n^{1/t})$ would be 0 (since we are looking for minimal RATE of growth, not for the minimal value of the function itself, so $n^{1+1/t}ln^2(n) = 0$.

Is that a correct approach, or I completely misunderstood the question/concept of the rate of growth?


texts: Show that if $NP\subseteq BPP$ then also $NP=RP$ - considerations about solution

texts:
Show that if $$NP ⊆ BPP$$ then $$NP = RP$$

  Solution: It is enough to show that if $NP ⊆ BPP$ then $3SAT∈ RP$.
  Let $A$ be a $BPP$ algorithm for $3SAT$. Given a formula $ϕ$ with n variables,
  we first run $A$ on $ϕ$. If $A$ rejects, we reject. Otherwise, we try to
  construct a satisfying assignment for $ϕ$ one variable at a time. That
  is, we try instantiating $x_1$ to $0$, and then use $A$ to decide if the
  resulting formula is satisfiable: if so, then we permanently set $x_1$ to
  $0$ and proceed with $x_2$; otherwise we set $x_1$ to $1$ and proceed with $x_2$.
  If we manage to construct a satisfying assignment we accept, otherwise
  we reject, and so on. If $ϕ$ is unsatisfiable, then we always reject. If
  $ϕ$ is satisfiable, then we construct a satisfying assignment and accept
  provided that the $n + 1$ invocations of $A$ that we make are all correct.
  We can ensure that this happens with high probability by replacing
  each invocation of $A$ with $O(\log n)$ independent ones and taking the
  majority answer

It is fine solution from https://people.eecs.berkeley.edu/~luca/cs278-04/notes/sol.pdf

My only question is: Why $O(\log n)$ ? After all, we can run it polynomially to make error probablity exponetially small.


texts: Solving analytic gradient of loss function for neural networks

texts:
Please note that I am talking in about theory rather than ''what someone would do in a real, practical situation''.

Given a multi-layer Perceptron with at least 1 hidden layer, and sigmoid (or other non-linearities), and a loss function, let it be a quadratic loss function such as
$L= ||\phi(X,W)-Y_{target} ||_{2}^2$, where $\phi(X,W)$ is the output of the net, W are the weights, X the data matrix, $Y_{target}$ the correct labels.
I think it does not make sense to solve for $\nabla_W L = 0$ to find a minimum ?
I think it does not because, first of all, the function $L$, even though being ''the square of something'', is non-convex (possibly very complex with many ''hills'' and ''valleys'') and there can be many different values of $W$ giving a value of 0 for the gradient. Moreover, these points (W) where the gradient $\nabla_W L = 0$ could also be maxima rather than minima! Therefore, I think solving $\nabla_W L = 0$ would only make sense if $L$ is convex.

Can someone with good theoretical background answer this/confirm/complete this please?


texts: If a set S is infinite and recognizable, is there an infinite subset of S that is decidable?

texts: If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?


texts: Empty LBA why all the configurations must be all equal

texts: While trying to prove the Empty LBA one of the rules says that for having a computational story you have the 3 rules : and one of the 3 rules says that Ci has to produce Ci+1 and all the configurations must be equal like 001#001....001 and I don't get why. Can anyone help me please ?


texts: How does the index of a disk work in finding the desired address?

texts:
I've been trying to understand computer concepts and such recently and I've been curious to know how the process works of a processor asking for an address and sending the bits to the hard drive, as well as how the hard drive index works when it's just a bunch of magnetic specs that cooperate with a mechanical arm. What does the index say to the system? How do the processor and HDD cooperate? Hopefully I'm asking on the right website this time due to the fact that I accidentally posted this question on the Computational Science site. Thanks

-Ryan


texts: iterating over subsets by switching one element at a time

texts:
How do I iterate over all the $k$-element subsets of $\{1,2,\dots, n\}$ by switching one element at a time?

123
134
234
124
145
245
345
135
235
125

This comes from Ch2 of  Combinatorial Algorithms by Nienhuis and Wilf.

Equivalently I am asking for a Hamiltonian circuit on the Johnson graph of $k$ element subsets of a set of $n$ elements connected if their intersection has $k-1$ elements.

I am trying to understand how the equation $$A(n,k) = A(n-1,k), \overline{ A(n-1,k-1)}\otimes \{n\}$$ from Nienhuis-Wilf leads to a type of "gray code" for subsets.  In fact, it is the gray code when you restruct to $k$-element sets.

Here, $A(n,k)$ is an ordering, looping over the $k$-element subsets of $\{1,2,\dots, n\}$.   The notation $\overline{ A(n-1,k-1)}\otimes \{n\}$ means we should list the $k-1$-element substs of $\{1,2,\dots, n-1\}$ and append the element $n$ to each element of that list.

This equation can also be thought of a set theoretic version of the binomial coefficient identity

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Using this formation I came up a means of listing all the subsets in order.

Here gc(n,k) is returning an array of $k$-element arrays, enumerating the $k$-element subsets of $\{1,2,\dots, n\}$.

def gc(n,k):
    if(k==1):
        return [[i+1] for i in range(n)]
    elif(n == 0):
        return []
    else:
        L = [ x+ [n] for x in gc(n-1,k-1)]
        return gc(n-1,k)+ L[::-1]

How do I find the predecessor or successor of a given subset without generating all the subsets?  I wrote some python code for this, which is different from what is in the textbook.  It still doesn't return the correct answer.

def S(n,k,a):
    if k == 1:
        return [(a[0] + 1)%n]
    elif(a[-1] == n-1):
        return P(n-1,k-1, a[:-1]) + [n-1]
    else:
        return S(n-1,k,a)

def P(n,k,a):
    if k == 1:
        return [(a[0] - 1)%n]
    elif(a[-1] == n-1):
        return S(n-1,k-1, a[:-1]) + [n-1]
    else:
        return P(n-1,k,a)

This looks pretty close to the recursion in Nienhuis-Wilf but I would like to understand where I am going wrong in my implementation.


texts: A variant of hitting set problem? Is this also a NP-hard problem?

texts:
Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\{S_1,S_2,S_3,S_4,S_5,S_6\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$,  it is easy to know that a minimum hitting set is $\{2,4\}$.

I am thinking what this "hitting set" problem would be if the set $S$ is also a collection of sets.
For instance, given
$S_1=\{\{1,2,3\},\{3,4\},\{1,2\}\}$,
$S_2=\{\{3\},\{3,5\},\{1,3\}\}$,
$S_3=\{\{2,5\},\{4\},\{1,5\},\{1,10,6,7\}\}$,
and in this new problem, the "hitting set  $H$" should be a set that:
1. For each $S_i$, there must exist an element $s$ which is a subset of $H$;
2. The cardinality of $H$ is as small as possible.

Therefore, we can see that $\{3,4\}$ is a solution.

It looks like I am trying to select an element from each set where each is a collection of sets, and then the cardinality of the union of these selected elements is as small as possible.

Does anyone have an idea to solve this problem? Do you think it is a variant of hitting set problem? Is it an NP-hard problem?


texts: I have searched but didn't get any exact difference between RAM and a buffer. If both are used for temporary storage, then why they are named differently while both having same property?


texts: Is there a generic word for "thread or process"?

texts:
I'm writing about a problem that could be caused by race conditions between multiple threads, or OS-level processes on the same machine or different machines, or VM-level processes like the Erlang VM has.

In this context, the fact of parallel execution is the important part; the language or memory-sharing model is irrelevant.

Is there a generic word that means "thread or process"? "Concurrent unit of execution" is the best attempt I have so far, but it sounds awkward to me.


texts: defining a programming language grammar for doing arithmetic

texts:
I'm studying programming language design, and I've been taught the grammar below which lets you write basic math expressions.

Exp ::= Num | Exp Op Exp
Op ::= + | - | * | Div
Num ::= Digit | Digit Num
Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

According to the lecturer things like 1 - (2 -3) are not valid as it can't generate expressions with brackets and it can't do -1 because it can't start with -1.

While I understand the first one, the second is a little harder to understand.

Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.


texts: Minimal regular expression from minimal NFA for finite language in polynomial time?

texts:
Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language?

This question is based on a recent question regarding minimization of regular expressions for finite languages given a regular expression. I was surprised to learn there don't appear to be any stronger results. (see Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?)


texts: Showing that a Particular Word Problem is Decidable

texts: I need to give an algorithm to show that the word problem in the group $\langle x,y \mid \mid x^{1984} = y^{2014} = 1 \rangle$ is decidable. How do I show this? I'm not too sure where to start.


texts: Stacking problem, dynamic programming algorithm

texts:
I'm working with a problem that is similar to the box stacking problem that can be solved with a dynamic programming algorithm. I read posts here on SO about it but I have a difficult time understanding the DP approach, and would like some explanation as to how it works. Here's the problem at hand:

  Given $X$ objects, each with its own weight $w$ and strength $s$, how
  many can you stack on top of each other? An object can carry its own
  weight and the sum of all weights on top of it as long as it does not
  exceed its strength.

I understand that it has an optimal substructure, but its the overlapping subproblem part that confuses me. I'm trying to create a recursion tree to see where it would calculate the same thing several times, but I can't figure out if the function would take one or two parameters for example. Also I need to figure out what the recurrence relation is, which I find difficult.


texts: PSH flag in TCP header send a singal to the receiver process?

texts: we know that when TCP data is received with PSH set, it will immediately transfer the received data to the application.and let's when pushed data arrives the receiver side and the receiver application is not reading any data(busy with other tasks). then how does the receiver pass the data to its application process since the receiver's process is not even reading data?is a signal sth like SIGXXX triggered and sent to receiver process to notify it that pushed data has arrived and you need to process it immediately?


texts: Is hedge union always as fast as divide and conquer?

texts:
Adams describes a divide-and-conquer algorithm for finding the union of two sets (represented as weight-balanced binary search trees). He then describes a then-new "hedge union" algorithm which he claims improves on the divide-and-conquer one. However, he does not offer a proof, or even a real explanation, of why it should be $O(m + n)$, let alone why it should be faster than divide-and-conquer.

Blelloch, Ferizovic, and Sun show that Adams's divide-and-conquer algorithm actually attains the theoretically optimal $\Theta (m \log (n/m + 1))$ where $m \le n$. They do not, however, address the hedge union algorithm.

Is hedge union, in fact, as efficient as divide-and-conquer? The least obvious part is the inner trim. It appears, at least superficially, to duplicate work between the left and right subtrees that the full split shares between them. Perhaps this is okay for some reason, but I don't know why.

A further inquiry: Haskell's Data.Set and Data.Map use hedge variants of intersection and difference, as well as union. I have not found any published discussion of those algorithms at all. Similar questions apply to these as well.


texts: explain ackerman's recursion. how long it takes to execute the following code for an average PC

texts:
how does  that recursion work

#include <stdio.h>

int ack(m,n)
int m,n;
{
int ans;
if (m == 0) ans = n+1;
else if (n == 0) ans = ack(m-1,1);
else ans = ack(m-1, ack(m,n-1));
return (ans);
}

int main (argc, argv)
int argc; char ** argv;

{ int i,j;
for (i=0; i<6; i++)
for (j=0;j<6; j++)

printf ("ackerman (%d,%d) is: %d\n",i,j, ack(i,j));
}


texts: Formula for number of attempts to insert a value into a hash table using linear probing

texts:
Suppose I have the simple hash-probe function and we are using linear probing

(k,i) = (k + i) mod m

Assume that there are 3 keys that need to be inserted(k1,k2,k3).
Is there a formula for the average number of attempts required to insert each of the 3 keys?

I know that the avg. no of attempts to insert k1 = 1, since there is no values in the table yet, so it cannot collide with anything so will always take 1 attempt. However i'm struggling to come up with a formula for k2,k3.


texts: Can a DFA have two symbols on one arrow?

texts:
I know that a DFA has to have exactly one transition for each symbol in the alphabet, but is it allowed to have two symbols on the same arrow? If, for example, I have a DFA with states $q_0$ and $q_1$, can I have one arrow from $q_0$ to $q_1$ with both $a$ and $b$?

This may be a stupid question, but I need to be completely sure that this is allowed (I believe it is).


texts: How can I create an algorithm in pseudo-code generating a sequence of numbers in such an order that they only are different at one position by 1?

texts:
Let's say we want to create sequences of the numbers {0,1,2} which are all at length n
What I want to create is an algorithm which generates (and outputs) such sequences that they are only different at one position by 1.
This is what I mean, for n=4
0000
0001
0002
0012
0022
0021
0020
0010
0110
0111
etc.
I think you get the idea behind that. Something like:
0002
0010
is not possible
So how should I create such algorithm (in Pseudo-Code)?


texts:
I always thought that TSP currently requires time exponential in the number of cities to solve.

  How, then, has Concorde optimally solved a TSP instance with
  85,900 cities?!?

Is this a typo? Is the base of the exponential 1.0000000000000001 or similar? Was it an instance specifically constructed to be solvable easily? What is the asymptotic runtime of the best known TSP solving algorithm?


texts: Looking for Methods in Computer Vision for Distinguishing Disappearing and Fading Objects

texts:
Suppose I have a video in which there are two objects $A$ and $B$. Object $A$ appears suddenly at time $Ta1$, and then disappears suddenly at time $Ta2$. Object $B$ appears suddenly at time $Tb1$, and then starts to fade gradually at time $Tb2$, and at $Tb3$ the object $B$ completely fades away. The background intensity is nearly constant, but is changing at a slope $s$ ($s$ can be a very small positive, zero or very small negative) in the long run. For simplicity, we can assume the objects never move. Also, the time $Ta1$, $Ta2$, $Tb1$, $Tb2$ and $Tb3$ are not known beforehand, they can only be inferred from the data or the graphs.

In the graphs below, (a) shows the intensity of a pixel where object $A$ appears against time, (b) shows the intensity of a pixel where object $B$ appears against time, and (c) shows the intensity of a background pixel against time. The graph on the left hand side is the theoretical plot, while the graph on the right hand side is the actual plot from my data. In all graphs, the slope $s$ is a very small positive number.

I tried to use the Running Gaussian Average with Selective Background Update method. It is quite successful in segmenting the background from the objects $A$ and $B$, except that a slight amount of background may be wrongly regarded as foreground at a late time (when the intensity of the background increases by a certain amount). But leaving this issue aside, I would like to do one step further, that is, to distinguish between objects $A$ and $B$. Surely if $Ta1=Tb1$ and $Ta2=Tb2$, the distinction can only be made after $Tb2$ (or even $Tb3$). But what methods can be applied to perform the distinction?


texts: Two Step Verification. 4 digits vs 6 digits

texts: From a security level standpoint (such as Server, DataBase, Token Code, Authorization, Authentication, etc.) in regarding the Two Step Verification, usually Apple send a total of 4 digits security code vs Google send a total of 6 digits security code. What are the main differences?


texts: Key differences between interactive and time sharing operating systems?

texts:
Couldn't find much online on how an interactive system is different from a time-sharing system, or the different traits of both.

My understanding of a time-sharing system is many people at terminals being able to use the system at the same time, and the CPU's aim is to maximise response time not CPU time (unlike a multiprogrammed batch system). The switches between jobs are very frequent, and users get immediate responses, when for example submitting interrupts via keyboard inputs. There is very little CPU idle time, duplication of software etc, but it is less reliable, there might be lower security and integrity, and potentially bad data communication. An example would be a chat messaging client or system.


texts: What is an appropriate global optimization technique for a noisy and expensive function?

texts:
I have a function which takes 22 real-valued parameters as input that returns a real value. The function is reasonably fast for low return values (ms/seconds/minutes), but takes much longer (minutes/hours) to compute for high/optimal values. The noise will also increase with higher values.

I expect the function to contain many local maxima, and I cannot use vanilla gradient descent.

I want to find the parameters that maximize the expected return value.

As this is going to run on a desktop computer, I don't mind storing all inputs and results in memory, as the limitation is probably going to be the run-time anyway.

Do you have any suggestions for an appropriate optimization algorithm?


texts: Maximum boundary edges amount of union of rectangles

texts:
I've read that the maximum boundary edges amount of union of $n$ rectangles, named $p$, is bounded by

  $p \leq n^2 + 4n$

I tried to prove this by induction, but it's seems too difficult to me, can anyone help me with the proof? thanks.

an induction try:
$n = 1$, $p = 4 \leq 1^2 + 4$ is clear.
assume when $n = m$, $p \leq m^2 + 4m$ is correct
when $n = m + 1$,  $p <= m^2 + 4m + (boundary\ egdes\ generate\ by\ the\ m+1 th\ rectangle)$
$......\ (after\ some\ steps)$
 $p \leq m^2 + 2m + 1 + 4m + 4$
 $p \leq (m+1)^2 + 4(m+1)$   end of proof
here is an example of boundary edges(red line part)
can draw a $p = n^2+4n$ case if $n$ is even (upper bound seems not tight when $n$ is odd)
origin claim is here (page 8 line 21) if needed link

(p.s. It's first time I post a question, I apologize if it's hard too read)


texts: Why is the language of TMs that have some quadratic time bound undecidable?

texts:
The language in question is $L = \{M : M \text{ is a Turing machine that halts in } 100n^2 + 200 \text{ time}\}$.

Attempt 1

Suppose $L$ is decidable. Let $M_1, M_2, \ldots$ be the Turing machines in $L$. Now construct a new Turing machine $M$ that works as follows:

on input of length $n$ run $M_n$ and output the opposite answer

On the one hand, $M \in L$ since it halts in the appropriate time. On the other hand, $M \notin L$ because it is different from every machine in $L$. Therefore $L$ is undecidable.

Is this correct?

Something that bothers me: I think I am only using the fact that there are countably many Turing machines; I never used the fact that there is some TM that decides $L$.

Attempt 2

As suggested, here's a new Turing machine $M'$:

M'(M,x,1^n):
    if M is not a valid Turing machine then halt
    otherwise
        run M(x) for 100n^2+200 steps
        if it halts, then run forever
        otherwise halt

Ask oracle: does $M'(M,x, 1^n)$ halt on all inputs within $100n^2+200$ steps?

If yes, then $M$ doesn't halt on input $x$.

If no, then some input causes it to loop forever, which means $M$ halted on $x$ in a certain amount of time.

This would allow us to decide the halting problem, which we know is undecidable.

Is this correct? If so, I still think of the details are a bit fuzzy... For example, it's a bit unclear to me as to what happens with the inputs $M$ and $x$ are very large...


texts: Language in PSPACE that isn't PSPACE-hard and isn't in PH

texts:
Can there exist a language L in PSPACE such that L isn't PSPACE-hard and L isn't in the polynomial hierarchy (PH)? Intuitively, it seems like the answer is no, since TQBF is PSPACE-complete, and any version of TQBF bounded finitely to i alternating quantifiers is complete for one part (depending on whether it starts with the existential or universal quantifier) of the i-th level of the polynomial hierarchy. But, I'm unsure how one might go past this intuition to make a convincing argument.
To put it more abstractly, I'm wondering if there can exist a set of languages "layered" between PH and PSPACE, or whether the completeness of these QBF problems constrains their boundary (if there is one -- open question, I know) to have no such fillable gap.


texts:
I am trying to convert a XML based configuration to JAVA based configuration. Can someone please let me know the java annotation based configuration for the following

  <int-amqp:inbound-channel-adapter
    channel="ids-callForth"
    queue-names="${app.callForthQueue}"
    connection-factory="rabbitConnectionFactory"
    error-channel="rabbitErrorChannel" />


texts: structure of cache when CPU uses words smaller than the main memory

texts:
As the title says, i have the following excersice:

An associative mapping cache with four lines in each set, can store in each line two words of 16 bits each. It can store 4K words, that they have length 32bits from Main memory. The CPU is 16 bits and the address that he produces is 24 bits length. So the solution is shown below:

I can understand why set has 10 bits, or why tag is 12, but I can't figure out the word select and byte select signals. Also how can this cache store two words as the image shows (Word 0 and Word 1), when the line size is 16 bit, but the word size from Main Memory is 32 bits.


texts:
I am implementing a Naive Bayes algorithm for text categorization with Laplacian smoothing. The problem I am having is that the probability approaches zero because I am multiplying many small fractions. Therefore, the probability eventually yields zero. This is because there are several words within the documents and training sets.

Because of this, I am not able to categorize the texts. Is there a way I can get around this problem? Am I doing something wrong in my implementation?


texts: Computational complexity of described algorithm

texts: Is algorithm which schedules tasks to machine and then for every time point in the makespan of machine does an operation considered pseudo-polynomial or quasi-polynomial? (if machine execute tasks from time 0 to 100 then it goes over every time point 0,1,2...100 separately and executes O(1) action) I would guess pseudo-polynomial as it is very similar to Dynamic programming but I'm not sure and I don't know how to validate it.


texts: How do you proceed if your milp is not solvable

texts:
We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical).

We went with a very simple aproach (make a cube person x visit x Time and add constraints from here on). Our solution works well if the problem is solvable.

Our customer needs a solution with alternative options if the problem is not solvable, for example "here is a possible solution with X more people" or "a solution with 2 hours more worktime".

Our initial thoughts were to extend our people / time cube by a given number of cells and then add high penalty values to our goal function for these values.

Does anyone have a better idea / knows what is common practice?


texts:
I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below:

The director of a hospital want to schedule a working plan for a nurse
in a given period of N consecutive days 1,..., N. Due to the policy of
the hospital, each nurse cannot work all the days 1,..., N. Instead,
there must be days off in which the nurse need to take a rest. A
working plan is a sequence of disjoint working periods. A working
period of a nurse is defined to be a sequence of consecutive days on
which the nurse must work and the length of the working period is the
number of consecutive days of that working period. The hospital
imposes two constraints:
Each nurse can take a rest only one day between two consecutive
working periods. it means that if the nurse takes a rest today, then
she has to work tomorrow (1)
The length of each working period must be greater or equal to K1 and
less than or equal to K2 (2)
The director of the hospital want to know how many possible working
plans satisfying above constraint?
input
6 2 3
output
4

I have thought a lot and just give an initial idea: I will use an 1-D array to represent a schedule from day 1 to day N. for each day (ith day), I have two choices: the nurse will work this day or the nurse will not work on this day.
If the nurse does not work on the ith day, the ways for this case is the total ways of the ith-2 day. (Because she must have a day off on the previous day.
Else, the ways for this case will be the sum of total ways of the ith-j day, with j in [K1, K2].
However, I do not know why I am wrong and which way will be the correct answer. I really need your help to derive an appropriate algorithm


texts:
B-tree is a data structure, which looks like this:

If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I need to go through several elements in the child-node to find its right child-node etc.

The point is, when I have $n$ elements in every node, then I have to go through all of them in the worst case. So, we have $O(n)$ complexity for searching in one node.

Then, we must go through all the levels of the structure, and they're $log_m N$ of them, $m$ being the order of B-tree and $N$ the number of all elements in the tree. So here, we have $O(log N)$ complexity in the worst case.

Putting these information together, we should have $O(n) * O(log n) = O(n * log n)$ complexity.

But the complexity is just $O(log n)$ - why? What am I doing wrong?


texts:
I understand that a PDA is an automata with a stack (LIFO) but I still can't understand how to answer a very simple question like this one.  I've read so many pages on it, searched all over Google, watched countless videos on YouTube & yet I still can't grasp this for the life of me.  This is my last resort.

I know if I understand this problem, I'll be able to the others.

Thanks for taking the time to read.

Let L be the language accepted by the pushdown automaton:
M = (Q, ∑, gamma, delta, q, F)
where:
Q = {q,s};
∑ = {a,b};
gamma = {B};
F = {s};
and the transition function delta is defined as follows:

[q,a,λ,s,B]
[s,a,λ,s,λ]
[s,b,B,s,λ]

Write a regular expression that defines L.


texts: A $log(k)$ algorithm for the matroid secretary problem

texts:
I'm reading the following article that presents a $log(k)$ algorithm for your secretary problem.

I'm in the analysis section at the left part of page 5 there is the following claim:

  $B^*$ is a set with elements $x_1,...,x_k$ with respective values
  $v_1,...,v_k$ where $v_1\geq...\geq v_k$. Denote $n_i(B^*)$ as the number of
  elements in $B^*$ with value at least $v_i$. Then the sum of the $q$
  largest elements is
  $[\sum_{i=1}^{q-1}(v_{i+1}-v_{i})n_{i}(B^{*})]+v_{q}n_{q}(B^{*})$

I fail to see how the sum presented is the sum of the largest $q$ elements. From what I understand $n_{i}(B^{*})=i$ since the elements with value at least $v_{i} $ are $v_{1},...,v_{i}$.

If I open the sum than all the inner element ($v_{2},...,v_{q-1}$) has a coefficient of $1$, but the coefficient of $v_{1}$ is $-1$ and the coefficient of $v_{q}$ is $2q$.

Can someone help me understand this equality?


texts:
I am reverse-engineering a file format that contains in some places in the binary file what should be a representation of integer numbers. However, I cannot make sense of the relation between the bytes values and the numbers. The sample data I have is the following. Only two bytes seem to be relevant. I have also included the bits representation for convenience.

Number  Hex          Bits
  32   00 42   0000000 01000010
  64   80 42   1000000 01000010
  96   c0 42   1100000 01000010
 128   00 43   0000000 01000011
 160   20 43   0010000 01000011
 192   40 43   0100000 01000011
 224   60 43   0110000 01000011
 256   80 43   1000000 01000011
 288   90 43   1001000 01000011
 320   a0 43   1010000 01000011
 480   f0 43   1111000 01000011
 512   00 44   0000000 01000100
 544   08 44   0000100 01000100
 992   78 44   0111100 01000100
1024   80 44   1000000 01000100
1056   84 44   1000000 01000100
2016   fc 44   1111100 01000100
2048   00 45   0000000 01000101

What is the relation between the values in hexadecimal (or bits) and the decimal numbers? Does this correspond to a common data type? For the second question, it might be relevant to know that the two bytes to the left of the bytes above and the two bytes to the right are always set to zero.


texts: Solving a modified Travelling Salesman Problem(TSP)

texts: I am trying to solve a modified version of the TSP. In my version, multiple visits to a city are allowed, as long as the path is the shortest, and also, only subset of the cities are compulsory to visit, as in, you can go through other cities to visit all the subset cities if path is shorter, but if not, the other cities can be ignored. For simplicity, starting city is fixed. Also, all cities are not connected to others directly. I know approx. solutions for the traditional TSP, but, I have trouble solving this one. A naive approach can be to find all possible combinations of the subset cities and check which has the shortest total path length, but that solution will have a n^2 complexity for trying each combination, plus the complexity for finding shortest path for each two cities. So, what should I use to solve this problem?


texts: Determine if a language is Decidable or semi decidable

texts:
Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$.
We need to determine, without using Rice's Theorem, whether:

$L\in \text{R}$, i.e., $L$ is decidable.
$L \in \text{RE}\setminus \text{R}$, i.e., $L$ is semi-decidable but not decidable
$L \notin \text{RE}$, i.e., $L$ is not semi-decidable.

Any hints or some steps on how to approach this problem would be appreciated.
Also, if $L\notin \text{R}$, can we prove that using Rice's Theorem?


texts: Transitive reduction with vertex additions?

texts:
The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In some cases, the addition of vertices can considerably reduce the number of edges required. For example, a complete bipartite digraph $K_{a,b}$ has $a + b$ veritices and $ab$ edges, but the addition of a single vertex in the middle results in a digraph with the same reachability relation that has $a + b + 1$ vertices and only $a + b$ edges.

More formally, given a directed graph $G = (V, E)$, the challenge is to find $G' = (V', E')$ and injective function $f: V \rightarrow V'$ such that $f(b)$ is reachable from $f(a)$ in $G'$ if and only if $b$ is reachable from $a$ in $G$ and such that $|E'|$ is minimized.

Are there any known results or algorithms related to this problem?


texts: Asymptotic calculation check for triple-nested for-loops

texts:
I have the following repetition structure:

sum = 0
for (i = 0; i < n; i++) {
   for (j = 0; j < i*i; j++) {
      for (k = 0; k < j; k++) {
         sum++
      }
   }
}

By the following, I have reasoned the runtime of this structure to be in $O(n^7)$ :

$\sum_{i=1}^{n} (\sum_{j=1}^{i^2}(\sum_{k=1}^{j} k))$

$= \sum_{i=1}^{n}(\sum_{j=1}^{i^2}(\frac{j^2+j}{2}))$

$= \frac{1}{2} (\sum_{i=1}^{n}(\sum_{j=1}^{i^2}j^2 + \sum_{j=1}^{i^2}j))$

$= \frac{1}{2} (\sum_{i=1}^{n}(\frac{i^2(i^2+1)(2i^2+1)}{6} + \frac{i^2(i^2+1)}{2}))$

$= \frac{1}{2} (\sum_{i=1}^{n} \frac{2i^6+3i^4+i^2}{6} + \sum_{i=1}^{n} \frac{i^4+i^2}{2})$

$= \frac{1}{2} (\frac{1}{3} \sum_{i=1}^{n} i^6 + \frac{1}{2} \sum_{i=1}^{n} i^4 + \frac{1}{6} \sum_{i=1}^{n} i^2 + \frac{1}{2} \sum_{i=1}^{n} i^4 + \frac{1}{2} \sum_{i=1}^{n} i^2)$

$=\frac{1}{6} \sum_{i=1}^{n} i^6 + \frac{1}{2} \sum_{i=1}^{n} i^4 +\frac{1}{3} \sum_{i=1}^{n} i^2$

$\approx \frac{n^7}{42} + \frac{n^5}{10} + \frac{n^3}{9}$

$\therefore \text{runtime} \in O(n^7)$

The approximation at the end comes from the rule:

$\sum_{i=1}^{n} i^k \approx \frac{n^{k+1}}{k+1}$

Is this correct? I'm fairly confident that it is but some of the results that I've gotten from running the structure in JMH (Java Micro-Benchmarking Harness) don't really reflect this result so I just want to confirm.


texts: Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?