texts: How to prevent the optimization algorithm from just shrinking the image?

texts:
I'm trying to optimize a set of patterns in an image, but unfortunately they only way I have of evaluating the images results in smaller versions of the pattern scoring much better than larger versions.

As a result, the optimization methods I've tried all just end up shrinking the pattern down until they run into aliasing issues, and start becoming erratic.

I've tried normalizing the images by resizing the patterns to all be the same size at each step, but the optimization algorithm quickly just adds 'decoy' pixels to the corners, defeating the normalization.

I've considered trying to do the optimization with a vectorized form, but evaluating a pattern requires it to be rasterized to a particular size anyway.
Vectorizing the pattern also doesn't solve the problem with normalization and adding decoy geometry.

How can I prevent the optimization process from just scaling down the image?


texts:
If a pointer specifies a point in memory, would the amount of space a pointer takes not be dependent on how much memory it could possibly range over?

So for example, if we have 4 locations of memory and a pointer, then the pointer can be 2 bits, but if we have $2^k$, we will need $k$ bits.

My confusion stems from people who say that a fixed number of pointers is $O(1)$ space complexity.


texts: Origins of misconception about using equality signs with Landau notation

texts:
From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other function:

$f(n) = O(g(n))$

where what we actually mean is this:

$f(n) \in O(g(n))$

What is the origin of this misconception? And why is this misconception perpetuated, even today?


texts: Non-deterministic finite state automoton

texts: I am taking a course in the theory of computation and am trying to understand how to correctly design NFA's so that I can transform them into regex. I was wondering if I have Sigma={a,b} and need to design a NFA over Sigma Star that has at least one of its last 2 characters to be an 'a'; Can I simply start 2 threads, one that will accept 'a' as the last character and the other will accept 'a' or 'b' in the second to last position and 'a' as the last symbol? Also, the fact that this will be over Sigma Star, would that also mean that I have to have epsilon transitions included in this design?


texts:
I'm looking at the reccurrence
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).

Using induction, I found that $T(n) = O(n\log n)$, but have been told that this is not tight. Indeed, assume inductively that $T(k) \leq Ck\log k$ for all $k<n$ (and sufficiently large values of $k$), then

\begin{align*}
T(n)&\leq C\frac{n}{2}\log\frac{n}{2} + C\frac{n}{3}\log \frac{n}{3} + n\\
&= C\frac{5}{6}n\log n - n(C/2+C\log3/3 - 1).
\end{align*}

Now I choose $C$ large enough for $(C/2+C\log3/3 - 1) > 0$, and so the last expression is dominated by $C\frac{5}{6}n\log n\leq Cn\log n$.

My first question is, what is a tighter bound that this?

Second, I tried to use the Akra-Bazzi method to solve this, so let $p$ solve
$$\left(\frac{1}{2}\right)^p + \left(\frac{1}{3}\right)^p = 1.$$
Then approximately $p=0.79$, and (with $g(n) = n$) I get
$$\int_1^n \frac{g(u)}{u^{p+1}} du = \int_1^n \frac{1}{u^{p}} du = \frac{1}{1-p}(n^{1-p}-1),$$
and so

$$T(n) = \Theta\left(n^p\left(1+\frac{1}{1-p}(n^{1-p}-1)\right)\right).$$

This equals $\Theta(n^p + \frac{1}{1-p}n-\frac{1}{1-p}n^p)$, so overall $\Theta(n)$, since $p<1$. My second question is that I don't really believe that $T$ is linear, so what went wrong in my application of Akra-Bazzi?

Best regards.


texts: What is the meaning of the output weights of a Conditional Random Field (CRF) model?

texts:
Problem

When train my linear chain CRF with annotated observations, I feed it with a number of sequences containing observation values and a "ground-truth" label for each observation. I'm currently using the hCRF Matlab interface. (see 1)

In my case I have 4 continuous observation values (some in the interval [-1,1], some around [140, 200]; none outside [-10, 250] though). The label is an integer between 1 and 17, giving a total of 17 possible labels.

Question

After training, my model consists of 17*17 = 289 edge weights and 17*4 = 68 window weights. Can I understand the edge weights as some sort of probabilities for state transitions (even though they are not actual probabilities in the range [0,1])? And what exactly do the edge weights tell me?

Reference

For reference, the CRF produces conditional probabilities of the form

$$p(y|x) = \frac{1}{Z(x)} \exp{ \left\{ \sum_{k=1}^{K} \lambda_k f_k(y, x) \right\}}$$

where to my understanding, the $\lambda_k$ are my edge weights and the $Z(x)$ are the window weights I get.

I read some tutorials about CRFs but I still do not quite understand, how the feature functions $f_k(y, x)$ are looking if I simply put in sequences of 4 tuples (the 4 observation values).

Thanks in advance for any pointers.


texts: Is the set of codes of Deterministic Finite-State Automata a regular language?

texts:
Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is a regular language?

For example for Turing machines, the set of codes of Turing machines over a fixed alphabet is decidable, and we can speak of decidable sets of Turing machines (through their codes).

Of course we can also speak of regular sets of DFA's (through their codes). Is the set of all DFA's regular in this sense?


texts: Algorithm for generating random number given a discrete distribution

texts:
I have a list of couples "probability"+"value".
What is the best algorithm for generating random values with that specified level of probability?

1st proposal:

Approximate the probability up to 10^-k. Create a set of 10^k items each of witch with the corresponding value,
Eg:

  x=[0.1:a, 0.2:b, 0.4:c 0.3:d]

Approximating with 10^-1 accuracy, we get a set of 1 element a + 2 elements b + 4 elements c + 3 elements d. For a total of 10^1 elements.

Create a set/array of those values

1->a
2->b
3->b
4->c
5->c
6->c
7->c
8->d
9->d
10-d

And now extract a random item (generating a random number with uniform distribution from 0 to 10k.)
The correspective value associated is the random value.

Pro:
It's O(n) in pre-computation
Theoretically I think it scales easily
Cons:
It's very ugly and uses a lot of space, in O(N)

2nd proposal:

Pre-computation:

for each position, save the current weight + the value of all the other weight.

Run-time:

extract a random number x from 0 to 1.
Compare the current array[i] with x, if x > index[i], skip to the next, otherwise return the value of the current.
Iterate until a result.

Pro:

easy and nice

Cons:

-

3rd proposal:

Create a binary tree, where the laves contain the value, while the nodes are just "decision", and the edges are probability values. The values of the edges are created according to the sum of the probability of the exiting edges of their children.

> x=[0.1:a, 0.2:b, 0.4:c 0.3:d]
>
> root->(node1, 0.3),(node2, 0.7)
> node1->(a, 0,1),(b, 0.2)
> node2->(c,0.4),(d, 0.3)

Generate a random number from 0 to 1. Follow the tree from the root finding the closest values of leaf.

Pro:

Graphs ;)
Pre-computation O(n)?
Execution is just O(logn)

Cons:

-

I have found a really nice heuristic for creating the tree, and i think it's the best one.

Perhaps it's possible to do something using (stochastic?) matrix / graph (heap?) / finite state automata, but I'm not 100% sure.

Are there any others better algorithms? Any paper/link or documentation on software who do this works it's appreciated.


texts: What is the time complexity of subset testing?

texts:
Consider the following problem:

  Let $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_m\}$ be
  two finite sets over $\mathbb{N}$. The sequences $a_1,...,a_n$ and $b_1,...,b_m$ do not have to be sorted.
  Given as inputs the strings $a_1,...,a_n$ and $b_1,...,b_m$, determine if $A \subseteq B$.

What is the time complexity of this problem?


texts: Is regularity of the language accepted by a given Turing machine a semi-decidable property?

texts:
Given is the definition of a general problem: $\{ \langle M,  S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of languages S?

I'm stuck with the following instance of that problem: $L = \{ \langle M \rangle \mid M \text{ is a } TM, L_M \in \mathrm{REG}\}$. I have found proof that it is undecidable, however I'm stuck at finding if it's recognizable (synonyms: Turing-acceptable, semidecidable, ...) or not.

The problem in words means: Given a TM M, does the TM decide a language that is an element of REG (the set of regular languages)?

To prove a language is not semi-decidable, I would try to prove that it's complement is semi-decidable and that the language is not decidable (which I did by reduction from the Halting-problem).

To prove it is semi-decidable, I would prove it by reduction to the $A_{TM}$, which is semi-decidable.

I have tried both for this problem, but I get stuck / lose my way of thinking at every try ... Some directions would be greatly appreciated!


texts:
In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games.  To be impartial, a game must satisfy these conditions:

(1) The game is finite; i.e. there is a constant $c$ such that all games end in $c$ moves or fewer.

(2) There are no draws; either player 1 or player 2 wins.

(3) The rules of the game draw no distinction between the players.  That is, given any position, if we switch the active player then the set of legal moves is still the same, and the player who wins the game under perfect play switches.

It is often said in introductory CGT resources (here for example) that a major class of games that violate condition (3) are those in which each player has their own piece set.  For example, chess violates (3) because the white player can only move the white pieces and the black player can only move the black pieces, so if we switch the active player then the set of legal moves changes.

However, it seems to me that this problem can be circumvented by the following trick.  Instead of defining a "position" as the locations of the white and black pieces, we define a position as the locations of the active player's pieces and the passive player's pieces.  Now the conditions in (3) are satisfied.

This trick seems too simple to be original, though, and I have read in many places about how chess is a classic example of a partisan game.  So what am I missing?

Aside: To circumvent (1) and (2), we need to modify chess in some reasonable way; i.e. forbid 3x repetition of a single position and declare stalemate to be a win for the stalemating player.  But that's beside the point of my question.

Years-later edit since this question has gotten some random attention lately: neither of the answers really understood the point of the question (which is probably my fault for an unclear OP).  My current understanding is that there is indeed a natural isomorphism between finite drawless chess and an impartial game, but impartiality is not a property that is always preserved under isomorphism, and my misunderstanding came from the assumption that it was.


texts:
Consider a connected undirected graph $G = \langle V, E\rangle$, we say that a subset $C$ of vertices is a Path-Cover if the following holds. For every finite path $p$, it holds that $p$ traverses all the vertices in $C$ iff $p$ traverses all the vertices in $V$. I am interested in finding a Path-Cover of minimal size in polynomial-time, yet all my attempts failed.
I tried a greedy approach where I start with $C = V$, and then I remove a vertex and check whether the graph remains connected. Yet, I'm not sure whether this greedy approach gives a global minimal Path-Cover.


texts: Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

texts:
I was trying to do the following:

  Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). For example 12.9, would be a valid decimal number while 0.129 would be not since it does not begin with 1.

but it didn't seem to work:

1(0|1|2|9)*.(0|1|2|9)*9

or

S::=1X
X::=E|0X|1X|2X|9X|Y
Y::=.Z
Z::=E|0Z|1Z|2Z|9Z|A
A::=9

Why? Whats the correct answer?


