texts: Probability of reaching a state in asymmetric random walk

texts:
Consider the following random walk:

Namely, if $S_i$ is the state at time $i$, then $\Pr(S_{i+1}=1|S_i=0)=1$, and for every $s>0$ we have
$$S_{i+1}|S_i=s=
\begin{cases}
s+1 & \text{w.p. }1-p\\
s-1 & \text{w.p. }p
\end{cases}.
$$
In my application, $p>\frac{1}{2}$. I'm interested in two quantities, $\Pr(S_T > H)$ and $\mathbb E(S_T)$. My intuition is that $\Pr(S_T > C \ln T)\leq \frac{1}{T^2}$ for some global constant $C$, and that $\mathbb E(S_T)=O(1)$. However, I couldn't show it (yet).
Any ideas?

Here are some trivial claims. First, $\Pr(S_T > H) \leq \exp(-\frac{H^2}{T})$ due to Azuma's inequality, but that doesn't use the value $p$ nor the fact that $p> \frac{1}{2}$. Second, $\mathbb E(S_T) \leq O(\sqrt{T})$ since $S_t$ is stochastically dominated by a symmetric random walk, for which the expected place at time $T$ is $O(\sqrt{T})$.
The stationary distribution is easy to find, being $\pi_0=1-\frac{1}{2p}$ and  $\pi_i = \frac{\pi_0}{p} \left(\frac{1-p}{p}\right)^{i-1}$, but I'm not sure how to use it.


texts: Are objects appropriate for modeling the real world?

texts:
First of all, I know objects are not meant to model the real world, although they have been marketed as such and perhaps that was an intention at some point.
Here I say 'modeling the real world' in a general sense. That includes simulations, modeling of abstract (non-real) concepts and modeling of business support applications, although I'm not sure it is appropriate to develop all of them in a single general-purpose OO language.
Under the assumption that modeling the real world in software development is a desirable and advantageous trait (not considering inappropriate models), I'm inspecting the foundations of object-oriented programming and the Simula languages.
However I'm asking this question in the hope that someone can provide a quick spoiler.
I am under the impression that objects (i.e. endurants) may not be enough to model the real world since a) their classes are static across time, e.g. a Person is always a Person, not a Child who becomes an Adult and thus his/her responsibilities and actions change b) processes (i.e. perdurants) are not first-class citizens as objects are, and c) time also is not a first-class citizen.
Aren't requirements such as these necessary for a language to properly model the real world? Why haven't they been included in the concept?


texts:
The original problem statement is:

    Given a sequence of numbers $A[1..n]$, find $k < n$ consecutive numbers such that the sum of these $k$ numbers is maximized where $k$ is a positive integer given together with the sequence. Specifically, we want the index $i$ such that $A[i+1..i+k]$ is the largest.
    Design $O(n)$ greedy algorithm to solve this problem.

Because my solution is broken up into an initialization step followed by the greedy step, I think this algorithm in general will not classify as greedy. On the other hand, I would argue the initialization step does not invalidate the classification of this algorithm as greedy. Since I'm the student and not the teacher in this case, I seek outside perspective.

My solution idea is to compare every $k$ sub series of elements against the previous greatest sub series of $k$ elements, updating $T$ when a new greater sub series is found. Temporary sub series are stored in lowercase $t$ for comparison. For every iteration in the greedy step, I replace $t$ by removing the previous first element in $t$ and add the new next element in iteration thus constantly having an updated sum of the $k$ sub sequence for comparison against the greatest current sub sequence in $T$.

Proof of correctness isn't what I seek. I wish to know if my implementation below is classifiable as a greedy algorithm?

def find_max_k_sequence(A, k):
    T = 0 # running total
    m = k-1 # marks the index at end of max sequence
    i = 0

    # initial sum 0 to k
    while i < k:
        T += A[i]
        i +=1

    # greedy remaining steps
    n = len(A)
    t = T
    while i < n:
        t = t - A[i - k] + A[i]
        if t > T:
            T = t
            m = i
        i += 1

    return m-k+1, m, T

A = [1,2,1,3,1,4]
print(find_max_k_sequence(A, 3))

>> (3, 5, 8)


texts: Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

texts:
You are given a weighted undirected graph  G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight  by some value. You now want to come up with a smart way to find the new MST of the graph.

My approach would be the following. Take this edge (u,v) that you changed and add it to your MST. Start from u and travel around in your MST until you end up back in u, since it is guaranteed that after inserting (u,v) you will create a cycle (MST is a tree). Then from the cycle that you found, remove the edge with the maximum weight.

I feel like this is correct but I don't know how to prove it. Can someone guide me?

Here's what I've tried:

My intuition about the problem is the following. Let's call T, the MST that we found before updating an edge (u,v). Now after updating this edge (u,v), let's just add it to our MST. What is the resulting structure? Since we connect two nodes that are part of the MST with an edge that was previously not in the MST, we create a cycle. Of course this indicates that some edge/edges need to go, since what we just created is not a valid MST. We can not remove any edges that are not part of the cycle that we just created, since this action would give us two components that are not connected. If we look at the cycle that we created, we can only remove exactly one edge and no more than that. Since we want to minimize the weight of all the edges part of the MST, we simply remove the edge with the largest weight. So in the end we get something that is definitely a spaning tree, and it is also minimal. Proving that it's spanning tree is trivial. To prove the latter, the edges that are not part of the cycle, should definitely be part of some MST (they are light edges of some cut), so it's ok to leave them there, as for the cycle removing the max weight will give a min total weight.


texts: Analyzing time complexity for change making algorithm (Brute force)

texts:
I'm new to analyzing time complexities and I have a question. To compute the nth fibonacci number, the recurrence tree will look like so:

Since the tree can have a maximum height of 'n' and at every step, there are 2 branches, the overall time complexity (brute force) to compute the nth fibonacci number is O(2^n).

Now, looking at the coin make change problem. If the coin denominations are [1, 5, 10, 25] and the input number to make change for is 'C', the recurrence tree should look something like this:

