texts: Is a secondary TM sufficient to detect all loops?

texts:
Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever reaches the same configuration as the first, a loop was detected (obviously).

Claim: All infinite local loops in a TM can be detected in the above manner.

Local loop, in this context, refers to a machine running within a certain tape interval without ever stopping. To clarify, in particular this excludes any machines which extend the tape in any direction without bounds.

Has this been proven? I'm pretty sure I found this claim in a paper, I believe one of Marxen's, though I can't seem to find it.


texts: How to detect Farkas or MPEG4 FDP points on image with a face?

texts:
Brief problem description

I'm using a Basel Morphable Face Model, which was labeled with MPEG4 and Farkas landmarks. I can generate different faces, use different lighting conditions, rotations, perspective etc.

I want to use it to train an algorithm in order to find these landmarks on real pictures further.

More strictly

Given a labeled set of images (with fixed size, if it's critical), I want to get a function $q\left( x \right)$ (where $x$ is an image), which will minimize loss expectation (Bayes' task)

$$E = \sum\limits_{x \in X, k \in K} P\left( k \mid x \right) \cdot W\left( k, q\left( x \right) \right)$$

$k$ is a tuple of feature points' coordinates like $<(x_1, y_1), (x_2, y_2), \dots>$.

Loss function is either

$$W\left(k, k'\right) = \sum\limits_{i=1}^n ||k_i - k_i'||^2$$

or

$$W\left(k, k'\right) = \sum\limits_{i=1}^n(1\; if\; ||k_i - k_i'|| > \Delta\; otherwise\; 0)$$

Maybe there is a better problem description, and loss expectation minimization is not suitable for this task?

Details

I guess, there are more specific algorithms for this issue than Brute Force (estimate probabilities by training set and use them to find landmarks on input images) or Artificial Neural Networks.

Why not ANN: the problem "as is" is incredibly hard. I have $44$ points, most of which have symmetric ones (so, it's something between $60$ and $80$). Given image $100×100$, I have at least $10'000^{60}$ different solutions and should find the best one (or weighted average in case of $l^2$ loss function). $10^{240}$ is a huge number. Add probabilities estimate to this Math carnival, and you'll get a problem of estimating probability function for $10'000$ dependent random variables via each image of the training set. So, if some general approach will work fast, I'm not sure that it will be accurate enough. The new problem will occur — what exactly will we lose when ANN will be applied?

Maybe two-dimensional context-free grammars can solve this, and I just need a proper representation to take scale and rotations into account.

Maybe the problem can be stated in terms of constraint satisfaction problem and solved efficiently.

Question

Which algorithms you can recommend for my purpose?


texts: Is there a faster algorithm for my graph problem?

texts:
I'm working on a tool that can analyze sizes of individual functions in a compiled binary. For each one it calculates how much space would be saved if the function was removed.

However, the current algorithm is quadratic in the number of functions and as such is quite slow. Is there a better one? The problem formulation follows.

Let $G=(V, E)$ be a directed graph with labeling $f\colon V\to\mathbb{N}$, and $R\subseteq V$ be a set of root vertices. Here, $V$ represents the functions in the binary. The graph edges represent the dependencies between the functions: $(u, v)\in E$ iff $u$ references $v$, thus forcing $v$ to be present in the binary. $f$ assigns to each function its size in bytes. Functions in $R$ (the main function in the executable or the set of exported functions in an .so) are the functions we want in the binary, the rest of them were pulled in directly or indirectly from $R$.

For a set of vertices $U\subseteq V$ and edges $F\subseteq E$, we define $r(U, F)$ as the set of vertices reachable from $U$ along the edged from $F$.

$$r(U, F)=\{v\in V\mid \exists r\in U. (r, v)\in F^*\}$$

We guarantee that $r(R, E)=V$, that is all vertices are reachable from $R$ in the original graph (not that it helps).

We define $s(U) = \sum_{u\in U} f(u)$ as the total size of all functions from $U$.

For each $u\in V$, let $E_u\subseteq E$ be the restriction of $E$ in which all edges adjacent to $u$ are removed. Then $r(R\setminus\{u\}, E_u)$ is the set of functions that will be present in the binary if we remove $u$. Note that other functions besides $u$ may disappear as they will no longer be reachable from $R$.

Our goal is to compute for each $u\in V$ the size of the binary after removing $u$, i.e. to compute $g\colon V\rightarrow\mathbb{N}$ at all points, where

$$g(u)=s(r(R\setminus\{u\}, E_u))$$

I can easily compute $g(u)$ in $O(|V|+|E|)$ with a simple depth-first-search. Computing the entire $g$ thus yields $O(|V|(|V| + |E|))$. Is there a faster algorithm?


texts: Application of difference array for overlapping glass-tint problem

texts:
For this problem, I heard that using a difference array can solve the problem but I can't seem to figure out how to solve this problem. Could anyone give me some advice? Please keep it simple since I am only a high school student preparing for the national infomatics Olympiad.

Given an array of numbers, we can construct a new array by replacing each element by the difference between itself and the previous element, except for the first element, which we simply ignore. This is called the difference array, because it contains the first differences of the original array. We will denote the difference array of array A by D(A). For example, the difference array of A = [9, 2, 6, 3, 1, 5, 0, 7] is D(A) = [2-9, 6-2, 3-6, 1-3, 5-1, 0-5, 7-0], or [-7, 4, -3, -2, 4, -5, 7].
Source

I've found a solution in Python , but I can't understand it.
Canadian Computing Competition: 2014 Stage 1, Senior #4:

You are laying N rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors.
You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the x-axis or the y-axis (that is, there are no "diagonal" pieces of glass).
You would like to know the total area of the finished stained glass window with a tint-factor of at least T.

Input Specification:

The first line of input is the integer $N$ ($1\leq N\leq 10^3$), the number of pieces of glass. The second line of input is the integer $T$ ($1\leq T\leq 10^9$), the threshold for the tint-factor. Each of the next $N$ lines contain five integers, representing the position of the top-left and bottom-right corners of the $i$-th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order $x_1$ $y_1$ $x_2$ $y_2$ $t$, where the top-left corner is at $(x_1,y_1)$ and the bottom-right corner is at $(x_2,y_2)$, and tint-factor is $t$. You can assume that $1\leq t\leq 10^6$. The top-most, left-most coordinate where glass can be placed is $(0,0)$ and you may assume $0\leq x_1<x_2\leq K$ and $0<y_1<y_2\leq K$, and ...

Output Specification:
Output the total area of the finished stained glass window which has a tint-factor of at least $T$.
I have an implementation but I'm not quite sure how it works. Any explanation would be greatly appreciated.


texts: Why does the denotational semantics for a while loop have a existence quantifier?

texts:
I was going through these notes and they have the following operator on partial functions:

$$
\mathcal F^{k}(\bot)(\sigma) =
\left\{
 \begin{array}{ll}
  \alpha(  [\![s]\!]\sigma )  & [\![b]\!]\sigma=true \\
     \sigma & [\![b]\!]\sigma=false \\
        \bot & [\![b]\!]\sigma=\bot
 \end{array}
\right.
$$

and supposedly it gives the following definition somehow (which ends up being the right denotation for while loops)

$$
\mathcal F^{k}(\bot)(\sigma) =
\left\{
 \begin{array}{ll}
    [\![s]\!]^i  & \mbox{if $ \exists i \in [0,k)$  s.t. $ [\![b]\!] [\![s]\!]^i \sigma = false,\ [\![b]\!] [\![s]\!]^j \sigma = true,\ j \in [0,i) $}\\
     \bot & \mbox{ o.w. }
 \end{array}
\right.
$$

the proof by induction is shouldn't be hard. However, it feels that it doesn't really answer the question for me intuitively because I could do the induction mechanically without understanding what is going on. Why isn't the definition something like:

$$ f(\sigma,i) = [\![s]\!]^i\sigma$$

then the induction is easy:

$$ f(\sigma,0) = [\![s]\!]^0\sigma =  \sigma$$

then the inductive step:

$$ f(\sigma,k+1) = f \circ f{\circ}^k(\sigma)= f \circ[\![s]\!]^{k}\sigma$$

but also notice $f = [\![s]\!]^1\sigma$ by strong induction:

$$ f(\sigma,k+1) = [\![s]\!]^{k+1}\sigma$$

as required. But that doesn't seem at all to be the sort of argument being used (assuming what I wrote is right). Did I miss something?


texts: I am trying to figure out if this truth table is possible. I've tried inverting the numbers, adding them, subtracting them, but I still cant find anything that works. I am starting to think that this is not possible.


texts: lower bound proof with adversary argument

texts:
We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full or empty is to put them in the Walkman and try it out. We cannot tell which one is empty or full if we put inside one full and one empty.

The question is to find the minimum needed step to run the walkman (to find 2 full batteries)

I modeled the problem like that :

  Let the Walkman br a function $f$ which take two arguments and returns 1 if the walkman works, and 0 otherwise.
  $$ f\colon \{b_1,b_2 \dots b_{30}\} \times \{b_1,b_2 \dots b_{30}\} \rightarrow\{0,1\}$$

I was given a hint to use the Turán lemma:

  When a graph $G=(V,E)$ with $V$ the vertex set and $|V|=n$ does not contain a $k$-clique with $k >1$, then
  $$ |E|\leq \left(1-\frac{1}{k-1}\right)\frac{n^2}{2} $$

The idea was to consider the batteries as vertex and create a complete graph and then when $ f(b_i,b_j)=0$ we delete the edge between $b_i$ and $b_j$.

Using the adversary argument I have to prove that the lower bound to find the battery must be 18, so any help how to solve this?


texts: Average Case Running Time of Quicksort Algorithm

texts:
From this website, it states that the average case of Quicksort algorithm is

  T(n) = T(n/9) + T(9n/10) + θ(n)

Im a bit confused. Is it supposed to be ?

  T(n) = T(n/10) + T(9n/10) + θ(n)


texts: Potential General Model of Computation with Physics?

texts:
I posted a question about a month back regarding the significance of Turing machines (relative to other models of computation). In that post, I mentioned vaguely some conversion between an input string and a physical system as a model of computation. (I just got my BS in CS, so it's likely I have no idea what I'm talking about.)

Would the following be a valid, or at least meaningful, general model of computation:

Let $ f: Z \mapsto Z$ be a function. Then, $f$ is computable iff for all integers $a$, there exists a bijection $P$ from the integers to formal physical systems (Classical mechanics?), such that when $P(a)$ is "set into motion", it reaches and equilibrium or static state $s$ where $P^{-1}(s) = f(a)$.

If this makes sense, please let me know.


texts: DP recurrence relations: Coin change vs Knapsack

texts:
Take:

KP recurrence relation

$ max { [v  + f(k-1,g-w ), f(k-1,g)] } $    if w <= g and k>0

CCP recurrence relation

$ min {[1  + f(r,c-v), f(r-1,c)]} $      if v <= c and r>0

I don't understand (much as I've researched) exactly what the reasoning is behind KP comparing in both cases (take the element/don't take it) to the above row $('k-1')$ while CCP only does this when it doesn't take the coin (the same number that's a row above in the same column persists).

To evaluate the case where the coin is taken, CCP says to go back on the same row as much columns as you get when subtracting the coin value of that row from the column you're in . Then it says to add 1 (because you'd be taking the coin).

Supposing I understood this well enough, the latter logic makes perfect sense to me. I don't see the need for KP to go up a row when taking the element (I see why it adds 'v' and goes back a number of columns, it's just the $'k-1'$ that baffles me)

What's the logic behind this?

_

EDIT:

Underlined in red you'll find what I'm referring to, more especifically.

  Knapsack 0-1 Problem:

Take the 24 : it's the result of comparing the 15 directly above it (not taking the element) to the 15 up and to the left (taking the element) . This last 15 is not on the same row as 24 is.

See source: http://www.mafy.lut.fi/study/DiscreteOpt/DYNKNAP.pdf

  Coin Change Problem:

Goes back on the same row where our starting point is(case where coin is taken).

See source: (page 2): http://condor.depaul.edu/rjohnson/algorithm/coins.pdf


texts: Undirected min cut has a well known poly sized LP formulation by expressing the problem as one of finding a certain metric on the vertices minimizing the sum of distances on edges. Can this be extended to directed min cut? If not, is there a different, simple, poly-sized LP for the problem?


texts: Detecting rotational symmetries of spatial structures

texts:
I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of these structures? In particular, I'm interested in all the rotational axis along which I can rotate the structure to overlap itself, as well as the degree of rotation. For example, an equilateral triangle (3 vertices + 3 edges) would have one rotational axis perpendicular to its plane, with a degree of 3 and 3 others in its plane, with a degree of 2 each.
The closest I could find are molecular packages identifying the symmetry groups of molecular structures. I would prefer not to go that far as I'm only interested in rotational symmetries and not entire group theory description of structures.


texts:
Do the following two CFGs describe the same language

S → aS | bS | ε
S → aS | Sb | ε

Would the answer to this be no, because the order can't be switched? bS and Sb are different. I'm a bit confused about how I would find out if they described the same language.


texts: complexity of determining whether a language given by context free grammar is empty

texts:
I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word of length $\leq 2^n$ (or maybe $\leq 2^{n+1}$, I'm not sure) belongs to the language, where $n$ is IIRC the number of nonterminals in CNF. If not, then no longer words belong either and the grammar is empty.

The above algorithm has the unpleasant property of having exponential complexity. The questions that interest me are:

Is there a polynomial algorithm to check whether given CFG represents empty language?
What's the (asymptotically) best known algorithm for that?
What's the simplest polynomial algorithm for that (not necessarily having best known complexity)?


texts: Utilization of static evaluation functions in chess

texts:
Disclaimer: I'm very new to computer science & game programming

I'm having trouble with understanding how to implement a static evaluation function in chess. The logic seems simple like just apply a weight to each piece on the board and subtract the pieces from each side, but its much more complex than that isn't it? You'd have to calculate a method of analyzing the board and each of the MULTIPLE actions that are occurring on the board at the same time (ie. Castling, checking pawns are being lost, if you're in check etc etc).

Is there a relatively simple way of implementing a static evaluation function to a chess board to "see" whats going on at each stage?

Side Note: I understand that you could implement things like Minimax (with $ \alpha - \beta$ pruning) searches onto the trees created via the static evaluation functions, so correct me if I'm wrong but whats going on is that $$ f(Board) = c_1 * (thing 1) +  c_2*(thing 2) + \cdots $$ but where do those $ \cdots$ end??? And from there, we get a number which we put in our tree then implement the minimax algorithm, to figure out the best move forward?

Are there any resources for this type of thing that I could possibly read? Thank you.


texts: Using induction vs invariants to prove correctness of algorithms

texts: In my algorithms class I have generally been proving algorithms by induction. So for example, given some algorithm $A(n)$ that computes $x$, I show that the algorithm works for some base case, say $A(1)$, then I assume that the algorithm will work for $k<n$. Then I show that the algorithm works for some $z=n$. Are there cases where this won't work or where this isn't recommended? I see algorithms textbooks commonly define loop invariants, and then show that the invariant holds before and after the loop. Is this approach always necessary when dealing with loops? Can't I just assume that it will work for the case where $z=n-1$ and then show it works for $z=n$ i.e. using normal/strong induction?


texts:
I've just read in a discussion about dynamic typing

  Reflective towers is an open problem for statically typed languages.

What are reflective towers?

I think it might be related to reflection, but I'm not sure.

If you create an example, I would prefer Java.


texts: Is there a line that separates two sets of points?

texts:
You have two $n$-point sets $P$ and $Q$ of two-dimensional points:
  $$
P = \{p_1,\dots,p_n\}, \text{ where } p_i = \{a_i, b_i\} \\
Q = \{q_1,\dots,q_n\}, \text{ where } q_i = \{c_i, d_i\}
$$

  You must determine whether there is a line $L$ so that $P$ and $Q$ are on opposite sides. This line essentially must separate both of the sets. The algorithm must run in $O(n)$, and is aimed to be deterministic (yes or no).

Could anyone provide help regarding this problem?


texts: Can you give an inductive definition to define the length of a list L?

texts:
Having trouble understanding what it means to define something inductively in the following context.

  Can you give an inductive to define the length of a list L?

  a. The total number of items in L is the length of L

  b. Basis: the length of an empty list is 0
  Induction: the length of a list is 2*(length of half the list)

  c. Basis: the length of an empty list is 0
  Induction: the length of a list is (length of head(list))+(length of tail(list))

  d. Basis: the length of an empty list is 0
  Induction: the length of a list is 1+(length of tail(list))

The answer is (d). Why might this be?

And also for this similar question:

  Can you give an inductive definition to define what it means for an element X to
  be a member of a list L?

  a. X is a member of a list L if and only if X belongs to the list L.

  b. X is a member of a list L if either X is the head of the list or X is a member of the tail of L.

  c. X is a member of a list L if we can find an element Y in L and X=Y.

  d. X is a member of a list L if we can find an element Y in the tail of L

The answer is (b).

Thank you.


texts:
I know you can convert every context-free grammar into Greibach normal form grammar.

But can I convert every deterministic context-free grammar into deterministic Greibach normal form grammar?


texts: Complexity of domino tiling with dominoes placed in a line

texts:
Let's say I have a bunch of cards or dominoes with one color on the left side of the
card and another color on the right. (The two colors could be the same.)
Dominoes can't be rotated so the color on each side is fixed. There is no
limit on the number of colors and colors can be repeated on cards.

Dominoes are placed in a line, one after another.

The rule is, the color on the right hand side of a domino must match the
color on the left hand side of the domino placed next to it.

The problem is, given a pool of dominoes, is it possible to put all of the
dominoes in a line while following the rule? (I believe this is the same
problem as given a group of matrices is it possible to multiply them all
together.)

So for example given these dominoes: R-R, R-B, G-Y, GG-Y, Y-GG, R-R, R-B,
..., R-B, B-R, P-G is it possible to form a straight line with all
adjoining sides having the same color.

My real question is this: Is the complexity of this problem (determining
if it is possible to put all N dominoes in a line) NP?


texts: Calculate the number of elements after multiplying/adding two polynomials

texts:
Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients.
I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial has.
I want to determine the amount of significant coefficients in the results of
$f(x) + g(x)$ ,$f(x) \cdot g(x)$ , $f(x) - g(x)$ etc. .

But I'd like to do it before I create the object that holds them, is there some efficient way of doing this without calculating the result twice?

I can assume that I know the current rank and number of elements in $f(x)$ and $g(x)$

If this is not possible knowing that the new polynomial's non-trivial coefficients will be at least half of the rank will suffice, but I'm unsure how to do it as well.

I did try to apply various heuristics but didn't come up with something consistent and fast.


texts: Simple way to extend period of LCG (expected cycle length)?

texts:
Let's consider 128-bit pseudorandom generator. From Harris 1960, if we model uniform random permutation, we know that every period length $l$ has equal probability $1/n$ (Eq. 5.2) for any particular starting point, where $n = 2^{128}$ is the size of the domain, so the expected cycle length is $\sum_{i=1}^n i/n = (n + 1)/2 \approx 2^{127}$.
We know that in typical LCG's modulo $2^{128}$ it is not always the case:
https://en.wikipedia.org/wiki/Linear_congruential_generator
We can use Hull–Dobell Theorem to achevie period equal modulus. But what period we could expect in general in LCG, when we will choose multiplier and increment randomly? Let's consider only LCG's modulo $2^{n}$. And the main question. Let's consider some simple modification of LCG - compute output in (binary) little endian, in other words our output is reversed block of ordinary LCG. What period or expected cycle length we can expect with such modification?
My preliminary experiments indicate that these cycles will be larger than in regular LCG's. But I checked not much LCG's that way. Also I'm looking for some mathematical aproach or proof.


texts: Find coverage for plane from half-planes

texts:
The document (see pic. below) states that it is possible to find a cover of the plane by a subset of 3 half-planes. It proposes to use linear programming for this. How to formulate such a program?

The original document can be found here: On the Separation of a Polyhedron from Its Single-Part Mold.

EDIT: For clarity: i need to understand how can i use LP to find subcoverage of size 3 from coverage of bigger size.


texts: Euclidean algorithm - runtime in specific case

texts:
I'm going to solving many times this specific equations:

$$2^{x+y} \cdot c - a^{y} \cdot z = 1$$

in which $$a$$ can be equal to: $$-7,-5,-3,-1,1,3,5,7.$$ And $$x+y$$ will be equal to $$128.$$ It has to be done with euclidean algorithm, but how many step it requires in average in this specific case?

I know that euclidean algorithm requires at most $$5\log_{10}b$$ steps (Wikipedia), where b is the smaller number, but in this case we don't know which number will be smaller, $$2^{x+y}$$ or $$a^{y}.$$ That's why I have a problem with this case.


texts: Optimization of Hierarchical Data Propagation

texts:
I have a system in existence which works on parent-child model.

They share common attributes, as they belong to same class.
A parent can enforces certain data on any user selected attribute, and the data is required to be propagated down the hierarchy for the same attribute in all children and their children.
For a given attribute, if a child's parent dies (object gets destroyed) or child has not been enforced by parent, child can behave the same way, like in point #2, (on user request) for its children.

My system is pretty big (in database). For example:

Each object of the class has 150 atributes.
There are in total about 8 million attributes for objects created. Hence, the objects are close to 53,333.
There is a single parent for the objects. Its a big tree.

If I want to enforce data on the top most parent for a single attribute, it takes about 8 mins for it to complete.

Does anyone know a model which can perform faster than hierarchical model, but similar to behaviour?


texts: How to position images within a canvas while avoiding overlapping

texts:
I have a canvas. On this canvas, I want to position 1, 2 or 3 images.  The images can be positioned anywhere on the canvas just as long as they're within the canvas. The images move by their top-left corner.  To make sure that the images do not leave the canvas, I am doing this:
image_topLeft_x_position = random.randint(0, (canvas_width - logo_width))

image_topLeft_y_position = random.randint(0, (canvas_height - logo_height))

I can save these locations in a list of tuples like this:
locations = [(image_topLeft_x_position, image_topLeft_y_position)]

After saving a location, I want to generate new locations within the canvas that don't overlap with the previous ones.  However, I've been stuck on this problem for well over a day. Any help is appreciated.


texts: If L is regular, show that even(L) is also regular

texts:
I am stuck on the following question.

  If $L$ is regular show that $\mathrm{even}(L)$ is also regular, where $\mathrm{even}(L) = \{ even(w) : w \in L \}$, $w$ is a string in $L$ and $\mathrm{even}(w)$ is the string obtained by extracting from $w$ the letters in even numbered positions.

How can I prove that $\mathrm{even}(L)$ is also regular?


texts: Essence of the cost benifit obtained by using "markings" in Fibonacci Heaps (by using a mathematical approach)

texts:
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al

The authors deal with a notion of marking the nodes of Fibonacci Heaps with the background that they are used to bound the amortized running time of the $\text{Decrease-Key}$ or $\text{Delete}$ algorithm, but not much intuition is given behind their use of it.
What things shall go bad if we do not use markings ? (or) use $\text{Cacading-Cut}$ when the number of children lost from a node is not just $2$ but possibly more ?
The excerpt corresponding to this is as follows:

We use the mark fields to obtain the desired time bounds. They record a little piece of the history of each node. Suppose that the following events have happened to node $x$:

at some time, $x$ was a root,
then $x$ was linked to another node,
then two children of $x$ were removed by cuts.

As soon as the second child has been lost, we cut $x$ from its parent, making it a new root. The field $mark[x]$ is true if steps $1$ and $2$ have occurred and one child of $x$ has been cut. The Cut procedure, therefore, clears $mark[x]$ in line $4$, since it performs step $1$. (We can now see why line $3$ of $\text{Fib-Heap-Link}$ clears $mark[y]$: node $у$ is being linked to another node, and so step $2$ is being performed. The next time a child of $у$ is cut, $mark[y]$ will be set to $\text{TRUE}$.)

[The intuition of why to use the marking in the way stated in italics portion of the block above was made clear to me by the lucid answer here, but I still do not get the cost benefit which we get using markings what shall possibly go wrong if we do not use markings, the answer here
 talks about the benefit but no mathematics is used for the counter example given]

The entire corresponding portion of the text can be found here for quick reference.


texts:
Just out of curiosity:

Do there exist algorithms for which the Big-O cannot be found out?

I have done a quick search in the google search bar:
"Big o, impossible to evaluate"
"algorithms without big o"

And these gave results which were unsatisfactory. Mostly, teaching me how to find the big o. Nothing I haven't learned earlier.

On a side note, it is my understanding that finding the big o requires us to assume the worst possible case. But, is that always a correct metric for efficiency? What is the likelihood a function is called with the worst possible argument?


texts: Chernoff-like Concentration Bounds on Permutations

texts:
Suppose I have $n$ balls. Among them, there are $m \leq n$ black balls and the other $n - m$ balls are white. Fix a random permutation $\pi$ over these balls and denote by $Y_i$ the number of black balls in the first $i$ positions of our permutation $\pi$. I would like to show that $Y_i$ is sharply concentrated around its mean.

The expected value

It is not hard to compute the expected value of $Y_i$: the probability that a black ball appears somewhere along the first $i$ positions is $i/n$; moreover, there are $m$ black balls, hence $$\mathbb{E}[Y_i] = \frac{m\cdot i}{n}.$$

But can we show that $Y_i$ is actually very close to its mean?

A failed attempt

For every black ball $b$, one can define an indicator variable $X_b$ which equals 1 if $b$ appears in the first $i$ positions of $\pi$ and 0 otherwise. Denoting the set of all black balls by $B$, we have

$$ Y_i = \sum_{b \in B} X_b.$$

I was hoping to be able to use a Chernoff bound type of a concentration bound, but unfortunately for two black balls $b$ and $b'$, $X_b$ and $X_{b'}$ are not completely independent. If $X_b = 1$, then there are only $i-1$ spots left for $b'$ to appear in the first $i$ locations and hence the probability of $X_{b'}$ being 1 gets smaller.


texts: The wikipedia page about comb sort claims that the average complexity of comb sort is Omega(n^2/2^p) where p is the number of increments. Take as example an uniform distributed array of 1000 elements, using the standard shrink factor of 1.3 the length of the gaps list is 23. Is this the p mentioned in the wikipedia article? If it is the complexity is omega of 1000^2 / 2^23 ~ 0.120 Someone could please explain what I don't understand? Thank in advance


texts: undecidability proof by using Turing Machines

texts:
I have been reading some material about undecidability of a language, and I am not quite sure of one part. For what I see:

I start with a decider H, that has an input <M,w> where M is a Turing Machine and w is a string, so I have the following:

H(<M,w>)=accept if M accepts w
         rejects if M rejects w

all fine until this point. Now it says that I construct a new Turing Machine D, and this TM has H as a subroutine. If I make a graph I imagine something like this:

-------------      D that is a TM
|   -----   |
|   | H  |  |
|   |____|  |
|___________|

So it says that D calls H to determine what M would do if the input is M, it means something like:

H(M,<M>)

Now it says that it should do the opposite this decider H, it means that:

H(M,<M>)=reject if M accepts <M>
         accepts if M rejects <M>        ---------(1)

and this procedure can be generalized for D like:

D(<M>)=accept if M does not accept <M> ----------(2)
       reject if M accept <M>

I have two questions here, for not opening another thread, but in part (1) why the decider H makes the opposite? What would happen if it does not? I have read in a book that the argument is that sometimes a program can receive a program as an input, such as in a compiler, why it decides to do the opposite?

The interpretation of part (2) does it mean that the Turing Machine D, with input M, this input refers to the same Turing Machine that was put as an input for the decider H?

At the ends there is a contradiction, but I cannot get it, why in step (1) it is decided to do the opposite?


texts: Practical Applications of regular grammars

texts:
A regular grammar is a mathematical object, $G$, with four components, $G = (N, Σ, P, S)$, where. $N$ is a nonempty, finite set of nonterminal symbols, $Σ$ is a finite set of terminal symbols , or alphabet, symbols, $P$ is a set of grammar rules, each of one having one of the forms. $A → aB$.

I want to know what's Practical Application of these grammars.  I mean where and how do we use these in real world?

Also it may be helpful if someone tells me about the weaknesses of regular grammars.

Thanks in advance.


texts: A question on analysis of the time complexity of a recursive branching algorithm

texts:
I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows:

  Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\alpha(G)$ be the cardinality of an maximum independent set of $G$. If $G$ is empty, output $\alpha(G)=0$(base instance). Otherwise, choose any node $v$ of maximum degree, and output
  $$\alpha(G)=max\{\alpha(G-\{v\}),1+\alpha(G-N[v])\}$$
  where $N[v]$ is the set of $v$ and its neighbors.

The running time of the above algorithm can be bounded as follows:

  The recursive calls induce a search tree, where the root is the input instance and the leaves are base instances. Observe that each branching step can be performed in polynomial time(excluding the time needed to solve subproblems). Therefore, the running time of the algorithm is bounded by $O^*(L(n))$, where $L(n)$ is the maximum number of leaves of any search tree generated by a $n$-node graph.Let us assume $L(n)\le c^n$ for some constant $c\ge 1$. When we branch at node $v$ we generate two subproblems containing $n-1$ and $n-|N[v]|$ nodes.Therefore $c$ has to satisfy $$c^n\ge c^{n-1}+c^{n-|N[v]|} \tag{1}$$

Question I couldn't figure out why inequation $(1)$ holds, and I was wondering the meaning  behind the inequation from a more intuitive perspective.

The original paper is rather long and I've tried to describe my question without lose of information. But if you need more information, please let me know in comments, I'll update it.


texts: Rational agent question from Russell and Norvig

texts:
Question from Artificial Intelligenge: A Modern Approach by Russell and Norvig (Exercise 2.1).

  Suppose that the performance measure is concerned with just the first
  $T$ time steps of the environment and ignores everything thereafter.
  Show that a rational agent's action may depend not just on the state
  of the environment but also on the time step it has reached.

This question is extremely confusing to me. My initial thought is that this is obvious. A rational agent wants to maximize its performance, and the first $T$ time steps are a factor in the performance measure. So for instance, if the environment is in state $A$ at time step 1, the performance measure can be different than being in state $A$ at step 2 since the state of the environment in step 1 is relevant to the performance measure in the latter case. Thus as the performance measures can be different, the rational agent may make different actions.

Perhaps that is the answer, but I am still confused on why it matters that the performance measure is concerned with only a finite sequence of initial time steps. My interpretation of the question seems to make that irrelevant. Only the fact that the performance measure has some historical factor is of any concern.

Can anyone help clarify what is happening in this question?


texts: Failing to understand the pseudo code of the inorder traversal

texts:
Edit: Solved, see comments

I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is:

sub P(TreeNode)
   If LeftPointer(TreeNode) != NULL Then
      P(TreeNode.LeftNode)
   Output(TreeNode.value)
   If RightPointer(TreeNode) != NULL Then
      P(TreeNode.RightNode)
end sub

If I've understood correctly, then the algorithm above, for the BST below, would first traverse to the node with element 5 and then output it. After that, it checks whether the right child of that node is NULL, which it is. Doesn't the algorithm stop there?

Or is the pseudo code above incomplete? I have looked at quite a few sites and they all give the same short code. If it is incomplete, what would I have to add to the pseudocode so that it walks through the whole tree?


texts: Sequence of operations of Union-Find of length $m$ ($n$ being the number of Make-Set operations) with time complexity in $\Omega(m\log n)$

texts:
In Union-Find with link-by-rank but no path compression find a sequence of operations Make-Set, Find, Union of length $m$, containing $n$ Make-Set operations, and with time complexity in $\Omega(m\log n)$.

My idea was to spawn $n$ nodes with $n$ Make-Set operations and then create a "tree" with $\log n$ height out of them. That would take $\frac{n}2 + \frac{n}4 + \ldots + 1$ (this sequence is $\log n$ long) Union operations.

Now I would be able to keep calling Find on this tree as long as necessary.

However I have no idea if this is the right way because I don't know how to sum up the complexity of the sequence of these operations.


texts:
This is similar to a previous question I asked, but doesn't seem aminable to the same technique. Given a regular language $A$, show the following language is regular:
$$
\{x|\exists y \; |y| = 2^{|x|} and \; xy \in A\}
$$
I'm aware of the notion of regularity preserving functions, and that it would suffice to show that $f(x) = 2^x$ satisfies the property that for an ultimately periodic set $U$, $f^{-1}(U) = \{m|f(m) \in U\}$ is ultimately periodic. I'm struggling to $f$ has this property, but the book from which this comes implies a solution not using this is possible. It appears to be looking for a construction.
I can see that by repeated application of the idea behind the Pumping Lemma, if $A$ has DFL with $k$ states, that for any $x$ with $|x| \geq k$ then
$$
\exists y \; |y| = 2^{|x|} and \; xy \in A\ \implies \exists y \; |y| \leq k \; and \; xy \in A\
$$
But this doesn't give anything going in the opposite direction, that shows that some suitably short $y$ guarantees the existence of a $y$ of the required length.
Any help in solving this, or hint at how to progress would be very helpful.


texts: Non recursively enumerable language proof by reduction to non-HP

texts:
I am trying to understand how the reduction proof for non r.e. languages works by following the examples from this website. In most cases to prove that a language is not r.e., you can reduce the language to the non halting problem which is not r.e.

For example, if I have

$$L_2 = \{\langle M\rangle\mid M \text{ is a TM and }|L(M)|\leq 3\}\,.$$

I construct $\tau(\langle M, x\rangle) = \langle M'\rangle$ such that $M'$ on input $w$: it
erases its input, copies $M$ and $x$ to its tape, and runs $M$ on $x$; it accepts if $M$ halts on $x$. Then I prove the reduction is valid (see website)

But then if I have the language

$$L_4 = \{\langle M\rangle\mid M\text{ is a TM that accepts all even numbers}\}\,,$$

I construct $\tau (\langle M, x\rangle) = \langle M'\rangle$ such that
$M'$ on input $w$: it
runs $M$ on $x$ for $|w|$ steps; it rejects if $M$ halts on $x$ within $|w|$ steps, and accepts otherwise.

I know this may sound like a stupid question but beginnings are always hard until you understand the main logic behind it but why does $M'$ need to reject when $M$ halts? Why not accept when $M$ halts like in the first case?


texts: If we have a static implementation of branch prediction and we always fetch the next sequential instruction isn't inefficient to do that if we, at a future point verify if the prediction was correctly done? We just evaluate the branch in future... Why don't we just simply verify this thing every time we encounter a branch and not just execute what we think it's correct? I see here a delay because we double check the incorrect situations. 10 predictions, 4 wrong => 14 evaluations instead of 10. I know I'm wrong but I can't figure it why.


texts: Is Functional Complete means Turing Complete?

texts:
I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates.

A Turing machine may halt or not in a particular input but a combinational(not sequential) logic circuit always gives an output in a particular input. You may not agree with my point on combinational circuit but a combinational circuit is just a deterministic system so I can evaluate step by step in a input until it gives an output, in other words, there is no loops in a combinational circuit, I think.

So, I want to know whether I can represent any computable function only by those three gates ?

Any way, thx!


texts:
Given the sentences, S1, S2, if S1 |= S2 then all models that satisfy S1 also satisfy S2, how is the following statement correct?
A ∧ ¬A |= B
How can something and not something equate to true?
I am stuck trying to work out how true and false can still entail true, actually how can A and ¬A occur at the same time?
Thanks.


texts: Ranking (k-best) or genetic coding for spanning arborescences

texts:
I am wondering if there is a simpler way to rank spanning arborescences or any way to code spanning arborescences genetically.
According to the comment by @BearAqua in my another question, min spanning arborescence can be applied for multi directed graphs. However, I need multiple "good" solutions, which should resemble the min spanning arborescence in a meaningful way.
For ranking spanning arborescences (or k-best spanning arborescences), which finds the second minimum, the third minimum, ... solutions in sequence, I found two papers [camerini1980k] and [camerini1980ranking], which are too hard for me to implement.
Genetic (evolutionary) codings can be used to find similar solutions as well. They are used mainly in genetic algorithms or other heuristic algorithms. For example, there are 8 ways to code spanning trees summarised in [raidl2003edge]. However, it seems that there is no genetic coding designed for spanning arborescences.

By the way, the genetic coding must support in-complete graph. That is, some edges will be removed first, and the corresponding algorithms for the proposed genetic coding must be able to generate candidate in the feasible region.

[camerini1980k] Camerini, P. M., Fratta, L., & Maffioli, F. (1980). The k best spanning arborescences of a network. Networks, 10(2), 91-109.
[camerini1980ranking] Camerini, P. M., Fratta, L., & Maffioli, F. (1980). Ranking arborescences in O (Km log n) time. European Journal of Operational Research, 4(4), 235-242.
[raidl2003edge] Raidl, G. R., & Julstrom, B. A. (2003). Edge sets: an effective evolutionary coding of spanning trees. IEEE Transactions on evolutionary computation, 7(3), 225-239.


texts: About the relationship between non-termination and inconsistency?

texts:
I've been trying to get into Agda and I noticed that it doesn't have recursion, which implies that it isn't Turing-Complete.

From what I could understand, if Agda had recursion, it would make itself an inconsistency from a type theory perspective.

Something stuck to my mind: Is it possible to exist a language that it isn't strongly normalizing but, yet, consistent? Or does the existence of recursion mandatorily implies inconsistency?


texts: Set Basis Problem Variant reference for NP-Completeness?

texts:
Given: Collection $C$ of Subsets of a finite set $S$, positive integer $K <=|C|$

Problem Statement: Is there a collection $B$ of subsets of $S$ with $|B| = K$ such that for each subset $c$ in $C$, there is a sub-collection in $B$ whose union is $c$ ?

This Set Basis Problem is NP-Complete.

If we enforce an additional constraint that $B$ is a subset of $C$, is the problem still NP Complete?

My assumption is yes, but I could not find any reference to this problem. Can anyone please point out to one?


texts: Unification --- removing equations and updating the solution

texts:
This question is concerned with the first order unification. Suppose I have a set $D$ of equations and a solution to these equations. Let this solution be a set $S$ of substitutions. Now, suppose I remove some equations from $D$. Is there an algorithm that just uses these removed equations and quickly updates $D$, or the unification
needs to be done from scratch?

(In my application, I tend to have a lot of equations, so that is why I am interested in a solution that does not recompute everything.)


texts: Performance of row- vs. column-wise matrix traversal

texts:
Scott Meyers describes here that traversing a symmetric matrix row-wise performes significantly better over traversing it column-wise - which is also significantly counter-intuitive.

The reasoning is connected with how the CPU-caches are utilized. But I do not really understand the explanation and I would like to get it because I think it is relevant to me.

Is it possible to put it in more simple terms for somebody not holding a PhD in computer architecture and lacking experience in hardware-level programming?


texts: How to find longest recurring pattern from lage string data set?

texts:
I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example

TYUFRIETEYM0SQZLHBCTN0W1KA9HELAT4LTQ14W7ZW484GSK1XTNOBJ2R6AMGW9KU36G7ITMPF315Y7ESYPR1XE2C1953J0DXUNBJLNTDG7IHS63854SGSS7YDEFJYSFP0DLL54GK6NUZ5UU5FRIETEYCPNGHIJOX23QOVSCBYHKE7HRIETEYV0H49I5SX9CW967CDGKX3TYCVNVBNCFGGDGDGDDFIIPGDSDVGDDSRGDGVCZAQRIOPKLMVFGCDGDTYGSDCBGDUSLVAQEFCGDGRIETEYDGDFG

In above character set there is two substring one is GD and other is RIETEY algorithm able to identify RIETEY because it is longest the substring, also pattern must occur at least twice to be considered a recurrence and patterns will not overlap.

I found a algorithm but it only work for less that 100,000 characters

any suggestion for this problem  ?


texts: Computer Generated If-Statements to create A.I

texts:
Just a thought-experiment, could a program be written so that the computer generates it's own if-statements (semi/randomly) and runs them, gathers the results, then tests them in new scenarios, and iterates from there?
This idea came to me because it's kind of how we humans operate.  When we're born, we have a genetic foundation (programming language), and through experience, trial-and-error, cause and effect, etc. we learn about our world and create new "truths" about our world and ourselves (if-statements that are found to be 'true' are ones that were tested and had some kind of result).
How a program would deem an if-statement has worth is what I'm unsure of, at this point.  It would generate so many non-sensical if-statements, but eventually one would be written that could pass.  Most likely, it would have to tie in to some other network, like with humans it's our sensory organs, so whatever analog for a computer we could make that would tie-in to its if-statement library.
What do you think?


texts: Reference Request - Typed First-Order-Logic Book

texts:
There are many great references for computer scientists interested in untyped first order logic, such as Melvin Fitting's "First-Order Logic and Automated Theorem Proving" or John Harrison's "Handbook of Practical Logic and Automated Reasoning".

However, I have been having difficulty finding a solid reference that specifically deals with typed (or "many-sorted") first-order logic.

While much knowledge of untyped first-order logic transfers well to a typed setting,  there are some interesting questions specific to typed first-order logic that I am interested in seeing a rigorous treatment of, possibly with sample implementations. An obvious example is type-checking, but another is whether it is useful in a typed setting to syntactically distinguish between formulas and terms, or if formulas should just be treated as terms of type Bool, and the consequences such decisions have on computing normal forms. I'm sure there are other interesting questions as well.

Are there any books you can recommend that have a focus, or even just a lengthy enough chapter, specifically dealing with typed first-order logic?

EDIT: There are some resources listed on Wikipedia for Many-Sorted Logic, however many have to do with Order-Sorted Logic (which is a more sophisticated kind of typed logic than I am looking for, I am only looking for a basic many-sorted logic with disjoint types), or are about one specific kind of algorithm (e.g. Resolution).

One suggestion on there that I like is the first chapter of Calogero G. Zarba's  decision theory lecture notes, though it does not really go into the depth I was hoping for and is written more as a summary of definitions, whereas I was hoping more for a thorough book along the lines of Fitting or Harrison.

Perhaps this is too much to hope for as simple many-sorted first-order logic is very similar to untyped first-order logic.


texts:
I have read that TSP and Subset Sum problems are NPC problems which are also NP Hard. There are also problems like Halting Problem which is NP Hard, but not NP Complete

And Wikipedia defines this as

  A problem $H$ is NP-hard if and only if there is an NP-complete problem
  $L$ that is polynomial time Turing-reducible to $H$.

Like NP Complete problem is there any problem considered to be the first NP Hard problem?

To show one problem to be NP Hard we need just to reduce one NPC problem to it?

Whether all NPC problems are NP Hard?

If no, why not?


texts: Proving specific prefixes of regular languages are regular

texts:
There are particular problems in Kozen that I'm unable to solve, and they seem to be similar to each other. It is showing that sets:

$$ \{x \mid \exists y: |y| = 2^{|x|} \text{ and } xy \in A \}$$
$$ \{x \mid \exists y: |y| = |x|^2 \text{ and } xy \in A \}  $$

are regular for a regular set $A$.
The only method I'm familiar with that is similar is proving that first-halfs or first-thirds or any other linear parts of a regular language are regular (using a 2-NFA). I've tried looking online, but I only found that it's hard to construct NFAs for that. Is there some other way of proving existence?
I also don't understand how we can even compute $|x|^2$ or $2^{|x|}$ for different strings in the language to use that value.


texts: Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time

texts:
Suppose you are given an input set $S$ of $n$ numbers, and a black box that if given any sequence of real numbers and an integer $k$ instantly and correctly answers whether there is a subset of input sequence whose sum is exactly $k$. I want to show how to use the black box $O(n)$ times to find a subset of S that adds up to $k$.

This is what I've done: the first time we enter our set $S$. If it returns yes we can continue, otherwise it isn't possible to form the sequence which sums up to $k$. The next step is to test our set without the first element. If the black box returns yes we can delete it from our set otherwise we know that it is needed. We do this for each element and our $S$ shrinks to a set which sums up to $k$. Can I use induction to prove this?


texts: Is there a simple way to construct a Boolean formula that is true if and only if at most $k$ of the input variables are true?

texts:
I could of course construct a truth table for the function
$$f(x) = \left(\sum_i x_i\right) \leq k$$
Where $x$ is an assignment and I'm slightly abusing notation to count Booleans. And then I could make a formula from that.
But if there are $n$ variables then this truth table will have $2^n$ rows, rather unwieldy. Even if I only consider those rows for which $f(x) = \text{true}$ I'll still have ${n}\choose{k}$ clauses which remains exponential if $k = n/2$.
Alternatively I can write a program for verifying that only $k$ variables are true and then go through the construction in the Cook-Levin theorem to produce a 3-SAT formula, this time only of polynomial size.
But I feel like this problem ought to be even simpler than that. Does anybody have an idea?


texts: What property of cons allows elimination of tail recursion modulo cons?

texts:
I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops.

foo(...):
    # ...
    return foo(...)

I also understand that, as a special case, the function can still be rewritten if the recursive call is wrapped in a call to cons.

foo(...):
    # ...
    return (..., foo(...))

What property of cons allows this?  What functions other than cons can wrap a recursive tail call without destroying our ability to rewrite it iteratively?

GCC (but not Clang) is able to optimize this example of "tail recursion modulo multiplication," but it's unclear what mechanism allows it to discover this or how it makes its transformations.

pow(x, n):
    if n == 0: return 1
    else if n == 1: return x
    else: return x * pow(x, n-1)


texts: Upper bound on register machine contents

texts:
I am doing some work on register machine theory which revolves around a 2-register register machine and attempting to show that it is not possible to compute an upper-bound on the final contents of its two registers on the basis of its program code and initial input, in halting configurations only. I believe this can be related in some way to the busy beaver problem, but I cannot quite see how, and the stipulations that it is for halting configurations only has confused me somewhat.

What do I know so far?

Clearly a register machine configuration specified by the 3-tuple (instruction label, register 0, register 1) has an infinite number of possible states, owing to the abstract nature of the machines, as no practical limit is imposed on the size of the natural numbers which can be stored in each register.
I considered whether I could simply define a partial function $f : \mathbb{N}^3 \to \mathbb{N}$ where the arguments are the program encoded as a natural number and the initial contents of the two registers, but I do not think this gets me anywhere. I defined the function to be undefined when the partial function computed by the register machine specification is undefined on the given input, as the problem specifies computing the upper bound for halting configurations only. Therefore, I cannot use a diagonal argument to suggest it would imply the halting problem, because being undefined for a non-halting configuration suggests it would not.
Secondly, I tried to come up with a proof on the basis that there is an infinite number of possible configurations which a 2-register machine can be in. In particular, there is an infinite number of possible programs $e \in \mathbb{N}$ which could be executed, and each of those programs can be executed on an infinite number of initial register configurations $\mathbb{N}^2$.By construction, if there is a machine which can decide this partial function for any given combination, then I thought it may be the case that it required an infinite number of states in which to do so - which is of course not possible, as a register machine must be specified by a finite number of instructions.

I am not confident that either approach is correct or not, and wonder whether either of the above is a correct tact or if a formal proof exists for this?


texts: Lempel-Zilv-Welch Algorithm Decoding Question

texts:
Hello i am studying about LZW algorithm by watching this video:
https://www.youtube.com/watch?v=j2HSd3HCpDs&t=481s

I couldnt fully understand decoding process.
At current 258,how does 116 come at add to dictionary part ?
At current 256,how does 101 come at add to dictionary part ?


texts:
I am not able to find a clear explanation about Ordered Arrays. All I know is

  The array is 1-ordered it is in the usual order. (For the
  1st must be less than the 2nd which in turn must be less than the 3rd
  which ... which must be less than the $n$th.)

But what is 2-ordered, 3-ordered... so on array?

Can someone guide me?


texts: What is the maximal difference between the depths of 2 leaves in AVL tree?

texts:
I'm wondering what's the answer of the following question:
What is the maximal difference between the depths of 2 leaves in an AVL tree?
Intuitively I think that it shouldn't exceed $log n$ but have no idea how to prove that. On the other hand, I saw multiple articles that claim the depth can become larger and larger without any formal proof (I always get a contradiction when trying to draw such trees)
I would really like if someone can explain me why it's correct\incorrect.


texts: Reducing a problem with two knapsack that needs equal number of items from Knapsack?

texts:
I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness.

The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from left to right and not necessarily following the value $v_i$ (meaning the sort order is implicit),(assume those values are the "volumes" of "objects"). The problem also recieve a value $V$ that stands for the maximum volume of both knapsack (there are two knapsack with same supported volume). Each element have volume $v_1, v_2, ..., v_3$ and every one has the same weight (let's say 1). There is a the restriction that If I were to select the item $v_i$ I HAVE to have taken every object from $v_1$ to $v_{k-1}$. Another restriction is that each knapsack must have the same numbers of items.

So I need to take the greatest ammount of objects in the knapsack that the sum of their volume do not exceed the knapsack $V$, and both knapsack must have the same number of objects. ($|knapsack_1| = |knapsack_2|$) And also following the restriction for taking objects.

After trying to reduce from some NP-Complete problems I reduce it from knapsack, but somehow I made a mistake and now I don't know how to do it correctly.

I'll show you what I did:

I used the decision problem for the Knapsack Problem, it recieve a list of tuples $x_i = <p_i, w_i>$ ($p_i$ is the profits of taken element $i$, and $w_i$ is how much object $i$ weights), a value $W$ (for supported weight), and a minimum profits from elements $C$. The problem returns a True if there is a list of $x_i$ ($x_1, x_2, ..., x_n$) that satisfy that $\sum_{i=0}^{n}p_ix_i \geq C$ and $\sum_{i=0}^{n}w_ix_i \leq W$. False otherwise.

After working a little bit with the values, I tried to transform the input from Knapsack problem to my problem. (The one described above). So I tried to find a relation between the Profit and The weight to some how sort the objects following that relation. So I did:

$-\sum_{i=0}^{n}p_ix_i \leq -C$

$\sum_{i=0}^{n}w_ix_i \leq W$

And sum both sums:

$\sum_{i=0}^{n}x_i (w_i - p_i) \leq W - C$

After doing that used the $W-C$ elements as the $V$ for my two knapsack problem, and I sorted the list of elements by their $(w_i - p_i)$. My interpretation was to found a relation between the profit and the weight, and some how guarantee the same result. Then I duplicated every element on the list, for my problem to distribute both objects of the same type if it select them. For example, the list should look like this: $o{_1}{_1}, o{_1}{_2}, o{_2}{_1}, o{_2}{_2}, ..., o{_n}{_1}, o{_n}{_2}$

But problem arises when profit and weight has values very distanct and will get negative numbers and don´t know to work with them properly.

So I´m stuck with this reduction, can any one tell me if I am using the correct aproach, and send me a link, and if not, help me with this!

Thanks in advance


texts: Finding number not in list with wildcards

texts:
I have a list like this:

1*0*0
1**0*
0*0**
001**

Where the number of elements in each row is $n$ and * is a wildcard for 0 or 1. I need a polynomial-time algorithm that can determine if there exists an $n$-bit number that does not equal any of the rows. Does anyone know of an algorithm that could do this? I've been thinking about evaluating the total number of possible solutions for each row and subtracting from $2^n$ but I can't figure out how to delete duplicates in polynomial time.


texts:
I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one:

bX -> abY

which Type of Grammar would this be, unrestricted grammar, context-sensitive grammar context-free grammar or regular grammar

Thank you for your help


texts: What do you call a subtree covering a subset of contiguous leaves?

texts: In the data structure field, what is the (best) term used to identify (designate) a subtree covering a subset of contiguous leaves?


texts: Definition of “K-fairness” with respect to concurrency?

texts: There are definitions of Absolute, Strong and Weak Fairness available across the internet, but I cannot find a definition of "K-Fairness" property for critical section algorithms (also algorithms that satisfy a 1-fairness or 3-fairness property). Does this actually exist or is this something that was made up to describe a phenomenon that I am not recognizing?


texts: How to partition a tree on a fixed budget of edge cuts?

texts:
Suppose I have a tree $T=(V,E,w)$ with vertex weights $w(v)\ge 0$ for all $v\in V$.  I want to partition this tree into $k+1$ trees by cutting $k$ edges such that the deviation from the mean of the sum of vertex weights in each partition is minimized.

Is there an algorithm to get a good approximation in polynomial time?

Literature research has yielded this method finding a partitioning with bounded partition size, but it doesn't seem to adapt readily to the desired fixed number of cuts.  Likewise, there is a lot of research on tree partitionings where multiple subtrees can be placed into one partition, an NP-hard problem.  This doesn't seem relevant either as each partition must be a single subtree in my case, significantly changing the problem. This question seems to ask the same question I ask but doesn't specify what kind of partitioning is optimal.  The dynamic program given in this answer would work for the unweighted case, but my graph is weighted, so it doesn't apply.


texts: Anti-symmetry of polynomial time reductions

texts: I read somewhere that, if $A\leq_p B$ and $B\leq_p A$, then it is said that $A\equiv_p B$. What exactly does this mean? Is it saying that both $A$ and $B$ are the exact same level of complexity?


texts: Methods for Finding Asymptotic Lower Bounds

texts:
I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for the lower bound.  I'm using Corman's definition of $\Theta$:

$$\exists c_1,c_2>0\in\mathbb{R}:\forall n\geq n_0: 0 \leq c_1 g(n)\leq f(n)\leq c_2 g(n)$$

Showing the upper bound usually doesn't give me too much trouble, but for the lower bound I allot of times find myself using limits.  And even though I'm getting the right answers, I'm a bit worried that my method isn't very rigorous and that maybe I'm doing a bit of hand waving in the process.

For example, problem 2.17 from Skiena's Algorithm Design Manual:

Show that for any $a,b\in \mathbb{R}: b>0$ that $(n+a)^b = \Theta(n^b)$

In this case I used limits to help find both constants.

For the upper limit I decided to look for some $c$ such that $(n+a)^b \leq c^bn^b$.  So taking the $b$th root of each side and dividing by $n$ I have $\frac{n+a}{n}\leq c$ which gives me $1 + \frac{a}{n} \leq c$.  For any $a\in\mathbb{R}$, $\lim_{n\to\infty }1+\frac{a}{n}=1$.  If I pick $n_0>|a|$, then for $a<0$ the expression approaches 1 from the left starting arbitrarily close to $0$.  If $a>0$ then the expression approaches 1 from the right starting arbitrarily close to 2. So choosing $c=2$ will satisfy the inequality and we have $c_2=2^b$.

Now for the lower bound.  I'm looking at the same expression except with the inequality pointing the other way.  In this case I'm trying to find $n_0$ and $c$ such that $c\leq 1+\frac{a}{n}$.  The value of $n_0$ has to be greater than $|a|$ because otherwise we would have $c\leq 0$ which isn't allowed.  This puts us in the same range of values between $0$ and $2$ approaching 1 from each side.  So I choose any $c,n_0$ such that $n_0>|a|$ and $0 < c\leq 1-|\frac{a}{n_0}|$.  So I could choose $n_0=3|a|$ and $c=\frac{2}{3}$.

Thus we have $0 < (\frac{2}{3})^bn^b \leq (n+a)^b \leq 2^bn^b$ for any $n \geq 3|a|$.

Is there an easier way to do this?

Normally when looking for upper limit constants where the two functions are of the same magnitude I simply eliminate negative lower order terms and change positive ones into multiples of the highest order term such as :

$$3n^2+15n-5\leq 3n^2+15n^2=18n^2$$

But when looking for the constant for the lower bound I find myself typically resorting to looking at limits.  Is there any kind of short cut to finding the lower bound constant like there is for the upper bound constant?


texts: Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)

texts:
Given the following NP-complete problem:

  PARTITION

  Input: A list of positive integers $a_1, a_2, \dots, a_n$.

  Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such that the sum of each part is the same?

Now I want to reduce PARTITION to the following problem:

  TRIPLE-SUM

  Input: A list of positive integers $a_1, a_2, \dots, a_n$.

  Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such that the sum of the numbers in $A_1$ is exactly three
  times the sum of the numbers in $A_2$?

I'm struggling to see how the transformation can take place. I've tried transforming the list $a_1, a_2, \dots, a_n$ by multiplying each element by $3$ (stupid... I know...) but everything I tried failed. Is there a way to perform this reduction? Does it even require to modify the input list?


texts: Find a source-sink-path that touches a subset of edges

texts:
I have a directed graph that has a source node and a sink node and a subset of marked edges.

I need to find a path from source to sink that contains at least one marked edge and is cycle-free.


texts: Substituting two different identifiers with the same identifier in Coq - why does this work?

texts:
I'm playing around with Coq and Software Foundations and is somehow very confused by something I took for granted since forever.

To prove

Theorem app_length_cons : forall (X:Type) (l1:list X) (x:X),
                              length (l1 ++ x :: l1) = S (length (l1 ++ l1)).

we can first prove

Theorem app_length_cons' : forall (X:Type) (l1 l2:list X) (x:X),
                             length (l1 ++ x :: l2) = S (length (l1 ++ l2)).

which is a straightforward induction,

Proof.
  intros.
  induction l1 as [| h l1'].
  reflexivity.
  simpl.
  rewrite -> IHl1'.
  reflexivity.
Qed.

Then simply

Proof.
  intros.
  apply app_length_cons' with (l1:=l1) (l2:=l1).
Qed.

However, there is something strange going on here - in the induction proof, we are doing induction on l1 and not l2 - and from the proof, it looks like we are assuming l2 doesn't change in the induction case. But when we later apply it with l2:=l1, we are breaking this assumption.

Indeed, if we try to prove

Theorem app_length_cons'' : forall (X:Type) (l1:list X) (x:X),
                              length (l1 ++ x :: l1) = S (length (l1 ++ l1)).

use the same method

Proof.
  intros.
  induction l1 as [| h l1'].
  reflexivity.
  simpl.
  -- Can't rewrite use IHl1' : length (l1' ++ x :: l1') = S (length (l1' ++ l1')),
  -- since the goal is S (length (l1' ++ x :: h :: l1')) = S (S (length (l1' ++ h :: l1')))

it looks like the assumption that l2 doesn't change is broken thus the proof won't work.

I'm pretty sure I'm missing something here. Why can we substitute different identifiers with the same identifier?


texts: Is it possible to go from code to circuit?

texts: I am wondering if it is possible to have a program that interprets programming code and is capable of turning that code into an optimized circuit. Is this possible, and if so, does it exist?


texts: Can you add up all the nodes of a special binary tree in polynomial time, in respect to the number of levels?

texts:
Let's say you have a binary tree defined by a group $S=\{a:[5,6],b:[7,67],c:[45,12],...\}$ (this group is just an example). The binary tree is constructed so that there are two starting parent nodes, $a[0]$ and $a[1]$. Each of those nodes have two child nodes $b[0]$ and $b[1]$. Each of those nodes ($b[0]$ and $b[1]$ from both $a[0]$ and $a[1]$) have two child nodes, $c[0]$ and $c[1]$, and so on and so on. To evaluate such a tree, you start at the bottom of the tree, add up the two leaf nodes in each of the last parent nodes, and multiply that by its parent node. This is now the new value of the parent nodes. This process is repeated upwards until you do $a[0](b[0]+b[1])+a[1](b[0]+b[1])$ (remember that $b[0]$ and $b[1]$ are no longer $7$ and $67$, respectively at this point). Can you do this evaluation in polynomial time, in respect to the number of levels of the tree?
Follow up: Can it still be done in polynomial time if some of the leaf nodes are missing?
EDIT: Here is a picture with what I mean:


texts:
I need to implement piecewise linear functions (this is not homework, it is for my own personal project). However, I have been having difficulties to get it right. Below, I describe the characteristics of the function, operations, and what I have tried so far.
Function: It is defined by linear segments. It may be discontinuous, and some segments may actually be points rather than lines. The function can be any mix of increasing or decreasing parts. The domain is completely bounded by a box with $x \in [0,M]$ and $y \in [0,M]$. The maximum value $M$ is always defined (e.g., never $\infty$).
Operations: The operations I need to perform are fairily simple in mathematical terms. I need:

Shift in $x$ and $y$ (easy)
Shrink/expand pieces (always at the end or start of the function, never in the middle)
Take the maximum between two piecewise linear functions $f(x)$ and $g(x)$ considering that all pieces are within the domains of the box ($[0,M]$) but the actual domain of the functions may not be the same (this has been tricky!)

What I have tried: So far I tried to implement the function as a series of linear pieces defined by their starting starting $(x_0,y_0)$ and ending ($x_1,y_1)$ coordinates. A function then is simply an array of such pieces. However, defining the maximum operation has been quite difficult for me, specially when there are discontinuities and the domain of the two functions $f$ and $g$ are different.
I know this may look more like a "help me with my code" question, but all I wanted was some guides in how to better implement such functions and operations. For example, is my current strategy good? Is there a description of an algorithm to take the maximum of two functions somewhere in the internet? I have tried Stack, Git, and Googling, but have not found any good result to help me with that. I guess either it is too easy and I just don't see it, or it is too obscure and few people do it.
NOTE: I really don't care about operation complexity right now. As long as it is polynomial it is good for me.


texts: Understanding multi-variable big O (time complexity)

texts:
I have something of this kind:

$$(n-1) d m + m + 2m*v+2v^2 + v$$

Where all n,d,m,v are variables.

My little knowledge of computational complexity leads to do this kind of approximation:

$$ O( (n-1) d m + mv + v^2 )$$

However I feel I could further simplify into

$$ O( n d m + mv + v^2 )$$

and

$$ O( n d m + v^2 )$$

hence

$$ O(v^2)$$

Are my assumptions correct?

can I remove the $-1$ from $(n-1)$?
can I remove $mv$ since $v$ will grow $v^2$ any way?


texts: Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form

texts:
The grammar have the following producitons,

\begin{align}
S&\rightarrow aTbS \mid\epsilon\\
T&\rightarrow aTb\mid\epsilon
\end{align}

Already turned this homework in, but I need to convert this grammar to chomsky normal form. Our teacher didn't go over this very well and all the documentation doesn't make sense to me and they almost all over the same example. Can someone please help? I only understand the first step which is making a new start state go to $S$. I have a vague understanding that I have to remove the null terminations next.


texts: Is there a Tree with deterministic traversal, but which nodes can vary?

texts:
I have a dynamic closest-pair problem. In my problem though, the points never move, but instead disappear and reappear.

That is, I would like to find for a point $p$ (where $p\in\mathbb{R}^3$)* in a set of points $P$, the closest point in $S$ where $S\subset P$. The catch its, while $S\subset P$, which elements of $P$ it contains can change at any time.

I was thinking of pre-computing a kd-tree where each leaf contains exactly one element of $P$, and each node/cell has an 'active' property. Then when I get a new $S$ I can recursively 'turn on' the levels of the tree which lead to active leaves. The active branches can then be traversed very quickly, ignoring nodes and leafs which do not contain active points.

The problem with this though is as particles are deactivated the bounding volumne goodness-of-fit will change and its no longer trivial to determine which branch should be traversed when there is a choice.

Is there a tree or spatial subdivision structure that will retain its deterministic traversal property even as points are added and removed (so long as they don't change position)?

The tree should be suitable for traversing on the GPU; primary consideration is performance.

*I've specified $p$ as having three dimensions, but it may have/be able to have 2 or even 1, if it is significant for the tree. Getting into details, $P$ will be an isomap of a 3D triangle mesh, but the mesh will not be simple, therefore its hard to say right now whether the isomap will have less than three dimensions or if the error will be too large if I try to fit it in 1 or 2. Three dimensions will be the worst case.


texts: How to find the nearest point in the coordinate system

texts:
There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 points, calculate the distance 800 times and find the smallest value. But I want to make more efficient algorithm that doesn't execute 800 times due to that it might be sorted in a certain order before searching.
That is, if the points is put in a certain order,
 Could you recommend some notions?


texts: What kinds of problems are modeled by a recursive definition of a set of strings?

texts:
Given this definition:

  The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by:
  BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string)
  RECURSIVE STEP: If $w \in \Sigma^*$ and $x \in \Sigma$ then $wx \in \Sigma^*$

My understanding of this is that the subset $\Sigma^*$ will expand with each iteration by what appears to be $|\Sigma|^n$ elements where $n$ is the number of iterations. So for example, given $\Sigma = \{a,b,c\}$ we have:

Base Case: $\Sigma^* = \{\lambda\}$
Iteration 1: $\Sigma^* = \{\lambda,\lambda a, \lambda b, \lambda c\}$
Iteration 2: $\Sigma^* = \{\lambda,\lambda a, \lambda b, \lambda c, \lambda aa, \lambda ab, \lambda ac, \lambda ba, \lambda bb, \lambda bc, \lambda ca, \lambda cb, \lambda cc \}$

Etc.

If this is the correct interpretation of the data structure described by this recursion, what types of problems are structures like this used to study/prove in CS?


texts:
I'm confused about where the probability from the hiring problem comes from.
For background:

We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). We interview for n days. If on the $i^{th}$ day, person i is more qualified then all the previous candidates, then we hire that person. Find the expected number of people we hire.

We can proceed to solve the problem using linearity of expectation and the method of indicator random variables.
Let X be the number of people we hire.
$$X = X_1 + X_2 + X_3 + ... + X_n$$
where $X_i = 1$ if we hire the with person and $X_i = 0$ if we don't.
According to online resources, the probability that we hire the with person is $\frac{1}{i}$ since each person is equally likely to be the highest so far.
However, this doesn't make sense to me. Why doesn't the probability that we hire the $i^{th}$ person depend on the quality characteristic we've seen so far?
Take, for example, the second person:
Shouldn't the
$(2^{nd} \text{person hired}) =1 - n_1$
where n_1 is the quality characteristic of the first person?
If we use what online resources say then $P (2^{nd} \text{person hired}) = \frac{1}{2}$. But what if person one had a quality characteristic of .9, then $P(2^{nd} \text{ person hired}) = .1$ and not half.
Can someone tell me where my logic is wrong?


texts: Prove/Disprove that $f(n) + g(n)= O(g(n)*f(n))$?

texts:
I would like to know if this statement is true:

I thought of giving a counter example by defining:

 which will give us that  but i'm nut sure if it's possible to say that  beacuse I suspect that it might be right because of the definition of Big O.

And if that's right that means that the counter example i gave is not good.
Am i right? or the statement is true? If it's true, how am I suppose to approach such questions?


texts: If a NAND gate is universal, why you don't have NAND OISCs

texts: If a NAND gate can be used to construct all other of the basic logic gates, then I'm wondering why you don't/can't have a purely NAND-based One Instruction Set Computer (OISC). All the OISC single instructions are complicated like "addleq, add and branch if less than or equal to zero", but I don't see why you can't just have an OISC be "nand, perform nand operation". Wondering what I am missing.


texts: Union of infinitely many recursive sets that is not recursive but recursively enumerable?

texts:
I am looking for an example such that the union of infinitely many recursive sets is not recursive but recursively enumerable.

I was thinking taking $S_i=\{i\}$ and then taking the union of these with the indexes in the halting set, so that the union is the halting set, which is not recursive, but recursively enumerable.

However, I am not sure this is the union of infinitely many sets, is the halting set infinite?


texts:
This question and this question got me thinking a little bit. For sorting an array of length $n$ with $k$ unique elements in $O(n + k \log k)$, we need to be able to store counts of values in the array. There are some suggestions, but I'm looking for a way to do this in worst case linear time. More specifically:

  Given a list $A$ of $n$ elements with $k$ elements distinct, determine a list of tuples $U = \{(x_i, c_i)\}^k$ of all unique elements $x_i \in A$ such that $c_i$ is the count of element $x_i$ in $A$.

Here are some (failed) ideas I've had and have been suggested:

Balanced Binary Search Tree - With this it will take $O(\log k)$ to insert into the tree and increase values. After inserts we could do a tree traversal in $O(k)$. Thus, total time comes out to $O(n \log k)$ which is too slow.
Hash Map - With this we can get $O(1)$ expected inserts and thus $O(n)$ expected time. However, this is still not $O(n)$ worst case.
Empty Space Mapping - Find the minimum and maximum element in $A$. Allocate (but do not initialize) enough memory to cover this range. Use this memory basically as a hash map and include a random hash so that we don't try to access corrupted memory. This strategy presents issues. (1) It's probabilistic with very very very low probability of failing, but still not guaranteed. Using memory like this limits us to floating-point or integer constraints.
Associative Arrays - There are many other associative arrays that can be used, similar to hash maps and BSTs, but I am not finding any that match these constraints.

Maybe there is some obvious method I am missing, but I also think it could be potentially not be possible. What are your thoughts?


texts: Median of medians: bound on pivot position

texts:
If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at least 30% of elements will be removed in each selection pass.

But I have tried to prove this percentage inductively but failed. In fact, I have found what I thought is a counterexample (where $\vec{v} \times n$ repeats $\vec{v}$'s elements $n$ times and $+$ is concatenation, as in Python lists):

\begin{align}
\begin{bmatrix}
1 & 2 & 3 & \infty &\infty
\end{bmatrix} \times 3 +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2
\\+ \begin{bmatrix}
4 & 5 & 6 & \infty &\infty
\end{bmatrix} \times 3  +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\
+ \begin{bmatrix}
7 & 8 & 9 & \infty &\infty
\end{bmatrix} \times 3  +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\
 + \begin{bmatrix}
10 & 11 & 12 & \infty &\infty
\end{bmatrix} \times 3 +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\
+ \begin{bmatrix}
13 & 14 & 15 & \infty &\infty
\end{bmatrix} \times 3 +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2
\end{align}

In place of $\infty$ we can just put any large number.

After the first step, we have:
\begin{bmatrix}3&3&3&\infty&\infty&6&\cdots&9&\cdots&12&\cdots &15&15&15&\infty&\infty\end{bmatrix}
Second step: \begin{bmatrix}3&6&9&12&15\end{bmatrix}
Finally we get the median-of-medians $9$. However in the initial array only $3\cdot 3\times 3 = 27$ of $5 \cdot (2+3) \cdot 5 = 125$ elements ($21.6\%$) are $\le 9$. Which seems to violate the 30% bound.

I doubt the algorithm is incorrect so what am I getting wrong? A proof would be much appreciated.


texts: Evolutionary algorithm - is there a relation between minimum iterations and size of decision variables

texts: I am solving an optimization problem using SPEA2, my problem has three cases with decision variables 25, 50 and 100 in each case. I want to ask if there is some relationship between the number of variables and iterations of evolution process. I mean to say I run algorithm fewer times when decision variables are 25 than once they are 50. Thanks in advance.


texts:
I'm trying to count the number of subsequences of a long string.

e.g. BANANA -> B, A, N, BA, BN, AA, NN, NA, BAN, BAA, BNA, BNN, ANA, AAA, NAN, NNA, etc

There's the horribly inefficient way, which is to iterate all of the substrings and keep hash of some sort to keep track of the ones already seen. The size of the hash explodes with any non-trivial length strings, so I need to figure out something more efficient.  I tried dynamic programming, but could not find a good recursive formula.

This problem is originally from http://ahslaaks.users.cs.helsinki.fi/oh/, and they don't use the term "subsequences" when describing it.


texts: Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

texts:
There are two operations as follows:

insert(num): insert num into the data structure.
find(sum): return a pair(a, b) such that a + b = sum, if no such pair exists return -1

How such data structure could be designed, possibly with find $\in o(N)$ and insert $\in o(\log N)$ operations?


texts:
I'm a bit confused on what exactly the meaning of a 'key' is in computer science. I understand key-value pairs, primary keys, etc... But I can't find a definition of what the term 'key' means by itself.

As far as I can tell it just means a piece of data. In CLRS, data associated with tree nodes are referred to as 'keys'. Data to search a hash table is called a 'key'. Is this what a 'key' is?


texts: Undecidability of two Turing machines acting the same way on an input

texts:
So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this:

$M_1$ and $M_2$ behave the same way on an input $x$, when they both don't halt, or when they both accept $x$ or when they both halt and reject $x$.

I found a reduction from the halting problem which uses the fact that if the Turing machines behave in the same way, than they must have the same language. But this all breaks down in the case that $M_1$ rejects $x$ and $M_2$ doesn't halt, obviously they could have the same language, but they don't act in the same way.

I do think the best way to approach this is by reducing from the halting problem, but I just can't find a valid reduction. Any help would be appreciated.


texts: Inapproximability result for a special version of 1-in-kSAT

texts:
Max 1-in-kSAT is the following maximisation problem :

Given $n$ variables $x_1,\dots,x_n$, and $m$ clauses $C_1, \dots, C_m$, find a valuation such that the number of clauses satisfied by exactly one literal is maximal.

In the following paper, there are several inaproximability results about this problem, such as

Theorem 9 : if $ZPP\neq NP$, then for every $\epsilon$, there is a constant $c$ such that there
is no polynomial time $(n^{1-\epsilon})$-approximation algorithm for Max 1-in-$(c\log n)$SAT

https://people.eecs.berkeley.edu/~luca/pubs/gt05.pdf

I want to know if this result is still true if we suppose that $m=O(n^{\delta})$ where $\delta$ is any positive constant

Any ideas, remarks, or paper would be useful :)


texts:
How can I know if my DFA is implemented correctly?
For example, I need to build a DFA, and then minimize it which will recognize my name.
Language which describe my name is:
L = {pustai, marius}

I came with this solution:

>(0)--p-->(1)--u-->(2)--s-->(3)--t-->(4)--a-->(5)--i-->(6)(goto state 0)
  |
 (7)--m-->(8)--a-->(9)--r-->(10)--i-->(11)--u-->(12)--s-->((13)) (final state)

How can I know if this is implemented correctly?
And about minimization of this automate I think is impossible.


texts: Describing C3 in terms of predicates on types

texts:
What is the right way to describe the properties for a method resolution order that naturally lead you to the C3 linearization algorithm?

I'm trying to nail down desiderata for an MRO that are conceptually prior to the C3 algorithm itself.

I recently read a blog post on C3 resolution order and its use in Python here.

The post talks about C3 satisfying a monotonicity property and informally describes an invariant that we'd like to hold for the system as a whole.

  Within a complex inheritance hierarchy, you want to be able to satisfy
  all of these possible rules in a way that is monotonic. That is, if
  you have already determined that class A should be checked before
  class B, then you should never encounter a situation that requires
  class B to be checked before class A (otherwise, the result is
  undefined and the inheritance hierarchy should be rejected).

We can take that (section of a) paragraph and run with it. We define two predicates:

$A < B$ means $A$ is a subclass of $B$ and $A \neq B$
$A \sqsubset B$ means $A$ is checked before $B$ and $A \neq B$

And then we start coming up with rules (101-104). $(A \;\text{extends}\; B,C)$ is meant to be interpreted fact about the source code, not a new predicate. (I don't know if it's valid to draw a distinction like that). The other thing I'm doing that's a little weird is creating a partial order out of a $<$-like and $=$-like predicate instead of just a $\le$-like one, but I think the meaning is clear.

$$ (<, =) \;\;\; \text{ is a partial order} \tag{101} $$

$$ (\sqsubset, =) \;\;\; \text{is a partial order} \tag{102} $$

$$ \frac{A < B}{A \sqsubset B} \tag{103} $$

$$ \frac{(A \;\text{extends}\; B, C)}{A < B \;\;\;\text{and}\;\;\; A < C \;\;\;\text{and}\;\;\; B \sqsubset C} \tag{104} $$

However, from these facts we can immediately tell that (105) should be rejected as invalid since $E \sqsubset F$ and $F \sqsubset E$ cannot simultaneously be true.

$$ (A \;\text{extends}\; E, F) \;\;\;\text{and}\;\;\; (B \;\text{extends}\; F, E) \implies \bot \tag{105} $$

However, the equivalent Python 3+ (106) will run without producing any errors:

class E: pass         # (106)
class F: pass
class A(E, F): pass
class B(F, E): pass

In order to get Python to complain about the method resolution order, we actually have to inherit from both $A$ and $B$ simultaneously (107).

class E: pass      # (107)
class F: pass
class A(E, F): pass
class B(F, E): pass
class Z(A, B): pass

produces the following error:

Traceback (most recent call last):
  File "inherit.py", line 5, in <module>
    class Z(A, B): pass
TypeError: Cannot create a consistent method resolution
order (MRO) for bases E, F

This immediately raises some questions:

Is (106) actually "invalid" in some sense and Python simply doesn't reject it?
Do we want to replace $\sqsubset$ with a three-place predicate that captures "where we're resolving methods from"?


texts:
We are given a array of positive numbers. We can perform two types of operations on these sequence of numbers.

If number E is even, then we can replace it by E/2
If number E is odd, then we can replace it by 2E

We have to find the minimum absolute difference between any two elements after performing these operations any number of times.

Example 1: let the array of numbers be 1,2

Then we can replace 1 by 1*2=2

so the sequence becomes 2,2

Then the minimum absolute difference between any two elements would be 2-2=0

Example 2: let the array is 5,8

then we can replace 5 by 10 or(and) 8 by 4.

But for minimum absolute difference we will replace 8 by 4.

So the answer would be 5-4 =1

I am not getting any idea how to write an algorithm for it. Can anybody please help me in this.

According to me, the answer always should be 0 or 1.


texts: NP-hardness of resource allocation problem

texts:
I am tring to prove the NP-completeness of the following Binary Integer Linear Program (BILP):

$$ \text{min}\sum_i\sum_j x_{ij}\\
\text{subject to} \sum_jr_{ij}x_{ij} \geq R,\ \ \forall \ \ i \in [L]\\
           \sum_i x_{ij} \leq 1,\ \ \forall \ \ j \in [N]\\
           x_{ij} \in \{0,1\}.$$

This a resource allocation problem in which I am trying to minimize the number of resources utilized while guaranteeing a certain minimum rate for all entities.

$x_{ij}$ is an indicator random variable that indicates whether or not a resource $j$ is allocated to an entity $i$. The first set of constraints impose a minimum amount of resource guaranteed for each entity. $r_{ij}$ is the rate that an entity $i$ can get in a resource element $j$. The second set of constraints ensure that a resource is not allocated to multiple users as sharing of resources is not possible in this problem. $[L]$ is the set of user entities and $[N]$ is the set of resources here.

I have tried looking at several covering problems like set cover that look like this but the second set of constraints
seem to be falling out of place every time. Can anyone suggest an existing NP complete problem that can be reduced
to this problem to prove it's NP-completeness?

Thanks


texts: Using Limits to Determine Asymptotic Relationship

texts:
Let's say we have $3^{4n}$ and $4^{3n}$. With the note of  The Asymptotic Cheat Sheet from MIT.
We should first calculate the lim n->infinity   $3^{4n}$/$4^{3n}$. and it result is $\infty$.
In the we have
lim n→∞ f(n)/g(n) != 0,∞  ⇒  f=Θ(g)   Note 1

and
lim n→∞  f(n)/g(n)=∞     ⇒ f=ω(g)   Note 2

My questions is:
Given that f(n) is $3^{4n}$ and g(n) is  $4^{3n}$ in this case, which "case" should we apply ?
How should one read Note 1 correctly ? Does it mean  "lim n→∞ f(n)/g(n) not equal to 0, but equal to infinity? then f=Θ(g) " Or
"lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?
Also if f(n) = $\theta $ g(n)? doesn't that already mean f(n) = $O$ g(n)?
if so, then note 1 should read as
"lim n→∞ f(n)/g(n) not equal to 0 and not equal to infinity, then f=Θ(g)?


texts: What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)

texts: I am learning beowulf cluster. And I want to know what is pvm and how it's work and there is any difference between mpi and pvm


texts: How to test implementation details when there are multiple ways of implementing the algorithm, without reading the code?

texts:
I want to make sure that the code that the written code is precisely doing what it is expected to do.

For example, if I want to search in an array particularly using linear search, I don't want binary search to pass the test.
Unit test to test the method "search" would pass irrespective of the implementation which is not what I want.
(I understand that binary search won't work if the data is unsorted, but lets say the data is sorted and I still want to make sure that it is a linear search and not the binary. In this case, I know that for sufficiently large input, BS would be way quicker than LS, but I want a generic answer where there might not be considerable difference in performance.)

Is there a way to achieve this?

An idea comes to my mind -
Divide the method in extremely small submethods and make sure that all the submethods are implemented correctly and are used in main method. However this is not desirable, this might not be feasible always.


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

The question

If $L_1,L_2,L_3 \in \lbrace 0,1 \rbrace^*$, and different from $\lbrace 0,1 \rbrace^*$ and from the empty language, prove that if $L_1 \leq_p L_2  \cap L_3$, where $L_2 \in NP$ and $L_3 \in P$ then $L_1 \in NP$

My answer

Due to the fact that $P \subseteq NP$, we know that $L_2 \in NP$ and that $L_1 \in P$. $L_2 \cap L_3$ is at most $L_3$ so $L_2 \cap L_3 \in P$ then I proved that $L_1 \in P$. But the question asks to prove that $L_1 \in NP$. Is it a joke? Am i missing something?


texts: Slowest growing upper bound for the minimum length of a complementary prefix regular expression

texts:
A postfix regular expression acting on a binary alphabet (specification from this post) can be described using the following grammar,

R → 0 or 1 or _ or ! or RR; or RR| or R+

where,

0 and 1 match their selves,

! matches nothing,

_ matches the empty string,

; is concatenation,

| is alternation,

R+ matches 1 or more occurrences of R.

(The linked post above gives some example regular expressions and the strings it matches.)

What is the slowest growing upper bound on the length of the regular expression complementary to another regular expression as a function of the length of the latter?

So far, I have a double exponential. I show that an "input" regular expression $r_1$ will give an NFA that has 1 more state than the length of $r_1$. By the powerset construction, the resulting DFA will a maximum of have $2^{1+\text{length(}r_1\text{)}}$ states. Clearly, the complementary DFA will have the same number of states, i.e. the same size.

I then use an algorithm to construct a regular expression given a DFA to get the upper bound of the length of this regular expression as a function of the size of the DFA. This gave another exponential, $\frac{16}{3}(4^n-1)$ where $n$ is the size of the DFA.

Combining the two gives $\frac{16}{3}(4^{2^{n+1}}-1)$, where $n$ is the length of $r_1$, as the length of the complementary regular expression. I am not concerned about the constants, as stated in the question, only how fast it grows. So, if I got my big-O notation correct, this gives $O\left(4^{2^n}\right)$.

This seems unnecessarily large, can it be lower? Can it be lowered to a mere exponential?


texts: MIPS CPU (Single Cycle MIPS Processor)-R Type instruction ALUOp code confusion

texts:
I have question about the ALUOp control signal.

When doing R type instructions, 31-26th bits are all 000000.
What decides the instruction is actually the func field of 5-0th bits.

In that case, I wonder why the ALUOp signals for the R type(add,sub,and,or,slt) below the table should all differ. I don't know why ALUcontrol needs to receive data from both instruction and Control when ALUOp for R type looks useless.

Can't ALUcontrol tells ALU what operations to do by just receiving 5-0th bits?
If so, all the ALUOp signal can be all same for the R type.

Thanks in advance!


texts: In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But is there any theory what makes this difference or is it mainly emprical?


texts: How to make a parse tree for the following propositional logic formula?

texts:
I have a formula $ \neg((q \implies \neg q) \vee p \vee (\neg q \implies (r \wedge p))) $.

As it contains 3 subformulas between the $\vee$'s, how can i put it into a parse tree, as a parse tree contains 2 branches from each node.