texts: Maximum Ratio of White/Black pixels in an Edge Map

texts:
Is there a maximum possible ratio of white/black pixels in an edge map?

In my theoretical consideration all areas in an image which have the same intensity are black and only the edges are white. Hence, the white/black ratio must be theoretically smaller than 50/50 in any conceivable picture of our environment (In my opinion) as there are always areas with the same intensity and the edges cover these areas.

What I'm searching for is a theoretical upper limit for this ratio.

If I think about a 100x100 pixel array where e.g. every second line is a horizontal, vertical or both (checkerboard pattern) edge, I expect the  theoretical maximum ratio between white and black pixels to be 50/50?

Anyway, does anyone know if there is a mathematical proof, paper or source where this problem is described?


texts: How to convert 2 or gates (x1 V x2 V x3) to NAND

texts:
How can I convert a clause of size 3 that is made of 2 OR gates

example:

(x1 OR x2 OR x3 )

to one or more clauses of size 4 made only of NAND gates and not gates? So without parentheses inside the clauses.

examples:

(x1 NAND x2 NAND x3 NAND x4)
(not x1 NAND x2 NAND not x3 NAND not x4) AND (x1 NAND x2 NAND x3 NAND x4)

additional notes:
The original question asked is to prove that 4-SATCNF (A CNF expression that can be satisfied, with clauses of size 4 and with NAND gates between the 4 terms.) is NP-Complete by showing the polynomial reduction of 3-SAT <=p 4-SATCNF. I'm stuck at the part where I need to find a function for the reduction. I suppose the function should be something around the form showed above, if not can somebody helped me find the good function?

Thank You

Articles that I consulted so far:

3-Sat to 4-sat polynomial conversion: https://www.csie.ntu.edu.tw/~lyuu/complexity/2012/20121106s.pdf

NAND Conversion:
https://en.wikipedia.org/wiki/NAND_logic


texts: Matrix multiplication in recurrent neural networks

texts:
I was looking at a tutorial for recurrent neural networks in Python, and I have a question in regards to multiplying matrices of different sizes. Specifically, why does S[t] have 100 elements in it?

  s[t] = np.tanh(self.U[:,x[t]] + self.W.dot(s[t-1]))

Earlier in the tutorial, the author lists the dimensions for each variable:

  \begin{aligned} x_t & \in \mathbb{R}^{8000} \\ o_t & \in \mathbb{R}^{8000} \\ s_t & \in \mathbb{R}^{100} \\ U & \in \mathbb{R}^{100 \times 8000} \\ V & \in \mathbb{R}^{8000 \times 100} \\ W & \in \mathbb{R}^{100 \times 100} \\ \end{aligned}

From how I understand the above line of code, it multiplies U by x[t] and adds it to the product of W and s[t-1], then computes tanh for each element.

Sources like this say that you cannot add matrices of different dimensions, however that seems to be what is happening here (because multiplication is just repeated addition). In fact, it seems that U is 2D and x[t] is 1D. How are these added? Also, how is the sum of the two products then 100 elements?


texts:
I wish I knew the correct terminology for the question that I would like to ask, but I don't, so please forgive me if I am not calling the right things by the right names. The practical problem that I am trying to solve (and whose specific nature is to do with data compression) can be phrased as follows:

We have a directed graph with a number of parallel edges with positive weights. So, I am guessing that this might be called a directed weighted multigraph. I need to construct a shortest path on this multigraph, but I cannot use any standard algorithms for it because my graph also happens to be dynamic.

Now, when I tried searching academic literature on dynamic multigraphs, they usually talk about the graphs where you have to be able to reconstruct your shortest path as you follow it, e.g. maybe for realtime traffic navigation. My graph is different in that it does not change due to an external factor. However, it changes every time when particular edge is selected to be a part of the shortest path. So it is as if once you choose edge 1 from node A to B for your shortest path/spanning tree, you disable edges 3-5 from node B to other nodes. So, the graph is changing as the direct result of our traversal.

I am hoping that this kind of dynamic graph problem can have another name, so that I can try to find some academic literature on how one can attack problems of this kind. Or, maybe there is a standard way of recasting this type of problems that makes them more aminable to the efficient computation. Basically, I would appreciate any pointers on how I can try dealing with something like this efficiently, i.e. without setting up direct brute-force iteration through all possible options.


texts: Undecidability of the PCP problem with bounded width

texts:
Given two ordered sets of words $a_1, a_2, ..., a_k$, $b_1, b_2, ..., b_k$ taking values in some discrete alphabet $A$, a solution to the PCP problem is a sequence $i_1, ..., i_n$ taking values in $1, 2,..., k$ such that $a_{i_1}|a_{i_2}|...|a_{i_n}=b_{i_1}|b_{i_2}|...|b_{i_n}$ where $|$ means concatenation. $k$ can be called the length of the problem, $n$ the length of the solution and if we let $w$ be the length of the largest word in $a_1, a_2, ..., a_k, b_1, b_2, ..., b_k$, $w$ is called the width of the problem.

I know that the PCP problem becomes decidable in several scenarios, for instance: for bounded $n$, or if $A$ is unary, etc. On the other hand for $k\geq7$ PCP is still undecidable. My question is, is there any result known for bounded values of $w$?


texts: What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?

texts:
Before asking the question, I should say that I am not sure here is a proper community to ask this question or not.
I have an NP-hard problem and an optimization to deal with the problem. Recently, I have found that the problem has a phase transition where, before a threshold for a property,  the problem can be solved in polynomial time by a greedy approach and, difficult cases are after the threshold.
Now, I want to show this phase transition by some parameters related to the optimization that solves the problem. But, I don't know which parameters can show this phase transition in a valid way, like time-solving, the number of iterations to solve the problem, or .....


texts: Overlay two Voronoi Diagrams and calculate membership and areas of intersecting polygons

texts:
I would like to generate a composite diagram of two Voronoi diagrams.  I'm currently researching the cgal library for options, but I'm not sure if my precise application is covered.

Basically, I have two sets of convex polygons (Voronoi diagrams) generated by two sets of overlapping coordinates.  I want to overlay the Voronoi diagrams on top of each other and calculate the the areas of the intersected polygons as well as the membership of each intersected polygon -- each intersected polygon is a member of 2 polygons, one polygon from each Voronoi diagram.

I start with two sets of Voronoi cells calculated over the same region of interest.  I want to output a list of intersected polygons with their associated Voronoi members as well as the areas of the intersected polygons.

Thanks.


texts: Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time

texts:
A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the tree when the points are not sorted.

I am thinking of a way to do this, which is as follows:

Construct a BST on the points.
 Since the points are sorted then it will take O(n) time.

I followed the approach given in this link for this step.
Check if all the nodes satisfy the min-heap property based on the x-coordinates

This will take O(n) time.

So total time complexity will be O(n)

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates??


texts: Comparisons of functions, their big-oh and their implications

texts:
I don't understand why the $1^{st}$ is false but I think I see why the $2^{nd}$ is true.

If $f(n) = O(n^2)$ and $g(n) = O(n^2)$,  then $f(n) = O(g(n))$.

If $f(n) = O(g(n))$ and $g(n) = O(n^2)$,  then $f(n) = O(n^2)$.

I understand why the second is true but not the $1^{st}$. For case 1, if

$f(n) < c_1n^2$ for some $n > n_1$ and
$g(n) < c_2n^2$ for some $n > n_2$

by using constants instead of big-O notation , can't we find $c_3$ such that $f(n) < c_3g(n)$ for some $n > n_3$ ?


texts: Match students and teachers based on ranking

texts:
I have a similar question to that of Stable Marriage Problem.

This is the criteria1) 1 Student must have 1 Teacher only.2) 1 Teacher ideally should have 3-4 Students.

The spreadsheet is done using Google Apps Script (Javascript).
How do I go about with the system calculation and giving teachers the system-generated result (3-4 Students) ?


texts: Big Oh Time Complexity Involving 'for i in range(n)'

texts:
Given the code below and the comment analysis:

n = len(L)  # O(1)
for i in range(n):  # O(n) - I read online that range(n) will take constant time
                      but the 'for i in range(n)' part would make this O(n)?
    if L[i] > 0 :  # O(1)
       for j in range(n):  # O(n)
           answer = answer + L[i]  # O(1) - since indexing takes constant time
    else :  # O(1)
        for j in range(n):  # O(n)
            answer = answer - L[i]   # O(1)

My Overall Analysis:

$O(1)$ for the first variable assignment
first if statement takes overall $O(n)$
else statement also takes overall $O(n)$
=> Overall if/else statements take $O(n)$ as well
for loop iterates n times => $O(n * n)$ => $O(n^2)$

=> Overall time complexity $O(n^2)$

Thanks in advance for the suggestions!

EDIT: I am wondering if the

for i in range(n)

portion of the code takes O(n) or O(1)? I read that range(n) would take O(1) but since its a for loop it would take O(n)?


texts: How to properly describe this behavior (in terms of time complexity)

texts:
After completing the time analysis for an algorithm I have been working on, I need some help to write its time complexity properly, let me describe how it works...

The algorithm has two inputs $x$ and $y$.

When $x < 15$, steps to solve are $2^y$, so I know this is $O(2^y)$.

However when $ x >= 15$, the steps to solve begin ramping down (from the $2^y$) at a rate of $-1\%$ as $x$ increases, up to $x < 50$ (don't know how to express this part)

And then, when $x>=50$ it flats out, and keep the same cost, that is $O(2^y*35\%)$, and doesn't matter what is the value of $x$ (as long as it is greater than $50$)

How to write a time complexity that has 3 delimited phases depending on the inputs?


texts:
I tried to solve the following exercise :
What is the order of growth of the worst case running time of the following code fragment
as a function of N?
int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i*i; j++)
        for (int k = 1; k <= j*j; k++)
            sum++;

and I found that the complexity is O(n^4), however the correct answer is  :

The answer is : N^7
For a given value of i, the body of the innermost loop is executed 1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~ 1/3 i^6 times. Summing up over all values of i yields ~ 1/21 N^7.

I would like some help to understand this answer and the correct way to calculate complexity in this case.


texts: Shortest distance from multiple points to one point

texts: I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the end node $v$. I want the shortest $d$ to $v$.


texts:
I try to solve an exercise in Distributed Algorithm described as follow.

Let's define a label assignment problem as follow. There is a anonymous network (vertices don't have unique ID's , nodes don't have any clue about $n$ - number of vertices nor about network topology ). The labels assigned to vertices must be distinct and there is no limitation on the length of the label. The initiator is given. Show the algorithm for solving the problem in asynchronous model with time complexity $\text{O}(D)$ and using $\text{O}(m)$ messages (where $D$ is the diameter of graph and $m$ number of edges), prove that the labels are indeed distinct. Show the changes in complexities if the algorithm is executed on the synchronous network.