In this case, the tree can have a maximum height of 'C' and the number of branches per step is 4 (The number of coin denominations we are given. Let's call this 'n'). With that being the case, shouldn't the time complexity be O(n^C). I read everywhere that the time complexity is O(C^n). Can someone please explain?


texts: Is this clique algorithm in polynomial time correct or might it have another time complexity?

texts:
I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity and I am not sure where I might have went wrong.
First I will show the algorithm, argue about its correctness and then what I tried on finding the time complexity.
So given a Graph $G = (V,E) $ and $n = |V|$ and $m = |V|$  and the case of k > 3 we would use the following algorithm:

Find every 3-Clique first in $O(n^3)$ (using three for loops for checking every possible triangle) and using hashing whether a triangle was already added or not.
Now we have the set $M := \{(i,j,k) | i,j,k \in V \land (i,j), (i,k), (j,k) \in E \}$ of triples of all disting 3-cliques.
Next we use the list of 3-Clique to search for 4-Clique through looking at every adjacent node $l$ of of every triple $(i,j,k)$.
If one the the adjacent nodes is connected to all $(i,j,k)$ so that $(l,i),(l,j),(l,k) \in E$ we have found a 4-Clique.
We proceed this process for every s-Clique with $s \in \{4,...,k \} $ usingal found $s-1$ clique

For the correctness of the algorithm it should be enough to show by induction that every s-clique consists of s-1 possible (s-1)-cliques. So once we have all s-1-clique it is easy to find every s-clqiue, since we just have to check every adjacent node of the s-1-clique for a connection with every node in the s-1-clique.
I tried to estimate the time complexity the following way:

Worst Case Complexity is finding a n-Clique in $G$. So this means we have $ m = n(n-1) $

We would have to do  $(n - 3)$-Loops for finding every s-clique in the sth loop.

In every loop we have less n s-clique where every s-clique might have maximum $s(n-1)$ adjacent nodes to look at.

Since we have less then n s-clique this would mean looking at $n*s(n-1)$ possible edges for finding a new s-clique.

This would sum up to $O(n^5)$ using gauss sum for every s-clique, but this would mean clique is in P and this seems a little bit to easy to be true.


texts: Reference Request: Factorization of PseudoPrimes?

texts:
Is there any literature/survey/papers/books regarding the factorization of Strong PseudoPrimes (wrt. to a given base).

I am aware of the fact that weak Pseudo Primes can be factorized in Polynomial time. But, I was unable to get anything significant/detailed regarding Strong PseudoPrime factorization (I am aware the general Problem is considered hard), but I am looking for much more detailed analysis of the subsets that are easy (factorizable in polynomial time, sub exponential time etc.) rather than this blanket generalization.


texts: Smallest cost in weighted directed graph with combinations

texts:
I am trying to develop an algorithm that can traverse a graph with intermediary/all or nothing(?) nodes.

The problem is that there are companies B, C and D that are bidding on projects X, Y and Z.  The companies can do individual bids for any of the projects, or they can say that they will complete a combination of projects for a total of x dollars.  However this combination is all or nothing and cannot be split.  I need to find the path with the least cost for all of X, Y and Z from the initial A (manager) node, that takes into account the combination of costs.

The following graph illustrates the problem that I am trying to solve:

A typical graph traversal algorithm would say that for A -> X the path A -> B -> X with cost 5, for A -> Y the path A -> C -> Y with cost 4 and for the path A -> Z the path A -> C -> Z with cost 6 should be taken.  Making the cumulative total be 15.

However, introducing the idea of an intermediary/combination node, would say that for A -> X the path that should be taken would be A -> B -> X with cost 5.  Then for A -> Y and A -> Z it should share the cost and take A -> D -> DL -> Y combined with A -> D -> DL -> Z with the lump sum of 8.  This would result in the lesser cost of 13.

Some general notes are that this is a very small example of the overall problem that I am trying to solve. At any given time there can be many companies and many projects (100+), and additionally, there can be may bids/edges between the companies and projects and there can be many combinations/lump sum bids.

The could explain the problem best using a graph but it doesn't necessarily mean that it is the best solution. It almost seems to me to be graphing up front, but then introducing the combination nodes makes it seem like a derivative of the knapsack problem. I appreciate any help or direction.

edit Typically there will be 20 companies and anywhere from 20-100 categories.  Typically the number of bids will be (companies) * (categories) where 20% of the bids are combinations.  So if there are 2000 bids approximately 400 could be a combination bid.  The number of projects in a combination could make up only min + 1 or all of the categories.


texts: LT codes with constant degree on information symbols

texts:
I have just read a Luby’s paper on the very basic idea of the LT codes, which may be of interest for me.
For my application, encoding k information symbols is done in a process that generates a big table T of size k’.
Then, for every information symbol s, choose d indices in the table $x_1,\ldots,x_d$ and add s to $T[x_i]$ (And beside $T[x_i]$ store the index of s, but I ignore this for the question).

So basically this is exactly as the encoding of the LT codes except that the degree distribution of the code words is not the same. So I wonder if there is an analysis of this variant.
Do you know a paper that treats this variant? Any thoughts on why it should/shouldn’t work?


texts: Creating a CFG that connects lengths of three blocks

texts:
I have to create a CFG which generates

$$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$

The first part is easy enough, I came up with

$$\begin{align*}
    S &\to aS_2abS_3 \\
    S_2 &\to aS_2ab \mid \epsilon
\end{align*}$$

However, the second part is very confusing. So far I have

$$S_3 \to S_4 \mid \epsilon$$

The problem I have is how do I possibly keep track of all of these variables? $k$ has to be less than $m$, $m$ has to be equal to $\ell + k$, and $\ell$ must be at least $1$ by extension. Can someone give me some general tips for approaching these CFG's?


texts: Preventing oversell, allocation of limited resources with overlapping properties

texts:
I am trying to solve problem of preventing oversell of limited resources.

Consider resources (people) who are described by set of properties where each property belongs to different category (example properties from four categories:  male, age 25-30, 2 children, interested in games).

Buyers want to allocate access to resources. Buyers can specify subset of categories and one property from each category (example: allocate 1000 males, age 25-30 or allocate 100 females, age 25-30, interested in music).

In my real life example I have 6m+ possible set of properties (profiles) where for each set of properties I know how many profiles exists.

My initial approach was to build a graph like one below:

and then traverse using edge weights, for instance validating if demand for 100 females, age2 can be satisfied:

check if size(female, age2) < 100
for each parent:

check if size(parent) < 100 and go to 2.

for each child:

check if size(child) < 100 * weight(edge(node, child)) go to 1.

(above algorithm is simplified as does not prevent visiting same node multiple times)

It all works fine when graph is small, however when number of nodes and edges (dependencies) between nodes (profile universe groups) grows it does not scale very well.

Consider example:

large graph, 6m nodes, 20m+ edges
buyer wants to allocate 1000 males (and there are only males and females in gender category)

algorithm would start with top-level 'male' node which probably has 10m+ outgoing edges and 10m+ checks would be required (and probably each of those 10m outgoing edges has incoming edges which need to be checked as well).

I was trying to find different approach but failed. I was trying to google out existing solutions but seems like I am unable to even name problem properly. Any reference to what is this problem similar to would be good for me as a starting point.

Thanks for comments/help.

Two more graphs to present exponential growth of the graph:
3 categories

4 categories

Update

Regarding size, assuming 8 categories of properties where each category has: 2, 6, 6, 6, 6, 8, 1140, 150 values respectively then estimated number of profiles: 2*6^4*8*1140*150 ~= 3.5 * 10^9. Number of nodes in graph: at least 7 * 10^9, number of edges in graph: at least 140 * 10^9.

Update #2

Formula for number of nodes is:

$\sum_{i<n}\prod_{k<i \atop j_1, j_2, ..., j_k < n} s_{j_{1}} ... s_{j_{n}}$

where $n$ is number of categories and $s_x$ is size of category $x$.

So in my example there would be 11'169'108'657 nodes.

Update #3

As per @Raphael advice - I have reduced number of nodes and now formula is:

$\sum_{i<n-M}\prod_{k<i \atop j_1, j_2, ..., j_k < n} s_{j_{1}} ... s_{j_{n}}$

where $M<n$ and assumed that distribution of resources across smallest slices of universe is equal.
At the same time removed lot of edges from graph.

Example of sub-graph size reduction:


texts: Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

texts:
I am trying to solve the Budgeted Maximum Coverage Problem.
I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller.
Both are approximation algorithms. The greedy provides a $1/2(1-1/e)$ approximation, and the modified greedy guarantees $1-1/e$.
I am trying to get better results than this using a genetic algorithm.
However, I am not sure if that is at all possible.
My question is, can GA (or any metaheuristics) provide better results? Or is trying such a thing futile?


texts: Write a routine to print the numbers 1 to 6 and back to 1 again without using any loops

texts:
Can anyone help with this question? I currently have this solution that prints

  1 2 3 4 5 6

but I'm having trouble going back down to 1.

public class noLoop{

     public static void main(String []args){
        noLoop(6);
     }

     public static void noLoop(int n) {

         if (n == 0) {
             return;
         }

         else {
             noLoop(n-1);
             System.out.println(n);
         }
     }
}


texts:
I have a problem in backpatching "if-else"
statements, for generating 3 address codes.

The grammar rule is :

  S -》 if E then M1 S1 N else M2 S2

The semantic rules are : {

 backpatch(E.truelist, M1.quad)
 backpatch(E.falselist, M2.quad)
 S.nextlist = merge(S1.nextlist, N.nextlist,
 S2.nextlist)

}

Explanation :

  Merge(p1, p2) : concatinates lists pointed by p1 and p2)

  Backpatch(p, i) : inserts i as the target label for each of the statements in the list pointed to by p)

  S.nextlist : "goto" statements to the next instruction after this statement (s)

I don't understand why we need "N" in the semantic rules above.
Why should we merge N.nextlist along with S1 and S2 nextlists for getting S.nextlist?? I mean why there is "N.nextlist" among other inputs?
Tnx for answering, in advance :D


texts: Finding the Largest "Ordered" Difference in Elements of an Array

texts:
Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$.

I would like to design an algorithm to find the maximum profit that you can given this array of prices. Profit is made by buying at a given date $i$ and selling at a later date $j$ so that $i \leq j$.

One easy solution is the following "exhaustive algorithm":

profit = 0
for i = 1 to N-1
  for j = i+1 to N
    if P(j) - P(i) > profit
      profit = P(j) - P(i)

The issue with this however is that it takes time $\Omega(N^2)$.

Can anyone think of something faster?


texts: Longest possible path from root to a leaf of a red black tree

texts: For the worst case of a red-black tree, what would a tree with 10 nodes look like?Since there can not be 2 consecutive red nodes and there is rotation is it safe to say that it balances out the trees leveling it I tried this attempt at creating a tree with 10 nodes:


texts: What portion of all possible turing machines halt?

texts: Has anyone estimated Chaitin's constant for Turing machines with an empty tape as input?


texts:
I am working with HOL-Light parser and keeping seeing references to preterm parser.

What is a preterm parser?

The most informative statement I find is from the HOL-Light reference for the parse_pretype function.

  This is mostly an internal function; pretypes and preterms are used as
  an intermediate representation for typechecking and overload
  resolution and are not normally of concern to users.


texts: What is the theoretical result of flattening a list containing only itself?

texts:
Consider the following python code
X = [None]
X[0] = X

This has many fun properties such as
X[0] == X

and
X[0][0][0][0][0][0][0][0] == X

I understand how this works from a practical standpoint, as it's all just the same pointer.
Now, when flattening a list, we tend to convert things from
[[1, 2, 3], [[4, 5], [6, 7]], 8, 9]

to
[1, 2, 3, 4, 5, 6, 7, 8, 9]

In this case, I am considering flattening to be reducing a multi-dimensional list down to a single list of only non-list elements.
In practice, flattening this list would be impossible, as it would create an infinite loop.
This may be more mathematical in nature, but I'm unsure how to put it in mathematical terms. Suppose we could flatten this list, would the result simply be the empty list?
For context, I initially got this idea by considering the list
X = [[], []]
X[0] = X

It is clear to see that at each pass of flattening, the empty list that is the second element simply disappears. This lead me to think that the overall result, may be the empty list.
Could it be possible that flattening this list would theoretically produce an infinitely long list of the list itself, as in
X == [X, X, X, X, X, X, ..., X]

This is purely a fun thought exercise. Any insight and discussion on this would be appreciated.
P.S. Although I'm looking for an answer in plain terms, if anyone is more mathematically inclined, I would be interested to see how this problem could be formulated in some sort of set notation. Please feel free to point me to a relevant math exchange thread as well.
P.P.S. I would also be interested in a solid proof (not formal) to go along with the answer.


texts: Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$

texts:
I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:

  Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a node [1,2,3,4] need to be split with 2 as a median  and resulting in nodes [1] and [3,4]. So, we selected 2 as a median, whereas 3 could also be the candidate for the median and 2 is on left of 3, so "left biased". (I just made up the term "left biased median" for convenience, it might sound bad) Left biased median will leave more keys in right child than left child.
  Insert elements in increasing order, which will further result in insertion in right children nodes, which were already more filled in comparison to left children due to left biased median.

For example, if $m=4$ and $n=10$, and we insert keys:1,2,3,4,5,6,7,8,9,10, then there will be 5 splits as follows:

Insert 1,2,3
=================
[1,2,3]

Insert 4
============
   [2]
   / \
[1]   [3,4]      (Split:[1,2,3,4])

Insert 5,6
===============
   [2,4]
   / | \
[1] [3] [5,6]      (Split:[3,4,5,6])

Insert 7,8
===============
    [2,4,6]
   / /   \ \
[1] [3] [5] [7,8]    (Split:[5,6,7,8])

Insert 9,10
===============
        [4]
       /   \
     [2]   [6,8]
    /  |  /  |  \
 [1]  [3][5][7] [9,10]    (Split:[5,6,7,8],[2,4,6,8])

Total splits: 5

However, can we derive the closed formula (if not closed formula, then a summation series?) for this for given $m$ and $n$? It seems that splits are occurring on every two insertions, but how can we capture in formula, number of splits that occur for each such iterations?


texts: Algorithm for checking if a list of integers is pairwise coprime

texts: Are thre any efficient algorithms for checking if a list of integers is pairwise coprime, or would a more general algorithm be the best option available?


texts:
I have some difficulties in understanding the intuition behind Naive Bayes Classification.

In general, I do understand every argument of the definition, however I don't understand why it's correct and why any other argument is incorrect.

Start from the beginning:

Goal: $v_{MAP} = argmax_{v_i} p(v_i|a_1...a_n)$

the goal is simply to find the maximum aposteriori of the value of the target function given the set of features Note,  here we don't mention the hypothesis, because we are not interested in hypothesis.

After developing the formula with Bayes formula, we get

$argmax_{v_i} p(v_i)p(a_1...a_n|v_i)$

Now, the trick goes $p(a_1...a_n|v_i)=\prod_{j} p(a_j|v_i)$

The question is why in the very begging, having the formula of

$v_{MAP} = argmax_{v_i} p(v_i|a_1...a_n)$

I cannot apply the trick $p(v_i|a_1...a_n)=\prod_{j} p(v_i|a_j)$

It's just a reverse direction, in addition we don't have to calculate the prior probability of $p(v_i)$, so for me it looks like the better way to go.

What's wrong with my reasoning.


texts: Which pretrained model will be best for my dataset?

