texts: Give one example where it takes Non- deterministically exponential time to solve the problem?

texts: I am a starter in complexity theory though I have fair knowledge in Turing machine. I know what it means to be non-deterministically polynomial time solvable but I am trying to understand where the time goes beyond polynomial time even using non-deterministic concept. Is it possible or we can do everything in polynomial time using non-deterministic concept though in reality it can not be implemented. Therefore, I am looking for an example where we can't do it in polynomial time rather it takes exponential time even after using non-deterministic concept. Please explain clearly why it takes exponential time(non-deterministically).


texts:
if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting state itself, right?

the starting state accepts 0,1 so I can essentially take the string 1010 and self loop it in the starting state itself... is that correct?


texts: NP problems with exponentially complex average time solution?

texts:
Assuming $P \ne NP$, is there a problem such that is NP such that:

There is always a solution

Alternatively, there is asymptotically almost surely a solution

On average, it takes exponential time to solve
The probability distribution can be any distribution which can be sampled from in polynomial time.

Also, what would such a complexity class be called?


texts: Is there a reasonable algorithm to generate a certain "independent clique graph" with minimal vertices?

texts:
In the process of trying to find a solution to the rat and poison puzzle with two rats, I've found myself needing the solve the following problem, in polynomial time:

Given any $k_0, k_1, k_2,..., k_{n-1} \in [2,\infty)$, we want to produce a simple graph $G = (V, E)$ and some $c_0, c_1, c_2,..., c_{n-1} \subseteq V$ such that:

Each set of vertices $c_i$ is a clique of size $k_i$ in $G$
For all $(u, v) \in E$, there exists exactly one $c_i$ such that $u, v \in c_i$
$|V|$ is minimal.

This essentially means that we want a graph with at least $n$ cliques, each of size $k_i$, such that each edge is in exactly one of these cliques, and we want the smallest such graph. Extra cliques that aren't represented by a $c_i$ will still occur but don't count as overlap, so $G$ isn't generally a block graph.


texts: How does consistency imply that a heuristic is also admissible?

texts:
A heuristic function $h (n)$ is...

Consistent if the estimated cost from node $n$ to the goal is no greater than the step cost to its successor $n'$ plus the estimated cost from the successor to the goal.
Admissible if $h(n)$ never overestimates the true cost to the goal state.

The textbook for my Artificial Intelligence course states that consistency is stronger than admissibility but does not prove it, and I'm having trouble coming up with a mathematical explanation.


texts: Calculate the sum of all sub-arrays with given indices

texts:
I am new to Algorithms and Competitive Coding. I have a problem as follow:

For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic Programming or any other way which can run in less than O(nlogn) or even O(n) and the limit memory is 256 Mb.
Initially, I have a simple approach to dynamic programming as follows: I just create a table size nxn and fill it with numbers that represent the minimum element from the index I to index j (i <= j). After that, I refer to the given indexes (ik and jk) on the table and add them up.
However, as submitting the code as the previous approach, I get 3 cases of wrong answers and even runtime errors. The runtime error is due to the input constraint: up to 10^6 elements which cause the exceed of memory (10^6 * 10^6 = 10^12, which is very large). I also get accepted status on 3 tests however, the number of wrong answers makes me quite confused. I really need your help to check and update the algorithms.
Sample test case:
Input:

16

2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4

4

1 5

0 9

1 15

6 10

Output:

6