Let's say that the initiator is the node A, wlog assign it $A_{id} = 1$, broadcast $A_{id} = 1$ to all children of $A$ by flooding algorithm, any node $B$ by receiving message from it's parent for the first time will assign $B_{id} = PARENT_{id}+1$ and send $B_{id}$ to it's children, if $B_{id}$ is already defined, drop the message. $T=\text{O}(D)$ - time complexity, $M=\text{O}(m)$ - message complexity for broadcast.

It seems like on synchronous network the complexities will be the same, just becasue broadcast and convergecast on synchronous and asynchronous network run in $T=\text{O(D)}$ and $M=\text{O}(m)$.

If there are any change in complexities on the synchronous network? Does the above algorithm look good?


texts: In index allocation scheme, what parameters does the maximum size of a file depends on?

texts:
My understanding is as follows:
Number of address entries in one index block (A) = Block size / Address size
Total address entries (B) = Number of index blocks * (A)
File size = Block size * (B)

So, we must know the block size, block address size, and the number of index blocks to find the file size. However the sites I've looked at say that file size can be calculated from just the index size and number of index blocks.

https://interviewmania.com/discussion/91851-database-database-miscellaneous
https://www.geeksforgeeks.org/gate-gate-cs-2002-question-47/#:~:text=When%20indexes%20are%20created%2C%20the,option%20(B)%20is%20correct.
https://www.geeksforgeeks.org/ugc-net-ugc-net-cs-2015-jun-iii-question-12/

Are they wrong or am I missing something?


texts: How to construct a perfect BST from an unbalanced BST with n elements (assuming that n=(2^i)-1, i is natural)

texts: How do I construct a perfect BST from an unbalanced BST with $n$ elements (assuming that $n=2^i-1$, $i$ is natural). ** At the worst case of $O(n)$**.


texts: How can I get index of combination from element indices

texts:
An array of combinations is generated from two arrays,
               indices:  0   1   2   3   4   5
               array 1: [a,  b]
               array 2: [A,  B,  C]
     repeating array 1:  a,  b,  a,  b,  a,  b
     repeating array 2:   A,  B,  C,  A,  B,  C
          combinations: [aA, bB, aC, bA, aB, bC]    length = LCM(2, 3)

INPUT : a, C
OUTPUT: 2, which the index of aC in the generated combinations.

Say, when a and C are given whose indices are already known as 0 and 2 in the original arrays, how to find the index of aC, which is 2? Is there any algorithmic way to do this?
For detailed background information, please check version 1 of this question.


texts:
How to choose from a set of positive numbers all the subsets that sum to some number x?
For example if the set $S=[1,1,2,3,4,5,6,7]$ and I'm searching for all the subsets that sum to $7$ I would have $[1,6],[1,6],[2,5],[1,1,5],[3,4],[1,2,4],[1,2,4],[7]$.
What I'm trying to do now is to generate all the possible tuples of $\{0,1\}$, so for the set $S$ which has length $7$ I have: $\{0, 0, 0, 0, 0, 0, 0\}, \{0, 0, 0, 0, 0, 0, 1\}, \{0, 0, 0, 0, 0, 1, 0\},...$, multiply the element of tuples of $0$ and $1$ by the corresponding element of the set $S$ and check if the sum is equal to $7$.

I got the idea of the tuples in this question: N subsets with a given sum?
However that problem is slightly different from mine so I was wondering if there's a way to speed things up.


texts: Are "TM M accepts some string of length greater than 100" and "TM M accepts some string of length at most 100" decidable?

texts:
I have two questions as in the title:

TM M accepts some string of length greater than 100
TM M accepts some string of length at most 100

Since 1. is infinite, we can rephrase question as "does TM accept a string", which is clearly undecidable and there are many proofs for that.

2nd question on the other hand is finite and all finite languages are decidable.

Is my reasoning correct? I can't find any confirmation of my theories.


texts: What does the "0 ≤ K < N-1" expression means?

texts:
Given the following statement:

  "A nonempty array A consisting of N integers is given. Any integer K,
  such that 0 ≤ K < N-1, splits array A into two non-empty parts"

What does the 0 ≤ K < N-1 expression mean in this context?


texts: Solving T(n) = 2T(n/2) + log n with the recurrence tree method

texts:
I was solving recurrence relations. The first recurrence relation was

  $T(n)=2T(n/2)+n$

The solution of this one can be found by Master Theorem or the recurrence tree method. The recurrence tree would be something like this:

The solution would be:

$T(n)=\underbrace{n+n+n+...+n}_{\log_2{n}=k \text{ times}}=\Theta(n \log{n})$

Next I faced following problem:

  $T(n)=2T(n/2)+\log{n}$

My book shows that by the master theorem or even by some substitution approach, this recurrence has the solution $\Theta(n)$. It has same structure as above tree with the only difference that at each call it performs $\log{n}$ work. However I am not able to use same above approach to this problem.


texts: What is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array?

texts:
There is D-dimensional array A. The number D and the size Sd of every dimension d=1..D is input from keyboard. There is also 1-dimensional array E of size N. It consists of unique integer numbers 0..N-1. N is also input from keyboard.

First we need to fill A with elements of E so that every element is presented at least once (see comment on this). Then we need to generate all possible permutations of A. Every unique permutation (transpositions are considered as unique permutations) need to be stored in a file.

Please explain what algorithms/theoretical methods will be helpful here. I need the fastest possible solution (minimum time-complexity). Is there a way of counting the number of all possible permutations first? I will be really grateful for the pseudocode.

Comment: If there are several fillings possible, we need to work with all of them (this happens when N < S1*S2*..*SD). If there is impossible to fill an array (N > S1*S2*..*SD) the error need to be returned.


texts: Can any recursion implementation be written as tail-recursion?

texts: Can any method that uses recursion be written as tail-recursion?


texts: Finding the Voronoi cell a point belongs to

texts:
Given a set of Voronoi edges. Each edge consists of (indices of, pointers to) 4 points: $\mathrm{left}$ and $\mathrm{right}$ are sites, $\mathrm{begin}$ and $\mathrm{end}$ are vertices (one of them or even both (in case if all the sites lies on a straight line) may point to infinity). $\angle \Big(\overrightarrow{(\mathrm{left},\mathrm{right})},\overrightarrow{(\mathrm{begin},\mathrm{end})}\Big) \equiv +{\pi \over 2}$. Sites and vertices lies in two dedicated arrays. Sites are lexicographically ordered (i.e. by $x$ then also by $y$), vertices also can be easily sorted in the same manner.

What is the best way to locate point in Voronoi diagram defined as above (here, find closest site)? What are the best online and best offline ways (if differs)? I sure both of them can be constructed in linear-logarithmic time, but maybe one of them can have much lesser constant factor?


texts: Why are all problems in FPTAS also in FPT?

texts:
According to the Wikipedia article on polynomial-time approximation schemes:

  All problems in FPTAS are fixed-parameter tractable.

This result surprises me - these classes seem to be totally different from one another.  FPTAS characterizes problems by how easy they are to approximate, while FPT characterizes problems by their difficulty relative to some parameter.  Unfortunately, Wikipedia (as of the time I'm asking this question) doesn't provide a citation for this.

Is there a standard proof of this result?  Or is there a source I could consult to learn more about this connection?


texts:
Can we prove the following, or find a counterexample?

$$f(n) = O(g(n)) \Longrightarrow f(h(n)) = O(g(h(n)))$$

I should figure out whether $\log(n^{\log n}) = O(a^{\log n})$, and this will be facilitated if the above holds.


texts:
I'm working on the following problem:

  Suppose that we're given a connected, undirected graph $G = (V, E)$ with
  edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find
  the lightest spanning tree in which the nodes of $U$ are leaves (they
  may be other leaves as well). We want to do so in $O(|E|\log(|V|))$ time.

Here's my thinking: since every node $v \in U$ must be a leaf, there must exist a vertex $u \in V \setminus U$ that is the source (i.e. each leaf in $U$ is connected to $u$). However, I'm having trouble find a way to do this that doesn't involve running a polynomial time algorithm. Can anyone help?


texts: Contamination in Atomic Broadcast in crash stop failure model

texts:
I'm reading several papers about different broadcast algorithms. Most of them are designed for crash stop model but they also consider contamination scenarios.

  For example for a Causal Atomic Broadcast when a faulty process
  fails to delivers messages in order and then starts broadcasting other
  messages based on its inconsistent state which causes inconsistent
  state in other correct processes.

The above is just an example why a specific process could have such a weird behavior although our failure model is crash stop. Follwoing paper describes it more.

  A Modular Approach to Fault-tolerant Broadcasts and Related Problems.
  V. Hadzilacos and S. Toueg, Distributed Systems, 97-145, 1993.

See here section 3.11 (page 22) for more sophisticated example. This is really confusing to me. Why do we don't consider this type of failure as byzantine failures? In crash stop model a single failure should result in a crash. A faulty process can NOT continue to run without crashing. What am I missing?


texts:
Check if class $PSPACE$ is closed under polyonomially space reduction

Any ideas ? It is fairly difficult to prove it, because I don't understand exactly what it does mean that problems are closed under space reduction.


texts:
Suppose of I two sets of $n$ integers bounded in $[-B,B]$. The integers are $$a_1,\dots,a_n$$
$$b_1,\dots,b_n$$

I want to find if there is a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{i\in I}a_i=0$$$$\sum_{i\in I}b_i=0$$

This problem is $NP$-complete.

Is there a pseudo polynomial time algorithm with complexity for this problem like the regular subset sum problem on bounded integers which has an $O(B^2)$ algorithm (https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution)?


texts:
First, let me write the definition of big $O$ just to make things explicit.

$f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ such that $0\le f(n)\le cg(n), \forall n\ge n_0$

Let's say we have a finite number of functions: $f_1,f_2,\dots f_n$ satisftying:

$O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n)$

By transitivity of $O$, we have that: $O(f_1)\subseteq O(f_n)$

Does this hold if we have an infinite chain of $O's$? In other words, is $O(f_1) \subseteq O(f_\infty)$?

I'm having trouble imagining what's going on.


texts: What is the type system (or class of type systems) that that ensures all your tree Branches end in Leaves?

texts:
I've come across this situation numerous times in the past few years where I have some classes like (pseudo-Java):

interface Node<T> { ... }

final class BranchNode<T> implements Node<T> {
    List<Node<T>> children;
}

final class LeafNode<T> implements Node<T> {
    List<T> elements;
}

If you know the height of a balanced tree in advance, you can make classes for each height of node instead of a single BranchNode class.  I think Daniel Spiewak did this in his Scala PersistentVector implementation:

final class Height2Node<T> implements Node<T> {
    List<Height1Node<T>> children;
}
final class Height1Node<T> implements Node<T> {
    List<LeafNode<T>> children;
}

But if you don't know the height of the tree or need to support an arbitrary height, or only care whether a node is a Branch or a Leaf, is there a type system that can ensure that all your Branches end in Leaves?