texts: I am trying to build a classification algorithm having 28 classes. These classes consists of Logo of companies like adidas , Nike etc. I have very low dataset below than 100 images and greater than 70 images. I have trained CNN model but not got decent results . Accuracy is not good. I want to switch on pretrained model. I don't know which pretrained model should I use either VGG , ResNet etc. because I saw on Internet that you may use Pretrained model on  similar dataset but I have logo of companies , I don't know that any pre trained model is trained on such similar type of objects or not. How should I choose pre trained model that will performs well on my dataset.


texts: How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?

texts:
Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$.

I am thinking of constructing a DFA $M$ for the Language $L$ so the DFA for the language of its complement will be just changing the final states to non final states but the states will be same. So the classes do remain same? How do I put this in a more formal way?


texts: name perfect generalized sum tree with variable number children for each level

texts:
I was wondering if there is a name for the construct described below:

Given $N$ integers $n_0, ..., n_{N-1}$ we construct a tree of height $N$ levels such that:

each node of level $0$ (i.e the root) has $n_0$ children.
each node of level $1$ has $n_1$ children.
...
each node of level $N-1$ has $n_{N-1}$ children

also, this is a sum tree, which means that:

an integer is associated with each node
we arbitrarily set the associated integer for each leaf node
the integer associated with each parent is set to be the sum of the integers associated with its children

Is there a name for that?


texts: Why doesn't the recursion theorem prove there is an undecidable finite set?

texts:
I created something similar to Sipser's proof for the undecidability of $A_{TM}$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't figure out why for the life of me.

$A_R := \{\langle M \rangle | M = R \land M \text{ accepts "foobar"}\}$
Assume $D$ decides $A_R$. $R:=$ On any input:

By the recursion theorem, get own description $\langle R \rangle$
Run $D$ on $\langle R \rangle$
Do the opposite of what $D$ says. If it rejects, accept. If it accepts, reject.

$R$ contradicts what $D$ says about $R$. So $D$ can't be a decider. (i.e. If $D$ accepts $R$, $R$ should accept "foobar", but $R$ will reject all strings. If $D$ rejects $R$, $R$ should reject "foobar", but $R$ will accept all strings).

But because $A_R$ can only contain $R$, $A_R = \emptyset \lor A_R = \{\langle R \rangle\}$. Either way, it's finite, so $A_R$ is decidable.
So what's wrong with the first argument? A few ideas cross my mind:

I'm losing an important detail by making an informal argument.
Something odd in the recursive relationship between building $A_R$ and referencing $D$. (this could possibly be avoided by narrowing it to the subset of TMs with the length of R, which we could "guess" before R is created - and it would still be finite)
Logic shenanigans (a la the Liar Paradox)

But I just don't see exactly what the problem is.
Elaborating on my interpretation of the error for additional reference:
The argument looks like this:

Given an arbitrary decider for $A_R$, we can construct a TM $R$.
Given $R$, we construct $A_R$.
Then we can obtain a contradiction. So there is no decider for $A_R$.

That's circular, and hopefully more obviously wrong. And guessing the length of $R$, as previously suggested, doesn't work either - because an arbitrary decider has an arbitrary length.


texts: Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$

texts:
I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$
$$L=\{a^nb^m\mid 2n<m<3n\}$$


texts: Impossibility of certain type of tree traversal algorithm

texts:
I was wondering for some time how to approach a situation like the following one. Imagine a standard binary tree data structure with $n$ nodes in it. Each node contains pointers to its left and right children, and from that node we can navigate to each of these children in constant time.
We are looking to find whether an algorithm with given requirements exists, or not. In case there is such an algorithm, we should be able to come up with one. In case such an algorithm does not exist, I am very much interested in how to formally prove that. Most impossibility results I've come across usually rely on reduction to other problems which are known to be not solvable (like general purpose comparison-based sorting in time, asymptotically faster than $O(n\log n)$) or using some sort of decision tree argument directly.
However, in this particular case I am completely stuck both in ideas, and in a much more fundamental way: how to formally state some of the requirements.
Let's move on to the problem.
Condition 1: The algorithm should visit each node of the tree once, in other words, it is a traversal algorithm. We don't care about the order of the traversal: in-order, post-order, level-order, etc. Any order, even a completely random one and/or non-deterministic one, will do.
Condition 2: The time complexity of the algorithm should be $O(n)$. Clearly an optimal one.
Condition 3: The space complexity of the algorithm should be $O(1)$.
Condition 4: The tree is read-only, it should not be modified during the traversal.
Condition 5: The tree structure does not contain pointers from each node to its parent. In other words, we cannot assume that there exists a pre-built lookup table or any other mechanism that allows us to jump from a node to its parent in constant time.
Let's now consider following questions:
Q1: Does there exist an algorithm that satisfies all of Cond1, Cond2, Cond3, Cond5?
A1: Yes, one example is the well-known Morris traversal. Please note that it violates Cond4.
Q2: Does there exist an algorithm that satisfies all of Cond1, Cond2, Cond3, Cond4?
A2: Yes, one example is the classical in-order traversal by navigating to the smallest node in the tree (if we imagine it to be a BST), and then repeatedly moving to the successor while it is not $null$. This, however, heavily relies on parent pointers. There are other solutions too, again exploiting parent pointers. In other words, all approaches known to me violate Cond5.
Q3: Does there exist an algorithm that satisfies all of Cond1, Cond2, Cond3, Cond4, Cond5?
A3: I don't know!
My personal conjecture is that such an algorithm does not exist. However, I am totally stuck as to how to approach proving that. I've taken some classical Computational Complexity classes in my MSc studies that teach Turing machines results and theorems, but my major problem here is:

how to even formally state Cond4 and Cond5 under the Turing machines model, or any other standard computational formalism? Obviously these conditions are necessary for the (supposedly) negative result, since if we relax any one of them, the answer becomes affirmative, as shown by Q1 and Q2.

Has anyone else explored formally this topic before? I am really interested in a formal rigorous proof.
Please note that I am contemplating on this problem only because of personal interest and curiosity. It is not related to any studies, homework, exams, contests, etc.


texts:
Assume that $B_b$ denotes the finite set of bitstrings of length $b$, if we are given its subset $A = \{e_i\}, i \in \{0,... n\}$, such that $e_i \in B_b$, what is "the parity sum of As bitstrings" ($parity_A$)?

Is it a single bit $parity_A = parity(concat(parity(e_1), parity(e_2), ..., parity(e_n)))$?

Or is it a bitstring $parity_A = concat(parity(e_1), parity(e_2), ..., parity(e_n))$?

Or is it something else?


texts:
Given this sorting algorithm:

Sort(A, n):
    if (n == 1)
     return
    isSorted = true
    for i=1 to n-1 do:
        if (A[i] > A[i+1]):
            isSorted = false
            temp = A[i]
            A[i] = A[i+1]
            A[i+1] = temp
    end for
    if (isSorted)
         return
    else
         Sort(A, n-1)

I'm required to find the upper bound for the best case.
My question is - is the best case considered when the array length is 1? Or when the array is already sorted and then the loop runs only once? Or both cases?

Also, I need to find a recursive formula for the worst case.
I got to this formula:

if n $\neq1$
$F(n) = F(n-1) + n - 1$
else
F(n) = 1

Is it correct?


texts: What assumptions do I have to make about monitors (in OS)?

texts:
I am taking a course in Operating Systems. I am going through old exams and there is a question about monitors. We are supposed to give a solution for the producer-consumer problem using monitors. That is quite clear. But, it also says in the question:

List also the assumptions that you make about monitor semantics

Can anyone explain what is meant by this?


texts: Using SMT solvers to generate random solutions to given predicate

texts:
I am interested in generating random solutions to predicates. I only need SMT for integers with the following predicates/functions <, >, <=, >=, ==, !=, +, *

The algorithm I want should produce a random assignment of variables to values (a substitution) such that applying the substitution to the given predicate yields a true statement. In the UNSAT case I just need to know that it is UNSAT.

It is probably important to clarify what I mean by random. I think a sufficient definition is that there might be an extra parameter that acts as a seed. If I give a different seed the algorithm should give me a very different solution rather than the same solution. Frankly I'm not sure how to cash this out but it much the same way that a typical random number generator generates an integer between X and Y (well with a modulus and an addition anyhow) I'd like to generate to a wider class of predicates.

I would like to use existing SMT solvers ideally in either Haskell or the JVM stack (more ideally Haskell however). I have thought of basically just randomizing the DPLL algorithm and translating the SMT problems into SAT my self but that sounds like a terrible idea when really good existing SMT solvers exist.


texts:
Hi I am currently learning about orthogonal range search and found two data structures with two different runtimes and wanted to proof that one always dominates the other.
So I found out about k-d-trees with a query time of
$$\mathcal{O}(n^{1-\frac{1}{d}})$$
and range trees with a query time of
$$\mathcal{O}(\log^{d-1}n)$$
and would like to show that
$$\mathcal{O}(\log^{d-1}n) << \mathcal{O}(n^{1-\frac{1}{d}}) \quad \forall d \in \mathbf{N}$$
I tried around on Wolfram Alpha and the solutions were of the form
$$ n > \exp\left(-d \cdot W_{-1}\left(\frac{-1}{d}\right)\right) $$
where $W_k(z)$ is the analytical continuation of the product log function. But I wasn't able to proof this always holds. Thank you in adnvance :)


texts: Prove undecidability of a TM M that accepts at least one input AND rejects at least one input

texts: I got stuck trying to prove that AND statement. I assumed that the TM will accept if its language is not empty and the complement of its language is not empty and reject if its language is empty or the complement of its language is empty. I tried reducing the Halting Problem but got stuck with proving that both the language and it complement are not empty. Any thoughts?


texts: Is this problem just an application of traveling salesman? If not is it some other already "solved" problem?

texts:
Description of the problem in question:

Say I have a complete graph with positive weighted edges. 1 vertex is specified as the "end". A subset of the other vertices are designated as "start" vertices.

I want to find paths from each start vertex to the end vertex with the following conditions:

As input, each path is given a maximum number of vertices it can visit. ie a path with a max of 5 vertices can only visit 5 other vertices before going straight to the end.
Each vertex can only be visited by one path
Each path must visit its max number of vertices, as long as there are unvisited vertices still available.
The total combined cost of the paths should be minimized

Basically, I want to find a path from each start vertex to end vertex that hits as many other vertices as possible, limited by each paths max and that each vertex can only be visited once. So it's possible that not all vertices will be hit or that a path won't visit its max number of vertices.

I want to know if and how this problem breaks down into TSP, or some other problem. In general, I want to figure out how to solve this problem but I'm just looking for a place to start.

Any insight would be greatly appreciated.

Thanks a lot


texts: Approximating all independent sets of size k in a graph