void make_table()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            if(i == j)
            {
                Table[i][j] = arr[i];
            }
            else
            {
                Table[i][j] = min(arr[j], Table[i][j - 1]);
            }
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    make_table();
    ll sum = 0;
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        sum += Table[x][y];
    }
    cout << sum << endl;
}
```


texts: Minimum cost of wood for woodworking project problem

texts:
This is a fun one, I really can't wrap my head around it. It's like an n-sum problem combined w/ a knapsack problem and I cant seem to find a solution.
I'm currently building a cabinet, and had just enough wood that if I calculated my cuts right, I would've had enough, if I had even cut one certain length from one board instead of another, Id have needed an extra length of wood and would have to go back to the store. And it made me start thinking about if there is a non brute force solution for calculating the minimum amount of wood lengths I needed.
Then started to think about it further, given a bin of infinite lengths of wood in various lengths. Ie: infinite 96", infinite 72", etc, and a cost for each. What would be the minimum cost of wood I'd need to buy.
So the problem would be like, given lengths of wood that have a certain price:
{ cost: 3, length: 96 },
{ cost: 2, length: 72 },
{ cost: 4, length: 144}

And a list of cuts (lengths) needed,
[ 24, 24, 24, 24, 48, 48, 48, 48, 36, 36, 36, 36 ]

What would be the cheapest combination of wood pieces I could buy and still have enough wood.
(Lets assume that we do not have to take into account the amount of wood lost during a cut due to the width of the blade)


texts: Turing machine generating $a^b$ for given a and b

texts:
I want to draw an state diagram for a Turing machine such as:
If "a" and "b" are the inputs, output in tape will be $a^b$.
I saw many Turing machines that output:
$a+b$ $~~$ ,$~~$ $a-b$ $~~$ , $~~$$a*b$ $~~$ ,$~~$ $a/b$
And also I know how to design a Turing machine for accepting $x^{2^n}$,$x^{3^n}$ and ...
But for generating I have no idea...
Question 1:
Is it possible to improve $a*b$ Turing machine inorder to generate $a^b$  ?  How ?
Question 2:
Should we add more than one tape to this machine or thats easy to show even with only one tape?


texts: What are the simplest known algorithms to compute PI?

texts: There are many algorithms that compute PI. Some are obviously complex, involving huge formulas and constants. Some formulas are not that complex, but involve operators such as division which is somewhat complex by itself. Is there any algorithm that is inherently simple and could be expressed very tightly on the untyped lambda calculus?


texts: Confluence versus the property of every term having at most one normal form

texts:
If a term rewriting system is confluent, then every term has at most one normal form. Is the converse also true, or is confluence a strictly stronger property? I.e. if every term has at most one normal form, does the rewriting system need to be confluent? My intuition is that the answer is no; for example, it seems to me that you could theoretically have a term rewriting system in which every non-variable term has NO normal form (and thus, at most one normal form), but which is NOT confluent, because you might have one term that has infinite reductions in two different 'directions'. But this is just intuition, not a formal proof or counterexample.

Any help would be appreciated!


texts: Given a TM $T$ does $T$ ever leave the initial state when start tape is blank?

texts:
I want to determine whether this decision problem is decidable. I have tried to establish reductions from Halt and "Accepts empty-string", but I've not yet found a solution.

Can someone help me out?


texts: Approximability of convex programming (convex optimization)

texts:
Convex optimization is defined here: https://cstheory.stackexchange.com/questions/22314/definition-of-convex-optimization-problem-by-stephen-boyd-and-lieven-vandenbergh

The problem is NP-hard: https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti

But is anything known about the approximation complexity of the problem?  Does it have a PTAS (poly time approximation scheme)?  Or is there a proof that a PTAS is impossible unless P=NP?  Are there any known results on upper/lower bounds on its approximability?

Any information will be much appreciated.


texts: How to prove that adding incoming edges to source node doesn't alter the max flow

texts:
I am given a homework assignment on this question:

  Show that if we add any number of incoming arcs, with any capacities, to the source node, the maximum flow value remains unchanged. Similarly, show that if we add any number of outgoing arcs, with any capacities, at the sink node, the maximum flow value remains unchanged.

While, it can be graphically proved with the help of an example, I am unsure of how to prove it systematically (like usual proofs in textbooks)


texts: Show that some context free languages must contain more that one non-terminal

texts: Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular set, there must be some languages that requires more than one non-terminal. How can I show or proof this formally?


texts: For every imperative function, is there a functional counterpart with identical performance or even instructions?

texts:
Currently, I haven't learned about a functional language that can achieve the same performance as C/C++. And I have learned that some languages that favor functional programming to imperative programming, such as Scala and Rust, use imperative ways to implement their library functions for better efficiency.
So here comes my question, on today's comptuters that execute imperative instructions, is this a limitation of the compiler or functional programming itself? For every imperative function with no side effects, either in a language without GC such as C/C++/Rust/assembly or one with GC such as Java, is there a pure functional counterpart in Haskell, Scala, etc. that can be compiled to run with identical performance in time and space (not just asymptotic but exactly the same) or even to the same instructions, with an optimal functional compiler that utilizes all modern and even undiscovered optimization techniques such as tail recursion, laziness, static analysis, formal verification, and so on which I don't know about?
I am aware of the equivalence between λ-computable and Turing computable, but but I couldn't find an answer to this question online. If there is, please share a compiler example or a proof. If not, please explain why and show a counter-example. Or is this a non-trivial open question?

Supplementary edits as suggested by Andrej Bauer:
To be more specific, here are 2 examples that led into thinking about this question.
For example, tail recursion and accumulators can improve the performance of some recursive functions to be identical to an imperative implementation using for. In some cases they might even have the same instructions.
Another example is about laziness in Haskell. Laziness can help avoid unnecessary copying of data structures and make performance better. However, laziness leaves wrappings, closures, etc. in the runtime and still can't make the program as fast as an imperative implementation where there are no such things. So I am wondering whether such things can be statically removed before runtime during compilation.
Supplementary edits as suggested by Nearoo:
The question can also be stated in this way: is there a language that supports both pure functional programming and imperative programming, paired with an optimized compiler, in which every function with no side effects implemented imperatively can be replaced with one implemented purely functionally, at no cost of performance or even compiled to the same instructions?


texts: Prove/disprove: If $_1$ is a finite language but not empty and $_2$ is NOT regular then $_1 \circ _2$ is NOT regular

texts:
That what I have so far, but I am not sure at all.

Assume toward contradiction that $_1 \circ _2$ is regular.

Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $.

Define a regular substitution $\forall\sigma\in\Sigma, h(\sigma) = \sigma'$.

$h(_1) = \{ = '_1'_2 ... '_ |  = _1_2 ... _ \in _1\}$ is also regular and finite by the closure of RL under substitution.

Therefore, by the assumption $h(_1) \circ _2$ is also regular.
Define regular substitution $\forall\sigma'\in\Sigma',g(\sigma')=\varepsilon,\forall\sigma\in\Sigma,g(\sigma)=\sigma$.

$g(h(L_1) \circ _2) = _2$ which is regular by the closure of RL under substitution, in contradiction to the assumption.
Therefore, $_1 \circ _2$ is not regular. Q.E.D

I am not sure about this statement "$h(_1) \circ _2$ is also regular".

Thanks for any help!!


texts: Best algorithm for splitting up departments such that the least unique ones are assigned per day

texts:
I have a collection of people who need to be assigned to one of 10 dates. Each person is in a specific department. The departments have vastly varying amounts of people (from ten to thousands). Each date can accomodate a set amount of people, let's say 5000. My task is to assign each person to a date such that the amount of departments participating that day is as small as possible AND as average as possible. Basically every time you put a new department in a day it adds a lot of overhead (adding people doesn't) which means that doing a lot of departments in a single day is really bad. So for example, 1 huge department being assigned day 1 and 15 small ones being assigned day 2 is undesirable, it's better to do half of department 1 one day, and half on the other and then splitting the small ones such that its basically 7.5 one day and 8.5 on the other. But the less departments particpating in a day, the better. So if you had 3 days and 3 equal departments it would be undesirable to have 3 departments (1/3 of the employees of that department) participating each day, it would be better to have each department on a single day. The 'spots' have to be filled up, that is each day MUST have 5000 participants. Any ideas on how to approach this?

My first thought is to minimize the maximum, that is find a solution such that the highest amount of departments per day is the lowest it can be. Is this the best solution?


texts: What properties of a programming language make compilation impossible?

texts:
Question:

"Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine code of a traditional CPU is not possible. What are these properties?"

Compilers: Principles and Practice by Parag H. Dave and Himanshu B. Dave (May 2, 2012)

The book gives no clue about the answer. I tried to find the answer on Concepts of Programming Languages (SEBESTA), but to no avail. Web searches were of little avail too. Do you have any clue?


texts:
Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well.

Here's the k-key problem: given an undirected graph $G$ and a number $k$, decide whether $G$ contains k $k$-key.

I want to show that the k-key problem is a NP-complete.

I want to make a reduction from the 'Undirected Hamiltonian Cycle' problem in which the input is a graph, and the problem is to decide whether it contains a Hamiltonian path. I already know that this problem is NP-complete. The input for the reduction would be an undirected graph $G$ and the output is $G'$ graph and $k$. Can you please help me understand what manipulation I should do to the original graph in order to show this reduction? And why should it work?


texts: Finding which functions are bounded by $O(n^2)$

texts:
I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$.

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

I choose the answers 1, 2, and 4:

Simplifies to $n \cdot n = n^2$, which is bounded by $O(n^2)$
Simplifies to $\frac{n(n + 1)}{2} = n^2/2 + 1/2$, which is bounded by $O(n^2)$
$n^2 + n$ is obviously not bounded by $O(n^2)$
$1$ is obviously bounded by $O(n^2)$

However, it was alerted to me that one of my answers is incorrect. That seems strange, considering that after expanding all the expressions mathematically, I believe that I have chosen whether they are bounded by $n^2$ correctly.


texts: Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

texts:
I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative state.

Does anyone know what the best way would be to calculate the full set of combination values that fits this constraint?

Right now I just implemented a simple counting algorithm, but that will take forever since I have to test if there are n positive and negative variables at 3^64 levels, and that is before I even start to evaluate the weighting term I am actually interested in.


texts: Is is possible to determine if a given number is xor combination of some numbers?

texts:
I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$d$,$e$)

e.g - ($a$ xor $d$) , ($b$ xor $c$ xor $e$) , ( $a$ xor $e$ )

What i know clearly is that lets say X= ($b$ xor $d$) , Now if I xor X and Y i get
($a$ xor $c$ xor $e$), as ( $b$ xor $b$=0 ) and if it was some number not a xor combination (say $p$ ) then i would have got ($a$ xor $b$ xor $c$ xor $d$ xor $e$ xor $p$)

How should i approach this question?


texts: Compile most likely text based on faulty snippets

texts:
Input: Recognized text from images of labels taken with a cell phone in varying conditions. One image may enclose the entire text, or just a part of it.
Expected output: The most likely version of the original text, ideally with an indication of the certainty. More images will of course provide better results.
Even though it seems to me that this should be a rather common problem, I could not find any research, algorithms or code directly related.
My best idea so far (after three or four attempts of an implementation now discarded for various reasons...) was to find the best matches for various inputs, potentially by finding the longest common substrings, and then generate some sort of tree indicating the most frequent connections between individual characters. Parsing the tree should then return the most likely original. Even though this might work in principle, it's always in the details, and there may be much more efficient solutions out there.
Thanks


texts: Single-source shortest path algorithm for graphs representing stacked behavior

texts:
I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG).

That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent interprocedural call and return. The impact of these is that they determine which edge must be traversed on a call return.

Is there a shortest path algorithm adapted to this kind of graph?

Edit
Clarification: suppose that I am able to identify a pair of nodes of interest (n1, n2) in the graph using a plain boring graph traversal, I want to obtain the shortest path between n1 and n2 that respects the constraints of the graph.


texts: Resolution and incomplete Knowledge Base

texts:
Assume I have an incomplete knowledge base, for example:

(rich(dave), poor(dave))  // dave is either poor or rich

(not rich(dave), not poor(dave))  // dave is not poor and rich at the same time.

My questions are:
1. If I do resolution on the above clauses, will I get the empty clause?  and 2. If Yes, Does that mean my knowledge base is inconsistent?


texts:
I'm trying to understand sorting algorithms. And I'm thinking about a totally different way to tackle sorting: Use array indexes to sort a given set of integers.

Suppose We want to sort a list of positive integers (for now). Let's call it toSortArray

Create a boolean array that has a length equal to maximum integer in toSortArray + 1. Lets call it boolArray. All items in the array are false initially.
Loop through toSortArray and for each integer item, set the boolean at index item true: boolArraty[toSortArray[i]] = true;
Loop through boolArray and if boolArray[i] is true,  set the first element of toSortArray to i

Here is the pseudo-code if the algorithm is not clear:

    var boolArray = new bool[toSortArray.Max() + 1];

    for (int i = 0; i < toSortArray.Length; i++)
    {
        boolArray[toSortArray[i]] = true;
    }

    var index = 0;
    for (int i = 0; i < boolArray.Length; i++)
    {
        if (boolArray[i])
        {
            toSortArray[index] = i;
            index++;
        }
    }

First, Does every body agree that time complexity is O(N)?

Second, Am I missing something about this algorithm (As I don't think I'm the first one thinking about it)?


texts: Algorithm SAGE- PARI? for splitting polynomials over field extension

texts:
I tried to follow with SAGE the solvability of solvable quintic polynomial. I took the example of the solvable polynomial $f=T^5+15T+12$, fully studied in Dummit. I understand that the splitting field $L$ is radical with $[L:\mathbb{Q}]=20$.

The square root of the discriminant is (SAGE)  $2^53^25^2\sqrt5$ so we have a quadratic subfield $k=\mathbb{Q}(\sqrt{5})\subset L$. This polynomial (as a function) is strictly increasing over $\mathbb{R}$  so has a unique real root $x$.  We consider the extension $k(x)/k$ of degree $5$ ($f$ is still irreducible over $k$) so the last extension of the chain of subfields $\mathbb{Q}\subset k=\mathbb{Q}(\sqrt{5})\subset k(x)\subset L$ is quadratic. The polynomial $f$ must split over $k(x)\;(\subset\mathbb{R})$ into a product of the linear factor $(T-x)$ and two quadratic factors $P_1,P_2 \in k(x)[T]$ whose roots are the pair of complex conjugated roots $x_1$,$\bar{x}_1$,$x_2$,$\bar{x}_2$ of $f$.

We can write the euclidean division $f(T)/(T-x)$ in the form:
$$P_1P_2=T^4+xT^3+x^2T^2+x^3T+x^4+15$$
   $$= \left(T^2 +A(x)T+N_1(x)\right)\;\left(T^2 +C(x)T+N_2(x)\right)\in k(x)[T]$$

How does SAGE gives the coefficients of $P_1=(T^2 +A(x)T+N_1(x))\in k(x)[T]$?
The result given by SAGE is: (recall that the ground field is $\mathbb{Q}(\sqrt{5})$ and that $x$ is a root of $T^5+15T+12$, in other words $x^5\equiv -15x-12$)

$A(x)=\frac{\sqrt{5}}{10}x^4 + \frac{\sqrt{5}}{10}x^2 +(\frac{\sqrt{5}}{10} + \frac12) x + \frac{6\sqrt{5}}{5}=x_1+\bar{x}_1$

$N_1(x)=(\frac{\sqrt{5}}{20}+\frac14)x^4+ (\frac{\sqrt{5}}{20} - \frac14) x^3 + (-\frac{3\sqrt{5}}{20} + \frac14)x^2 + (\frac{3\sqrt{5}}{20} - \frac34) x + 3=x_1\bar{x}_1$

and I feal that understanding how SAGE/PARI computes this would give a better understanding of field extensions.

Further, the simplier example for the last quadratic extension $L/k(x)$. It is generated by any other root. Take one root $x_1$, so $x_1^2\in k(x)$, and define the quadratic extension $L=\{k(x)+x_1k(x)\}$ generated by this root. It's conjugate (over $k(x)$) is $x'_1=-A-x_1$. The other pair is $x_2=a+bx_1$ whose conjugate (over $k(x)$) is $x'_2=a'-bx_1$, and both are roots of $P_2=T^2+CT+N_2$ with $x-A=C$ and $xN_1N_2=-12$. How does SAGE finds the values $a,a',b$?


texts: Are there master theorems that deal with parameters of the form $n-c$?

texts:
While thinking about this question on a recurrence I checked out some stronger master theorems.
Unfortunately, they do not seem to apply because terms

$\qquad\displaystyle T(n) = \dots + T(n-1) + \dots$

are not covered.

Roura [1] investigates (in the discrete case) recurrences of the form

$\qquad\displaystyle T(n) = t_n + \sum_{1 \leq d \leq D} (w_d + r_{d,n}) \cdot T(z_d n + s_{d,n})$

where $\sum |r_{d,n}|$ and $\sum |s_{d,n}|/n$ have to vanish for $n \to \infty$ and, sadly, $0 < z_d < 1$. I did not go through the proof, but an application to the example at hand yielded a quite clearly wrong result of $T \in \Theta(g)$, so this one does not carry over as is.
Akra and Bazzi [2] consider only recurrences of the form

$\qquad\displaystyle T(n) = g(n) + \sum_{i=1}^k a_i T(\lfloor n/b_i \rfloor)$

with $b_i \geq 2$, so above parameter choice is clearly not covered.

Leighton [3] introduces a more general form of Akra-Bazzi for recurrences of the form

$\qquad\displaystyle T(x) = g(x) + \sum_{i=1}^k a_iT(b_ix + h_i(x))$,

but similarly requires that $b_i \in (0,1)$. It seems to me that existence of $p$ as solution of

$\qquad\displaystyle \sum_{i=1}^k a_i b_i^p = 1$

in Theorem 2 can no longer be guaranteed if there is one $b_i=1$ since all $a_i$ are positive.
Drmota and Szpankowski [4] look at recurrences of the form

$\qquad\displaystyle T(n) = a_n + \sum_{j=1}^m b_jT(\lfloor p_j n + \delta_j \rfloor)$

with $0 < p_j < 1$. The proof does not explicitly use $p_j \neq 1$. I am not too sure about the properties of several Dirichlet series (cf section 4.1) if some $p_j=1$, though.

Does any of the theorems hold if there are recursive parameters of the form $T(n-d)$? Can one be adapted to cover such cases, or are there other, more general results that do so?

To summarise, what do we know about solutions of recurrences of the form

$\qquad\displaystyle
  T(n) = \sum_{i \in I} a_i T(n/b_i) + \sum_{j \in J} c_j T(n-d_j) + f(n)
$?

An improved master theorem for divide-and-conquer recurrences by S. Roura (1997)
On the solution of linear recurrence equations by M. Akra and L. Bazzi (1998)
Notes on Better Master Theorems for Divide-and-Conquer Recurrences by T. Leighton (1996)
A master theorem for discrete divide and conquer recurrences by  M. Drmota and W. Szpankowski. (2011)


texts: Sorting $n^2$ numbers which consist of numbers from 1 to $n$

texts:
I wish to sort $n^2$ numbers which all come from the set $\{1,2,3,...,n\}$, i.e duplications are allowed. I know I can just use
merge sort which has complexity $\mathcal{O}(n^2\log (n))$, but I was wondering if it was possible to do better since I know all the numbers will be coming out of $\{1,2,3,...,n\}$.
If there is a special name for this type of problem please let me know. Any references or answers are greatly appreciated.


texts: Big theta notation in substitution proofs for recurrences

texts:
Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$.
For example, on page 91, the recurrence
$$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$
is written like so in the proof
$$ T(n) \le 3T(⌊n/4⌋) + cn^2. $$
But can't $\Theta(n^2)$ stand for, let's say, $cn^2 + n$? Would that not make such a proof invalid?
Further in the proof, the statement
\begin{align}
T(n) &\le (3/16)dn^2 + cn^2 \\
     &\le dn^2
\end{align}
is reached. But if $cn^2 + n$ was used instead of $cn^2$, that step would instead be the following
$$ T(n) \le (3/16)dn^2 + cn^2 + n $$
Can it still be proven that $T(n) \le dn^2$ if this is so? Do such lower order terms not matter in proving recurrences via substitution?


texts: Grokking pseudo-code for solution to gas station problem

texts:
I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill or not to Fill: The Gas Station Problem. The algorithm is reproduced below for ease of reference:

There are some obvious things to fix here in any implementation of the algorithm.

The case $q = 1$ needs special consideration as noted by j_random_hacker in this CS SE answer.
It may happen that no $v$ satisfies $g \leq d_{uv}$ so that there is no vertex to pick in line 10 of the algorithm. In this case, the table entry should be declared infinite, $C[u, q, g] = \infty$.

Even with those two fixes, though, it seems to me that something is still off. As the description supporting the algorithm notes, cases where $c(v) \leq c(u)$ should only be considered when $g \leq d_{uv}$, hence the special treatment in lines 9 and 10, but this additional constraint can be ignored when $c(v) > c(u)$ (according to the formula for $A(u, q, g)$ preceding Theorem 2.2). In practice, this means that the generated program does not match the recurrence relation: Below is a rough Python implementation of lines 7--11 of Fill-Row (after r has been sorted):

i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while g > d[v] - d[u]:
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

If this implementation is assumed to be a correct implementation of the pseudo-code, it is easy to generate examples where $C[(u, q, g)]$ does not match $A(u, q, g)$.

A first attempt at fixing this would be to ignore $g \leq d_{uv}$ for $c(v) > c(u)$:

i = 0
v = r[i]
for g in GV[u]:
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

This seems to work, in that I haven't been able to construct a counter-example. Yet it seems to me that it shouldn't: If $c(v) > c(u)$ occurs for low values of $\mathrm{indep}[v]$, we risk skipping them for all but the smallest $g \in GV[u]$. As such, I would expect that we should rather reset the loop over r ($R$ in the paper) for each iteration, moving the first two lines inside the loop over GV[u]:

for g in GV[u]:
    i = 0
    v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
        continue
    while True:
        if g <= d[v] - d[u] or c[v] > c[u]:
            break
        i += 1
        if i == len(r):
            break
        v = r[i]
    if i == len(r):
        C[(u, q, g)] = inf
    else:
        C[(u, q, g)] = indep[v] - g * c[u]

However, doing so takes us from $O(n \log n)$ to $O(n^2)$, which invalidates Theorem 2.2. You can probably do something more clever by keeping track of the cases $c(v) > c(u)$ and $c(v) \leq c(u)$ separately, but that doesn't seem to be in the spirit of the pseudo-code (and in particular, I'm aware that an algorithm with lower complexity exists in A fast algorithm for the gas station problem, so that clearly we can do something to remedy this), so I'm simply wondering: Am I misreading the pseudo-code?


texts: How can i solve the recurrence $T(n)=2T(n-2)+n\log n$

texts:
What would be the solution of the following recurrence?
$$T(n) = 2T(n-2) + n\log n.$$

I've managed to get:

$$T(n) = 2^{n/2}T(0)+\sum_{i=0}^{n/2} 2^i (n-2i) \log(n-2i). $$

The sum cannot be easily bounded for estimating the recurrence, because part of it increases while the other part decreases as the index grows.


texts:
Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with high probability the number
$W = \sum_{\mathcal{T} \in \tau(G)} \sum_{e \in E(\mathcal{T})} w(e)$
without actually enumerating all the spanning trees? Are there asymptotic estimates on this number?


texts: Does types being terms imply your dependend theory is considered polymorphic?

texts:
In the introduction of the book by B.Jacobs, "Categorical Logic and Type Theory" (it's online here), he classifies type systems into three general flavours: Simply typed ones, depended typed (term depended types) and polymorphic types (type depended types). He says also there are also mix types.

Now if you start out with a dependently types theory and introduce transitive universes, hence forcing types on the level of terms, are you automatically speaking of a polymorphic type system then?


texts: Count minimum number of steps to destroy all blocks

texts:
Given a sequence of integers $A_x$ of length $n$ such that $1 \leq A_x \leq N$,in one step we can remove an element, but when we remove an element we also delete all adjacent numbers which have the same value as the element we remove. We want to count the minimum number of steps to remove all elements.
For example, if our sequence is $[1, 2, 2, 2, 2, 3, 3, 3, 1]$, we can remove it in three steps: firstly we remove the twos, then we remove the threes, and on the end we remove the final two ones.
Our sequence transforms as follow: $[1, 2, 2, 2, 2, 3, 3, 3, 1] \to [1, 3, 3, 3, 1] \to [1, 1]$.
I tried using Dynamic Programming to solve this problem, and my idea was to use $DP[i][j]$ to represent the minimum steps to clear the interval $[i, j]$, however I'm not sure how to work out the transitions, and I'm stuck on the part that there can be some element in the middle of the interval which can be merge with the ends of the interval, and my DP relations cannot handle such cases.


texts:
What is the Monodic Second Order formula that encodes all binary strings that represent a valid parenthesis matching ? By this I mean 1s represent '(' and 0s represent ')' and at every position, number of 1s in the prefix is greater than or equal to the number of 0s .

Can someone tell me how to proceed ?

Thanks!


texts:
Im currently learning about removing left recursion. Ive watched a few youtube clips and understand the basics. For example, i can remove left recursion for the following;

$E \rightarrow E+T \mid T$

Answer

$E \rightarrow TE'$

$E'\rightarrow \varepsilon \mid +TE'$

Ive been given the following question which has sort of 3 parts to it and has me confused a lot (compared to the question example above). The question is remove the left recursion from the following grammar;

$A \rightarrow Ba$

$B \rightarrow dab \mid cB$

$C\rightarrow cB\mid Ac$

Is there another rule to follow for this, or when it has more than 1 statement as such.

Any help will be much appreciated


texts: Can sampling remove the limitations in greedy algorithm?

texts:
Given the limitations of greedy (i.e., not always finding the optimal solution), does sampling the data space in a randomized manner or some structured manner reduce or remove the limitations of greedy algorithm?

I understand the answer to this is problem-specific, but given a problem that shows the limitation of greedy algorithm can sampling be used in any way in order to guide the greedy algorithm to generate an optimal solution?


texts: Indistinguishability of exponentially close distributions

texts:
Let $D_{1}$ and $D_{2}$ be two probability distributions over $n$-bit strings such that the total variation distance between them is $\mathcal{O}\left(1/{2^{n}}\right)$. Given as input a polynomial number of samples from any one of the distributions, the task is to output $1$ if the samples come from the first distribution and $0$ if they come from the second one. I am trying to show that no polynomial-time algorithm (even with bounded error) can do this task.
Intuitively, it should be very clear that two distributions that are exponentially close are indistinguishable. But how do I formalize the intuition?


texts: How to calculate the depth of sorting networks?

texts:
I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs.

For example, in case of selection sort, we have:

$\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$

which leads to

$\qquad \displaystyle D(n)=2n-3=\Theta(n)$

I have confirmed that the depth of selection sort is equal to $2n-3$ by hand, but I can't understand how the recurrence $D(n)=D(n-1)+2$ is derived.


texts:
I'll preface this by saying that this IS a homework question.

However, when asked about how to solve it in class, (I believe) my professor was unable to complete it.

The question is:

  Compute the weakest precondition for each of the following
  assignment statements and postconditions:
  $$a = a + 2b - 1\ \{a > 1\}$$ (where a > 1 is the postcondition)

His answer was: "$a > 2 - 2b$."
Is this correct? It seems that he broke the rules of equivalents, by using the ">" as "="

I believe the answer is:
$$\{a>1\;\wedge\; b<\tfrac12\}\quad\text{or}\quad \{a > 0\;\wedge\;2b-1 +a >1\},$$
    where the "$\wedge$" symbol means "and"

We're using Concepts of Programming Languages, by Sebesta, 10th Edition, so any references from that material would be excellent :)

Thanks!


texts: Binary heap removal peculiar potential function analysis

texts:
Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized,
meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based sort if we build the heap in $O(n)$.

Where is the falling point in this potential function, and does it not give a $O(1)$ time guarantee and why?

\begin{align*}
    \overline C_i     =&  C_i + \phi_i-\phi_{i-1} \\
    \phi_i  =& \sum_{a\in Heap}{depth(a)} \\
\end{align*}

meaning the potential function is the sum of depths of all nodes in the tree.
\begin{align*}
    C_i           &= \log n \\
    \phi_{i}      &= \phi_{i-1} - \log n \\
    \overline C_i &= \log n + \phi_{i-1} - \log n - \phi_{i-1} = 0
\end{align*}


texts: Stability for couples in the Stable Matching Problem

texts:
In the Stable Matching Problem, it is stated that there can exist cases where the $m$ list of men can be content with their decisions, yet the list of $f$ cannot when the algorithm is run with men's proposals.

From what I read, an unstable match occurs when $m$ and $f$ prefer each other to their current partners.

I am a little lost in the definition of Stable Matching for this case. I'm going over the slides here.

  Is a pair $(m, f)$ stable as long as the men are content even though the female's preferences have not been matched?


texts: All nearest neighbor in a changing 2d euclidean space

texts:
I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem:

Given a 2D space with $N$ random points $p_1...p_n$, calculate the nearest neighbor of each of the points, where the distance is at most $C$.

Note that our list of points is unsorted, and that each point is an actual object so I could give it any property I want.

Now this can easily be done in $O(n^2)$ time, it is also the easiest and not really an issue.
However, the time it takes when a new point is added or a point is removed is also $O(n^2)$, and I would like to get that down, because this is done during gameplay (while the initial step is only done at start).

Does anyone know a possible improvement over the simple 'bruteforce'? I tried sorting, twice, and keeping it up to date (using a 4x linked list (up, down, left, right)) but that did not seem to work.


texts: Probability that a random hash from a universal family is injective

texts:
This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows:

In class we saw universal hashing as the solution to processing N elements in the range {0,1,...u-1}, arriving
one at a time. Using universal hashing we can get O(1) processing time for each request, but in expectation. Hence
sometimes we might get unlucky and processing time might be longer. Consider another scenario where we are given
the N requests in advance. Can we process them together and store in a hash table so that any future lookup request for
any of these items can be processed in worst case O(1) time (so no uncertainty or expectation here)? In this problem
you will design a solution for this, again using universal hashing.

You are given a set S of N items in the range {0,1,...u-1) in advance. Consider the following algorithm
that stores these items into a table of size N*N.

SquareHash(S, u)
Input: A set S of N items, an integer u such that
each item is in {0,1, ... , u-1}
Output: A hash table of size N*N and a corresponding hash function
1. Initialize a table T of size N*N
2. While true
        3. Pick a function h uniformly at random from a universal family H
        that maps {0,1, ... , u-1} to {0,1, ... , N*N-1}
        // Assume that this can be done in O(1) time
        4. Insert all the elements of S into T using h as the hash function
        5. If T has no collisions, return (T,h). Otherwise empty T

Clearly if the above algorithm terminates then it will produce a table with no collisions and hence any future
lookup will be in O(1) time guaranteed. However in the worst case the algorithm might run forever. Show that
this is unlikely. In particular, compute the expected running time of the algorithm above.
[Hint: Each time a function h is picked, compute the probability (or a lower bound on it) that the resulting table
will have no collisions. Then use the fact that if a coin of bias p is flipped until it turns up Heads, the expected
number of flips is 1/p]

I understand intuitively this is unlikely to run forever. If a hash function causes a collision, it will pick another one until it finds one that does not cause any collisions. However, I am unsure of how exactly to prove this formally and how to compute the expected running time. I know that the probability of two elements colliding is 1/m, where m is the expected range of outputs.


texts: How do I interpret this divide and conquer algorithm for removing duplicates in a list?

texts:
Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French.

What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ compared?


texts: How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$?

texts:
I'd like your help with proving that the language
$$L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}$$
is decidable iff $\mathrm{P}=\mathrm{NP}$.

If $\mathrm{P}=\mathrm{NP}$, I get that it's the language of empty Turing machines. So $L$ is a $\text{co-RE}$ problem — but that's not what's being asked, so I got confused.

I know that in order to show $\mathrm{P}=\mathrm{NP}$, I need to show problem which it's $\mathrm{NPC}$ and $\mathrm{P}$ as well.

Any help?
Thanks!


texts:
According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most part it makes sense. However, I am particularly interested in the $k \times k$ square grid graph case, but have been struggling on how it is possible to make a tree decomposition of such a graph with that low of a width.

One of the problems I run into when trying to draw out decomposition trees of small square grids with groups of at most $k+1$ (to ensure a decomposition tree where the width is $k$) is that since the graph is "cyclic", one of the corner nodes shows up in two opposite ends of the tree, but not in any nodes on the path between the two. This clearly violates the coherence property of decomposition trees, which according to Wikipedia (which gives a more precise definition than most) is:

  If $X_{i}$, $X_{j}$, and $X_{k}$ are nodes (in the decomposition
  tree), and $X_{k}$ is on the path from $X_{i}$ to $X_{j}$, then
  $X_{i}\cap X_{j}\subseteq X_{k}$.

For the case of the $3 \times 3$ graph, the only valid (or at least what I believe to be valid) decomposition tree I can think of contains 2 nodes: $\{\{1, 2, 3, 4, 6, 7, 8, 9\}, \{2, 4, 5, 6, 8\}\}$ where the nodes are labeled by row starting from the top left corner:

$1\space2\space3$

$4\space5\space6$

$7\space8\space9$

I did this by taking the perimeter vertices for the first tree node, and the inner vertex ($5$) along with its adjacent vertices to ensure all edges and vertices are included.

Ultimately, my question is, how can the treewidth of a square $k \times k$ square grid graph actually be equal to $k$? And if this is correct, could you present/explain a simple example of a decomposition tree that demonstrates this property?


texts:
I don't know exactly how to solve the exercise below.

  Show that the multiplication lies in $\text{FL}$.

  Hint: A useful approach to a solution is to split the exercise into two parts and to explain that each function lies in $\text{FL}$. The standard multiplication scheme can be used as an intermediate step. Example:

  $\begin{align}
1001 \cdot{} 1100 & = \\
 1001000\\
 + \ \ \ 100100\\
 + \ \ \ \ \ \ \ \ \ \ \ \ 0\\
 + \ \ \ \ \ \ \ \ \ \ \ \ 0\\
\end{align}$

  Other useful approaches are certainly also accepted.

Useful definitions from our lecture notes:

Let $f : \Sigma^* \to \Sigma^*$ be a function, let $t : \mathbb N \to \mathbb N$ be a time bound and let $s : \mathbb N \to \mathbb N$ be a memory space bound.

$\bullet$ It is $f \in \text{FDTIME}(t),$ if there exists a DTM $M$ with an output tape, calculating $f$ and for which $T_M \in O(t)$ holds.

$\bullet$ It is $A \in \text{FDSPACE}(s),$ if there exists an offline DTM $M$, calculating $f$ and for which $S_M \in O(s)$ holds. The fields being written on the output band are not considered for the amount of memory space.

$\text{FP}=\bigcup_{k \in \mathbb N} \text{FDTIME}(n^k), \text{FL}=\text{FDSPACE}(\log n)$

I think the hint wants me to find two functions (one for the multiplication and one for the addition), but I don't see how to find two functions that do the calculation of the example in the appropriate way. Can somebody help me, please?


texts:
Problem : Two players have in front of
them a single pile of objects, say a stack of 7 pennies. The first player divides the original
stack into two stacks that must be unequal. Each player alternatively thereafter does the
same to some single stack when it is his turn to play. The game proceeds until each stack has
either just one penny or two—at which point continuation becomes impossible. The player
who first cannot play is the loser. Show, by drawing a game tree, whether any of the players
can always win.

Why is the state 6-1 not going to 3-3-1?If we have 6-1 pennies we can remove 3 pennies from the 6 stack and we have 3-3-1 pennies.So why isn't 3-3-1 not a child of 6-1?


texts: Image sharpening : Adding prewitt's filter resulted images. Is it correct?

texts:
I'm reading that 'Prewitt' filter is high-pass filter, which means that it can sharpening the image (via edge highlight).

But I'm not sure to implement the sharpening process (not just edge detection) to the original image in this case.

So I mimic Laplacian process :

x-direction 1st order derivate is define as :
f(x+1),y) + f(x-1,y) -2 f(x,y)

so , the filter approximation :

 0  0 0
 1 -2 1
 0  0 0

y-direction 1st order derivate is define as :
f(x,y+1) + f(x,y-1) -2 f(x,y)

so , the filter approximation :

 0  1 0
 0 -2 0
 0  1 0

Now adding both of these filters we get :

 xy =    0  1 0
         1 -4 1
         0  1 0

So I get the new image Laplacian filtered image;

A = im2double (I);
I4 = imfilter(A,xy); % new image Laplacian filtered image

Substracting the original Subtracting the Laplacian filtered image from the original image can help sharpen edges and remove blur.

X = A - I4; % new sharper image

So now I apply this same principal but using Prewitt's filter instead.

w = fspecial('prewitt')
 I4= imfilter(A,w)+imfilter(A,w'); % new image Prewitt filtered image

Subtracting the Prewitt filtered image from the original image can help sharpen edges and remove blur.

X = A - I4; % new sharper image

Is it a correct approach? I need your help. Thanks


texts: Integer set disjointness query on sketches with something like homomorphic hashing

texts:
Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. These sketches can be checked for disjointness with a function $\mathsf{disjoint}_n : 2^n \times 2^n \to 2$, where if $\mathsf{disjoint}_n(\mathsf{sketch}_n(A), \mathsf{sketch}_n(B)) = 1$, then $A \cap B = \emptyset$ (but $A \cap B = \emptyset$ may also be true when $\mathsf{disjoint}$ returns 0, i.e.: no false positives).
This can easily be accomplished with a bloom filter, where $\mathsf{sketch}_n$ is the result of inserting each element of the set into a bloom filter and $\mathsf{disjoint}_n(x, y) = (x \,\&\, y) \equiv \mathbf{0}$ ($\&$ being bitwise AND).
Now, suppose that I want there to exist a function $\mathsf{shift}_n : 2^n \times \mathbb{Z} \to 2^n$ such that $\mathsf{shift}_n(\mathsf{sketch}_n(X), \delta) = \mathsf{sketch}_n(\{x + \delta \mid x \in X\})$. Is there a data structure that supports this operation, perhaps using some variety of homomorphic hashing?
Alternatively, $\mathsf{shift}_n$ need not exactly return the same sketch as $\{x + \delta \mid x \in X\}$, but rather a different sketch that still has the no-false-positives property when checked for disjointness with another set.
I'm also willing to consider answers where we can't ensure no false positives, but there is a good bound on the probability of a false positive.
Also, wherever I've said $\mathbb{Z}$ here, feel free to interpret that as some finite set of integers (e.g.: 32-bit integers).
Bonus points if there is a way to compute the union of two sketches, and if there is a way to extend this to sets of tuples in $\mathbb{Z} \times 2^p$ where $\mathsf{shift}$ only affects the first element of each tuple.


texts: Is there a formula to state the number of 'sets' of 'ordered sets within ordered groups'?

texts:
I am new to this and an amateur... please help.

My Question in practical terms:
Given The three following inputs... determine the number of unique group arrangements as an ordered set.

INPUT:
'a' = Students
'b' = Groups
'c' = students per group

OUPUT ANSWER:
'z' as an integer

OUTPUT RULES:
 - All elements considered are ordered from left to right starting with the smallest number.
 - Order is not important... (1,2,3)=(2,3,1)=(3,2,1)=(3,1,2)=(1,3,2)=(2,1,3)...THEREFORE (1,2,3) is the only unique group that is to be counted.

Problem Example #1:
I have 12 students that I need to arrange into 4 groups.  I want the 4 groups to each contain 3 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 880 ordered arrangements.
[Output Format: (1,2,3)(4,5,6)(7,8,9)(10,11,12)]

Problem Example #2:
I have 12 students that I need to arrange into 3 groups.  I want the 3 groups to each contain 2 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 13,860 ordered arrangements.
[Output Format: (1,4)(3,6)(7,11)]

Problem Example #3:
I have 24 students that I need to arrange into 3 groups.  I want the 3 groups to each contain 6 students with no student appearing in more than one group. How many arrangements are there? In this instance there are 125,847,260 ordered arrangements.
[Output Format: (1,2,3,4,5,6)(9,10,11,12,13)(15,16,17,18,19,20)]

Unless I am mistaken, these are not 'combinations' or 'permutation's or 'complete sets' or 'hoyosa index'.  So, for lack of better terms I am calling them ordered sets within ordered groups for now.

Is there a known formula to generate the answer without generating all possible solutions and searching?

20130822---ADDENDUM---
The numbers provided are accurate. The closest description tat I can call relate this to would be "Independent Edge Set AKA Matching"... except that I BELIEVE matching has a limit of two students per group. Sticking to the "Two Students per group" this can be determined using factorials similar to those you have provided.  HOWEVER, I cannot find a formula that allows for the three INPUTS a,b,c as provided and ONLY accounts for unique ordered sets.

Using Problem Example #2:  12 Students (a), 2 groups (b), 3 students (c), = 13,860 unique ordered sets
Set #1[(1,2,3,)(4,5,6)]
Set #2[(1,2,3,)(4,5,7)]
Set #3[(1,2,3,)(4,5,8)]
... Set #13,860 [(7,8,9)(10,11,12)]


texts: Knapsack problem -- NP-complete despite dynamic programming solution?

texts:
Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right?

I have read it is actually an NP-complete problem, though, which would mean that solving the problem in polynomial problem is probably impossible.

Where is my mistake?


texts: How do Functional Reactive Programming and the Actor model relate to each other?

texts:
FRP is about streaming events and behaviours through pure functions. The Actor model - at least, as implemented in Akka - is about streaming immutable messages (which can be considered to be discrete events) through potentially impure objects, called actors.

So on the surface they seem related.

What else can we say about how they related? Also, what can say about which of them might be more appropriate for different application domains?


texts: Algorithm to build a "hand" calculation for riichi mahjong game

texts:
I would like to discuss an algorithm to build a "hand" calculation for riichi mahjong game.

I will simplify terms to focus on the algorithm and not on the game specific terms.

Let's imagine that we have a card deck with three suits. Each suit contains cards from 1 to 9 and each card has four copies.

So card deck looks like this:

111122223333444455556666777788889999a (a is a first suit)
111122223333444455556666777788889999b (b is a second suit)
111122223333444455556666777788889999c (c is a third suit)

Each player has 14 cards in his hand and hand should contains four sets and one pair to be able win. Set can be built from three consecutive cards (123a) or from three same cards (444a).

Input data: 14 cards.

Output data: all possible variants of 4 sets and one pair.

Examples:

Input: 123678a234678b44c

Output: [123a 678a 234b 678b 44c]

Input: 233445a 44556677b

Output: [123a 345a 456b 456b 77b], [123a 345a 567b 567b 44b]

Also, it can be cases with 5-10 possible variants of the hand.

I tried to build it with recursion, but I wasn't successful. The main question how to determine that we don't have remaining variants?

Thanks for your help in advance.


texts: How does topic or tag suggestion algorithms work?

texts:
I know it's a keyword based search. But sites like Quora have some good suggesting algorithms where the algorithm understands the intent of question asked rather than just the keywords meanings.

For instance, for a question involving "O(n^2)" it adds 'Algorithms' and 'Computer Science' as topics and for a question involving "limit on friends in Facebook" it adds 'Facebook friends' as a topic. So it's more of a semantic search.

Google search also works on the same principles of semantic search. So how exactly does tag suggestion algorithm work?


texts: Let $G = (V,E)$ be an infinite digraph: $E \subset \mathbb{N}\times \mathbb{N}$ is decidable. Does it imply that $\delta (i,j)$ is a total function?

texts:
Problem:

  Let $G = (V,E)$ be an infinite digraph, such that $V = \mathbb{N}$, and $E \subset \mathbb{N}\times \mathbb{N}$ is decidable set. Does it imply
  that $\delta (i,j)$ is a total function?

  *(where $\delta (i,j)$ is the shortest path function between vertex
  $i$ and $j$).

I'm having a hard time trying to understand the problem, so any help would be appreciate.

Well, this is what I know (hopefully I'm not misunderstanding anything here):

A language (or set) $L$ is decidable if $\exists$ and algorithm $A$, such that if $v \in L$, then $A(v) = \text{Accept}$ and halts and if $v\not\in L$, then $A(v) = \text{Reject}$ and halts.

A function $f$ is total if $\exists$ and algorithm $B$ that computes it $\forall v\in \mathrm{Dom}(f)$ and always halts.

My attempt:

Suppose $\delta (i,j)$ is a total function and let algorithm $B$ be the Bellman-Ford algorithm ($BFA$).

The relaxation step in $BFA$ is given by

// Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

Because $|V| = \infty$ we have that the algorithm never halts, since size(vertices) - 1 $= |V| -1 = \infty$. This implies that $BFA$ doesn't compute $\delta (i,j) \implies \delta (i,j)$ is not a total function (So, to my understanding it would be only a partial function, since $\exists$ some vertices $u,\ v$ for which the function $\delta (u,v)$ is undefined).

Although to me at first glance it makes kind of sense, I guess I'm wrong, mainly because I didn't consider the fact that $E$ is a decidable set.


texts: Example of a Karp reduction between problems in NP that is not a Levin reduction?

texts:
What is an example of a Karp reduction $f$ between two problems $A, B$ in $\textbf{NP}$ such that $f$ does not provide a way to transform certificates of one problem into certificates of the other? In other words, such that $f$ is not the Karp reduction in any Levin reduction between $A, B$?

The accepted answer to this question mentions that it is not always the case that such a Karp reduction yields a corresponding Levin reduction:

"It is true that the well-known Karp reductions between natural problems turn out to be Levin reduction but this does not need to be true in general."

However, I'm struggling to find/devise a concrete ("natural", if possible) example of why this is the case.


texts: I do not understand why finding the minimum of elements take O(n) time

texts: I know that sorting the array take O(logn) time. But why finding the minimum of elements take O(n) time, which is more expensive? If I sort the array, I simply output the first element and this would be my minimum.


texts:
While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language.
But is there a regular language for every unambiguous grammar? How can I prove that this is/isn't true?


texts: What is the relationship between problems and languages?

texts:
I want to ask exactly what is the relationship between problems and languages.
We know that the set of all languages uncountable.
Is the set of problems also uncountable?
Can every problem be defined by a language?
Can a language solve more than one problem and vice versa?
Is there one-to-one correspondence between problem and languages?


texts: How to prove that the pseudo-code of thresholded-A* algorithm from my teacher's book is correct?

texts:
I have the following DFS2 pseudo-code, which is used in the pseudo-code of IDA*, from my teacher's book, but I cannot understand why it's correct:
DFS2(N0, f, threshold):

PQInit(PQ) // PQ means Priority Queue, for a pair (c, p) in PQ it represents a path from N0 to c.
PQ.offer(null, N0)

while isEmpty(PQ) is FALSE do
    current, parent := PQ.poll()
    R := next(current, parent)  // return the next child of parent

    if R is null then
        continue
    PQ.offer(R)

    Let P be the path from N0 to R.
    if f(P) > threshold then
        continue

    if isGoal(R) then
        return success

    if R in PQ then
        continue
    PQ.offer(null, R)

return fail

if I substitute the PQ to a Stack S in the code above, then it's just a non-recursive DFS which I can understand and prove its correctness. Even more I think I have a better version (reordering of the continue-conditions) of the non-recursive DFS:
StackInit(S)
S.push(null, null)               // assume that next(null, null) -> (N0, null)
while isEmpty(S) is FALSE do
    current, parent := S.pop()
    R := next(current, parent)
    if R is null then
        continue
    S.push(R,parent)
    if isVisited(R) then         // if it's visited then it cannot be goal
        continue
    markVisited(R)
    if isGoal(R) then            // if it's a goal then no need to visit its children
        return success
    Let P be the path from N0 to R
    if f(P) > threshold then
        continue
    S.push(null, R)
return fail

I thought this would be perfect since any visited node would not be visited again, but then I realized that revisiting of nodes (In CLRS this is called RELAXING weights of nodes.) is required to achieve A*. Can anyone explain for me why the A*(DFS2) pseudo-code I provided above is correct? And could anyone teach me how to improve my second DFS pseudo-code to make it a thresholded-A*?
In my current understand the nature of A*, which can be seen as a generalization of Dijkstra-shortest path algorithm, is BFS. So given a DONE set (A set of nodes which have been labeled with the shortest/smallest accumulated weight) A* will extend it by the end node of closest adjacent node(Greedy). In DFS2 not all adjacent edges are discovered since it's Depth-First, so how can I prove it that the path found is indeed optimal when it return success?


texts: Class C can have _______ 1s with the remaining bits 0s

texts:
A subnet mask in class C can have _______ 1s with the remaining bits 0s.

MyApproach:

Class C subnet is 255.255.255.0.So, accordingly it has 9 1s on first byte,9 1s on second byte and 9 1s on third byte.etcSo total 27 1s but the Ans is 25

@Edit

For 255 it has 8 1s on first byte,8 1s on second and 8 1s  on third.=24 How 25?

  Can anyone guide What I am doing wrong?


texts: Functional dependencies with the same key?

texts:
let's consider a table with

carID | hireDate | manufactory | model | custID | custName | outletNo | outletLoc

I want to evaluate all the functional dependencies to bring in first, second and then third normal form.

Functional dependencies

carID,hireDate -> custID

Partial dependencies

carID->manufactory, model, outletNo**

Transitive dependencies

custID->custName
outletNo->outletLoc

Since a car is in a outlet only I have in the partial dependecies this:

carID->manufactory, model, outletNo**

However this leads to anomalies in insertion (imagine adding a car with no outlet), so should not that be like this?

carID->manufactory, model
carID->outletNo

But isn't this still an normalisation anomaly?


texts:
I studied this algorithm. Link.
Is is about finding all possible binary trees with given inorder traversal.

I want to analyze this code with Big-O notation.
I think it is O(N^3). Below is my thought.

1) choose root node. let's say in[i]. (0 <= i < N). => O(N)
2) construct left subtree. in[0] ~ in[i-1]. => O(N)
3) construct right subtree. in[i+1] ~ in[N-1]. => O(N)

In order to count all cases, I considered product rule. So I concluded time complexity of this algorithm is O(N^3).

Is it correct?


texts: Running time of sparse matrix multiplication

texts: Given a sparse matrix $M \in \mathbb{R}^{n \times m}$ with $n \ll m$ and $\mathsf{nnz}$ being the number of non-zero-components. What is the running time of computing $M M^T$?


texts: How to describe algorithms, prove and analyse them?

texts:
Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only about orders of growth. The TAOCP thoroughly changes my mind.

TAOCP uses English mixed with steps and goto to describe the algorithm, and uses flow charts to picture the algorithm more readily. It seems low-level, but I find that there's some advantages, especially with flow chart, which I have ignored a lot. We can label each of the arrows with an assertion about the current state of affairs at the time the computation traverses that arrow, and make an inductive proof for the algorithm. The author says:

  It is the contention of the author that we really understand why an algorithm is valid only when we reach the point that our minds have implicitly filled in all the assertions, as was done in Fig.4.

I have not experienced such stuff. Another advantage is that, we can count the number of times each step is executed. It's easy to check with Kirchhoff's first law. I have not analysed the running time exactly, so some $\pm1$ might have been omitted when I was estimating the running time.

Analysis of orders of growth is sometimes useless. For example, we cannot distinguish quicksort from heapsort because they are all $E(T(n))=\Theta(n\log n)$, where $EX$ is the expected number of random variable $X$, so we should analyse the constant, say, $E(T_1(n))=A_1n\lg n+B_1n+O(\log n)$ and $E(T_2(n))=A_2\lg n+B_2n+O(\log n)$, thus we can compare $T_1$ and $T_2$ better. And also, sometimes we should compare other quantities, such as variances. Only a rough analysis of orders of growth of running time is not enough. As TAOCP translates the algorithms into assembly language and calculate the running time, It's too hard for me, so I want to know some techniques to analyse the running time a bit more roughly, which is also useful, for higher-level languages such as C, C++ or pseudo codes.

And I want to know what style of description is mainly used in research works, and how to treat these problems.


texts: Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \sim n^2$ but I cannot find a formal proof.


texts: Find if two numbers are linked by a greatest common divisor

texts:
Two numbers $x,y$ are 'connected' if $gcd(x,y)>g$. Here $gcd$ is the greatest common divisor. A path exists between two numbers $x,y$ if given $g$ and $n$ there is a sequence of numbers that connect $x$ to $y$ such that all numbers along the path are less than or equal to $n$.
How do you find if there exists a path between two numbers and if this needs to be repeated for multiple pairs of numbers would it be more optimal to first find all existing paths.
I've tried a basic approach of breadth-first search, where each query between two numbers involves calculating $gcd(x,y)>g$. However, this is quite laborious and want to see if there is a more optimal solution.
As a simple example to motivate the problem, let $x=10, y=30, z=18$. Assume $g>4$ and $n=50$. Then $x$ and $z$ are not directly connected but there is a path connecting $x$ to $y$ and from $y$ to $z$.


texts: In general, does $f(g)$ and $f(h)$ have the same time complexity?

texts:
I thought about this question while looking at a textbook where it wanted me to compare the time complexity of $\lg^*(n)$ and $\lg^*(\lg(n))$

Now it is well known that $\lg^*$ is a tremendously slow growing function, so what is inside of $\lg^*$ shouldn't contribute to its complexity.

But is it true in general that any $f(g)$ is $O$-equivalent to $f(h)$ where f is a non constant function?


texts: Minimizing transportation cost through a network, multiple source/sinks

texts:
I have the following problem:

Inputs:

A finite collection $V$ of vertices
A metric cost function $c:V^2\to\Bbb R$ (interpreted as the edge cost of a complete graph on $V$)
An amount of resource $s:V\to\Bbb R$ on each vertex, satisfying $\sum_{u\in V}s(u)=0$

The problem is to determine a transfer function $f:V^2\to\Bbb R^{\ge0}$ such that $\sum_{v\in V}(f(v,u)-f(u,v))=s(u)$ for all $u$, which minimizes $\sum_{u,v}f(u,v)c(u,v)$.

The story to tell is that the points represent places with some amount of resource (if $s(u)$ is positive) or with some need of the resource (if $s(u)$ is negative), and $c(u,v)$ is the cost of sending a unit of resource from $u$ to $v$. We assume that every vertex can send resource to any other vertex, and the direct path is usually better than passing through an intermediate point. How do we minimize the cost of sending everything from where it is to where it is needed?
What is the name of this problem, and do there exist efficient algorithms to solve it? It seems similar to the minimum cost flow problem, but this only has one source and one sink, has maximum capacities for all the edges, and often needs multiple node paths for the resource, while here the direct path is always at least as good as a longer path (because the cost function is a metric).


texts: Creating a temp array vs passing one in Mergesort

texts:
In my CS class, we've discussed two ways of dealing with the temporary array required for the merging phase of mergesort. One of them is to pass a full-size temporary array as a parameter, e.g. merge(array, tempArray, first, last), and another is to create a temporary array of appropriate size (or two half-sized arrays) in the function call, e.g.

merge(array, first, last):

...
leftArray = items from first to middle
rightArray = items from middle+1 to last
...

My CS professor is of the opinion that the first option will somehow have a performance (speed/memory) improvement over the second, but I don't understand why. Merging the arrays is a "tail" operation in mergesort, and so the second option doesn't seem like it will actually require more memory overall. Is the only reason why because memory allocation takes time?

Thanks!


texts: From a given regular expresssion r , can we minimize a regular expression r' such that L(r)= L(r')?

texts: Please help me out for finding the solution


texts: What are the gap functions in the $AC$ hierarchy?

texts:
Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth$-d$ $AC^0$ circuit needs a size $\Theta(2^{n^{\frac{1}{d-1}}})$. But PARITY is in $NC^1$ and PARITY is also the negation of the MOD2 and hence this shows that the following inclusions are strict, $AC^0 \subset AC^0[2] \subset NC^1$.

If I understand right then Razborov's 1987 result of exponential size lower bound for MAJORITY for $AC^0[2]$ or Smolensky's similar result in 1986 for MOD3 for $AC^0[2]$ do not in anyway strengthen the inclusion consequence of Hastad's result. Am I right?
But do we know whether $AC^i$ vs $AC^{i+1}$ separation is strict or not? Like do we know of functions which are exponentially sized for $AC^i$ but can be computed by polynomial sized circuits for $AC^{i+1}$?


texts: What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?

texts:
I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary.  The standard binary golden ratio notation works but is horribly space inefficient.  The  Balanced Ternary Tau System (BTTS) is the best I've found but is quite obscure.  The paper describing it in detail is A. Stakhov, Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic, 2002.  It is covered in less depth by this blog post.

BTTS is a balanced ternary representation that uses $\phi^2 = \phi + 1$ as a base and 3 values of $\bar 1$ ($-1$), $0$, and $1$ to represent addition or subtraction of powers of $\phi^2$.  The table on page 6 of the paper lists integer values from 0 up to 10, and it can represent any $\phi$-based number as well.

BTTS has some fascinating properties, but being ternary, I didn't think I'd be able to find a compact bit representation for it.

Then I noticed that because of the arithmetic rules, the pattern $\bar 1 \bar 1$ never occurs as long as you only allow numbers $\ge 0$.  This means that the nine possible combinations for each pair of trits ($3^2$) only ever has 8 values, so we can encode 2 trits with 3 bits ($2^3$, a.k.a octal).  Also note that the left-most bit (and also right-most for integers because of the mirror-symmetric property) will only ever be $0$ or $1$ (again for positive numbers only), which lets us encode the left-most trit with only 1 bit.

So a $2^n$-bit number can store $\lfloor 2^n/3\rfloor * 2 + 1$ balanced trits, possibly with a bit left over (maybe a good candidate for a sign bit).  For example, we can represent $10 + 1 = 11$ balanced trits with $15 + 1 = 16$  bits, or $20 + 1 = 21$ balanced trits with $30 + 1 = 31$ bits, with 1 left over (32-bit).  This has much better space density than ordinary golden ratio base binary encoding.

So my question is, what would be a good octal (3-bit) encoding of trit pairs such that we can implement the addition and other arithmetic rules of the BTTS with as little difficulty as possible.  One of the tricky aspects of this system is that carries happen in both directions, i.e.
$1 + 1 = 1 \bar 1 .1$ and $\bar 1 + \bar 1 = \bar 1 1.\bar 1$.

This is my first post here, so please let me know if I need to fix or clarify anything.

--Edit--

ex0du5 asked for some clarification of what I need from a binary representation:

I want to be able to represent positive values of both integers and powers of $\phi$.  The range of representable values need not be as good as binary, but it should be better than phinary per bit.  I want to represent the largest possible set of phinary numbers in the smallest amount of space possible.  Space takes priority over operation count for arithmetic operations.
I need addition to function such that carries happen in both directions.  Addition will be the most common operation for my application.  Consequently it should require as few operations as possible.  If a shorter sequence of operations are possible using a longer bit representation (conflicting with goal 1), then goal 1 takes priority.  Space is more important than speed.
Multiplication only needs to handle integers > 0 multiplied to a phinary number, not arbitrary phinary number multiplication, and so can technically be emulated with a series of additions, though a faster algorithm would be helpful.
I'm ignoring division and subtraction for now, but having algorithms for them would be a bonus.
I need to eventually convert a phinary number to a binary floating point approximation of it's value, but this will happen only just prior to output.  There will be no converting back and forth.


texts: How to improve my these specific math skills?

texts:
I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite of the fact that I know how to code I can't solve it. For example, if I don't know the formula for area of circle, I can't find it no matter how good I am at coding.

Have a look at this problem from a programming competition, I did not know how to solve it until Tad posted that it was Assignment Problem and it can be solved with Hungarian Algorithm.After knowing Hungarian Algorithm it was pretty easy to solve. Now you can see problem is with my math skills. I am looking for some resources where I can find such ALL(if not ALL then MOST) algorithms which a programmer/software engineer is supposed to know.


texts:
I was wondering, what is to be the shortest possible key using Vigenere encryption, if a text is ciphered one time with a key of length $i$ using Vigenere and second time with a key of length $j$ using Vigenere?

From what I understand, each time it is encrypted, each character shifts using the first key and then using the second one, so I believe that for each pair there's an equivalent shifting. but if the two keys have a different length, how can I find the shortest possible key?

I think it has to be something with lowest common denominator, but I am not sure. how can this be shown mathematically?

my previous edit was a mistake and i deeply sorry for it. i read the book wrong and didn't interpret what's written well. very sorry for it. yuval explained to me well and i continue to research it using his given information


texts: If a problem is PSPACE-complete what do we know about NL-completeness

texts:
I have a problem $A$ which was shown to be PSPACE-complete by reduction from planning.
However, $A$ can also be transformed into reachability problem which is NL-complete.

I know that $NL=NSPACE(log \ n)$ and $PSPACE=NSPACE$.

Does this mean $A$ is also NL-complete? IF yes, does it make any difference in this context to say whether $A$ is PSPACE-complete or NL-complete ?


texts:
I want to produce a value from a set, where each value has an associated weight.

Eg:

[(1, 4), (2, 3), (3, 3)]

should give me a 40% chance of picking 1, and a 30% chance of picking 2 or 3 respectively.

Using a cumulative sum table and binary searching on it yields the value I want in O(logN) where N is the number of values in the set.

I was thinking of another approach to this using a huffman tree (as described here) with the combined weights of its children stored on each node.

For the above case, the tree would look like

    (10)
   /    \
(1, 4)  (6)
       /   \
   (2, 3) (3, 3)

The algorithm for generate() would be something like:

Generate random number k in range [0, {value of root node})
Start at root node
If at a leaf node, return value
If k >= {value of left child}, go right else go left
Repeat from third step.

Now, in the case that the weights are about the same, this will take O(logN), similar to the binary search method.

However, if the weights increase in an exponential manner and the tree essentially becomes a list, the complexity becomes

$$
\sum\limits_{i=1}^N   k/2^k
$$

Which tends to 2.

I'm having some difficulty coming up with an expression for the average case for generate, but it definitely has an upper bound of O(logN) and a lower bound of O(1). Of course, worst case is O(N).

What's a good approach to figuring this out, and what are the possible pitfalls of this kind of an approach?


texts: Prove that {0^{n^3} | n≥0} is not context free

texts:
I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether $L = \{0^{n^3} \mid n\in\mathbb{N}\}$ is context-free or not.

Based on my intuition, it won't be.  There is no pattern of $0$'s that can be recreated by a pushdown automata but alas I need to prove this. I know you start off assuming it is by being able to create a substring $uvxyz$ where $v$ and $y$ are raised to the $i$th power where $i \ge 0$. I'm having trouble from there, any help in this and the understanding would be greatly appreciated.


texts:
Consider the following code snippet:

for(int i=0;i<n;i++)

The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

According to what I understand: when $i=n$, the for loop would increment $i$ to $n+1$ and check if $i<n$ which would evaluate to false and the loop will be exited.

So the increment would be performed a total of $(n+1)$ times. Is this correct? Should we count $(n+1)$ as the number of increment operations performed during algorithm analysis?

I know this would not make any difference to the complexity since $O(n+1) = O(n)$, linear time. But I was just curious to know if my understanding is correct or not.


texts: I'm very confused about this question, would it be correct to say that (a) is false since executing the state ~req ready being repeated would invalidate that statement ?


texts:
I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments.

Is it in NP?
Attempted answer: Suppose Peggy (prover) solves the problem & submits it to Victor (verifier). Victor can easily see that the final state of the solution is right (in linear time) but he'll have no option but to go through each of Peggy's moves to make sure she didn't make an illegal move. Since Peggy has to make a minimum of 2^|disks|  - 1  moves (provable), Victor too has to follow suit. Thus Victor has no polynomial time verification (the definition of NP), and hence can't be in NP.
 Is it in PSPACE  ? Seems so, but I can't think of how to extend the above reasoning.
 Is it PSPACE-complete?  Seems not, but I have only a vague idea. Automated Planning , of which ToH is a specific instance,  is PSPACE-complete. I think that Planning has far more hard instances than ToH.

 Updated : Input = $n$, the number of disks; Output = disk configuration at each step. After updating this, I realized that this input/output format doesn't fit a decision problem. I'm not sure about the right formalization to capture the notions of NP,PSPACE, etc. for this kind of problem.

 Update #2 : After Kaveh's and Jeff's comments, I'm forced to make the problem more precise:

  Let the input be the pair of ints $(n,i)$ where $n$ is the number of disks. If the sequence of moves taken by the disks is written down in the format (disk-number,from-peg,to-peg)(disk-number, from-peg, to-peg)... from the first move to the last, and encoded in binary, output the $i$th bit.

Let me know if I need to be more specific about the encoding. I suppose Kaveh's comment applies in this case?


texts:
Wikipedia lists the following algorithm for normalizing a lambda calculus term $t$:

If $t$ is not in head normal form, beta reduce the beta redex in the head position to get $t'$. Then normalize $t'$ to get $t''$. $t''$ is the normal form of $t$.
If $t$ is in head normal form, normalize each of its subterms to get $t'$. $t'$ is the normal form of $t$.

The implied base case is if $t$ is in head normal form but has no subterms, in which case it is in normal form already. If $t$ has a normal form, the above algorithm is guaranteed to find it.

The problem I'm having is that it does not seem that the algorithm ever eta-reduces.

For example given the algorithm normalizes $\lambda y.\lambda x.y x$ to itself (since it is already in head normal form, and $x$ is also in head normal form). It should normalize to $\lambda y. y$ though.

It seems apparent that you need to add eta-reduction steps at some point. The problem is I'm not sure where to put them and preserve the property that the algorithm is guaranteed to find the normal form.

When and where do you eta-reduce to achieve this?


texts: Progress of algorithms in problem spaces

texts:
Continuing in the vein of two prior questions (1) and (2), we started with sorting, where we had

a set of $n!$ input possibilities
a goal space of only one element consisting of the one correct sorted sequence

We then arrived at a generalized argument which I'll alter slightly and call A:

Define a space of input possibilities
Define the goal space, a subset of the input space
Reason about constraints in order to set a lower bound

Three Questions: given that there are quadratic algorithms for sorting,

Can we conclude for the quadratic sorting algorithms, where we have an input space of $n!$ input possibilities and roughly $n^2$ steps, that there are $O(n!/n^2)$ possibilities removed from the search space per step on average?
Let's say we're given a problem formalizable in the form of argument A above where the input space is exponential in terms of the size of the input, $O(2^n)$, and the problem is solvable in polynomial time, $O(n^c)$, for some constant $c$. Can we conclude there are $O(2^n/n^c)$ possibilities removed from the search space per step on average?
Can we at least conclude that a $O(2^n)$ problem cannot be solved in polynomial time by removing one element from the input space per step?


texts: Is final state mandatory in DFA(Deterministic Finite Automata)

texts: In state diagram of DFA is it mandatory to keep a final state. I mean whether DFA is possible without final state or not?


texts: Basic mapping reductions without using Turing machines

texts:
I have problems with the basics of mapping reductions.

I can understand how to do reductions using a Turing machine, but without it, I get a little bit confused.

For example:

How do I do a mapping reduction from $a$ to $b$, where $a$ is $\{0,1\}$ and $b$ is $\{0\}$ over the alphabet of $\{0,1\}$?
Does every language have a reduction to itself?


texts: Unusual applications of regular expressions?

texts:
I am looking for some interesting applications of regular expressions.

Can you name any unusual, or unobvious, cases where regexes find their application?


texts:
I need to compute prefix product of an array. For this reason I want to use counter tree fenwick .
Hehe is what I have for the usual Fenwick tree:

An array $T$ indexded from $0$ to $n$. $T[i]$ stores the product of $[F(i)..i]$ segment, where $F(i) = i\ \ \& \ \ (i+1)$.

For the counter tree I need another array $T'$, $T'[i]$ stores the product of $[(i+1)..F'(i)]$, where $F'(i) = i\  \ | \ \ (i + 1) $. Basically, the length of $[(i+1)..F'(i)]$ is equal to the length of $[F(i)..i]$

When I need to multiply an element of an array in a usual Fenwick tree by a certain value I just have to do the following procedure

multiply(index, value)
    for (i = index; i < n; i = i | (i + 1))
        T[i] = T[i] * value

And I do not really understand how to update $T'$. Could you help me please?


texts:
The question is from my complexity-theory course.

Explain the concept of polynomial reduction between problems and explain how, and under what circumstances, lower bound and upper bound problems can be determined.

My attempt:

a problem $A$ can be polynomial reduced to $B$ if given an instance  $a:A$ an istance $b:B$ can be built such that $a$ is true and $b$ is true.

  A decision problem $P_1$ is Karp-reducible to a problem $P_2$ (
  $P_1 \leq_m P_2) %$ if and only if exists an algorithm $R$ such that
  it transforms every instance $x \in I_{P_1}$ if and only if $y \in
> I_{P_2}$. $R$ is the Karp-reduction from $P_1$ to $P_2$

One particular case of Karp-reducibility is the polynomial Karp-reducibility:

  $P_1$ is polynomial Karp-reducible to $P_2$ ( $P_1 \leq^p_m P_2$) if
  and only if $P_1$ is Karp-reducible to $P_2$ and the reduction $R$ is
  an algorithm that runs in polynomial time.

In most cases the complexity of a solution given a particular problem isn't known. For example when we have a huge gap between the lower bound and upper bound. A tipycal situation could be the case of problems when their best lower bound known is $\Omega(n\log n)$ or $\Omega(n^2)$, however the most efficient algorithm has $O(c^n)$ complexity, for $c>1$. In those case the above concepts could be important tools in order to find the complexity relation to different problems.


texts: How many passes does it take to join 2 relations of fixed size with M buffer blocks?

texts:
So let's say 2 relations, B(R) = 200,000 and B(S) = 300,000. The memory buffer is M = 400 blocks.

How many passes would this take to join?

Notation:


texts: Formulating shortest path as submodular minimization

texts:
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.

The answer is probably negative.
But my problem at hand is simply the shortest path problem.

Consider a graphical model with two variables

$$X - Y$$

Both $X$ and $Y$ can take one of the two states $\{1,2\}$.  The task is to find the assignment of $X$ and $Y$ that minimizes

$$
f(X,Y) = \sum_{i=1}^2 \sum_{j=1}^2 T_{ij} \cdot [X=i \ \&\& \ Y=j].
$$

$T_{ij} \ge 0$ are given parameters. $[x]=1$ if $x$ is true, and $0$ otherwise. More generally we can have longer chains and more states, solvable by the Baum-Welch algorithm.

Question: is it possible to formulate this problem as a submodular minimization problem (over a lattice), so that the optimal $X$ and $Y$ can be read from its solution?  Some straightforward trials fail:

Encode $X=1$ by including $X$.  It fails because no assumption is made on $T$.
Introduce two indicator variables for $X=0$ and $X=1$. But then the constraint of exclusion leaves the feasible set not a lattice.

I guess it can be boiled down to min-cut, which has a submodular objective.  But I still can't connect the dots.  It is ok to add auxiliary variables, but going to the dual will be a pain (as this problem is nested in another problem at hand).

Thanks in advance.


texts: Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?

texts:
This is a follow-up question of "Not all Red-Black trees are balanced?" and "AVL trees are not weight-balanced?".$\def\le{\leqslant}\def\ge{\geqslant}$

  Definition: For a rooted tree $T$ and a vertex $v \in V(T)$, let $L_T(v)$ be the number of nodes in the left-subtree from $v$, and $N_T(v)$ be the number of nodes in the subtree rooted at $v$. We say that $T$ is $\mu$-balanced, with $0 \le \mu \le \frac{1}{2}$, if for every node $v \in V(T)$ the inequality
  $$ \mu \le \frac{L_T(v) + 1}{N_T(v) + 1} \le 1 - \mu$$
  holds, and if $\mu$ is minimal subject to this inequality holding.

(These are apparently also known as  weight-balanced trees in some of the literature.) A tree which is $\mu'$-balanced for some $\mu' < \mu$, we will say is μ-imbalanced.

The above-linked posts essentially show that neither AVL trees, nor Red-Black trees, can be guaranteed to be $\mu$-balanced for any $\mu > 0$: that is, for any such $\mu$, one can provide a sequence of inputs to be inserted so that the resulting tree is $\mu$-imbalanced.

Question. Is there any binary search tree structure, with the usual characteristics of $O(\log n)$ insertion and search time, and some $m > 0$, such that the tree will always be $\mu$-balanced for some $\mu > m$?


texts: Solving a recurrence relation with √n as parameter

texts:
Consider the recurrence

$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$

for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$.

I know the Master theorem for solving recurrences, but I'm not sure as to how we could solve this relation using it. How do you approach the square root parameter?


texts:
When do you use Turing- and when Karp Reduction? What are the advantages and disadvantages?

I've read about Karp Reduction mainly used in the Context of reducing a Language:

e.g. L1 $≤_p$ L2


texts: What will trigger a worst time search for a binary heap and what is the run time?

texts:
I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of $\mathcal{O}(n)$ because you will have to go through each and every single node to get to the value you want.

However, many sources state that heap has a worst case of $\mathcal{O}(n\log n)$ for (all?) transactions.

I don't see how you can do $n\log n$ for a monotonically increasing binary heap.

Can someone clarity?


texts: Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?

texts:
After removing multi-sets and sets that have elements that don't exist in $S$.

$S$ = $[9,6,7,4,5,1,8]$

$C$ =$[[9,6,7],[4,5],[1,8]]$

Transform the values in $C$ of the shared index values with $S$. (This must be done before touching $S$)

$C$ = $[[1,2,3],[4,5],[6,7]]$

And do the same for $S$

$S$ = $[1,2,3,4,5,6,7]$

Square each $x$ integer in both $S$ and $C$

$f(x)$ = $x^2$, $x ∈ S$ then $C$

$S$ = $[1, 4, 9, 16, 25, 36, 49]$

$C$ = $[[1,4,9],[16,25],[36,49]]$

Then remove all sets with repeating sums to prevent false positives. This means no $[1],[1]s...$ that could be used, to sum up to the total sum of $S$, This also means $[1,4,9]$ or $[4,9,1]$. (leave one though!)

After the transformation is complete use subset-sum solver and define total-sum as $140$ (total-sum of $s$)
Define list of integers as a summed up set of $C$ = $[[14],[41],[85]]$
Run Algorithm and get the solution

Question

Will this reduction of Exact Cover into Subset-Sum every yield a false positive?


texts: Proving that {0^{2^k}} is not regular with the Myhill-Nerode theorem

texts:
My language is the repetition of 0 to a length that's a power of 2:

$L = \{ 0^k \ni k=2^n, n \geq 1 \}$

I want to know how to prove that this language is not regular. I have attempted the proof below, but think it may be incorrect due to my potentially wrong assumption that the Myhill-Nerode theorem allows me to break up a regular language in the following way:

$j, p = 2^h$ for 2 distinct values of $h$, $h \in \mathbb{N}$:

$a = 0^{j/2}$

$b = 0^{p/2}$

$c = 0^{j/2}$

$ac = 0^{j/2}0^{j/2} = 0^j$ is in my language since $j$ is of the form $2^n$

$bc = 0^{p/2}0^{j/2}$ is not guaranteed to be in my language for every $p$ and $j$, since $j \ne p$

Thus my language must not be regular since $ac$ is in it but $bc$ is not.

Did I apply the Myhill-Nerode correctly? If not, what do I need to change in my proof?


texts: Would it be possible to use the cloud for RAM?

texts: I'm not sure if this is the right place to ask but I had this idea. Since the cloud can be used for storing memory, would it be possible to use it for RAM too?


texts:
Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable.

I don't think it's even recognizable, but I'm not sure. Regardless, I think I can show it's undecidable. Suppose $L$ is decidable by machine $D$. Then we can construct machine $S$ that decides the accepting problem, i.e. $\mathrm{ACC} = \{(M,w): M\text{ accepts }w\}$, which is undecidable.

For $S$ on input $(M,w)$, construct machine $M'$ with input $x$ such that if $x \neq 1100$, then loop, and if $x = 1100$, run $M$ on $w$. If $M$ accepts, then $M'$ halts. Next, run machine $D$ on $M'$. If $M'$ halts, then $D$ accepts. Otherwise, $D$ rejects.

So, if $M$ accepts $w$, then $x=1100$ and $M'$ halts, so $D$ accepts. On the other hand, if $M$ does not accept $w$, then $M'$ loops (and does not accept anything), and $D$ rejects. But then $D$ decides $\mathrm{ACC}$, which is undecidable. Hence, $L$ is undecidable.

Am I on the right track?


texts: Matching girls with boys without mutual attraction (variant of maximum bipartite matching)

texts:
Let us say you have a group of guys and and a group of girls. Each girl is either attracted to a guy or not, and vice versa. You want to match as many people as possible to a partner they like.

Does this problem have a name? Is it feasibly solvable? Sounds hard to me...

Ps. note that since the attraction is not neccessarily mutual the standard max-flow solution does not work.


texts: Show: "Checking no solution for system of linear equations with integer variables and coefficients" $\in \mathbf{NP}$

texts:
I've been struggling for a while trying to solve this problem:

Show that the following problem is in $\mathbf{NP}$:

  Check that a system of linear equations with $m$ integer variables and
  integer coefficients has no solution.

Let $L = \{\langle A, b \rangle\ |\ A \in \mathbb{Z}^m\times\mathbb{Z}^m\text{ and }Ax = b\text{ has no solution for }x \in \mathbb{Z}^{m} \}$

(please, feel free to correct if anywhere I'm wrong)

For showing that a language is in $\mathbf{NP}$ we have to construct a Turing Machine, indicating what we have chosen as certificate. If the TM is nondeterministic, then nondeterministically we pick a certificate and check the condition. If it is deterministic, we pass the certificate as one of the parameters (of the two parameters TM. The other parameter is, in this case, the pair $\langle A, b \rangle$).

I'm having trouble trying to choose the appropriate certificate.

My approaches:

1) Certificate: a vector $x \in \mathbb{Z}^{m}$, such that doesn't solve $Ax = b$. Issue: We would have to try every possible $x$ to show that $\nexists$ such vector for which solution may exist...

2) Certificate: Rank of $A$. if the $\mathrm{rank} A \neq m$, then the system has no solution and we $Accept$. Issue: doesn't necessarily mean that $x \in \mathbb{Z}^{m}$.

3) Consider $\overline{L} = \{\langle A, b \rangle\ |\ A \in \mathbb{Z}\times\mathbb{Z}\text{ and }Ax = b\text{ has a solution for }x \in \mathbb{Z}^{m} \}$.

Showing that the system has a solution seems easier than showing that there is no one. I guess the certificate has to be a vector $x \in \mathbb{Z}^{m}$, for which the $Ax = b$ is satisfied. Then, if I'm not mistaking, constructing a polynomial-time deterministic TM for $\overline{L}$ is straight forward. The thing is that this will show that $\overline{L} \in \mathbf{NP}$. This implies that $L \in$ co-$\mathbf{NP}$.

So showing that $L \in \mathbf{NP}$ would be equivalent to showing that co-$\mathbf{NP} = \mathbf{NP}$??


texts: The minimum three elements from two tuples of size 3

texts:
If I have two tuples (a1,b1,c1) and (a2,b2,c2), where we know each is ordered from smallest to largest, how would I return a tuple that takes the minimum elements from both tuples and orders them from least to largest?
I tried to break down the problem for two tuples so:
a1, b1 and a2, b2 are two tuples and we can do
if a1 < a2:
    if a2 < b1:
        return (a1, a2)
    else:
        return (a1, b1)
else:
   # similar for case above

But when there are 3 elements it's confusing me, so if anyone can help out I'd highly appreciate it. I don't want to try any sorting and instead use inequalities.


texts: How does each element in the output array of a DFT correspond to a specific frequency?

texts:
I have a basic understanding of the Fourier Transform, though I'm trying to use it in a program and I'm confused on the specifics. Based on source code I can find online, the DFT takes a set of samples/numbers, performs a summation for each term, and returns a set of these summations which is the same size as the input set. Suppose I have a periodic function. As I understand it, the output array should contain the amplitudes/weights of each frequency which sum to that function. What I can't figure out is how each frequency is encoded in the array as just an index. In each example I read, we just assign a summation at each iteration of the inner loop to the next consecutive index in the output array. How are these indices indicative of which frequency they correspond to?
I'm attaching the source code I'm referencing to the bottom of this in case the website I linked to ever goes down.
import cmath
def compute_dft_complex(input):
    n = len(input)
    output = []
    for k in range(n):  # For each output element
        s = complex(0)
        for t in range(n):  # For each input element
            angle = 2j * cmath.pi * t * k / n
            s += input[t] * cmath.exp(-angle)
        output.append(s)
    return output