I mean, you could walk the tree and use instanceof to find some leaf nodes and calculate the height of a given node from that and write code to ensure a balanced tree.  But I'm wondering if a type system exists that can model this in such a way that it allows building a valid tree and prevents building an invalid one?  If so, what is that type system, or class of type systems that can help solve this problem?

I've heard the words, "dependent types" and "higher kinded types" before. I could maybe even recognize simple examples of one or the other, but would have trouble explaining what they mean.  So go easy on me, or provide links.  Thanks in advance!


texts:
This question is prompted by Undecidable unary languages (also known as Tally languages)

How does the countability of a language imply (un)decidability?


texts: Classes of Functions Closed Under Polynomial Composition - Papadimitriou Exercise 7.4.4

texts:
I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".
I am trying to do Problem 7.4.4:

"Let $C$ be a class of functions from nonnegative integers to nonnegative integers. We say that $C$ is closed under left polynomial composition if $f(n) \in C$ implies $p(f(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$. We say that $C$ is closed under right polynomial composition if $f(n) \in C$ implies $f(p(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$.
Intuitively, the first closure property implies that the corresponding complexity class is "computational model-independent", that is, it is robust under reasonable changes in the underlying model of computation (from RAM's to Turing machines, to multistring Turing machines, etc.) while closure under right polynomial composition suggests closure under reductions (see the next chapter)."
Which of the following classes of functions are closed under left polynomial composition, and which under right polynomial composition?
(a) - $\{n^k: k > 0 \}$
(b) - $\{k \cdot n: k > 0 \}$
(c) - $\{k^n : k > 0 \}$
(d) - $\{2^{n^k} : k > 0 \}$
(e) - $\{\log^k n: k > 0 \}$
(f) - $\{\log n\}$

After understanding the definition of closed under left/right polynomial composition, I think I was able to solve items (a), (b), (c) and (f). However, I was not able to solve items (d) and (e).
My solution for item (a):

Closed Under Left Polynomial Composition: consider an arbitrary $f(n) \in C$ and an arbitrary polynomial $p(n)$. Then, $f(n)$ is of the form $n^{k'}$, for some $k' > 0$ and therefore $p(f(n))$ is a polynomial. Let $k''$ be the degree of the polynomial $p(f(n))$. Take $g(n) = n^{k''} \in C$ and we have $p(f(n)) = O(g(n))$.
Closed Under Right Polynomial Composition: same reasoning.

My solution for item (b):

Not Closed Under Left Polynomial Composition: consider as a counterexample $f(n) = n \in C$ and $p(n) = n^2$. Then, $p(f(n)) = n^2$. For every $g(n) = k n \in C$ we have $O(g(n)) = O(n)$. Since $n^2 \neq O(n)$ we conclude.
Not Closed Under Right Polynomial Composition: the previous counterexample applies.

My solution for item (c):

Closed Under Left Polynomial Composition: Consider an arbitrary $f(n) = k_1^n$ and a polynomial $p(n)$. Notice that $p(f(n))$ is a polynomial in $k_1^n$. For sufficiently large $n$, there exists some $k_2$ such that $p(n) \leq n^{k_2}$ and therefore $p(f(n)) \leq [f(n)]^{k_2} = (k_1^{n})^{k_2} = (k_1^{k_2})^n$. Therefore, taking $g(n) = (k_1^{k_2})^n \in C$ we obtain that $p(f(n)) = O(g(n))$.
Not Closed Under Right Polynomial Composition: Consider as a counterexample $f(n) = 2^n$ and $p(n) = n^2$. Then, $f(p(n)) = 2^{n^2}$, which is greater than $g(n) = k^n$, for every fixed value of $k$, if $n$ is sufficiently large. Therefore, $f(p(n)) \not \in O(g(n))$.

My solution for (f):

Not Closed Under Left Polynomial Composition: Consider as a counterexample $f(n) = \log n$ and $p(n) = n^2$. Then, $p(f(n)) = \log^2 n$. Also, $g(n) \in C$ implies that $g(n) = O(\log n)$. We have $\log^2 n \not \in O(\log n)$.
Closed Under Right Polynomial Composition: If $f(n) \in C$ then $f(n) = \log n$. Given an arbitrary polynomial $p(n)$, we have that there exists some $k'$ such that, for sufficiently large $n$, $p(n) < n^{k'}$. Then, for sufficiently large $n$:
$ f(p(n)) \leq f(n^{k'}) = \log n^{k'} = k' \log n = O(\log n) = O(g(n)).$

Can anyone help me with items (d) and (e)?
Thanks in advance. Of course, corrections/comments on the other items are also welcomed.


texts: Finding out if languages involving counting and modulo operations are regular

texts:
I am having trouble with the regularity of the two following languages:

i) $\{0^{n}1^{m}|n,m>0,n-m=0\,mod\,3\}$

ii) $\{0^{n}1^{m}|n,m>0,n+m=0\,mod\,3\}$

To clarify this is stating that the (#(0's) - #(1's)) mod 3 = 0.

I know how to prove that the first language is regular without the n,m > 0 restriction but with it I am inclined to think that the language is not regular because we'd need to make sure there is at least one 1 and 0 b and in doing so would also have to "remember" the previous numbers of 0's and/or 1's. Which is not possible with a DFA.

My logic is similar with the second statement.

Is my logic right?


texts:
I was watching this video:
https://www.youtube.com/watch?v=JCbZayFr9RE&list=PLXFMmlk03Dt7Q0xr1PIAriY5623cKiH7V&index=3

Honestly I do get most of it, except one.
At 7:14 he starts talking about recursive multiplication.
Now the strange thing is in general I do know what recursion is, can even write few algorithms.
But I am a bit confused why he is using recursive term here.
Can someone bring pseudocode how that recursive multiplication would look like as from 7:14?


texts:
I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.

I want to do this by replacing the numbers by a discrete key computed on them in such a way that when two keys differ, they map two significantly distant numbers.

$$K(r)\ne K(s)\implies |r-s|\ge 1.$$

The converse,

$$K(r)=K(s)\implies |r-s|<1.$$

may only partially hold, but should be false in a minority of the cases. ($K(r):=0$ is indeed a trivial solution to the first requirement, but is of no use because of the second.)

In my context (database search), the key being discrete and a single comparison for equality being sufficient are essential properties.

The first idea that come to mind is simple rounding, or equivalently, flooring, i.e.

$$K(r):=\lfloor r\rfloor.$$

Anyway this doesn't work as all values in range $[r,r+1)$ map to $K(r)$; the values $1$ unit away from these span $(r-1,r+2)$, which maps to one of $r-1,r,r+1$. So you would need a triple equality test

$$|r-s|<1\implies \lfloor r\rfloor=\lfloor s\rfloor-1\lor \lfloor r\rfloor=\lfloor s\rfloor\lor \lfloor r\rfloor=\lfloor s\rfloor+1.$$

If I am right, the reasoning can be extended to any function $K$: the numbers that map to $K(r)$ are in the set $K^{-1}(K(r))$; the numbers one unit away are in the Minkowski sum $K^{-1}(K(r)) + (0,1)$, which cannot be covered by a single $K^{-1}(K(s))$.

I can also accept a scheme where the key function is computed differently for $s$, but the single comparison principle must remain

$$K(r)\ne L(s)\implies |r-s|\ge 1.$$

Is this a known problem ? Is there a solution or a workaround ?

Update: the problem statement was reformulated in the original text.


texts:
I want to develop an interpreter. In the language, you have values and variables and types. The literals (the values) belong to some basic type. The subtypes can constrain the range of values. The spec says that making assignment, we ensure that the value assigned is assignable to the target (variable) range. Is it worth do the check on every assignment or ensure statically? How do you ensure it statically?

In the current implementation, I see that a type is attached to every value object. Are there are better approaches?


texts: Why can't we sort an Array in O(n) using Fibonacci Heap?

texts:
If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)?

Given an array with n elements:

Find the maximum of the array (largest key) in O(n).
Build a Fibonacci Heap of the elements in O(n), emptying the array in the proccess.
Use find-min and add the result to the now empty array.
Use increase-key on the element you found in step 3, and increase it by the maximum of the old array + 1 (making it now larger than any element of the old array)
Reapet steps 3 and 4, n times. Each time a new element from the old array is added, because all added elements are larger than max+1.


texts: Representing non-contiguous memory regions as a standard vector with O(1) access

texts:
What interesting alternatives are there for constructing an arbitrarily large static array from smaller scattered blocks of fixed-sized non-contiguous blocks of memory?

This is similar to the problem solved by hardware MMU pagetable mappings from virtual memory to physical memory, but in this particular case the scale is different, and it needs to be implemented in software, with virtual memory, and also in userland.

To clarify a bit, I'm using baker's treadmill as my GC, but it only supports fixed sized allocations (the current chunk size is 128 bytes, but I have some slight flexibility in re-defining it). The language I'm implementing requires arbitrary sized vectors with something close to O(1) access/write.

Currently I'm just building a pyramid of chunks, which gives something like log12(n) lookups, but the memory overhead sucks. Are there any interesting hashing solutions for mapping monotone index ranges to pointers?

What about run-time generation of a minimal perfect hash function? It seems they require at minimum 1.44 bits per key. If we bump the allocation block size to 512, we can support vectors with up to 1454080 elements, since we only need to map block numbers and not vector indices.

Edit:

See the paper "Z-rays: divide arrays and conquer speed and flexibility" (http://dl.acm.org/citation.cfm?id=1806596.1806649&coll=DL&dl=GUIDE) for more information regarding optimization of this array format:

These scattered blocks are sometimes called arraylets and are used by other GC algorithms: https://www.ibm.com/developerworks/websphere/techjournal/1108_sciampacone/1108_sciampacone.html

Also related: the Staccato GC: http://researcher.watson.ibm.com/researcher/files/us-groved/rc24504.pdf


texts: Is a reduced Wang B-machine Turing-complete?

texts:
A Wang B-machine has only 4 instructions:

right: Move tape head right
left: Move tape head left
mark: Mark square under tape head
branch: If square under tape head is marked, jump to instruction $n$.

Is the following instruction set also Turing-complete?

right: Move tape head right
markleft: Mark square under tape head, then move tape head left
branch: If square under tape head is marked, jump to instruction $n$.

I know that mark = right ∘ markleft, but left cannot be expressed so easily. The P'' language is an example of a language that achieves Turing completeness with a combined mark-move instruction.


texts: Multi objective optimization using genetic algorithm

texts: I have an objective function profit = income - expense . I want to solve it using genetic/evolutionary algorithm (strength pareto SPEA2). Since the algorithm is multi-objective so can I consider the income maximization as one objective and expense minimization as second objective?. I am using SPEA2 matlab code from YARPIZ. I am not sure whether this approach of breaking objective function is technically correct. Secondly, please also throw some light on how to do both conflicting objective simultaneously. The code in link is written for minimization of objective functions, but I have to minimize one and maximize other objective.


texts: proof of selection in worst-case linear time

texts:
Introduction to Algorithm,3rd

9.3 Selection in worst-case linear time

I have a question about its proof.

I have selected that sentence.

I agree that the number of elements larger than x is

$$
    3\times(\lceil\frac{1}{2}\times \lceil\frac{n}{5}\rceil \rceil -2)
$$

but, I think the number of elements less than x is at least
$3\times(\lceil\frac{1}{2}\times \lceil\frac{n}{5}\rceil \rceil)-1$

Am I right? Since the left up side contains $\lceil\frac{1}{2}\times\lceil\frac{n}{5}\rceil\rceil$ groups. Each contribute 3 elements except x itself.

Besides, step5 is

If i = k, then return x. Otherwise, use SELECT recursively to find the i-th
smallest element on the low side if i < k, or the (i - k)-th smallest element on the high side if i > k.

How can we get

$$
\frac{7n}{10} + 6
$$
in step 5?


texts: What does it mean to be "closed" under beta reduction?

texts:
I am reading the paper Compiling with Continuations, Continued, and in section 2.4, Comparison with ANF, the author draws attention to the fact that ANF is not closed under beta reduction. The snippet of text in question follows:

  As Flanagan et al. (1993) suggest, the “back end of an A-normal form
  compiler can employ the same code generation techniques that a CPS
  compiler uses”. However, as we mentioned in the Introduction, it is
  not so apparent whether ANF is ideally suited to optimization. After
  all, it is not even closed under the usual rule for β reduction (λx.A)
  v → A[v/x].

What does the author mean by this last sentence?
(My guess is that he means ANF beta reduction can introduce new, unbound variables into the reduced term. If that is the case, I am having a hard time visualizing when this would occur and would appreciate outside confirmation that my interpretation is correct.)


texts: Is the exponent bias $2^{n-1}-1$ or $2^{n-1}$

texts:
I'm a bit confused with the exponent bias. The sources I found online claim that it is either $2^{n-1}-1$ or $2^{n-1}$, $n$ is the number of bits used for the exponent. In my book when given examples on the bias of a 32bit system the bias is said to be $2^7$ which means the bias is $2^{n-1}$ while in an example on the bias of 64bit the bias is said to be $2^{11}-1$ which is $2^{n-1}-1$

So which one is it?


texts: Is the halting problem solvable for NPDAs?

texts:
After the total silence in response to my last question, I am rethinking my assumptions.  DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my prior question:

arrive at the same state as you were in previously
with the same top symbol as you had last time
without consuming anything on the stack, and
without consuming any input.

But is my last question actually unanswerable because we cannot, in fact, determine whether a NPDA will halt?  Is the halting problem even solvable for NPDAs?


texts: Calculating Binet's formula for Fibonacci numbers with arbitrary precision

texts:
Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite precision arithmetic, one would always have some (small) roundoff error.

  Is there a discussion/description somewhere of how to calculate the Fibonacci sequence using Binet's formula (ie not the recurrence relation) and floating point arithmetic which results in no roundoff error?


texts: Algorithm for scheduling unit time tasks with arrival times and deadlines

texts:
Suppose we have $n$ tasks to order over $n$ days.
Each tasks takes 1 day to be completed.
Each task has a start date when the task becomes available and a deadline when the task must be delivered.

Here is an example:

Is there an algorithm that can solve this problem with a worst case efficiency of $O(n)$ where $n$ is the number of tasks and days.


texts: In asymptotic notation how to prove that $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$

texts:
I have to prove that
 $$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$
The functions are non-negative.

Clarification:
$$\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$
it means
$$\mathcal{O}(f(n)+g(n))\subseteq\mathcal{O}(f(n))\land\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n)+g(n))$$

I try to explain my argument, i want to get on one side $f(n)+g(n)\in\mathcal{O}(f(n))$ and on the other: $f(n)\in\mathcal{O}(f(n)+g(n))$ in order to conclude that $\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$ true.

I start with the hypothesis:

$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\iff g(n)\in\mathcal{O}(f(n))$
$\iff(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)\leq c_1f(n),\forall n\geq n_0) \implies$
$\{$adding $f(n)$ to both members of the inequality$\}$ $(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq c_1f(n)+f(n),\forall n\geq n_0)\implies\quad(\exists c_1\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq (c_1+1)f(n),\forall n\geq n_0)\implies \{\textrm{taking}\quad c_1^{'}=(c_1+1)\}\quad  (\exists c_1^{'}\in\mathbb{R}_{>0},n_0\in\mathbb{N}:g(n)+f(n)\leq c_1^{'}f(n),\forall n\geq n_0)\iff \{by\quad definition\quad of \quad Oh-big \quad order\}\quad f(n)+g(n)\in\mathcal{O}(f(n))$

Now to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ start from the trivial proposition: $\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))$:

$\mathcal{O}(f(n))\subseteq\mathcal{O}(f(n))\iff f(n)\in\mathcal{O}(f(n))\iff(\exists c_2\in\mathbb{R}_{>0}, n_0\in\mathbb{N}:f(n)\leq c_2f(n),\forall n\geq n_0)\implies$ $\{$adding $g(n)$ to right member of inequality$\}\quad (\exists c_2\in\mathbb{R}_{>0}, n_0\in\mathbb{N}:f(n)\leq c_2f(n)+g(n),\forall n\geq n_0)$

At this point I'm stuck I don't know how to continue in order to achieve $f(n)\in\mathcal{O}(f(n)+g(n))$ to finish then the proof...

Thanks to everyone who read this :)


texts: Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?

texts:
I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG).
I suspect that languages like $\text{L} = \{10,10100,101001000, \dots\}$ can not be generated by a CFG. I can not see that intuitively (heuristics will help me). I have seen PDAs to be finite state automata in some places, and infinite in the rest.
Can someone tell me the limitations of a CFG / PDA (if any) and whether or not $\text{L}$ can be generated by a PDA/CFG? Additionally, are PDAs infinite state automata?


texts: What is the time complexity of the following loop?

texts:
function (n)
    i = 1
    s = 1
    while (s <= n)
        i = i+1
        s = s*i
        print "*"
end


texts: Searching the best trading route - algorithm

texts:
Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount a of good b for amount c of good d.

I have made a simple table to point out what I am trying to explain:

In this case there are three different goods: Wood, Sand and Gras.

I also live in the village and noticed that the prices of the traders vary greatly. I have 1 wood and want to increase it by simply trading between the five dealers. But: I must not visit a dealer more than once.

There would be different routes, for example I could do Dave - Adam, which would result in +1 wood for me. A better route would be Earl - Berta - Adam, because it would mean +2 wood.

I think at that point you might already know what I am asking for. I am looking for a technique / algorithm to find the route which maximizes my input. The rules are:

Input good = Output good
Output value > Input value
Each node ("dealer") must not be visited more than once
You do not have to visit all dealers
Each dealer is limited to one trade ("Giving amount a of good b for amount c of good d").
$a\in\mathbb{R}_{>0}$ and $c\in\mathbb{R}_{>0}$
The benefit is calculated at the end by output - input, i.e., by the increase in the quantity of the goods that you're starting with (if you start with 1 wood, then all that matters is the number of woods you end with).
It is important that the input good is the same as the output good ("Input good = Output good"). If I start with wood, I need to end with wood. If I start with sand, I need to end with sand, etc.

I don't even know how such a problem is called. That means that anything like algorithm names to solve it, the general name for this kind of problem, etc. would help me to continue with my research. I have already tried approaching it by converting the table to a graph and then run path-finding algorithms. That did not work, because I wasn't sure how to weight the edges and the Longest-Path-Problem was also in my way, which is NP-Hard for non-DAGs.

The traveling salesman problem (TSP) was already mentioned. I had a look at the Wiki page of the TSP. Quote: "The travelling salesman problem (TSP) asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
I think my problem is very different, because:

I look for the most profitable route, not the shortest.
I don't have to visit every dealer ("city").
I must not return to the origin, because as I said each node ("dealer") must not be visited more than once.

The "village" can get quite big. About 200 different goods and 500 dealers, so the algorithm should be able to perform good in this scenario.

The last possibility would be to brute-force, but I really want to avoid that.


texts: Rollback and Timestamp Ordering in Database

texts:
If we use the Timestamp Ordering for concurrency control in the following scheduling:

My TA says $T_2,T_3,T_5$ is Run and $T_4,T_5$ is Rollback. I think it's false. Is there any expert who could help us?


texts: Assembly language translation to machine code (process in "RAM")

texts:
How does a assembler (at very basic level) work in translation of Assembly language to machine code ? Just want to know that what is happening in RAM ?