texts: Given an undirected graph, I need an algorithm that outputs all the independent sets of size >= k (constant) in the graph. I know the problem is NPC, and I do not want to use the exponential brute-force solution. What I am looking for is to hear about the best solutions currently known to this problem. If someone can refer me to some known polynomial approximation algorithms that achieve good results, that would be very helpful.


texts: When do type systems start needing a logic engine?

texts:
I've noticed that some languages include a logic engine as part of their type system (e.g. Shen, Typed Clojure).

Other languages have a much more direct type checking algorithm (e.g. Haskell / Hindley-Milner).

What specific features of a type system make it necessary to include a logic engine?


texts:
My son who is just learning to read loves the concept of hiding one letter of a word with his finger and asking what the rest of the word spells. His favorite is turning "her" into "he" and "then" into "the."

As he's starting to learn bigger words I want to find some words for him that are "truncatable," similar to the concept of a truncatable prime. These would be dictionary words that are also dictionary words when a character is removed from either the left or the right side. A properly "truncatable" word would continue to be a word down to 1 character, but I would be really only looking for those that are truncatable down to three letters:

 Browser
 Browse
 Brows
 Rows
 Row

What is the best algorithm to do this? My initial naive approaches are proving quite horribly inefficient for the dictionary file that I am using. I am currently literally testing every word in the dictionary, recursively, and the running time and space are intractable and the methodology ends up testing each word many times.

Is there an efficient memoized or otherwise optimized way of finding truncatable words?

Edit: Thank you to https://cs.stackexchange.com/users/755/d-w who provided guidance, this is the code I ended up coming up with which works:

# find list of truncatable words in English
# truncatable words are those where a word
# can be dropped from the beginning or end
# to form a new valid word, all the way down
# to three letters or fewer!

def main():
    # Find the truncatable words

    # read dictionary into a list
    f = open("english3.txt","r")
    wordlist = []
    for line in f:
        wordlist.append(line.strip().lower())

    # sort by length

    wordlist2=sorted(wordlist,key=len)
    max_word_length = len(wordlist2[-1])

    # set up list of dictionaries for truncatable words
    Truncatables = []
    for filler in range (max_word_length+1):
        Truncatables.append({})

    # iterate through dictionary and test for truncatability
    for word in wordlist2:
        if len(word)<=3:
            Truncatables[len(word)][word]='default'
        else:
            front = word[1:] in Truncatables[len(word)-1]
            back = word[:-1] in Truncatables[len(word)-1]
            if front and back:
                Truncatables[len(word)][word]='both'
            elif front:
                Truncatables[len(word)][word]='front'
            elif back:
                Truncatables[len(word)][word]='back'
            else:
                pass
    print(Truncatables)

    # Define a function that recursively prints out a truncatable chain

    def printTruncatable(word):
        if word in Truncatables[len(word)] and word in wordlist2:
            print(word," ",end="")
        TruncType = Truncatables[len(word)][word]
        if TruncType == "back" or TruncType == "both":
            printTruncatable(word[:-1])
        elif TruncType == "front":
            printTruncatable(word[1:])
        elif TruncType == "default":
            print("\n")
        else:
            print("ERROR")

    # print the top truncatables
    for wordlength in range(max_word_length,7,-1):
        for key in Truncatables[wordlength]:
            print(wordlength,": ", end="")
            printTruncatable(key)

if __name__ == "__main__" :
    main()


texts: Determining whether a number is a perfect square without computing its square root

texts:
One of the interesting results of Number Theory is the theory of quadratic reciprocity. One finds that it is possible to determine whether an equation $x^2 \equiv a \pmod p$ has a solution $x$ without computing its solution.

Is it possible to do the same with the equation $x^2=a$, determine whether $a$ is a perfect square without computing its square root?


texts:
Given a Binary Search Tree and two elements $e1$ and $e2$ which are in the tree, find the length of the shorted path between them. Give the representation of the Binary Search Tree(use a linked representation with dynamic allocation without an attribute for parent or height). Implement the required operation and specify its complexity. Hint: try to find first the Least Common Ancestor of the nodes, the first node which is an ancestor for both nodes.

I thought that for finding the Least Common Ancestor we have to make a preorder traversal for example having the while loop : $while(!(e_1<a == e_2 < a))$, but I don't know how to count the length between them.
How should I count them?


texts: Using Union find to check whether there is a cycle in a graph

texts: I'm trying to learn about DSU, and I came across a point stating if two vertices belong to the same sub-set, then a cycle exists. In terms of implementation of DSU, I'm unable to make sense of this. Could you share a proof or explain this?


texts: Attempt to write a function with cubed log runtime complexity $O(\log^3 n)$

texts:
I'm learning Data Structures and Algorithms now, I have a practical question that asked to write a function with O(log3n), which means log(n)*log(n)*log(n).

public void run(int n) {
    for (int i = 1; i < n; i *= 2) {
        for (int j = 1; j < n; j *= 2) {
            for (int k = 1; k < n; k *= 2) {
                System.out.println("hi");
            }
        }
    }
}

I have come with this solution, but it seems not correct. Please help me out.


texts: Powerset construction is used to convert a non-deterministic finite automaton (NFA) into a deterministic finite automaton (DFA). Is the method/algorithm used to do this deterministic itself and if so, why?


texts:
I have a problem which i don't know how to calculate or more specifically what am I missing. The subject is about 802.11 (wifi)

The selected PHY rate is 54Mbit/s, that is whenever DATA is being sent the rate is 54Mbit/s, and when the node is not sending anything the rate is 0. To simplify the task, assume that there are no collisions and no errors in the channel.

The frames in the figure are marked up as follows:

Message Purpose Duration, us RTS Request to send 44 CTS Clear to send 48 DATA Payload packet Variable ACK Acknowlegement 44 SIFS Inter-frame-spacing 4 DIFS Same as SIFS 16 Backoff MAC arbitration 0..63

The question is: What would be average effective throughput (in Mbit/s) with basic signaling if the DATA packet takes 166 microseconds? Write your answer as average effective bit rate for whatever is being put into DATA packets. Allowed error is 2%

What am I missing?


texts: Solving the recurrence formula $T(n) = 3T(n/2)+n^2$

texts:
What is the solution of the following recurrence?
$$
T(n) = 3T(n/2) + n^2, \quad T(1) = 0.
$$
I cannot use the master theorem since I need to know the exact final expression, not just it's big O, which I know is $O(n^2)$.
I'm stuck at the following, after 4 steps:
$$3^4T(n/2^4)+((3^6)n^2)/((2^6)2^6)+(3^3n^2)/((2^2)2^4)+(3n^2)/(2^2)+(n^2).$$


texts: How many zeros should be in front of two's complement model?

texts:
The Problem
Convert 256 to its 2's complement representation.

My Work

   I know that 256's representation in unsigned binary is 100000000. What I know from working with two's complement model is that the most significant digit represents the sign of the  number. So in this case,   100000000 cannot be 2's complement representation as well because that would mean that the original number, 256 is negative.

   Is there a specified number of zeros I should add to the front of the binary representation? Would it be acceptable to just add one zero to the front, say 0100000000?


texts: What purpose do the leaves in a range trees serve?

texts:
I'm getting into algorithms and I came upon range trees. What confuses me is the leaves in a range tree, since for example:

When you remove the leaves:

It's just a regular BST.
And, every implementation I see of a range tree/range searching, for example, doesn't put the points in the leaves like in the first image.

So, why do depictions of range trees show all the points in the leaves when that would double the amount of space required? Is it just for visualization purposes, or does it represent the output? Is a range tree just a BST with a range query? This may seem nitpicky, but it really confuses me.
Graphic source: graphics.stanford.edu/courses/cs428-03-spring/03Talks/Range.pdf It isn't unique to this specific example. It's seen here: cs.uu.nl/docs/vakken/ga/slides5b.pdf and here:cs.umd.edu/~meesh/cmsc420/ContentBook/FormalNotes/MountNotes/…, even though they seem to just use regular BSTs and don't seem to put the leaves in the nodes

EDIT: It's probably just for  visual purposes: http://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring16/Lectures/cg-rangetrees.pdf


texts: k-armed bandit - index policies vs. Q-learning

texts:
I am interested in the stateless k-armed bandit problem, where an agent repeatedly chooses one of k independent arms, each with a different distribution of rewards, and tries to maximize its total reward.

I read many papers about this subject, but I am still confused, as there are two types of solutions:

A. It has been proven that the optimal solution to this problem is an index policy: For each arm, calculate a quality index, based on the rewards received from that arm so far. The index roughly estimates an upper confidence bound on the expected reward from that arm. Now choose the arm with the highest index.

B. On the other hand, this problem can also be presented as a Markov decision process, which can be solved by Q-learning. The general formula for Q-learning is:

$Q_{t+1}(s,a) := (1-z_t) Q_t(s,a) + z_t (R_t + g * max_{a'}(Q_t(s',a'))$

Where: t is the time, s is the state we were at, a is the action we did, s' is the state we got into, $z_t$ is the rate of learning at time t, R_t is the reward we received at time t, and g is a constant discount rate.

In this case, there is only a single non-terminal state. Each arm-pull is an episode: it starts with the initial state, and always goes to the final state. Therefore, the Q value of the final state is always 0, and we only need to calculate Q values for actions of the single initial state:

$Q_{t+1}(a) := (1-z_t) Q_t(a) + z_t R_t$

It is guaranteed that the process will converge to an optimal policy, if each action is selected eventually, and if the learning rate $z_t$ decreases in an appropriate rate (speficically, $\sum_{t=1}^\infty z_t^2 < \infty$ and $\sum_{t=1}^\infty z_t = \infty$).

Now, my question is: what is the relation between two methods for solving the k-armed bandit problem?

Is it possible to prove, that the Q values converge to one of the indices given in the literature?
Why use an index method, if it is possible to use the much simpler Q-learning method?


texts: When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar?

texts:
Options given were:

  (a) 2  (b) 3  (c) 4  (d) 5

This question was a part of my assignment. I think the answer is 2 internal states - one start state and the other end state/acceptance state, but I am not sure whether it is correct or not.
Please correct me if I am wrong.
Thanks.


texts:
Is the language $L = \{w w^r w w^r \mid w \in \Sigma^*\}$ context-free? ($w^r$ is the reversal of $w$.)

I heard that by using the pumping lemma, we can only prove that a language is not context-free, but can't prove that a language is context-free. I tried the pumping lemma and we can produce the language by repeating $v$ and $x$ by taking first $ww^r$ as $v$ and the second $ww^r$ as $x$ which again belongs to the same language. However I'm not able to build any grammar or build a PDA with one stack. I know that may if someone tries harder than me they may be able to construct it, but I'm thinking this may not be a context-free language. Does anyone have any idea about this language?


texts: What is the time complexity of this atrocious algorithm?

texts:
This grew out of a discussion of deliberately bad algorithms; credit to benneh on the xkcd forums for the pseudocode algorithm, which I've translated to Python so you can actually run it:

def sort(list):
    if len(list) < 2:
        return list
    else:
        if list[0] <= minimum(list[1:]):
            return list[0:1] + sort(list[1:])
        else:
            return sort(list[1:] + list[0:1])

def minimum(list):
    return sort(list)[0]

I'm interested in working out the worst-case, best-case and average-case time complexity, but I've found myself insufficiently practiced to do so.  I originally thought it would be O(n!), which would be equivalent to cycling through all possible permutations of the list, but because the results aren't even memoized I believe it's actually worse than that.

Mitigating that is the fact that not all of the recursive calls can possibly be worst-case, so I'm not even sure what the worst-case input is for the function overall.

However—even a sorted input of size 5 results in a total of 64 recursive calls, or $2^{n+1}$.  This is best-case time complexity.

What is the worst case input for this algorithm, and what is the time complexity for worst case and average case?


texts: Does Google's search algorithm really respect order of relevance imposed by PageRank?

texts:
I'm in doubt about that because in Google's results for a search on "bill clinton" [1],
the server "The 'Unofficial' Bill Clinton" (94.06%) appears first than the server "President Bill Clinton - The Dark Side" (97.27%) and there is no feedback mechanism modifing the ranks.

Since I've noticed that, I am wondering if google uses some algorithm for efficiently intesecting inverted indices that exploits the PageRank although not completely preserving order.

[1] The Anatomy of a Large-Scale Hypertextual Web Search Engine

http://infolab.stanford.edu/~backrub/google.html


texts:
What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA.
Can anyone quote an example and explain these concepts.


texts: Sampling data following some arbitrary normal distributions

texts:
Let say I have a matrix $D_{N \times 3}$ which its columns are $x, y, z$ and assume that assume that $N$ is a huge number and all $x, y, z$ are sampled from 3 different uniform distributions.
Now, I want to select a subset of rows and store it in $d_{m \times 3}$ (so $d \in D$) such that the selected rows meet the following criterias:

$x_d = d[:, 0] \sim \mathcal{N}(\mu_x, \sigma^2_x)$
$y_d = d[:, 1] \sim \mathcal{N}(\mu_y, \sigma^2_y)$
$z_d = d[:, 2] \sim \mathcal{N}(\mu_z, \sigma^2_z)$

Note that all $\mu_x, \sigma^2_x, \mu_y, \sigma^2_y, \mu_z, \sigma^2_z$ are specified by user and you can assume that specified averages and variances are within the original data. My question is, what is the best way to sample data to meet the criteria?
As a simple example if we had the following data on $D$:
X    Y    Z
1    2    3
2    3    8
3    4    9
1    1    1
2    6    6

and we had only one criteria to meet $x_d = d[:, 0] \sim \mathcal{N}(\mu_x=1, \sigma^2_x=0)$. Then $d$:
X    Y    Z
1    2    3

# OR

X    Y    Z
1    2    3
1    1    1

are both valid solutions. Note that there could be no answer exist, the answer should have the closest possible. If multiple answers exist, then any of them would be fine.


texts: "Real World" Applications of an Efficient Root Finder

texts: I don't know this is off-topic (if not, someone can direct me to the proper Stack), but here goes: Let's say there is some algorithm $T$ that can find the integer roots of any arbitrary real-valued continuous univariate function $f(x)$. For any value of $x$, $f$ can be computed efficiently ($O(n^k)$, where $k$ is some small constant). $T$ is similarly efficient. Are there any real life problems that would be benefited by having such an algorithm?


texts:
I am stuck on trying to understand how to solve the following question. Could someone please explain for a beginner to average-case analysis?

Considering the following algorithm A which takes as input a bit string b = b_1, b_2, ... , b_n (each b_i is either 0 or 1) and does the following:

A(b,n)
k = 0
FOR i = 1 TO n DO
    IF b_i = 1 THEN
        k = k + 1
j = k mod 2
IF j = 1 THEN
    FOR i = 1 TO k DO
        PRINT("Hello World")

Assuming each string is bit string b is equally likely, what is the average number of "Hello Worlds" that A will print?

The hint I have so far is I need to express the sum directly on the sample space, where $X$ below represents the number of times "Hello World" is printed,   and depends on individual inputs.
$$
E(X) = \sum_{L \in S_n} X(L) \cdot Pr(L)
$$


texts: Given language consisting Turing machines is decidable or not?

texts:
$$L=\{M\mid \text{there exist }x,y\in\Sigma^* \text{ s.t. }x \in L(M)\text{ and } y \notin L(M)\}\,.$$

I think it's not recursively enumerable because this language reduces to complement of the membership problem. $\langle M,w\rangle$ would be input where $y$ would become $w$ and $x$ belongs to $L(M)$.

Please tell me whether I'm correct or not, and help to solve if I'm wrong.


texts: Finding pairs of vertices which would disconnect a graph

texts:
An assignment question asks,

  Given a connected, undirected graph $G$, describe an algorithm which can determine if the removal of any pair of vertices would cause $G$ to become disconnected.

There is an obvious brute force solution, which is to just generate all pairs of vertices, produce new graphs with those vertices removed, and then test if that graph is connected using something like a BFS, running in $O(|V|^3)$ time.

However, I feel like this is not the intent of the question. We learned about an algorithm to find the articulation points of a graph, and it seems like something like this should be possible to determine if the removal of any pair of vertices would disconnect the graph, but I am not sure how it would be applicable.


texts: What is uniformity in Boolean circuits exactly?

texts:
I have two questions on Kaveh's answer to Definition of uniform boolean circuit :

Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is  a sequence of 1's repeated n times, but unary encoding is a sequence of 1's  and ends with 0 there is no power of 1 that gives 0... So how is $1^n$ a unary encoding?
Why do we use a unary encoding and not the binary encoding of n? what happens if we use binary instead?


texts:
I was doing reading on weighted quick-union using path compression. I have a clear understanding of why this is $O(1)$ with amortized analysis for union and find operations but do not understand how to address this special case.

Suppose we have $x$ items to start with, (all disjoint) and we perform a sequence of $m$ operations such that all calls to find come after all calls to union. I am trying to determine what kind of data structure could be used, because in my previous understanding of disjoint sets, the union operation is always dependent on the find operation.

Despite having this information about the order of operations, I do not quite see how it is useful- or, how it can be used to achieve an amortized analysis of $O(1)$. Also, not sure of how to approach the union operation without relying on calls to find.


texts: Calculation of Gen and Kill set for data flow analys

texts:
I'm currently preparing for an exam in compiler construction. The course is mainly about optimization in the backend of the compiler. For the optimization we have to do data flow analysis by hand.
In one example I do not understand how gen and kill sets are determined. My solutions differ a lot although I stuck to the transfer functions for reaching definitions. The analysis is structured by base blocks.

Code:

1: i=2;
L1:
2: if( i <= 220 ) goto L4;
L2:
3: t4 = i*8;
4: t5 = base() + t4;
5: t6 = t4 + j;
6: j = j+1;
7: if( t6 >= 120 ) goto L3;
8: t5 = t6 + t4;
L3:
9: i = t5 + 1;
10: goto L1;
L4:
11: return i;

Base Blocks:

BB1 = {1}

me:       gen={1} kill={2,3}
solution: gen={1} kill={2,3}

BB2 = {2}

me:       gen={} kill={}
solution: gen={2} kill={}

BB3 = {3, 4, 5, 6, 7}

me:       gen={3,4,5,6} kill={4,5,6,8,9}
solution: gen={3,4,7} kill={5,6,8,9} ???

BB4 = {8}

me:       gen={8} kill={4,9}
solution: gen={8} kill={9}

BB5 = {9, 10}

me:       gen={9} kill={3}
solution: gen={9} kill={2,3}

BB6 = {11}

me:       gen={} kill={}
solution: gen={} kill={}

The gen and kill set are used to compute the in and out set. In and out set are then used to compute reaching definitions.

Can somebody explain to me why the sets differ by so much?


texts:
From Wikipedia's definition of regular langauges

  The collection of regular languages over an alphabet $Σ$ is defined
  recursively as follows:

  The empty language $Ø$ is a regular language.
  For each $a ∈ Σ$, the language $\{a\}$ is a regular language.
  If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A • B$ (concatenation), and $A^*$ (Kleene star) are regular languages.
  No other languages over$ Σ$ are regular.

The regular languages also form a (full) AFL.

Parallel to the concept of generator for a sigma algebra, do the regular languages form the minimal  (full) AFL (or (full) semi-AFL, full trio, trio, ...)  that contains the empty language, and  $\{a\}, a ∈ Σ$? In other words, are the minimal  (full) AFL (or (full) semi-AFL, full trio, trio, ...) generated by the empty language, and  $\{a\}, a ∈ Σ$ exactly the regular langauges?


texts:
Let's say I have 2 graphs $g_1$ and $g_2$, each determined by a set of nodes and a set of non-oriented edges.

I also have 2 operations that can be done on a graph: edge contraction and node split:

Nodes have a position so it is possible to do the operation as specified on the figure, and we can assume that the neighborhood of a node is roughly planar.

How can I have a list of operations transforming $g_1$ into $g_2$ ?

I know there is a graph edit distance that find the cost of such a list of operations, but what is interesting me is the list itself. Are there some articles that I can read that answer (even partially) this question ? I wouldn't want to do a brute force approach, since even with 2 operations the number of possibilities is enormous.

Please note that there are some constraints verified these graphs:

each node has at least 2 edges connected to it
there can be only one edge between 2 given nodes (so no redundant edges)


texts:
Let $G = (V,E)$ be a directed graph  with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. Let $f : V \to \mathbb R$ be a given function. Describe an algorithm that runs in $O(|V| + |E|)$ time that answers yes/no to the question: is it true that for all $u \in V, f(u) = \delta(v,u)$, where $\delta(v,u)$ is the weight of the shortest path from $v$ to $u$?

Obviously what comes to mind is Bellman-Ford algorithm, but it doesn't satisfy the time requirement. I don't really see how having the candidate $f$ function helps us in this regard.


texts: Show {^i^j^k, i!=j!=k} is context free or not, how can we prove it?

texts: I stuck on this question for a long time and cannot figure out how to prove it?


texts: Given a set of segments, I would like to compute the set of closed polygons inside the convex hull of the set of the end of those segments. The vertices of the polygons are the intersections of the segments. For example, if you draw the 6 lines restricted which equations are: $x=-1$, $x=0$, $x=1$, $y=-1$, $y=0$, $y=1$, I would like the algorithm to output the four unit squares around the origin.


texts: Closest arithmetic progression to an array

texts:
Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference between the elements of the array and the elements of progression. Thus one needs to minimize the sum of absolute differences. It is a restriction that the values must be integers:
$1, 5, 10, 14, 19 \to 0, 5, 10, 15, 20$

It is easy to solve it with the help of linear programming without restriction to integers. But even the simplex method and other similar algorithms are not sufficient because they can handle cases when $N \leq 10^5$. In this case, the integers can be rather large (i believe up to $10^7$). Is there any algorithm for solving it in $O(N\log^k M)$ or even $O(N)$, where $M$ is the maximum integer value of an array?


texts: Schedule each entree so that all entrees are completed in the shortest amount of time

texts: Lets say we have plenty people to dress up entrees, but only one chef to cook them. Each entree $E_i$, takes $c_i$ time to cook and $d_i$ time to "dress up". The dressing up of entrees can occur while other entrees are being cooked and dressed up, but we can only cook one entree at a time. How would you go about creating an algorithm to schedule each entree $E_i$ in a manner that they all get finished in the shortest amount of time?


texts: How should $\lambda x. \lambda y. f z x y \stackrel{\eta}{=} \lambda x. f z x$ be read?

texts:
I'm currently learning untyped $\lambda$-calculus and especially the $\eta$-reduction.

The professor hat the following in his slides:

$$\lambda x. \lambda y. f~z~x~y \stackrel{\eta}{=} \lambda x. f~z~x$$

I don't know how to read and understand this. Could you please explain it to me?

My try

On the left side and the right side is a function and they are $\eta$-equivalent.

The right side seems simpler, so I start with that.

It is a $\lambda$ function with one bound parameter $x$ and two unbound parameters $f$ and $z$. But here start my problems: What does $f~z~x$ mean? Is this a triple? Is it a function $f$ and a function $z$ and a function $x$?

I think in $\lambda$-calculus everything can be viewed as a $\lambda$-function, so $f$, $z$ and $x$ are functions. So the right side is the same as

$$\lambda(x) = f(z(x))$$

correct?

Applying the same logic on the left side, I get:

\begin{align}
\lambda x. \lambda y. f~z~x~y &= \lambda(x)\\
&= f(z(x(y)))
\end{align}

As $y$ is not in $\lambda(x)$ it is not bound. So we can simply remove it. Correct?

I think this could work. But I still don't know how to read it. I guess it will be something like:

"The lambda-function with the parameter $x$ that is a lambda function with a parameter y is f applied to z applied to x applied to y is eta-equivalent to the lambda function with the paramter x that is f applied to z applied to x".


texts:
I'm abit afraid to ask this question here seeing as I asked it on programmers SE already, the thing is I think the question is more about the underlying theory than the use in practice (or call it confirmation bias). (If people here agree i should not have asked it here I will delete it and offer my sincere apologies) however I do think it will get a deeper meaning here as to why this is or isn't true.

Here is the question:
I have a teacher who (to me) seems quite intelligent, he really knows what he is talking about but he said something which surprised me (I'm paraphrasing): while loops can be proven where as for loops cannot.
I think this translates to: One can completely explain what happens in a while loop whereas you cannot do that for a for loop

Is my teacher right? (maybe this was the case when he started learning? ) and a more subjective question: Is there any clear reasoning behind this (why he would have stated this)?


texts: Running time of an algorithm containing binary elements for cryptography

texts: Hey guys sorry I'm new to cs and I'm trying to find the running time of algorithms... could you tell me about the algo given how much time is needed in terms of complexity?  The actual algo I created is the same as below but the sum must be more or equal to 2^(n-2).Thank you]1


texts:
I have an undirected weighted graph.

I want to find the path from A to B which length (sum of the weights) is as close as possible to a specific value "L".

To do that, I have been doing a DFS to check all the possible paths... When L is relatively small, it's ok. But when I ask for a bigger L, it takes too much time to complete. I added some criteria to stop searching useless paths but that cannot solve the problem.

So I was wondering how to do what I am searching for. Is DFS the only solution ? I thought about genetic algorithms but I don't know if it would work.

Thank you !


texts: Regularity of a language with odd and even positions containing an even number of 1's

texts:
Given an alphabet $\Sigma = \{0, 1\}$ and
a formal language $$L = \{ w \in  \Sigma^* |\ |\mathrm{odd}(w)|_1, |\mathrm{even}(w)|_1 \text{are even numbers} \}$$

That means that the number of 1's in the odd and even positions of a given string are always an even number. I've tried using the Pumping-Lemma on a $1^{4n}$ string but to no avail.

Any ideas how I can proove it is not regular. (I strongly assume it isn't regular).


texts:
Let

$T\equiv\lambda xy.x$
$F\equiv\lambda xy.y$

Numbers are represented as:

$0\equiv\lambda sz.z$
$1\equiv\lambda sz.s(z)$
$2\equiv\lambda sz.s(s(z))$
$N\equiv\lambda sz.\underbrace{s(s( ... (s(}_\text{N times}z))...))$

I want to define zero checking expression $Z$, being applied to $0$ reduces to $T$, otherwise $F$.

$Z\equiv\lambda f.f(\lambda t.F)T$

$Z0\equiv(\lambda f.f(\lambda t.F)T)(\lambda sz.z)=(\lambda sz.z)(\lambda t.F)T=T$
$ZN\equiv(\lambda f.f(\lambda t.F)T)(\lambda sz.\underbrace{s(s( ... (s(}_\text{N times}z))...)))=(\lambda sz.\underbrace{s(s( ... (s(}_\text{N times}z))...)))(\lambda t.F)T=\underbrace{(\lambda t.F)((\lambda t.F)( ... ((\lambda t.F)(}_\text{N times}T))...)))=F$

Is my solution correct?


texts: What does Djikstra mean by "formal techniques" in this essay?

texts:
In this essay (and others) by Djikstra, he refers to "formal techniques" a number of times.

... for the computing scientist, formal techniques would play a much more important rôle than they had done so far for the mathematician.
... The practical reason was that formal techniques are indispensable for dealing in a sufficiently trustworthy manner with the type of complexities a program designer has to control.
In our history, the computing scientist seems to be the first to be asked to apply formal logic on a grandiose scale and to make formal techniques an integral part of his daily reasoning; in a way, circumstances have forced him to become more mathematical than the Pope is Roman Catholic.
... what else can you expect in a world that has never seriously tried to apply formal techniques on a sizeable scale with elegant effectiveness?

I have only a vague idea of what he means by this term (which I'm sure has to do with the context he was writing in in 1985).
Does he mean something like "formal methods" -- proving mathematically that a program you've written is correct? If so, his assertions don't seem very accurate -- we're not doing that on a "sizable scale."
From other essays, I have the idea that perhaps he means "programming in a language with a specified syntax." To my understanding, this would make the third quote make more sense -- his argument is that mathematicians have no syntax their formulas must follow -- but I don't know why this would be called a "technique" or why it would be called "indispensable", as though it's some new technological advance for writing programs. How would programs be written, if not in terms of some strict syntax?
So I'm not sure I get what he's saying.


texts: Do any single-cell organisms exist that approximate NP-hard problems within a factor better than $1/2$ $log$2?

texts:
I've seen on Wikipedia; that set covering cannot be approximated in polynomial time to within a factor mentioned above. Unless $NP$ has quasipoly-time algorithms.
Now, this must pertain to classical algorithms and does not mention any approximation algorithms that may only work in nature.
(eg. Things like Amoebas solving $TSP$ problems)

Do any single-cell organisms show any promise in solving $NP$-hard problems in polynomial-time?

Or approximating them better than any known classical algorithms?


texts: What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth?

texts:
Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of recursion, it switches over to insertion sort. What is the running time of this modified algorithm?

I know that MergeSort has worst-case runtime of $O(n \log n)$ and Insertion Sort has worst-case runtime of $O(n^2)$, but I'm not sure how these bounds will be affected within the problem above.


texts: Is it possible to prove Tarski's Undefinability theorem from Turing's Halting Problem?

texts:
In the Wikipedia page for Turing's Halting problem, they mention that you can prove Gödel's First Incompleteness theorem from it. This is the relevant quote:

  Assume that we have a sound (and hence consistent) and complete
  axiomatization of all true first-order logic statements about natural
  numbers. Then we can build an algorithm that enumerates all these
  statements. This means that there is an algorithm N(n) that, given a
  natural number n, computes a true first-order logic statement about
  natural numbers, and that for all true statements, there is at least
  one n such that N(n) yields that statement. Now suppose we want to
  decide if the algorithm with representation a halts on input i. We
  know that this statement can be expressed with a first-order logic
  statement, say H(a, i). Since the axiomatization is complete it
  follows that either there is an n such that N(n) = H(a, i) or there is
  an n' such that N(n') = ¬ H(a, i). So if we iterate over all n until
  we either find H(a, i) or its negation, we will always halt, and
  furthermore, the answer it gives us will be true (by soundness). This
  means that this gives us an algorithm to decide the halting problem.
  Since we know that there cannot be such an algorithm, it follows that
  the assumption that there is a consistent and complete axiomatization
  of all true first-order logic statements about natural numbers must be
  false.

After reading this proof, I wondered if a very similar proof by contradiction could also prove Tarski's Undefinability theorem?

I was thinking of something along the following lines:

Imagine that a truth predicate isTrue($\ulcorner s \urcorner$) for any arbitrary logic sentence s were computable. In that case, this predicate would also be able to compute the truth status for any arbitrary H(a,i). Therefore, we would be able to compute isTrue($\ulcorner H(a,i) \urcorner$) for any possible H(a,i). Consequently, such isTrue($\ulcorner s \urcorner$) predicate would solve Turing's Halting problem, while we already know that it is fundamentally unsolvable. Therefore, such truth predicate is not computable.

Is there a flaw or a problem with this proof strategy?

The fact that the Wikipedia page mentions this proof strategy for Gödel's First Incompleteness but not for Tarski's Undefinability got me wondering. Maybe it does not work for Tarski after all? What's the catch?


texts:
Data flow analysis work over a control flow graph. When a language under consideration supports exceptions, control flow graph can explode.

What are the standard techniques for dealing with this blow-up?
Can we soundly disregard edges induced by exception? Data flow analyses anyhow compute over-approximations, so we would end up with a less precise but sound solution. Is this true?

Update: Here are few useful links that I was able to dig out at the end:

Analysis and Testing of Programs with Exception-Handling Constructs
Efficient And Precise Modeling of Exceptions for Analysis of Java Programs


texts: Turing machine: errata in computable numbers paper?

texts:
I'm reading Turing On Computable Number 1936, specifically the section pictured here:

Does anyone see errata here?  Should the second m-configuration "c" in the table, have the "final m-config" be gothic e instead of the gothic c used?

If this were the case then 010101... could be printed.  If not, I'm unsure how 010101... is printed.

Thanks for your input.


texts: Correctness of addition in 1's complement number representation

texts:
The one's complement representation of integer numbers in computer memory is generally defined as the system prescribes to invert all bits (all but the sign one) of a negative signed number. It didn't come to me swift what the rationale for this representation. However, things fall into place if the most significant bit of a representation (the sign bit) is considered to be a negative number, whereas the rest its bits - poitive ones. So having for simplicity's sake $n = 4$ bits we could represent the $[-2^{n-1} + 1 , 2^{n-1} - 1]$ ($[-7, 7]$) interval in such way:
$$1000_{2} → -7_{10} = -(2^3) + \mathbf2^\mathbf0$$
$$1001_{2} → -6_{10} = -(2^3) + 2^0 + \mathbf2^\mathbf0$$
$$1010_{2} → -5_{10} = -(2^3) + 2^1 + \mathbf2^\mathbf0$$
$$1011_{2} → -4_{10} = -(2^3) + 2^1 + 2^0 + \mathbf2^\mathbf0$$
$$1100_{2} → -3_{10} = -(2^3) + 2^2 + \mathbf2^\mathbf0$$
$$1101_{2} → -2_{10} = -(2^3) + 2^2 + 2^0 + \mathbf2^\mathbf0$$
$$1110_{2} → -1_{10} = -(2^3) + 2^2 + 2^1 + \mathbf2^\mathbf0$$
$$1111_{2} → -0_{10} = -(2^3) + 2^2 + 2^1 + 2^0 + \mathbf2^\mathbf0$$
$$0000_{2} = 0_{10}$$
$$...$$
$$0111_{2} = 7_{10} = 2^2 + 2^1 + 2^0$$
(The representation leaves out that $\mathbf2^\mathbf0$ which is implied).
Let's restrict ourselves here to negative numbers only. If the representation of a number $c$ is $repr(c) = c - 2^0$ and $a + b = c$ then $repr(a) + repr(b) = c - 2^1$. So to add representations of $a$ and $b$ and get the correct one for $c$ we should just add 1 above the result sum:
$$repr(a) + repr(b) + 2^0 = c - 2^0 = repr(c)$$
It's all very well but when a CPU adds two negative representations the output fills the $(n+1)$-th bit:
$$repr(-4) + repr(-3) + 2^0 = 1011_{2} + 1100_{2} + 0001_{2}  = 11000_{2} → -(2^4) + 2^3 + \mathbf2^\mathbf0 = -7_{10}$$
In view of the fact $-(2^4) + 2^3 = -(2^3)$ it seems the $(n+1)$-th bit can be omitted. However, there is an issue arises. Can be we sure the $n$-th bit will be 1 and not 0 after addition? (The premise is the sum is inside the allowable interval). I would appreciate any hints of precise proof.


texts:
A BTree has a $k$ value that determines that every node has $k$ to $2k$ children. When a node has $2k$ keys it needs to be split into two nodes.

Let's say I want to create a $k/(2k-x)$ tree. (like a 2-3 tree that follows the BTree rules, but isnt $k/2k$)

What is the possible range of $x$? The tree must follow the behavior of a BTree, meaning it needs to hold keys and split accordingly.


texts:
Hi I have this simple question. When adding a positive number with a negative number, both of same exponent. Imagine that after complementing the negative we have something like this:

1.111
+
0.001
.......
This makes a Carry out.

What I want to know if I don't take care of the carry out(1) or should I(2).

If (1) The answer would be 0.000 (I think this is wrong)

If (2) The answer would be 10.000

So it helps if someone could explain what happens with the carry out in this case.


texts:
An exercise problem stated that :

Which of the following addressing modes permits relocation without any change whatsoever in the code?

Indirect addressing
Indexed addressing
Base register addressing
PC relative addressing

Somewhere it explained as :

Base register addressing : In this mode , content of base register is added to the address part of the instruction to obtain effective address . A Base register is assumed to hold a base address and the address field of the instruction gives a displacement relative to the base address with a base register , the displacement values of the instruction do not have to change only the value of the base register requires updating to reflect the beginning of a new memory of constant .

Hence , option (3) is true .

I found another explanation too , which stated that base addressing mode and relative addressing mode are suitable for relocation at run time .

My question is :

Which addressing modes permits relocation without any change
 whatsoever in the code?

    Can you explain it in a formal way, please?


texts: Joining tables with minimum number of joins

texts:
I am working on a generalized problem where I am given only schema definition of multiple tables that i have.

Now i have to retrieve certain columns by joining multiple tables such that number of joins are minimized.(i will consider where condition in sql clause later)

Example: Suppose i have 3 tables and here is the list of columns that they have.

Table 1:(1,2,3,4,5), Table 2:(5,6,7), Table 3:(5,6,7,8)

Now suppose I have a query in which i want all the columns 1,2,3,4,5,6,7,8.

Now i can join either table 1,table 2 and table 3 OR table 1 and table 3.I would get the required information in both the cases but joining table 1 and table 3 would require only 1 join rather than 2 join in other case.

What i was trying was a greedy algorithm in which first i would consider table that has maximum number of required columns then eliminate the common columns between the query and table(from both query and table) and then consider updated required columns and update tables and so on.But i guess it would be slow.

So is there a generalized algorithm or if anyone can give me any hint in this direction?


texts: Can any left recursive grammar be converted into equivalent right recursive grammar and vice versa

texts:
I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows:

Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB
Convert  "RLG for LR" directly to "FA for LR"
Reverse "FA for LR" to get "FA for L" by

Change starting state to final state
Reverse direction of each transition
Create a new start state with $\epsilon$-transitions to all accepting states

Convert "FA for L" directly to "RLG for L"

Similar approach can be derived for converting "RLG for L" to "LLG of L".

LLGs and RLGs are regular grammars. Though LLGs are left recursive and RLGs are right recursive, when we say right recursive and left recursive, they also include CFGs too (right?). So can we have similar procedures for converting left recursive CFGs to right recursive CFGs and vice versa. Or in fact any left recursive grammar to equivalent right recursive grammar and vice versa, regardless of to which type of Chomsky hierarchy they belong?

(Extra question: Is there any other procedure to covert LLG to RLG and vice versa simpler than the above?)


texts:
Theorem. If and only if SAT instance $\varphi$ is satisfiable, there is a way to negate variables in $\varphi$ and get $\varphi'$ where all clauses have at least one positive literal.

Also we can change word 'negative' by 'positive'.

For example, let we have an instance $(x\lor y\lor\overline z)\land(\overline y\lor\overline t)\land(x\lor z\lor t)\land(\overline y\lor z\lor\overline t)\land(x\lor\overline t)$

We have monotone clauses $(\overline y\lor\overline t)$ and $(x\lor z\lor t)$.

$(\overline y\lor\overline t)$ is shorter, let's modify it.

Negating $y$ gives us a formula that has no negative clauses. So, $x\overline yzt$ is positive assignment.

Let us take unsatisfiable formula $(x\lor y)\land(x\lor\overline y)\land(\overline x\lor \overline z)\land(z\lor t)\land(z\lor\overline t)$.

There is one negative clause $(\overline x\lor \overline z)$.

Flipping $x$ or $z$ will not reduce the amount of negative clauses. In fact both renamings $xy$ and $zt$ do not allow to get rid of negative or positive clauses.

In fact, this can be seen as generalization for renamable Horn SAT.

We can try to implement an algorithm that will try to reduce the amount of these clauses. Is such way to solve SAT is known?


texts: Min Cost Max Flow algorithms for providing multiple solutions

texts:
Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow problems that I'm aware of include :

Cycle cancelling (reff)
Successive shortest path
Relaxation (reff)
Cost scaling (reff)

The above algorithms differ in their approach to solving the problem with some maintaining feasibility and attempting to achieve optimality (Cycle cancelling, Cost scaling) whilst iterating over the flow network and some maintain reduced cost optimality at every step and try to achieve feasibility (Successive Shortest Path, Relaxation).
My question is whether any of the above algorithms or one that I haven't listed, can be altered in order to provide a listing of the k-best flow routings that minimise the overall cost instead of the single optimal routing.


texts: How can I find a language from a given PDA

texts:
I have the following PDA:

And a given solution for his languages ${L}_{\mathrm{End}}(M_2)$ and ${L}_{\mathrm{PDA}}(M_2)$ with $ \mathrm{L}_{\mathrm{End}}\left(\mathrm{M}_{2}\right)=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} x\mid \mathrm{n}, \mathrm{m} \in \mathbb{N}^{+} \wedge x \in\{\mathrm{b}, \mathrm{c}\}^{*} \wedge| x |=\mathrm{m}\right\} $