[What my understanding is that when  when I type MOV A, B   : in RAM :'M' >> some bytes (ASCII CODE) in memory (RAM)in form of 0v and 5v (voltage may be different but you know what I mean) 'O' will be saved with same method & so V , A , "," , B .Now the programming software also have the part in RAM which we call "library" saved in 0s & 1s in the form of 0v /5v.So my question is that does "translation" mean that typed the 0s,1s of MOV A,B will be compared to saved 0s and 1s (library's)by logic ckt & then depending on the matching or mismatching of those 0s,1s will result in another 0s,1s (opcodes bits/bytes ,will be stored & later executed in RAM)?Am I right or is this a wrong way of thinking? ]


texts:
I've been stuck on this problem for a while. Any hints would be appreciated!

Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle x, w \rangle \in A\}.$$
Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$.


texts: Search a sorted array that ends with zeros in O(log n) time

texts:
I have an array of size $m$, $[1,1,2,2,3,4,5,...,f,0,0, \cdots,0]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted.

If I make a binary search including the 0's I get $O(\log(m))$.
I'm trying to make the algorithm better and to get complexity of $O(\log(n))$ with no success.

I thought maybe something with medians?
Any idea will be great.


texts: Is $x^2+x+1 (mod 2)$ a one-way function?

texts:
Given that $x^2+x+1 (mod 2) = 1$ and $x^2+x (mod 2) = 0$ for ${|x\rangle}_{x=0,1} \xrightarrow{F} \frac{1}{\sqrt{2}}[(-1)^{x}|x \rangle + |1-x \rangle]$ (Fourier transform). So, the 1-1 correspondence $x^2+x+1 = NOT(x^2+x)$ holds over $F_{2^3}$, where the input is the zero polynomial $x^2+x$ and the output is the positive polynomial
$x^2+x+1$ (arXiv:1609.01541, eprint.iacr.org/2017/681). Notice that the bijection $x^2+x+1 (mod 2)$ = $x^2 \oplus x \oplus 1$ = $x \land x \oplus x \oplus 1$ = $ x \oplus x \oplus 1$ = $x \oplus NOT(x)$, which corresponds to a coin toss.

It is important to note that the construction works for bit strings of any length because any positive polynomial is reduced to $x^2+x+1(mod2)$ and any zero polynomial is reduced to $x^2+x(mod2)$.

Considering that pseudorandom generators exist if and only if one-way functions exist (pseudorandom generator theorem) is $x^2+x+1 (mod 2)$ a one-way function ?


texts: Need clear explanation to Range updates and Range queries in Binary Indexed trees?

texts:
I have gone through few tutorials about how to perform range updates and range queries using Binary indexed tree. I have even gone through Range update + range query with binary indexed trees . I'm unable to understand the need of second tree. In the tutorial http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree :
It says as:

Consider a range update query – Add $\mathrm{val}$ to $[i,\dots,j]$. We will design a sum function, where we consider a summation function for all possible $x$ as following:
$0$  for  $0 \leq x < i$
$\mathrm{val} * (x - (i - 1))$ for  $i \leq x \leq j$
$\mathrm{val} * (j - (i - 1))$ for  $j < x < n$

I just want to know the following things:
If $i\leq x\leq j$, why is the sum $\mathrm{val}*(x-(i-1))$ ?
I'm not able to appreciate the entire algorithm.
Could someone explain me using examples?


texts: Distinguishability of distributions that are not close given just one sample

texts:
Consider (over $n$-bit strings) the uniform distribution $U$, and another distribution $D$ such that
\begin{equation}
\text{Distance}(D, U) \geq \frac{1}{e},
\end{equation}
where $\text{Distance}$ stands for the total variation distance, given by
\begin{equation}
\text{Distance}(D, U) = \sum_{z \in \{0, 1\}^{n}} \left|\underset{\text{Z} \sim D}{\text{Pr}}[\text{Z}=z] - \underset{\text{Z} \sim U}{\text{Pr}}[\text{Z}=z]\right|,
\end{equation}
for a random variable $\text{Z}$.
In other words, $D$ and $U$ are quite far from each other. Even then, it seems intuitively true to me that we should not be able to distinguish between these two distributions with a polynomial-time algorithm if we are given one (and just one) sample as input, with the promise that the sample comes from one of these two distributions.
By this, I mean that it seems intuitive to me the quantity
\begin{equation}
\left|\underset{x \sim D}{\text{Pr}}[A(x) =1] - \underset{x \sim U}{\text{Pr}}[A(x) =1]\right|
\end{equation}
is small, for a polynomial time algorithm $A$.
Is my intuition correct? If not, it just doesn't seem obvious to me how we could distinguish these distributions with just one sample. Isn't it too little information? Can you show how we are to distinguish by any explicit description of such an algorithm for any such $D$?


texts: Find sub-matrix containing the maximum number of elements consisting only of 1's

texts:
I am trying to get help on it here, originally posted first at:

https://stackoverflow.com/questions/59446920/find-sub-matrix-containing-the-maximum-number-of-elements-consisting-only-of-1s

Basically trying to get the max sub matrix that contains only 1's of a matrix that is filled with 0's and 1's.

I could figure out the max sub matrix, now I just need to find how to do so that the sub matrix is only 1's.


texts:
I'm looking for a formal definition of "graph levels" on a DAG. This example should illustrate what I mean by this.

The node 0 has no edges directed towards it, therefore this has level 0. Next is is 3 and 4 which will have level 1 and so on.

Level 0 : node 0

Level 1 : node 3, node 4

Level 2 : node 1, node 2

Level 3 : node 5


texts: What are advantages of "streaming" syntax in functional languages with for-yielding like Scala?

texts:
In Scala we can print list
val nums = (1 to 10).toList

with both
nums.filter(_ < 4).foreach(println)

and
for {n <- nums if n< 4} println(n)

Are there any advantages of first syntax except ability to omit variable name in foreach(println)? Can we express evrything with second syntax or there are some things expressing better with first one?


texts: Is it possible for MSO graph/tree transducers to reflect themselves, namely to create an interpreter of tree/graph transducers using tree/graph transducers? If yes, I'll be happy for some design guidelines.


texts: Calculate number of error-correcting code check bits

texts:
To design a code with $m$ data bits and $r$ check bits which allow all single-bit errors to be corrected, the formula
$$(n + 1) 2^m  \leq 2^n$$
with $n = m + r$ and $(m + r + 1) \leq 2^r$ is used.
Why is $+ 1$ used here, doesn't $n$ contain already all possible codewords?


texts: Determining whether the output of an algorithm is constant

texts: Suppose I have an algorithm $A$ that is known to halt before $f(n)$ steps for some function $f: \mathbb N \rightarrow \mathbb N$, where $n$ is the size of the input, and output is always either zero or one. Is it a decidable problem to determine whether $A$ always outputs zero?


texts: Understanding this explanation about Big O notation

texts:
I'm trying to learn the Big O Notation...and I got a bit confused by this article:

https://brilliant.org/practice/big-o-notation-2/?chapter=intro-to-algorithms&pane=1838

where it stands that f(x) = 4x and g(x) = 10x, (...), and that one could look at the Big O Notation by dividing f(x) by g(x): 10x/4x

Shouldn't it be 4x/10x instead in this very example? (since f(x) = 4x and g(x) = 10x) Or is just me who got it all wrong?...

Kind regards,

c


texts: Finding the nodes that have degree at least 3 in an undirected graph

texts:
I want to come up with a good algorithm that takes as input an undirected graph $G$ and checks which vertices to include in an output graph $G'$, such that each vertex in $G'$ has degree at least 3.

I've thought about traversing the graph once to eliminate any vertex with degree less than 3 since none of these can be included in the output. Then, I could have a set $S$ that initially contains some arbitrary vertex that hasn't been eliminated; the rest of the vertices are kept in the set $T$.

If I keep with this idea, I'm not sure how to start moving in vertices from $T$ to $S$ and at which point to delete them. I also wonder if there's a way to use BFS to scan and see if each vertex has degree at least three in the output tree of the BFS procedure. Any pointers/ideas would be appreciated; thanks!


texts: Are the definitions of constructs in terms of lambda terms issues in implementation/design or uses of functional languages?

texts:
In Lambda Calculus, natural numbers, boolean values, list processing functions, recursion, if function are defined in terms of lambda terms. For example, natural numbers are defined as Church numerals, and recursion is defined in terms of a fixed point of a function.

Functional languages are said to be based on Lambda Calculus.

Who shall be concerned about the above concepts in terms of lambda terms: the implementer/designer of the languages, and/or programmers in the languages?

Do functional programming languages define/implement the above concepts in terms of lambda terms?
As programmers in regular functional programming languages (such as Haskell, Lisp, ML),  is it correct that the above concepts are always given in the same way as in imperative languages, and we never have to understand or deal with their definitions in terms of lambda terms?

Thanks.


texts: Why is $3^{\log_2 n}$ the same as $n^{\log_2 3}$?

texts:
I am reading about divide and conquer algorithm at following link on page on 57 in this link. The document analyzes the running time of the algorithm. At the very top level, when $k = 0$, this works out to $O(n)$. At the bottom, when $k = \log_2 n$, it is $O(3^{\log_2 n})$, which, the author claims, can be rewritten as $O(n^{\log_2 3})$.

My question is:

  Why can $O(3^{\log_2 n})$ be rewritten as $O(n^{\log_2 3})$?


texts: Optimizing iteration over all permutations of a bit array

texts:
edited for clarity:

I have two functions–$f(x)$ which returns an integer and $T(x)$ which returns a boolean–that operate on a bit array of length $n$. I am trying to maximize $f(x)$ over all $x$ which satisfy the condition $T(x) = true$. I also know that if $b$ is a binary subset of $a$ then $f(a) > f(b)$ (e.g. $f(0b1101) > f(0b1001)$. I have no such insight about $T$. Can I avoid iterating over candidates which are subsets of inputs which satisfy $T$?

My current solution is this: beginning with $x = 1^n$ and an empty array as a cache, iterate through the various permutations in order of descending population count. Test if the next input $x$ is a subset of any values in the cache. If it is not a subset and $T(x)=true$, then compute $f(x)$ and add $x$ to the cache of supersets.

However, this strategy must search through the cache on every iteration. Instead, I am imagining a tree which (for $n=5$) looks like
$$0b11111$$
$$0b11110\qquad0b11101\qquad0b11011\qquad0b10111\qquad0b01111$$
$$...$$
The root node is $1^n$, and child nodes are created by changing a single $1$ to a $0$ so that all children are binary subsets of their parents. Iterating from the root node, when we reach a node $x$ for which $T$ is true, we could skip calculating $f$ or $T$ for all of its child nodes because they are binary subsets of $x$. Unfortunately, the tree as constructed has $n!$ nodes instead of $2^n$, and nodes begin to appear multiple times in each sub-tree, so pruning the tree is not so simple. Is there a way to realize this type of optimization?


texts: NP-hardness does not imply lower bound, strictly speaking?

texts:
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.

Hardness is often intuitively explained as a lower bound. But it isn't, strictly speaking. For the sake of the argument, assume P=NP. Now the definition becomes:

A problem is P-hard iff every P problem can be polynomially-time reduced to it.

Because the above definition uses the polynomial-time reduction, the overall running time is polynomial (reduction + solving the resulting problem), no matter how easy is the resulting problem. Hence we could get an absurd result: a problem, which runs in constant time (hence lower bound is constant), is P-hard.

The definition makes total sense if we assume that NP>P. Do people assume NP>P?

The same question arises for the definition of PSPACE-hardness, where book authors use polynomial-time reduction, rather than something strictly easier than PSPACE.

I guess the answer to this question is simply "yes", sorry for the rant.


texts:
I have a undirected graph with no edge costs. A subset of the nodes are labeled $c_1, c_2, ..., c_k$ and one node is labeled $K$. I want to find the minimum cut of the graph with the extra condition that all nodes $c_i$ are in the same half of the cut and the node K is in the other cut.

My idea was to begin by doing a BFS from $K$ to all nodes $c_i$, saving predecessors and then finding all paths from $K$ to a node $c_i$ and finally picking the minimum set of edges from the paths so that at least one edge from each path was chosen. Unfortunately, if I understand this correctly, this is equivalent to the NP-complete set cover problem.

Is there  anything sane with this approach? Do you have any hints to push me in the right direction?

Note: this is homework so I'd rather have some hints than a full solution.


texts: In the FLP Impossibility paper, why did the authors claim that e is applicable to every E in proof of lemma 3?

texts:
The paper is available here:
https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

The 1st paragraph of lemma 3's proof says

In other words,if event e is applicable to config C,and E is any config reachable from C without applying e,then e is applicable to E.

I can follow the whole proof except the above claim. In real,practical systems, the claim isn't necessarily true. Here is an example:

suppose process p has a code fragment like this:

open 2 udp sockets,f1 and f2,respectively,in nonblocking mode

s1: read a message m from f1，depending on m,do some local processing,then send a finite set of messages to other processes //m could be null

s2: read a message m' from f2，depending on m',do some local processing,then send a finite set of messages to other processes //m' could be null

The label s1 and s2 in the code are steps("In one atomic step, a process can attempt to receive a message, perform local computation on the basis of whether or not a messagewas delivered to it (and if so, which one), and send an arbitrary but finite set of messagesto other processe",quoted from the final paragraph of page 2 of the paper).

Use C and E to denote the system config when process p's program counter was pointing to s1 and s2,respectively. Obviously,E is reachable from C. Suppose another process q sent udp datagrams m1 and m2 to sockets f1 and f2,respectively,right before the system reached config C. Therefore,in config C,events (p,m1),(p,null) are both applicable.Suppose (p,null) was applied in config C,making the system reach config E.Obviously,event (p,m1) is not applicable in config E,because process p was unable to read socket f1 in config E.

Now we've seen (p,m1) was applicable in config C, config E was reachable from C, and along the path from C to E,(p,m1) was never applied, but (p,m1) was not applicable to E,violating the claim in lemma 3's 1st paragraph.


texts: I have a basic understanding how operators work (bitwise, logical, unary, ternary, etc.), but I am confused how you define what the operator does so the machine knows how to treat the operator when you use it in your code base. Are operators predefined by the compiler and is there a way for me to access the source code of an operator's definition?


texts: Can someone please tell me the difference between Non re and CoRE languages with an example?


texts: Is this language context free L=${a^mb^nc^pd^q: m+n=p+q}$?

texts:
L={ $a^mb^nc^pd^q: m+n=p+q$ }

I cannot find a grammar to prove that it is context free.
However I can visualise a PDA which can accept this language.
The PDA would push O's for every a and b which it can later match against c and d.

Please someone suggest a grammar for this language ?


texts: Min-plus matrix multiplication implementation

texts:
I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication:

  One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph.

I had a look at min-plus matrix multiplication, but can't quite understand what $min$ is doing in the description of the algorithm:

  Given two $n \times n$ matrices $A = (a_{ij})$ and $B = (b_{ij})$, their distance product $C = (c_{ij}) = A \star B$ is defined as an $n \times n$ matrix such that $c_{ij} = \min_{k=1}^n \{a_{ik} + b_{kj}\}$. This is standard matrix multiplication for the semi-ring of tropical numbers in the min convention.

What is the $min$ function here? When I think of $min$, I think of it like $min(1, 2) = 1$. But how does that make sense if we are doing a sum?

So, in my implementation of regular matrix multiplication, finding the value for $c_{ij}$ looks like this:

    for j := 0; j < p; j++ {
        sum := 0

        for k := 0; k < m; k++ {
            sum += A[i][k] * B[k][j]
        }

        C[i][j] = sum
    }

But if I add a $min$ (or a $max$) function here, like so:

...
sum += min(A[i][k] * B[k][j])
...

That doesn't make sense at all.

So how would one describe an implementation of the $min$ function described in the article for min-plus matrix multiplication? It is the $min$ of what?


texts: Converting final state PDA to empty stack PDA

texts:
I'm having a problem understanding this conversion. Let's say we have a CFL like this:
$ { a^nb^m : n > m } $

A final state acceptance PDA for this language would push $A$ symbols in the stack for every 'a' input, and pop them for every 'b' input. If the stack has no more $A$s while we still have 'b' inputs to process, the automaton goes in a non-accepting state, and the string is not accepted.

To convert this to an empty stack acceptance PDA, I add the two states, one before the previous start state, and another state after the last to empty the stack. Whenever the inner automaton goes to the accepting state, it also moves to the empty-stack state with an $\epsilon$ transition.

If I test the string $aabbb$, after we process the first 3 characters, we still have an $A$ symbol in the stack, but the automaton moves to the empty-stack state with an $\epsilon$, it empties the whole stack, therefore the string is accepted.

Where is my mistake in this reasoning?


texts: Why is the time complexity of insertion sort not brought down even if we use binary search for the comparisons?

texts:
There are two factors that decide the running time of the insertion sort algorithm:
the number of comparisons, and the number of movements.
In the case of number of comparisons, the sorted part (left side of $j$) of the array is searched linearly for the right place of the $j^{th}$ element. If instead, we use a binary search, then the time complexity of finding a place for the $j^{th}$ element comes down from $\operatorname{O}(n)$ to $\operatorname{O}(\log n)$. So, for all the $n$ elements, the time complexity for comparisons becomes $\operatorname{O}(n \log n)$. Even so, the number of movements is still going to take $\operatorname{O}(n)$ time, and the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. Why is that?
Are any of my statements wrong assumptions?
Can a possible explanation be: the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. This is because to search an element (using binary search) it takes $\operatorname{O}(\log n)$ time, and to move the elements it takes $\operatorname{O}(n)$ time. Total cost is $\operatorname{O}(\log n)+\operatorname{O}(n)=\operatorname{O}(n)$ time. To do this for $n-1$ elements, it takes $n(n-1)=\operatorname{O}(n^2)$ time?


texts: Show postcondition i:=i+1 using Hoare assginment rule

texts:
as far as I understand the hoare assignment rule works like:
{i+1=3}i:=i+1{i=3}

E.g. to get the precondition I take the postcondition {i=3} and replace every occurence of i against i+1.
But what if i want to show that if i holds a certain value before
{???}i:=i+1{i=i+1}

that after the assignment i is increased by one, i.e. {i=i+1} is true? I cant replace i against i+1, otherwise i will get something like which is
{i+1=i+1+1}i:=i+1{i=i+1}

{i+1=i+2}i:=i+1{i=i+1}       i+1=i+2 is not equal

Another example:
I want
{i=0}i:=i+1{i=1}

But replacing i against i+1 in the postcondition I get
{i+1=0}i:=i+1{i=1}

Something like
{i=i}...i:=i+1{i=i+1}

would be good


texts: Floating point precision from rearranging equation

texts:
When I run $x^2 - y^2$ with x=8.8888888888 and y=9.9999999999 in python, I get the following result:

>>> 8.8888888888**2 - 9.9999999999**2
-20.9876543205679

However, if I rearrange it to $(x-y)(x+y)$ with the same x and y values, I get:

>>> (8.8888888888 - 9.9999999999) * (8.8888888888 + 9.9999999999)
-20.987654320567895

It seems that the two equations, though logically equivalent, give varying amounts of floating point precision by a difference of 2 digits.  What could be causing this?


texts: Datalog maintaining views incrementally with negation

texts:
Given a single IDB rule

$$R(x) \ \mathop{:\!\!-}  \  A(x), \lnot B(x)$$

Where $A$ and $B$ are EDB predicates, how would I go about calculating changes to $R$ as tuples are added to $B$? As I understand, when tuples are added to $B$, tuples may need to be removed from $R$.

This paper says

  We present the DRed algorithm to incrementally maintain recursive views that use negation

and

  A semi-naive computation is sufficient to compute new inserted tuples
  for a recursively defined view when insertions are made to base
  relations.

The DRed algorithm seems to take an input of the deleted EDB tuples, so adding a new tuple (and starting with a null set for deleted tuples) would have no effect. Have I missed something here?

Perhaps I misunderstand the definition of stratified negation, is $R$ an invalid rule?


texts:
If we do not allow unit clauses, can 2CNF containing 3 occurences per variable be unsatisfiable?

Every time I try to connect opposing variables to a cycle, I need to draw 4 edges for at least one variable (2 per positive and negative occurences).

So, is it even possible?


texts:
Whats the intuition behind multiplying the factor $\log n$

  Master Method Case 2 (CLRS Section 4.5)

  If $f(n) = \theta(n^{\log_b a})$, then $T(n)= \theta(n^{\log_b a} \log n)$

In generalized form sometime it can be written as

  If $f(n) = \theta(n^{\log_b a} log^k n)$ with $k = 0$, then $T(n) = \theta(n^{\log_b a} \log^{k+1} n)$


texts: Distribution algorithm according to weighted parameters (with a min-max constraint)

texts:
I'm trying to solve the following problem related to distribution-

I have a list L of items (I1, I2,....In) sorted in order of importance, I1 being the most important. Each item has multiple tags assigned to it and the combination of these tags can be different on each item, so I1 may have tags T1 and T2, I2 can have tags t2, t3 and t4, and I3 can have tag T1, and so on.

Now, I have to make batches from this list L, with a distribution of items (according to the tags) subject to the following constraints-

Each batch has a fixed size B
Each tag has a range of items in the batch distribution, ranging from a minimum to maximum. So, B should contain minimum x1 items with tag t1, x2 items with tag t2, and maximum y1 items of t1, y2 items of t2 and so on.
We start picking items from the top of L and keep filling the batch until we reach the final distribution that satisfies the constraints. If, say, L has 300 items, and we have to make a batch size of 50, we can go until any number of items in the list and pick the items to make the desired distribution.
Remember that if an item is picked from the list, count of all the tags assigned to it goes up by 1.
I was thinking of a solution where in first, I make lists of items corresponding to each specific tag. I pick the minimum desired items for a particular tag from its list. So, I'd pick x1 items with tag t1 from the list of items with tags t1, irrespective of whether the items contain any other tag. This way I'd ensure that the 'minimum' criteria of all the tags are satisfied. But for the max part, each tag will most definitely go overboard. How do I recursively keep replacing items from the batch with the remaining items in L to make the final desired distribution?

Any other solution would be great. Or any existing algorithm that can get me in the right direction to approach this problem.

I know the question is a bit too wordy, and probably a bit confusing, but I'v tried to explain it as well as I can, and of course, the problem might be a lot interesting I suppose.


texts: Real life applications of finite automata

texts:
I have some confusion about the differences between finite & infinite.
can someone tell me how the Toll machine or Park meter, soda vending machine can be used with infinite language? if not, please give me an example of other application.


texts: Is the borrow checker mechanism in Rust based on quantitative types?

texts: I was trying to understand if the borrow checking mechanism for references is actually a quantitaive type in disguise because it does look very similar. In case these are just similar but unrelated concepts, is there some other type-theoretic foundation upon which the Rust borrow checking mechanism is based?


texts: I have a weighed undirected graph. How is possible find the minimum average cycle weight. The average weight of a cycle is the weight of this cycle divided by the number of edges in it. And I must return the answer up to $\varepsilon$, where $\varepsilon$ is required precision.


texts: Distribution of the number of bits changed during generation of all binary tuples

texts:
Knuth's TAOCP chapter 7.2.1 discusses generating all the $n$-bit binary strings.
I am interested in the total number of bits that change during this process.

During generation we store an $n$-bit string and can change some of the bits of the string in each round, with the string output at the end of each round.
Call the sequence of integers represented by the output strings the generating sequence.
Every $n$-bit string must be generated precisely once in a generating sequence.
We are interested in the sum of the Hamming distances between successive elements in the sequence, with the initial value assigned to the string regarded as an $n$ bit change.

For the ascending generating sequence $0,1,\dots,2^n-1$ the number of bits changed during the enumeration is then $2^{n+1} - 2$.
The generating sequence $0,2^n-1,1,2^n-2,2,2^n-3,\dots,2^{n-1}-1,2^{n-1}$ yields a larger number of bit changes, at least $(n+1)2^{n-1} = 2^{n-1+\log n}$, and $2^{n-1+\log n} \ge 2^{n+1} > 2^{n+1} - 2$ as long as $n\ge 4$.
A Gray code (which changes one bit at each step) yields  $n+2^n-1$ bit changes.
We can normalise these by dividing by $2^n$ to obtain the mean number of bits changed per step.

  What is the distribution of the mean number of bit changes per step, for a generating sequence chosen uniformly at random?

Even the expected value would be useful, or its behaviour as $n$ grows.
The mean number of bit changes per step tends to 2 for the ascending sequence and tends to 1 for Gray codes (which achieve the minimum), as $n$ increases.
However, I'm not even sure what the maximum is, other than being no larger than $n$ bits per step.


texts: Decidability of $\{p|∃y : \operatorname{Dom}(φ p ) ⊇ \operatorname{Dom}(φ y )\}$

texts:
I need to classify the set
$$\{p|∃y : \operatorname{Dom}(φ p ) ⊇ \operatorname{Dom}(φ y )\}$$
as decidable, semidecidable or not semidecidable.

I don't know how to start. Any ideas?

Dom (φp) it's all the inputs that are accepted by a turing machine "p", and the same for Dom (φy).
So if My(some input) accepts then Mp(same input) accepts too, Mp can accept more inputs than My but not less.

But I don't know how work with that.


texts: shortest path from start to end in a grid but with a twist

texts:
i am trying to solve a graph based problem , this is the statement:
i have to find shortest route from position marked (s) to position marked (S) [Note : i marked S and E just for ease of understanding]. here is the catch in problem i can go only through cells marked 0 and cells marked 1 represents walls which are impassable.also i have the option to remove only one wall if it fetches me a shorter route to exit. Moves can only be made in cardinal directions; no diagonal moves are allowed.

sample 2d grid:

[
    [0(S) 1  1  1  1   ],
    [0    0  1  1  1   ],
    [1    0  1  0  1   ],
    [1    1  0  0  0(E)],
]

if the option of removing walls were not present i could usebfs or dijkstra to find the shortest route. this question has been asked here:
here - they use full exhaustive search which is very bad for large matrices and they focus on language based optimisations which is not a good approach to a problem.

someone asked it here - the accepted answer has the following approach to it:

Run a breadth-first search starting at the prison door, to find the
distance of each passable space from the prison door.
Run another breadth-first search starting at the escape pod, to find
the distanceof each passable space from the escape pod.
Now iterate over the walls, and consider removing each wall in turn.
You know the distance of each passable space from the prison    door
and the escape pod, so you can immediately work out the length    of
the shortest route that passes through the space left by the wall
you just removed.

but i am not clear what does this(so you can immediately work out the length of the shortest route that passes through the space left by the wall ) mean in 3rd step above.

also is there any better way to approach it?


texts:
I am confused about the purpose/statement of the Acceptance problem:
$A_{TM} =\{\langle M\rangle\,s |$ Turing machine $M$ accepts $s\}$
It can be shown that $A_{TM}$ is uncomputable, so we know that, in general, one cannot compute whether an arbitrary Turing machine will accept some input.
Common sense tells me that for a total Turing machine $T$ (one that always halts on any input in finite time) we can easily check if $T$ accepts $s$ by simply running $T$. So $A_{TM}$ is only uncomputable if non-total Turing machines are allowed.
However, given that HALT is undecidable, what is the point of knowing that $A_{TM}$ is uncomputable? HALT is arguably a more relevant result, and $A_{TM}$ is anyway only uncomputable if we allow Turing machines that may not halt - and if we allow Turing machines that may not halt, then we cannot decide if they halt on input $s$.
Further, HALT and $A_{TM}$ can be many-one reduced to one another. So, what is the point of the Acceptance problem, given that HALT is among the most well-known decision problems?


texts: Is the language of Roman numerals ambiguous?

texts:
An ambiguous Language is a formal language for which there exists a string that can have more than one meaning (several possible meanings or interpretations). Multiple synthesis structures for a string.

[Question]
Are Roman numbers an example of an ambiguous language?

Because there can be more then one representation for some number such as 1999, which
can be written as MDCCCCLXXXXVIIII, MCMXCIX, or MIM.

I am confused. Sometimes I feel not, some time yes!

EDIT
[ANSWER]

Although there can be more than one representation of same magnitude in Roman Number System. That is basically Non-Positional Number System. But its possible to write Unambiguous Grammar for that can generate all possible/valid pattern in Roman Number System.

Here is again a beautiful link that describe symbol table, rule  , Grammar for Roman number.

I am not sure about this but some authors says that: "Roman numbers can be recognized by a regular expression, so you don't really need a context-free grammar." and a regular language can't be ambiguous.


texts: difference between predictive modeling and clustering?

texts:
What are the fundamental differences between predictive modeling and clustering? according to literature, predictive modeling is a supervised learning with aim to construct models to predict the value of target attribute. On the other hand, clustering is a unsupervised method to split a data set to a couple of groups.
In my idea, both of them are the same. when you are finding out the target attribute, you are actually trying to categorize it which is similar to clustering.
I know that in clustering, we make subgroups of available data while in predictive modeling we try to find a model to predict value of attribute of unseen data based on current available data.
Could anyone explain the differences between these two concept clearly?
Thanks


texts: Why the soundness error in the $\mathrm{IP}$ of GNI can implicate $\mathrm{\Sigma_2} \subseteq \mathrm{\Pi_2}$ if GNI is co-NP-Complete?

texts:
PDF here shows a way to proof GI is NP-Complete $\implies \Sigma_2 = \Pi_2$.

In the last step, it writes following:

  In other words, (1) is false in this case as required.

Book Computational Complexity also follows the same way and supplies the $\mathrm{\Sigma_2}$ formula:

$\exists{r \in \{0,1\}^m}\forall{x \in \{0,1\}^n}\forall{a \in \{0,1\}^{m`}}V(g(x),r,a) = 0$

It seems that if one wants to solve a problem in $\Sigma_2$, he can transform it into above form and call a $\Pi_2$ machine to solve the contrary question and flip the reasult.

But in my opinion, Soundness error means verifier may accept the input which is not a member of GNI, so the $\Sigma_2$ formula seems to be below and the error ratio is something about $r$ rather than $x$:

$\exists{r \in \{0,1\}^m}\exists{x \in \{0,1\}^n}\forall{a \in \{0,1\}^{m`}}V(g(x),r,a)=1$

Is my opinion right?


texts: Measuring the information of a document?

texts:
I'd like to measure how much information a document $D$ contains.

Clearly, the New York Times published yesterday contains more information than my diary wrote on the same day. But, I do not know how to quantify those differences.

I think there are at least two alternatives. Those are the information entropy, and tf-idf.

In general, the information entropy $H$ is employed to measure the information.
Basically the information entropy seems OK to measure document information.

For instance, let's compare two documents: $D_1 = \text{"Tom loves Mary. Tom loves Mary"}$; $D_2 = \text{"Tom loves Mary. Jack loves Jane."}$. In this case, clearly the information of $D_1$ is less than $D_2$ and $H(D_1) < H(D_2)$ holds.

The tf-idf is the second option. With tf-idf, more rare words are regarded as more informative words. This also sounds valid. In fact, tf-idf is used to measure the importance of documents in automatic document summarization.

Then, my questions are

Are there standard way to measure the information of a document?
Are The information entropy and tf-idf used for this purpose? Why or why not?

Update on Aug 17

Thanks to several kind comments, I came to clarify what my question really was. I'd like to know formal (mathematical) definition of what is information or informative in the "NYT-and-diary comparison".

Intuitively, the New York Times is more helpful than my diary in order to get valuable information. In fact, many people pay $3 for NYT, and most people do not for my diary.

However, formally (mathematically), I can not explain why NYT is more informative.

Hence, my question is equivalent to how to formally define information or informative in the NYT-diary case. Then, the questions in the comments like "what do you mean by information" is totally what I'd like to know :)


texts:
I know the reduction to from $A_{TM}$ to $HALT$. But is
the following reduction from $HALT$ to $A_{TM}$ correct?

We are looking for total computable function $f$ mapping from $HALT$ to $A_{TM}$.
The following TM $F$ calculates the reduction $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

I think the line if T accepts or rejects, *accept* is correct, but it would be great if someone could check this.

Edit: I found the following slides, but I don't think the construction in there is correct: http://slideplayer.com/slide/13791105/


texts: How to generate a number which is divisible by all numbers in a given range?

texts: Suppose I want to find a number that is divisible by all 3 digit numbers (100-999), how do I write a code for that. I know only "1" can divide all 3 digit numbers, but I just want to know the logic.


texts: Having trouble with turing machine over language $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$

texts:
I am having trouble giving the description of a Turing machine that goes for
$L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$. What I have so far is:

If we start with a blank, the string is empty and it should accept, if not, start reading $0$s and I thought marking the $0$s with $X$ and the $1$s with $Y$ would be OK. After we reach a $1$, start marking $0$. Now comes the part I'm worried about, what do I do when the 2nd round of $0$s comes? How will I check if there are equal amounts of $0$s and $1$s?

Thanks in advance


texts: Why isn't the search space size of TSP $(n-1)!$ instead of $n!$?

texts:
I'm just learning about the travelling salesman problem, and I've been playing around with it. I'm not sure if what I've found is just a special case or not. My professor says the search space size is $n!$, where $n$ is the number of cities.

Suppose we have a table with cities $A,B,C,D$ on each axis, and the elements represent the distances between cities:

\begin{array}{|c|c|c|c|}
\hline
& A & B & C & D \\ \hline
A&0 & 2& 3&4\\ \hline
B& 2 & 0& 10&5\\ \hline
C& 3 &10 &0 &15\\ \hline
D& 4 & 5& 15&0\\ \hline
\end{array}

From this, I can generate various permutations of possible tours, and their lengths:
$$A \to B \to C \to D \to A : 31$$
$$A \to B \to D \to C \to A : 25$$
$$A \to C \to B \to D \to A : 22$$
$$A \to C \to D \to B \to A : 25$$
$$A \to D \to B \to C \to A : 22$$
$$A \to D \to C \to B \to A : 31$$

Now, it seems to me that each of these permutations is cyclical. In this way, $B \to C \to D \to A \to B : 31 $ and $A \to B \to C \to D \to A : 31$ are equivalent, for example.

So in fact, it doesn't matter which city I choose initially, because the resulting shortest tour will be equivalent to one of the tours above.

And clearly, there are $3!$ of these tours, or $(n-1)!$ of them. So why isn't the search space size $(n-1)!$ instead of $n!$? Maybe there is a problem with my understanding of what search space size is, I'm not sure.


texts: Find pth percentile of a stream of numbers

texts:
I want to find the pth percentile of a stream of integers, exactly (not approximately).

If we know the number of integers which will be coming in the stream and the numbers can fit into the memory then we can simply sort the integers and find the pth percentile.

But, what if all the numbers can't be fit in memory?  How can we do that?

We can assume all integers are 64-bit integers.