and

$ \mathrm{L}_{\mathrm{PDA}} = \{a^*\} $

My problem is that I do not understand how to come up with this solution.
If I had a DFA, it would not be a problem to find the language, but here i have to find two, and I have no idea how find them.


texts: How to understand equivalence of indexes of a family of types that are not definitionally equal

texts:
So I've been reading things about HoTT and trying to get solid on the foundations before getting too much further into the book. I am confused by a certain point; maybe I just haven't read far enough yet however. I don't think my question is specific to HoTT but just dependent type theory in general.

Say you have a family of types defined by something like $B : Nat \to Set$. There are two fibers/indexed types defined by $B(x + y)$ and $B(y + x)$. These are definitely not definitionally equivalent but maybe they are extensionally equivalent because $x + y = y + x$. However I thought that perhaps indexes behave definitionally in some cases in which case $B(x + y)$ and $B(y + x)$ might be extensionally distinct.

I tried thinking about the case of $Fin : Nat \to Set$ (the integers less than a certain value). I think that both $Fin (x + y)$ and $Fin (y + x)$ have no inhabitants however because the standard constructors for them have no constructors that unify with $x + y$ or $y + x$. So they both have no inhabitants but what does that mean about their equivalence? This seemed like a bad case to think about to me.

My main question is the following: how does one think about the equivalence between these two types?

My subquestions/confusions are: Do these types have the same inhabitants? Are they extensionally equal? Does having the same inhabitants means that types are extensionally equal?


texts:
In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list.

Now if we have list of $n$ numbers we need $\log n$ bits to distinguish between those number. So number of radix sort passes we make will be $\log n$. Each pass takes $O(n)$ time and hence running time of radix sort is $O(n \log n)$

But it is well known that it is linear time algorithm. Why?


texts: Does an RL agent need to experience a complete episode in order to learn?

texts:
Suppose we have a game where there is no good measure of how "far" the target is (that we could use to nudge the agent towards the goal via the immediate returns).

If the agent gets only -1 reward per time step and experiencing a full episode where it reaches the goal is extremely improbable (it's equivalent to just blind search at this point), can it still learn?


texts: NP-completeness of maximum-sum subtree with quadratic constraint

texts:
Intuitively, given:

a graph
a root node
a reward mapping from node to real number
a cost mapping from node to real number

We want to find the tree that maximizes the reward while keeping a quadratic cost function under some threshold.

Formally, given:

a graph $G=(V, E, w, c)$ where $w: V \rightarrow \mathbb{R}$ and $c: V \rightarrow \mathbb{R}$
threshold $A \in \mathbb{R}$
root node $r \in V$

Find a tree $T=(W, D), W \subseteq V, D \subseteq E$ rooted at $r$ that maximizes

$\sum\limits_{v \in W} w(v)$

s.t. $ \sum\limits_{v \in W} (c(v) - \frac{1}{|W|} \sum\limits_{v \in W} c(v))^2 \le A$

Is this maximum-sum subtree with quadratic constraint NP-complete? Why?

PS:

A related problem is finding length-constrained maximum-sum subtree, which is NP-hard for general graph. Edged have length cost and vertices have reward value. The goal is to find a subtree that maximizes sum of vertex rewards while sum of edge lengths are below some given bound.

This can be seen as maximum-sum subtree with linear constraint, instead of a quadratic one.


texts: Companion volume to Concurrency verification of Willem-Paul de Roever

texts:
At the moment I am working hard with the book "Concurrency Verification
Introduction to Compositional and Non-compositional Methods" written by Willem-Paul de Roever et al. In the introduction section a companion volume is mentioned and even its structure and the questions answered in the companion are described.
The problem is: No matter how I hard I search for this companion volume I can not find it. It simply does not seem to exist.
Has anyone ever wondered too what volume this might be and also an answer?
Thank you
Marvin


texts: Compute minimum hamming distance of a code

texts:
How do you find the minimum hamming distance of a code?
A naive way is computing the distance of each pair of codewords in our code.

It becomes hard when the code is sufficiently large. Is there a formula for minimum hamming distance?


texts:
I have to write an algorithm that solves below problem statement -

There is a project requirement which has list of titles:-
"JobTitles" : [
    "Developer",
    "Programmer",
    "Java Developer",
    "Java Software Engineer",
    "Java Software Developer",
    "Application Architect",
]
There is a list of applicants who have titles like -

Need to find out which applicant is close to the project requirement based on scoring system.

Current logic that I have implemented is(pseudocode)-

If project_title.eqauls(applicant.split(,).forEach(title))
      applicant.score +=4

If project_title.contains(applicant.split(,).forEach(title))
       applicant.score +=2

Is there any other method to implement scoring system to find closest possible match based on the keywords of requirement and applicant job title?

Thank you!


texts: To prove or disprove that language is regular

texts: Suppose the language L = {w | w is an integer whose sum of digits is a multiple of 2}. I strongly feel like this is non-regular language, but how should I choose a string to apply the pumping lemma?


texts: What kind of recurrence relations has p < 0?

texts:
By the master method,
$T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$
where $p$ is real.

I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p<0$?


texts: cardinality of recursive/r.e/not r.e languages?

texts:
I was just looking into properties of languages and wondered about the cardinality of them

are all recursive languages countable or can they also be uncountable
(can u have a recursive language which is uncountable?)
can r.e languages be countable and uncountable?
(can u have a r.e but not recursive language which is uncountable?)
are all non r.e languages uncountable?
(can u have a non r.e language which is countable?)

an explanation would be nice but i am not necessarily looking for a proof. thanks!


texts: What is the change in time complexity due to substitution of variables?

texts:
This is a question I have after listening to a lecture.

def gosperize(curve):
    scaled_curve = scale(sqrt(2)/2)(curve)
    left_curve = rotate(pi/4)(scaled_curve)
    right_curve = translate(0.5,0.5)(rotate(-pi/4)(scaled_curve))

    return connect_rigidly(left_curve, right_curve)

def gosper_curve(level):
    return repeated(gosperize, level)(curve)

def identity(x):
    return x

def repeated(f, n):
    if (n == 0):
       return identity
    return composed(f, repeated(f, n-1))

def rotate(angle):
    def transform(curve):
        def rotated_curve(t):
            pt = curve(t)
            x, y = x_of(pt), y_of(pt)
            cos_a, sin_a = cos(angle), sin(angle)

            return make_point(cos_a*x - sin_a*y, sin_a*x + cos_a*y)
        return rotated_curve
    return transform

def joe_rotate(angle):
    def transform(curve):
        def rotated_curve(t):
            x, y = x_of(curve(t)), y_of(curve(t))
            cos_a, sin_a = cos(angle), sin(angle)

            return make_point(cos_a*x - sin_a*y, sin_a*x + cos_a*y)
        return rotated_curve
    return transform

I think this is all the code that is needed to contextualise my question properly. The lecture was on an abstraction on curves. It was mentioned that for the function gosper_curve,if joe_rotate is used instead of rotate, gosper_curve will turn into a process whose time is linear in the level into one which is exponential in the level. I do not understand how assigning pt=curve(t) could change the time complexity of the function. I would appreciate any help on my order of growth fundamentals.


texts: How to see if P is decidable semi-decidable, undecidable?

texts:
I've been trying to figure out a practice exam question, about if a given $P$.

$P$ is the characteristics of recursive enumerable set given as:

$$P(A) = \begin{cases} ⊤ &if &|A| ≤ 100 \\
                       ⊥ & else.
                       \end{cases}$$

Now I know string properties state:

Decidable if $ \{ x$   $|$$ $ $ P(x) \} $ is recursive
Semi-decidable if $ \{ x$   $|$$ $ $ P(x) \} $ is recursive enumerable
Undecidable if $ \{ x$   $|$$ $ $ P(x) \} $ is not recursive

How do I apply this and triviality, and monotonic properties to $P$ to see if it's undecidable. Or if you have another way, please share!

My first thought was that it's semi-decidable because it's r.e. but how do I prove it's not decidable? From the given statement, how can I tell if it's using recursion or not?


texts: Does a simple calculator require an operating system?

texts:
I don't mean a TI-84 type calculator, and I also do not mean a simple calculator app on your phone.

Does a basic scientific calculator require an operating system?


texts: Proving $\log (N)$ mistake bound is "tight" for a learner when learning thresholds

texts:
I'm studying the online learning model and the Halving algorithm.

We've seen the threshold problem:

The domain is $X=\left\{ 1,2,...,N-1\right\} $, the label set is  $Y=\{-1,1\}$ and the hypotheses class is $H=\left\{ h_{\theta}(x)=sign(x-\theta):\theta\in\left\{ \frac{1}{2},1+\frac{1}{2},...,(N-1)+\frac{1}{2}\right\} \right\} $

I'll denote the number of mistakes the learner $A$ does on the environment $E$ by $M(A,E) = \left|\left\{ i:\hat{y_{i}}=A_{\mbox{pred}}(x_{i})\neq y_{i}\right\} \right|$ where $E=\left\{ (x_{i},y_{i})\right\} _{i=1}^{n}$

For any environment $E$, the mistake bound for Halving  is  $M$(Halving,$E$)$\leq\left\lfloor \log N\right\rfloor $

Now I must prove that this bound is "tight", i.e., for any learning algorithm $A$ there exists a realizable environment $E$ such that $M(A,E)\geq \left\lfloor \log N\right\rfloor$

My try - I came to the conclusion that finding the correct $h^{*} \in H$ is pretty similar in this case to finding a value in a sorted array.
Since we'll need at least $\left\lfloor \log N\right\rfloor $ comparisons, an algorithm $A$ which can find $h^{*}$ and make less than $\left\lfloor \log N\right\rfloor$  mistakes "can find a value in a sorted array in less than $\left\lfloor \log N\right\rfloor$ comparisons for any given array, which is a contradiction."

The sentence in quotes is my intuition, but I'm having trouble proving it formally.

Is this the right way to go?

Many thanks.


texts: Can Non-Linear Grammars generate Regular Language?

texts:
I stumbled upon the following non-linear grammar

$$S \to AB$$
$$A\to aaA\mid \epsilon$$
$$B \to Bb\mid \epsilon$$

and the language generated by this non-linear grammar is {a^2nb^m : n ≥ 0, m ≥ 0} which looks to be regular. I was successful in drawing a DFA for this language.

Thus far, I have studied that Left Linear and Right Linear grammars classify as Regular Grammar and generate Regular Languages. I know there are certain Linear Grammars that can be converted to corresponding Left Linear or Right Linear equivalent forms. Similarly, I am guessing, we can write a Right or Left Linear grammar in a Non-Linear fashion and get the same regular language which is what is happening here.

Thus, what I understand is that Left Linear or Right Linear Grammars always generate Regular languages but a Non-Linear grammar may or may not generate a regular language. Is that the correct way to put it? Are there any gaps in my understanding?

Wkipedia states "an example of a linear, non-regular language is {a^nb^n}". Can I then say that above language is an example of non-linear, regular language? That sounds and probably is wrong.


texts: Paxos: Responding to Reordered Prepare Requests

texts:
In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a prepare request with:

  A promise never to again accept a proposal numbered less than n, and the proposal with the highest number less than n that it has accepted.

Therefore:

  [An acceptor] can receive two kinds of requests from proposers: prepare requests and accept requests. An acceptor can ignore any request without compromising safety. So, we need to say only when it is allowed to respond to a request. It can always respond to a prepare request. It can respond to an accept request, accepting the proposal, iff it has not promised not to.

Next, Lamport offers this optimization:

  Suppose an acceptor receives a prepare request numbered $n$, but it has already responded to a prepare request numbered greater than $n$, thereby promising not to accept any new proposal numbered $n$. There is then no reason for the acceptor to respond to the new prepare request, since it will not accept the proposal numbered n that the proposer wants to issue. So we have the acceptor ignore such a prepare request.

Suppose an acceptor receives a prepare request numbered $n$, but it has responded to a prepare request numbered $n + 1$ and accepted the proposed value (the prepare request for proposal $n$ was delayed arbitrarily by the network). The acceptor has thus promised never to accept a proposal numbered less than $n + 1$. However, we know that:

  an acceptor can always respond to a prepare request.

Therefore, the acceptor can respond with a promise never to accept a proposal numbered less than $n$ since it has already made a promise never to accept a proposal numbered less than $n + 1$, however it cannot respond to the prepare request for proposal number $n$ with the proposal $n + 1$ because it must respond with:

  The proposal with the highest number less than $n$ that it has accepted.

Since $n + 1 > n$ it can respond with no proposal. This would enable both the proposer of proposal number $n$ to choose a value, and the proposer of proposal number $n + 1$ to choose a value. However, even in the case where the proposer of $n$ sent their accept request before the proposer of $n + 1$, the accept request would be ignored because a majority has promised not to accept a proposal numbered less than $n + 1$. Thus, safety is still guaranteed. Is this correct?