# Question
Title: Formal grammar with constraints on the number of each symbol
I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in the language consists of at most 5 $a$, 3 $b$ and 2 $c$ characters. So $ababbc$ is valid, $ccbbbaaaaa$ is valid, but $abcabcabc$ is not. I'm struggling to come up with a grammar that satisfies such constraints without resorting to enumerating each possibility. Is it possible to have a concise set of rules that encode these constraints?

# Answer
No.

Since the permutation language is finite, you can produce a grammar by enumerating the individual sentences which comprise the language. Some simplifications are possible, for example by finding common prefixes and/or suffixes. But there is no grammar which is significantly smaller than the language itself (for some definition of "significantly").

This is not really as dramatic a conclusion as it sounds. Most finite languages lack compact grammars; grammars achieve concision when they can use recursive constructs which represent infinite languages.

In fact, in an interesting paper cited in the answer to this question on https://cstheory.stackexchange.com/, there's a proof that the no regular expression for the language $P\_n$ consisting of the permutations of $\\{1,2,\dots,n\\}$ can be shorter than $2^n$. However, the (infinite) inverse $\overline{P\_n}$ can be described by a regular expression of size $O(n^2)$. (There are lots of other interesting results in that paper.) @yuval-filmus extended that result in Lower Bounds for Context-Free Grammars to a larger set of languages, including the language of permutations of the multiset of $n$ different elements in which each element appears $k$ times.

In the halcyon era of SGML, whose syntax description language included a permutation operator, there was some investigation into how to optimise state machines to recognise such languages. IIRC, the final conclusion was that it can't be done and therefore the permutation operator is not a good idea. In practice, such languages are generally recognised in two phases: first, the input is matched against the infinite language of unrestricted repetitions, and then a second scan (not implemented with a CFG) is done to count repetitions of each element. But that algorithm is not completely sound. First, it assumes that there is a unique decomposition of a string into elements, which is not always the case, although it certainly was the case for SGML. Second, the algorithm greedily processes all successive elements. If the intention of the grammar were to recognise the longest *legal* permutation, leaving open the possibility that (over-)repeated elements be part of a different syntactic construct, then legal inputs will fail because of the greediness.
> 3 votes

# Answer
This language is regular, so you can write a NFA or a regular grammar that accepts this language.

See How to prove a language is regular? for our reference material on this topic.
> 1 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: what is the difference between an adapter and a controller?
1- why do have a USB controller but a display adapter ?

2- I have heard the terms network adapter and network controller being used, is there a differance between those ?

# Answer
> The distinction between the two\[adapter and controller\] is mainly one of packaging. Controllers are chip sets in the device itself or on the system’s main printed circuit board (often called the motherboard). An adapter is a card that plugs into a slot on the motherboard.Regardless, the purpose of each is to transfer information back and forth between the I/O bus and an I/O device.

Ref: Computer Systems: A Programmer's Perspective, 3rd Edition.
> 3 votes

---
Tags: computer-architecture, operating-systems
---


# Question
Title: converting for loop into mathematical notation
I am a bit confused with a problem that I am having.I am trying to do an amoritized analysis and I am able to represent the function that I want to use using code. I coded the function as follows:

```
sum = 1;
for(i = 1;i < n;i++){
    sum = ceil(1.5 * sum);
}

```

The code is suppose to represent $\lceil....\lceil\lceil\lceil1.5 \times 1\rceil\times 1.5\rceil\times1.5\rceil...\times1.5\rceil$ and is suppose to keep going $n$ times. How would I represent this mathematically.

Thanks.

Edit: So I am trying to do an amoritized analysis on an array that grows by a factor of 1.5. So what I am trying to do is mathematically write what the code does.

What the code is suppose to represent is it is doing $\lceil...\lceil\lceil 1.5 \times 1\rceil \times 1.5\rceil...\times1.5\rceil$ The ... is suppose to represent the function multiplying by 1.5 $n$ times.

Also as an example if you post the following into desmos it will give you ceil(...ceil(ceil(1.5 * 1))...) 8 times.

\operatorname{ceil}\left(\operatorname{ceil}\left(\operatorname{ceil}\left(\operatorname{ceil}\left(1\cdot1.5\right)\cdot1.5\right)\cdot1.5\right)\cdot1.5\right)

I want to be able to have the behaviour of what is represented above mathematically so I can use it in an analysis. If anything is unclear again please comment.

# Answer
Is the sequence $(a\_i)\_{i\<n}$, where $a\_0=1$ and $a\_{i+1}=\lceil 1,5\cdot a\_i\rceil$, what you need?
> 1 votes

---
Tags: algorithms, algorithm-analysis, amortized-analysis
---


# Question
Title: How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression?
I'm trying to understand the complexity of the Kruskal algorithm implemented with the Quick-Union by rank and with the path compression.

Now there is a theorem for the last structure above:

> The complexity of any sequence of **m** operations of Makeset, Union and Find, **n** of which are of Makeset, on a Quick Union by rank and path compression is in the worst case equal to $O(m\\,\\, G(n))$. Where $G(n)$ is the inverse of the Ackerman function

And this one is the Kruskal algorithm in pseudocode. Let $G=(V,E)$ be an undirected, connected and weighted graph, where $V$ is the set of vertices and $E$ the set of edges, then the following algorithm returns a Set $A$ that contains the edges of the Minimum Spanning Tree.

```
Kruskal(Graph G) {
    Set A

    For every vertex v in V {
         Makeset(v)
    }

    Order the edges in E in ascending order by weight

    For every edge (u,v) {
        If find(u) != find(v) {
            union(u,v)
            A = A + (u,v)
        }
    }

    Return A
}

```

Let's go back to my problem.
I understand that the second loop is executed at the worst $m$ times (the number of edges). Hence the number of operations of union and find is $m$, while the number of makeset is $n$ (the number of vertices).

The book where I'm studying, after making similar observations says that the complexity of the above operations equals to $O((m+n)\\,\\,G(n))$ and **I don't get why**. Of course, the other complexity to order the edges is $O(m\\,\\, log\\, m)$ so the final one is:
$O(m\\,\\, log\\, m) + O((m+n)\\,\\,G(n))$
But $m\>n-1$ then
$=O(m\\,\\, log\\, m) + O((m)\\,\\,G(n))$
However $m\<n^2 \implies log\\, m \< 2log\\, n \implies log(m)=O(log n)$, so
$=O(m\\,\\, log\\, n) + O((m)\\,\\,G(n))$
$=O(m\\,\\, log\\, n)$

Can you explain to me how to get the $O((m+n)\\,\\,G(n))$ complexity from the algorithm?

# Answer
> 0 votes
You are absolutely right. There is nothing wrong with your reasoning.

The running time of Kruskal's algorithm, when implemented in the way you describe, is $O(m \log m)$, or equivalently, $O(m \log n)$. If the book says its running time is $O((m+n) G(n))$, the book is wrong; that doesn't take into account the time to sort the edges by weight.

If you look at other sources I think you'll find that they correctly report the running time of Kruskal's algorithm.

# Answer
> 0 votes
You get the inverse Ackerman function when you look deeper into the complexity of the find operation. I recommend trying to understand the simpler $O(log^\*n)$ explanation (which is available here) before trying to understand the inverse Ackerman function one.

---
Tags: algorithms, complexity-theory, graphs, minimum-spanning-tree, union-find
---


# Question
Title: Determine if there is a path with alternating edge colours in directed graph
Given directed graph $G = \langle V, E \rangle$, such that some vertices are red, and some vertices are black, and some edges are blue or green, decide for all vertices $v \in V$ if there is path from $v$ to some red vertex with alternating edge colours (no edges of same colour are adjacent in the path, e.g. blue -\> green -\> blue -\> ...).

If $G$ is acyclic, the problem looks simple - just use DFS. But how can one solve it if *there are cycles* in $G$?

# Answer
Let's construct a new graph $G'$.

Every vertex $u$ from $G$ will become a pair of vertexes in $G'$, namely $u\_{blue}$ and $u\_{green}$ (index stands for the color of incoming edge).

Edge $u\_{c\_1}\rightarrow w\_{c\_2}$ in $G'$ exists iff

1. There is an edge $u \rightarrow w$ in $G$ colored $c\_2$
2. $c\_1 \ne c\_2$

Now it's easy to see that every path in $G'$ corresponds to a color-alternating path in $G$ (and the converse is also true), i.e. color-alternating path from $v$ to $u$ in $G$ exists iff there is path from $v\_{c\_1}$ to $u\_{c\_2}$ in $G'$ for some $c\_1, c\_2$.
> 1 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Universal hashing - insert / search / delete
I don't understand the highlighted text below in CLRS 3rd Ed.:

I'm not sure I even understand what the sentence is trying to say. For example:

* What do they mean by "... ***operations*** *containing $\mathcal{O}(m)$ INSERT **operations***"? Which operations contain which?
* If the (total) expected time is $\Theta(n)$ how can any of these operations **contain** other $\mathcal{O}(m)$ operations?

# Answer
> 1 votes
Let me try to explain this with an example. Let us say if m=10 and n=1000. If I have m number of insertions in a table with m slots, it is going to be O(m). Right? But if we have 1000 insertions in a table containing 10 slots, it is not the same math anymore. Since you will have to deal with collisions at a greater frequency. It no more remains linear math. Thus if the n stays small enough that it is in order of O(m), you can have expected Theta n for n inserts. If inserts increase at a number much greater than m, the collisions doesn't let it be linear.

---
Tags: algorithms, data-structures, hashing
---


# Question
Title: Lower bound on number of (different) circuits of given size?
For circuits with $n$ input bits, we know that, for any function $s$, there are at most $O(s(n)^{s(n)}) = O(2^{s(n) \log s(n)})$ circuits with size at most $s(n)$.

Say two circuits $C\_1$ and $C\_2$ are *different* if the function they compute is different, that is, there is an $n$-bit string $x$ such that $C\_1(x) \neq C\_2(x)$. The $O(s(n)^{s(n)})$ bound above is an *upper bound* on the number of circuits of a given size. Is there a known *lower bound* on the number of different circuits with size at most $s(n)$ for different values of $s(n)$ (e.g., $s(n) \in \mathsf{poly}(n)$, $s(n) \in n^{\textsf{polylog}(n)}$, or $s(n) = 2^{n^\varepsilon}$)?

Clearly such a bound must be strictly smaller than the $O(s(n)^{s(n)})$ bound since there are pairs of circuits with different structures (and even different number of gates) and which nevertheless compute the same function (i.e., they are not "different" as defined above)—but how smaller can it be?

# Answer
> 3 votes
Let $1000 \leq s \leq 2^n/n$. Every function on $m$ bits can be computed by a circuit of size $O(2^m/m)$ (I believe that even the optimal constant is known). Choose a value of $m$ such that every function on $m$ bits can be computed by a circuit of size $s$, and furthermore $s = \Omega(2^m/m)$. Since there are $2^{2^m} = s^{\Omega(s)}$ different functions on $m$ bits, we see that your upper bound is quite tight.

---
Tags: circuits
---


# Question
Title: Why does $x^{15}+x^{14}+1$ detect all errors at most 32768 bits apart?
Reference Question from Forouzon Book Computer Network. Find the status of the following generator related to two isolated, single-bit errors. $$x^{15} + x^{14} + 1$$ **Answer** given : This polynomial cannot divide any error of type $x^t + 1$ if t is less than 32,768. This means that a codeword with two isolated errors that are next to each other or up to 32,768 bits apart can be detected by this generator. Can some one please help me why is this true...? Or even how should I have an in general approach to analyze such questions...? (Sorry if this is very silly, but I am unable to get a grasp of how the reason works...!)

# Answer
> 2 votes
Your polynomial is primitive, which means that the order of $x$ modulo your polynomial is exactly $2^{15}-1$. In particular, $x^a \not\equiv 1$ modulo your polynomial for all $1 \leq a \leq 2^{15}-2$, which means that your polynomial doesn't divide $x^a-1$ for this range of $a$.

(This also means that your polynomial should divide $x^{2^{15}-1}-1$, in contrast to what the question claims.)

---
Tags: computer-networks, polynomials, crc
---


# Question
Title: For what data structures is jump search practically useful?
Jump search is a search algorithm for sorted lists which runs in $O(\sqrt n)$ time, but has the advantage of only making backwards steps at the end (and given the ability to make arbitrarily long backwards steps, guarantees only a single backwards step); thus, it may be preferable to binary search if reverse traversal is significantly more expensive than forward traversal.

Now, it's not hard to *contrive* situations in which that is the case--say, a skip-list which is doubly-linked at the lowest level (so that reverse traversal is *possible*) but singly-linked for every skip-link (so reverse traversal isn't *fast*). But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was *not* specifically constructed to be ideal for jump searching?

# Answer
> 2 votes
> But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?

Any context in which data is stored on a physical medium that allows forward jumping quicker than backwards jumping is a candidate. Just think of an ordinary hard drive. Its disk spins in a specific direction, making a forward jump much quicker than a backwards jump. To jump one unit backwards you need the disk to complete (nearly) a full rotation whereas jumping one unit forwards is near-instantaneous. Tape is another example, though here it is mostly the change of direction that is costly rather than backwards jumping specifically. For data stored in RAM, a CPU architecture might be specifically optimized for forward search rather than backward search (in principle, caching and branch prediction might cause differences in the speed of forward and backwards jumping).

---
Tags: data-structures, search-algorithms
---


# Question
Title: how to generate all spanning trees from one spanning tree
If I have one spanning tree from a connected and undirected graph, how can I generate all other spanning trees of this graph by modifying this spanning tree one edge at a time? All intermediates must also be spanning trees of the graph.

# Answer
The solution is greatly presented in Knuth's book at 7.2.1.6 (see page 23)
> 2 votes

---
Tags: graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: Understanding connection between length of codeword and hamming distance in Hamming code
I came across following in Huffman coding:

> Minimum Hamming distance to correct up to s errors is $2s + 1$ because that way the legal codewords are so far apart that even with $s$ changes the original codeword is still closer than any other codeword.

Then I came across following:

> Consider dataword length of $m$ bits, codeword length of $n$ bits. So redundant check bits will be $n-m = r$. Each of the $2^m$ legal messages has $n$ illegal codewords at a distance of $1$ from it. These are formed by systematically inverting each of the $n$ bits in the $n$-bit codeword formed from it. Thus, each of the $2^m$ legal messages requires $n+1$ bit patterns dedicated to it. Since the total number of bit patterns is $2^n$, we must have $(n+1) 2^m ≤ 2^n$.

Using this information, I took $m=4$ and found that to meet above equation, $n \ge 7$. So with $n = 7$, I prepared Huffman code for $m = 4$ as shown in the image ($d$ are data bits, $c$ are check bits):

The code has hamming distance of 3 which confirms with $2(1)+1 = 3$ as required to correct 1 bit errors.

**Q1.** But then, how satisfying $(n+1) 2^m ≤ 2^n$ also ensures hamming distance is 3?

**Q2.** Also what will be equation if I want to correct $k$ bit errors? Will it be $(\binom{n}{k}+1)2^m\leq 2^n$?

# Answer
> 3 votes
The answer to both questions is the sphere-packing bound.

Consider a binary code on $n$ bits with minimum distance $2d+1$ and $M$ codewords. Imagine surrounding each point of the code with a ball of radius $d$, consisting of all points at distance at most $d$ from the point. These balls must be disjoint: if the balls corresponding to $x,y$ contain some point $z$ in common (note that $z$ need not be in the code), then $d(x,y) \leq d(x,z) + d(y,z) \leq 2d$, contradicting the stated minimum distance. Each ball contains $\binom{n}{\leq d} := \sum\_{r=0}^{d} \binom{n}{r}$ points, and so $$ M \times \binom{n}{\leq d} \leq 2^n. $$ This is because there are $M$ disjoint balls, each containing $\binom{n}{\leq d}$ points, while in total there are $2^n$ binary strings of length $n$.

---
Tags: computer-networks, coding-theory, error-correcting-codes, hamming-code, hamming-distance
---


# Question
Title: Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?
I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I thought there could only possibly be one block, since linear probing will go through all addresses sequentially?

# Answer
For single key, there is only one block. But as it grows, it may reach the next cluster, making this cluster much larger:

aaaa.bbbb...

Here aaaa is cluster for "a" key, and bbbb is cluster for "b" key. Once you fill the first "." entry with data, clusters are combined. Now the next item for "a" key will be inserted after bbbb, so find() operation need to search the entire cluster:

aaaaabbbba..

There are techniques such as Robin Hood hashing which keeps all keys sorted by the position of the first entry where they can be stored, so the same data will build the following table:

aaaaaabbbb..
> 1 votes

---
Tags: hash, hash-tables, hashing
---


# Question
Title: Min-coin change problem with limited coins
I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite supply of coins and also where we only have 1 of each coin. I was able to quickly implement the solution for the first scenario using a recursive formula from here but was not able to find a recursive formula for the second case and I instead came up with an iterative solution.

We can just sum every possible combination of coins, check and see if the sum is equal to the target wanted and compare the number of coins used to the current lowest number of coins. I also realized that I can use binary counting to simulate all possible combinations using the bits in the iterator as a coefficient (either 1 or 0) for each coin and then calculate the Hamming Weight to check how many coins was used in the sum.

To visualize an example with 3 coins:

```
C1 C2 C3 | S                        | W
 0  0  0 | 0 * C1 + 0 * C2 + 0 * C3 | 0
 0  0  1 | 0 * C1 + 0 * C2 + 1 * C3 | 1
 0  1  0 | 0 * C1 + 1 * C2 + 0 * C3 | 1
 0  1  1 | 0 * C1 + 1 * C2 + 1 * C3 | 2
 1  0  0 | 1 * C1 + 0 * C2 + 0 * C3 | 1
 1  0  1 | 1 * C1 + 0 * C2 + 1 * C3 | 2
 1  1  0 | 1 * C1 + 1 * C2 + 0 * C3 | 2
 1  1  1 | 1 * C1 + 1 * C2 + 1 * C3 | 3

```

Obviously we can omit the case where all the coefficients are 0, but for completeness (when target = 0) and simplicity I've kept it in the solution.

My implementation in Python is:

```
import math

def least_coins(coins, target):
    least = math.inf

    # loop all 2^n possible sums of coins
    for i in range(2 ** len(coins)):
        sum = 0

        # add all the coins multiplied by their coefficient in this iteration
        for j in range(len(coins)):
            # get the j-th bit in i
            coefficient = i >> j & 1
            sum += coefficient * coins[j]

        if sum == target:
            count = 0
            # calculate the Hamming Weight of i to determine the number of coins used
            while i:
                i &= i - 1
                count += 1
            least = min(least, count)

    return least

coins = [3, 1, 1, 3, 2, 4]
target = 10
print(least_coins(coins, target))
>>> 3
# 3 + 3 + 4 = 10

```

As you can see the coins are not necessarily unique, but can only be used once. How can I turn this into a recursive formula (if possible and for the reason of possibly being able to optimize it using dynamic programming) or even introduce coefficients other than 0 and 1 so the problem can be more general where we have a certain amount of each coin?

# Answer
Let $N(t,S)$ be the least number of values from $S$ which sum to $t$. The basic recurrence is $$ N(t, S \cup \\{s\\}) = \min(N(t,S),N(t-s,S)+1). $$ I'll let you work out the details.

---

This recurrence leads to an efficient algorithm only if we are allowed to run in time polynomial in $t$.

If we think of $t$ encoded in binary, then this algorithm runs in exponential time.

Indeed, the very related SUBSET-SUM problem is NP-complete.
> 2 votes

---
Tags: dynamic-programming, recursion, python, coin-change
---


# Question
Title: Why doesn't A* give the optimal path for navigating from A to R in this state space?
Well, I have heard that the A\* algorithm is optimal and complete. However, when trying to navigate from A to R using A\*, it outputs the path, A --\> E --\> R, although there is a shorter path, A --\> M --\> R. My question is, is that possible for A\* to be not optimal sometimes? if not, what am I doing wrong here? Any helpful advice is highly appreciated.

The question: In the following diagram, A is the start node and R is the goal node. Arcs are labeled with the value of the cost function; the number gives the cost of traversing the arc. Heuristic function value for each node is given within brackets. Using A\*, find the route from A to R.

This is what I tried. But what I'm getting is not the optimal path.

# Answer
For A\* to be optimal, the heuristic needs to be admissible (and this example shows why). This heuristic is not admissible because the heuristic value at M is 40, while the shortest path from M to R has length 30.
> 2 votes

---
Tags: algorithms, a-star-search
---


# Question
Title: What if P implies Q is false when both P and Q are false?
This is actually a problem that our professor gave us, and I'm clueless of how to answer this. I browsed through various sources, but none were helpful regarding this question.

The question is,

> In the definition of semantics of logic, P implies Q is defined as true under the assignment of both P and Q are false. Although this is rather unusual at a glance, explain what would be the issue with logic, if the definition is differently.

Any helpful answer is highly appreciated.

# Answer
This question is a soft question IMO, it assumes there's common ground about what "should be true" independent of definitions but it doesn't clarify what those assumptions are. If I were to break it down, I'd say it's looking for a particular bit of reasoning (e.g. a proof or an inference rule) to hold and then asking you to show that that reasoning would be invalid if we defined the semantics of implication differently. In essence it's asking if there exists a proof that, under this new model, would be invalid.

Consider $\neg (Q \vee \neg Q) \to \neg (Q \vee \neg Q)$ which is provable, and should be valid in all models (no matter what we assign to $Q$ that is). As a general rule of reasoning it should always hold that $P \to P$ no matter what. I posit this is sufficiently fundamental common ground of "what should be true". So if we find this reasoning invalid, we have our soft contradiction. We can construct instances of $P$ for which $P$ is certainly false as shown above. So despite the very reasonable proof of $\neg (Q \vee \neg Q) \to \neg (Q \vee \neg Q)$ that would actually be false under the model...in fact it's negation would be valid in the model!
> 1 votes

# Answer
In classical propositional logic, we define $P \rightarrow Q$ to be $\neg P \vee Q$. But if we redefined the semantics of implication as suggested above, this would no longer hold.
> 0 votes

---
Tags: propositional-logic
---


# Question
Title: What are the limitations of symbolic model checking?
What are the limitations of the Symbolic Model Checking?

As far as I know, "state-space explosion" can still happen by this technique but it can explore much larger state space.

So, is the Symbolic Model Checking always better than the conventional model checking? If not, when to apply which one?

By the conventional model checking I mean: Clarke Jr, Edmund M., et al. Model checking. MIT press.

And by Symbolic model checking I mean: McMillan, Kenneth L. "Symbolic model checking." Symbolic Model Checking. Springer, Boston, MA, 1993. 25-60.

# Answer
> 1 votes
The primary limitation is that it can be more complicated to use.

# Answer
> 1 votes
* Limitation due to constraint solvers: The symbolic states are described by constraints. To validate a property on these states a constraint solver is used. Of course all limitations of these solvers apply. For example the non-linear arithmetic of the real numbers is undecidable in general. And the development of these solvers is extremely difficult and a lot is still left to be improved.
* Limitation due to the full directed graph: Symbolic model checking is still practically usable only on simpler programs. Even in the symbolic case a very large transition system is generated for a complexer program (e.g. a web browser) and there are too many symbolic states for the model checking algorithm to be computed. The algorithm demands to really check them all.

So for a concrete constraint solver like Z3 you can probably construct a pathologic case from these limitations which is solved slower or not at all symbolically, while the simple algorithm might succeed. But it is not possible to prove such a case in general.

---
Tags: model-checking
---


# Question
Title: Why table-driven LL (1) parser does not work with division and subtraction?
Everywhere, one grammar is used as an example table-driven LL(1) parser.

### Grammar

```
S -> E | (epsilon)
E -> TE'
E' -> +TE' | (epsilon)
T -> FT'
T' -> *FT' | (epsilon)
F -> NUM | (E)

```

With this grammar you can only add and multiply. I wanted a little more so added subtraction and division operations.

### my Grammar

```
S -> E | (epsilon)
E -> TE'
E' -> +TE' | -TE' | (epsilon)
T -> FT'
T' -> *FT' | /FT' | (epsilon)
F -> NUM | (E)

```

### Parse table

```
|-------------------------------------------------------------------------------------|
|     |   NUM   |    +    |    -    |    *    |    /    |    (    |    )    |    $    |
|-------------------------------------------------------------------------------------|
|  S  | S->E    |         |         |         |         | S->E    |         | S->e    |
|-------------------------------------------------------------------------------------|
|  E  | E->TE'  |         |         |         |         | E->TE'  |         |         |
|-------------------------------------------------------------------------------------|
|  E' |         | E'->+TE'| E'->-TE'|         |         |         | E'->e   | E'->e   |
|-------------------------------------------------------------------------------------|
|  T  | T->FT'  |         |         |         |         | T->FT'  |         |         |
|-------------------------------------------------------------------------------------|
|  T' |         | T'->e   | T'->e   | T'->*FT'| T'->/FT'|         | T'->e   | T'->e   |
|-------------------------------------------------------------------------------------|
|  F  | F->NUM  |         |         |         |         | F->(E)  |         |         |
|-------------------------------------------------------------------------------------|

```

But I have a problem if used this grammar to build a parse tree the string 6\*3/2, it turns out that the first operation is division and then the multiplication operation. I do not know why this is happening. Maybe this is because I have the wrong grammar or I'm doing something wrong. Help me.

# Answer
If you naively generate a parse tree from

$$\begin{align}T\to& FT'\\ T'\to& \*FT' \\ \mid&\\; /FT' \\ \mid&\\; \epsilon\\ \end{align}$$

then you're going to end up with something like this:

```
         T
        / \
       /   \
      /     \
     F       T'
     |      /|\
     6     / | \
          /  |  \
         *   F   T'
             |  /|\
             3 / | \
              /  |  \
             ÷   F   T'
                 |   |
                 2   ε

```

What you really want is this:

```
         T
        /|\
       / | \
      /  |  \
     T   ÷   F
    /|\      |
   / | \     2
  /  |  \
 T   *   F
 |       |
 F       3
 |
 2

```

But that belongs to a different, left-recursive grammar:

$$\begin{align}T\to& T * F\\ \mid&\\; T / F\\ \mid&\\; F \end{align}$$

To use the second grammar, you'd need to use a different parsing technique (not the end of the world :-). To get the second parse tree, you need to do a little surgery while constructing it (or in a post-parse tree-walk, but that seems like overkill).

Because LL grammars cannot deal with left-recursive grammars, they cannot directly represent left-associative operators (which is most operators). Without left-recursion, you only have one way to represent a repetition, which means you have to use the same style to represent both left-associative and right-associative operators. That's not an issue in practice -- you certainly know the associativity of all operators in your language -- but you might find it annoying that you need to annotate the parser in order to get the right parse. If you use a bottom-up parsing technique, this annoyance vanishes.
> 0 votes

---
Tags: parsers
---


title: Restriction of SAT to CNF

text:
# Question
Title: Restriction of SAT to CNF
I have spent a lot of time understanding these two issues. If you can help me, please.

1. Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in polynomial time.
2. Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most three times is NP-complete by showing $SAT \leqslant\_p SAT\_3 $ (hint: find a way to create “clones” of each variable with different names.)

Thanks.

# Answer
1. You can apply Davis-Putnam procedure and note that with the given restriction applying resolution rule will not be increasing formula size exponentially (in fact, it will be decreasing it). Thus, every iteration of procedure will have polynomial time complexity.
2. Read about Tseytin transformation and try to exploit the same idea. You can replace variable $x$ with $y$ and add $x \leftrightarrow y$ to the formula. With a proper replacement strategy you will be able to obtain an equisatisfiable formula in which every variable occurs at most three times: one in the original formula, one as the left part of equivalence, one as the right one.
> 0 votes

---
Tags: np-complete, polynomial-time-reductions
---


# Question
Title: Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence of $y$. Possible to do better than $O(n^2)$?
Consider the following algorithmic problem: Given a list of strings $L = \[s\_1, s\_2, \dots, s\_n\]$, we want to know all pairs $(x,y)$ where $x$ is a subsequence of $y$. We can assume all strings are of length at maximum $m$, where $m \<\< n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| \<\< n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a subsequence of $y$ is much smaller than $n$.

A trivial algorithm would be this:

```
1. foreach x in L:
2.   foreach y in L:
3.      if x is subsequence of y:
4.         OUTPUT x,y

```

However, this has complexity $O(n^2 \cdot m)$ \- I am curious to know whether there is a faster algorithm (Faster given that the number of pairs $(x,y)$ is much smaller than $n$, so for example an algorithm with complexity depending on the number of output pairs).

Note that this question is a follow up to this question, which is about the same problem but for substrings (not subsequences). There, the Aho-Corasick algorithm solved my problem perfectly - is there maybe somethign like this but for subsequences?

# Answer
> 4 votes
No, it is not possible to do better unless the Strong Exponential Time Hypothesis (SETH) fails. If we could solve this problem substantially faster than $O(n^2)$ we would immediately obtain a much faster algorithm for solving the NP-complete problem Satisfiability. This is true even for $m$ slightly more than $\log(n)$ and the case in which we want to decide whether such a pair $(x,y)$ exists at all.

See, e.g., these lecture notes under section 3 "Tight Lower Bounds for Orthogonal Vectors". The proof is analogous to the proof of Theorem 2 in these lecture notes.

First, we consider the more general problem of given two sets of strings $X,Y$, finding whether some string in $X$ is a subsequence of a string in $Y$.

Given a SAT formula, we split its $n$ variables into two equal sets of $n/2$ variables. In $\Sigma$ we take a character corresponding to every clause. In $X$ we add a string for every possible assignment to the first half of the variables, with a character corresponding to every clause *not satisfied* by those variables. Meanwhile, in $Y$, we add a string for every assignment to the second half of the variables, with a character for every clause that is satisfied by those variables. Clearly, the formula is satisfiable if and only if some string in $X$ is a subsequence of some string in $Y$.

If this problem can be solved substantially faster than $O(n^2)$, then this gives a substantially faster algorithm for Satisfiability than $2^n$. Suppose the problem could be solved in $O(n^{1.99})$ time, then Satisfiability could be solved in $(2^{n/2})^{1.99}=O(2^{0.996n})$ which contradicts SETH.

In your problem, there is only a single set of strings, all of which may be a subsequence of each other. This is however not a problem, as we can simply modify the strings in our instance such that no string $Y$ is a subsequence of any other string (for instance by padding all strings in $Y$ to have the same length), and similarly padding every string in $X$ to the same length as other strings in $X$ (but substantially shorter than strings in $Y$).

This can probably also be done with a constant-size (likely even binary) alphabet but this requires more clever encoding.

---
Tags: algorithms, strings, subsequences
---


title: Array segmenting algorithm

text:
# Question
Title: Array segmenting algorithm
I have a sorted array of integers \[x, ..., n, ..., y\] so that
x \> 0
n - x = random positive integer

The array might look something like this:
\[1, 2, 3, 15, 16, 17, 120, 121, 122, 123, 124, 125, 126, 127, 210, 211, 212, 213, 214, 215\]

I want to divide this array into segments so that,
1) The difference between last and first element of a segment \< 125
2) The number of segments is equal to k (predefined positive integer)
3) Sum of differences between first and last element of all segments is minimal

The end result should be a list of segments with their start and end values.
The minimum size of a segment is 1.

Suppose k = 2, then the given example array could be divided into two such segments:
Option 1) \[(1, 125), (126, 215)\]
Option 2) \[(1, 17), (120, 215)\]
Both satisfy requirements 1 and 2.

Sum of differences between first and last element of all segments:
Option 1) (125-1) + (215 - 126) = 213
Option 2) (17 - 1) + (215 - 120) = 111
Therefore option 2 is the preferred solution.

Python is the used language.

Any suggestions on how to approach this problem are welcome.

# Answer
From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $\[a\_1, \dots, a\_n\]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $\[a\_1, \dots, a\_i\]$ into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

* $\delta(0,j)=0$ for any $j \ge 0$;
* $\delta(i,0)=+\infty$ for $i\>0$; and
* $\delta(i,j) = \min\_{\substack{h = 1, \dots, i \\ a\_i - a\_h \< 125}} \big\\{ \delta(h-1, j-1) + a\_i - a\_h \big\\}$, for $i,j\>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$\- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

```
Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1 (representing +infinity);

for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>=125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];

return delta[n][k];

```
> 2 votes

---
Tags: algorithms, optimization, arrays, python
---


# Question
Title: Does the language defined in the details in NP-C or P?
It's known that: $$ \textrm{CLIQUE} = \\{(G,k): \mbox{G has a clique of size } k\\} $$ is $\textrm{NP-C}$, but what if every vertex has 2 neighbours (as defined in $\textrm{2d-CLIQUE}$)? $$ \textrm{2d-CLIQUE} = \\{(G,k): \mbox{every vertex in G has exactly $2$ neighbours and $G$ has a clique of size } k\\}. $$

# Answer
Assuming that every vertex of $G$ has degree $2$, no clique of $G$ can have more than $3$ vertices. Then $\textrm{2d-CLIQUE}$ is trivially in $\textrm{P}$ and, if $\textrm{P} \neq \textrm{NP}$, it cannot be $\textrm{NP}$-complete.

Under the above assumption (which is trivial to check), $(G,k) \in \textrm{2d-CLIQUE}$ iff one of the following conditions holds:

* $k=0$, or
* $k \in \\{1,2\\}$ and $G$ is not empty, or
* $k = 3$ and $G$ has a triangle, which can be checked in $O(n)$ time.
> 2 votes

---
Tags: complexity-theory, time-complexity, np-complete, polynomial-time
---


title: to bail out vs to back out

text:
# Question
Title: to bail out vs to back out
In a CS context, I have often come across the expression *to back out* meaning to say that a function is returned from before performing its actual task, as in this imaginary code comment:

```
double divide(double dividend, double divisor) {
  if (divisor == 0) {
    return 0; //divisor is zero => back out early
  }
  return (dividend / divisor);
}

```

Now I recently came across the expression *to bail out* in just the very same context. I know that *to bail somebody out* generally means *to provide funds to get someone out of a difficult financial situation*, so I was wondering if the writer confused *to back out* and *to bail out* or if *to bail out* really has this meaning, too.

Has any one ever heard or read a native speaker of English say or write *to bail out of a function*? Or, if you're a native speaker, would you say *to bail out* is also correct here?

# Answer
> 1 votes
I understand "to bail out" as to give up permanently; "to back out" is to give up some track, possibly to try something else.

---
Tags: terminology
---


# Question
Title: How to best calculate the best possible path with weights
Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output the path taken, as well as total coins taken. You may only travel in the direction of the arrows. We are allowed to take the same path twice. The solution for the situation in the figure below is the path 1 - 4 - 3 - 2 - 1 - 5 - 7 - 9 - 10 - 8 - 12, with a total of 7 coins. I think this should be possible in linear time. My idea so far is to start at the last node and go back, saving the "best attainable score" for each node. However, this implementation runs into issues when there are cycles in the graph. Is there a better way of doing this?

edit: Assuming *n* nodes, there will never be more than *10n* connections total.

# Answer
> 1 votes
Build the metagraph of strongly connected components. Then execute your idea on the metagraph. Note that once you enter a strongly connected component through any in-edge, you can collect all coins within it and leave through any out-edge out of that component.

---
Tags: algorithms, graphs, weighted-graphs, program-optimization
---


title: show that this decidable set $C$ exists

text:
# Question
Title: show that this decidable set $C$ exists
I came across this problem which says that given disjoint sets $A$ and $B$ s.t $\bar{A}$ and $\bar{B}$ are both computably enumerable (c.e.), there exists a decidable set $C$ s.t. $A \subseteq C$ and $C \cap B = \emptyset$.

I think one way to construct $C$ is to show that $\bar{A}-\bar{B}$ is c.e., but is the set difference $\bar{A}-\bar{B}$ for this particular case c.e.?

# Answer
No, it is not necessarily recursively enumerable. There are languages that are recursively enumerable but not recursive. Thus, their complement is not recursively enumerable. From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).
> 3 votes

---
Tags: turing-machines, computability, undecidability
---


# Question
Title: Overlapping between two intervals: reasoning / algorithm to find the set of disjoint and overlapping intervals
Consider the positive integers **{1, 2, 3, 4, ...}** and the corresponding Integer Number Line.

Suppose we have four integer numbers, A, B, C and D.

For example:

\_________________**A\___________________________B**\__________________ \___________________________**C\__________D**\_________________________

or

\_________________**A\___________________________B**\__________________ \___________________________**C\____________________________D**\_______

Consider the notation AB as the set of all consecutive numbers A, ...., B, and the interval CD as the set of all consecutive numbers C, ..., D.

I would like to know a simple yet abstract and generalizaed resoning (mathematical demonstration would be really apreciated) that we can apply if we want to find all intervals consisting of the "disjoint" numbers and the "overlapping" numbers between both set of numbers, AB and CD.

**Example 1:** If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7}, we have the following subsets for each set AB and CD:

* for AB: {2, 3}, {4, 5, 6, 7} and {8, 9}
* for CD: {4, 5, 6, 7}

**Example 2:** If AB = {2, 3, 4, 5, 6, 7, 8, 9} and CD = {4, 5, 6, 7, 8, 9, 10, 11, 12}, we have the following subsets for each set AB and CD:

* for AB: {2, 3}, {4, 5, 6, 7, 8, 9}
* for CD: {4, 5, 6, 7, 8, 9} and {10, 11, 12}

But, which one would be a great and yet simple reasoning behind disjoint and overlapping sets of numbers between two given set of integer numbers?

Thanks very much for any clue!!

# Answer
> 0 votes
For two integers $A$ and $B$ where $A\le B$, let $\[A,B)$ denote the half-closed half-open interval that consists of the numbers $A, A+1, \cdots, B-1$. In particular, if $A\<B$, then there are $B-A$ numbers in $\[A,B)$. If $A=B$, then there is no numbers in $\[A,B)$. For example,

* $\[0,1)$ means the number 0.
* Both $\[0,0)$ and $\[3, 3)$ mean no numbers.
* $\[5,11)$ means the numbers $5,6,7,8,9,10.$
* To denote the numbers $-2, -1, 0, 1, 2$, we can use $\[-2, 3)$.

---

**A nice property of half-closed half-open interval:** If $L\le M \le R$, then $\[L,R) = \[L,M) \sqcup \[M,R)$.

**Proof:** I am afraid it is obvious by definition. Done.

---

Suppose we are given $\[A, B)$ and $\[C, D)$, where $A\lt B$ and $C\lt D$. Then $\[A,B)$ overlaps $\[C,D)$ if and only $\max(A,C)\lt \min(B,D)$.

**Proof:**

"$\Rightarrow$": Let $n$ be a number in both $\[A,B)$ and $\[C,D)$, i.e., $A\le n\lt B$ and $C\le n \lt D$. Then $\max(A,C)\le n\lt \min(B,D)$.

"$\Leftarrow$": $A\le \max(A,C)\lt \min(B,D)\le B$, i.e., $\max(A,C)\in \[A,B)$. Similarly, $\max(A,C)\in \[C,D)$. So $\[A,B)$ overlaps $\[C,D)$.

Done.

---

Suppose $\[A,C)$ and $\[B,D)$ overlap. Then we have the following set decompositions.

* $\[A,B) = \[A, \max(A,C))\sqcup\[\max(A,C), \min(B,D)\]\sqcup\[\min(B,D), B)$
* $\[C,D) = \[C, \max(A,C))\sqcup\[\max(A,C), \min(B,D)\]\sqcup\[\min(B,D), D)$

**Proof:**

We have $A\le \max(A,C) \le \min(B,D)\le B$. So,

$$\begin{align} \[A,B) &= \[A, \max(A,C))\sqcup\[\max(A,C),B)\\ &= \[A, \max(A,C))\sqcup\[\max(A,C), \min(B,D)\]\sqcup\[\min(B,D), B). \end{align}$$

---

**Example 1:** If $I = \\{2, 3, 4, 5, 6, 7, 8, 9\\}$ and $J = \\{4, 5, 6, 7\\}$, then $I=\[2,10)$ and $J=\[4,8)$. We have the following set decompositions.

* $\[2,10) = \[2, 4)\sqcup \[4, 8) \sqcup \[8,10)$.
* $\[4,8) = \[4, 4)\sqcup \[4, 8) \sqcup \[8,8) = \[4,8)$.

**Example 2:** If $I = {2, 3, 4, 5, 6, 7, 8, 9}$ and $J = {4, 5, 6, 7, 8, 9, 10, 11, 12}$, then $I=\[2,10)$ and $J=\[4,13)$. We have the following set decompositions.

* $\[2,10) = \[2, 4)\sqcup \[4, 10) \sqcup \[10,10)= \[2, 4)\sqcup \[4, 10)$.
* $\[4,13) = \[4, 4)\sqcup \[4, 10) \sqcup \[10,13)= \[4, 10) \sqcup \[10,13)$.

The above examples should indicate clearly enough the algorithm that decomposes two overlapping intervals into disjoint intervals.

---
Tags: algorithms, sets, integers
---


# Question
Title: Why is the satisfiability of ESO formulas not equal to the satisfiability of FO formulas?
Existential second-order logic (ESO) formulas have the form $$\Phi = \exists R\_1 ... \exists R\_k. \phi$$ where $R\_1...R\_k$ are relation symbols and $\phi$ is a FO formula, which can use the relation symbols $R\_1...R\_K$ as well as other relation symbols. My claim is that

> *$\Phi$ is satisfiable if and only if $\phi$ is satisfiable.*

Indeed, satisfiability of a FO formula means finding a universe and an interpretation of all relation symbols. Therefore, we have an implicit quantification $\exists R\_1 ... \exists R\_k$ in front of the FO formula $\phi$, when considering satisfiability. (For validity, the claim does *not* hold.)

But the claim must be wrong since people study satisfiability of ESO separately from that of FO. What do I miss?

# Answer
> 0 votes
You're right: an ESO sentence is satisfiable iff its first-order "matrix" - with relation/function variables replaced with corresponding relation/function *symbols* \- is satisfiable.

TI'm not an expert here, but I think what's going on is "linguistic convenience." There are other related questions where we don't get coincision. For example, checking whether a first-order sentence is true in a given finite structure is usually harder than checking whether one of its "second-orderizations" is true in that same structure${}$*('s reduct)*. Similarly, as you say validity for ESO sentences is strictly more complicated than validity for FO sentences. In this way it may feel more consistent to talk about ESO satisfiability rather than FO satisfiability if we're *also* talking about ESO validity, ESO truth in a given structure, etc.

---
Tags: first-order-logic, higher-order-logic
---


# Question
Title: How to describe the languages of these regular expressions in plain English?
This is actually a question my lecturer gave us, so I know that it's kind of homework, but I tried to answer this and still had no luck.

The question is

> Give English description of the languages of the following regular expressions.
>
> 1. $(1+\epsilon)(00^\*1)^\*0^\*$
> 2. $(a^\*b^\*)^\*aaa(a+b)^\*$
> 3. $(a+ba)^\*b^\*$

I could only guess that the second one as the set of strings that at least have three consecutive $a$s. But I'm really clueless about others. Can someone make this clarified for me? Any help is highly appreciated.

# Answer
> 1 votes
The first regular expression captures all strings over $\\{0,1\\}$ not containing two consecutive 1s. It is not hard to check that any string in the language of the given regular expression has this property, and with some more work you can show the converse.

The second regular expression captures all strings over $\\{a,b\\}$ containing $aaa$ as a (consecutive) substring, as you also noticed.

The third regular expression captures all strings over $\\{a,b\\}$ not containing $bba$ as a (consecutive) substring, though this perhaps requires some verification.

---
Tags: regular-expressions
---


# Question
Title: DFA for binary language with constraints on triplets
I need to create a deterministic finite automata whose language consists of words over $\\{0,1\\}$ of any length, satisfying the following constraint:

> Among any subsequent 3 numbers, there needs to be exactly two 1s, and exactly one 0.

I've spent a couple hours studying DFAs, but I can only find solutions like the one I need to one of these issues. Meaning that among the 3, there can be at most 1 of something, or there needs to be at least 2 of something. I'm pretty much lost in how I'm supposed to combine these into a single DFA.

# Answer
Imagine writing a program on any high-level language for checking if string corresponds the given restriction. You would probably iterate symbols one by one and check if appending next symbol breaks the restriction.

Now note that you need only two last symbols to do it, and there are **finite** number of two-symbols combinations (namely $--, -0,-1,00,01,10,11$, where "$-$" stands for absence of preceding symbol at the very beginning of the string).

Why wouldn't we use these combinations as automata states? You are left only to add transitions, which are pretty straightforward (e.g. appending $0$ to $11$ transits to $10$, appending $1$ to $00$ transits to the dead state, and so on). Can you finish it now?
> 2 votes

# Answer
This is what I've come up with. Not sure if it's correct though.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Number of `m` length walks from a vertice with steps in [1, s]
The problem is stated as the following:

We are given a grid graph $G$ of $N \times N$, represented by a series of strings that describe vertices s.t.

* $L$ is the vertice we're interested in
* $P$ are vertices that are unavailable
* $.$ are vertices that are available

e.g.:

```
....
...L
..P.
P...

```

Would mean a graph that looks like this

```
   0    1    2    3
 +-------------------+
0|    |    |    |    |
 |    |    |    |    |
 +-------------------+
1|    |    |    |    |
 |    |    |    |    |
 +-------------------+
2|    |    |XXXX|    |
 |    |    |XXXX|    |
 +-------------------+
3|XXXX|    |    |    |
 |XXXX|    |    |    |
 +-------------------+

```

Where $v\_{2,3}$ and $v\_{0,3}$ are unavailable and we're interested in $v\_{3,1}$.

From each vertice we're only allowed to move on the axis (we can't move on the diagonal) and a move is valid from $v\_{x,y}$ to $v\_{q,p}$ if

* $ |x-q| + |y-p| \leq s$ and $v\_{q,p}$ is available.
* Staying in the same spot is also a valid move

Given $m$ \- maximal number of moves and $s$ what is the number of ways we can make $m$ moves from vertice designated by $L$.

My attempt was to

* First compute the neighbors reachable from each node. Create a look s.t. $\forall v N\[v\]$ is the list of reachable nodes from $v$
* Then build a starting record $M\_0$ s.t. if node is reachable $M\[i\]\[j\] = 1$ and $0$ otherwise.
* Then for each step calculate for $\forall i,j \in N$ (all the grid) $ M\_{i}\[i\]\[j\] = \sum\_{v\in N\[v\]} M\_{i-1}\[v\_i\]\[v\_j\]$ (where $v\_i, v\_j$ are the coordinates of $v$ on the grid) and store in a matrix $M\_i$

We iterate until $i==m$.

1. for each $v\_{i,j}$: 1. for each neighbor $n$ of $v\_{i,j}$: 1. $M\[i\]\[j\] += M'\[n\_i\]\[n\_j\]$

Unfortunately this doesn't work (tried to do it with a pen and paper as well to make sure) and I get fewer results then the expected answer, apparently there should be `385` ways but I only get to `187`.

Here are the intermediate states for the above mentioned board:

```
----------------------------

  5   6   5   5

  5   7   6   6

  4   6   0   5

  0   5   4   5

----------------------------

 25  34  27  27

 27  41  33  34

 20  33   0  27

  0  27  20  25

----------------------------

133 187 146 149

146 229 182 187

105 182   0 146

  0 146 105 133

----------------------------

```

This did work for e.g. m=2 and s=1 for the following board:

```
   0   1   2
 +---+---+---+
0|   |   |   |
 |   |   |   |
 +-----------+
1|   |   |   |
 |   |   |   |
 +-----------+
2|   |   |   |
 |   |   |   |
 +---+---+---+

```

Here's my reference code (`findWalks` is the main function)

```
using namespace std;
using Cord = std::pair<size_t, size_t>;

auto hash_pair = [](const Cord& c)
{
    return std::hash<size_t>{}(c.first) ^ (std::hash<size_t>{}(c.second) << 1);
};

using NeighborsMap = unordered_map<Cord, vector<Cord>, decltype(hash_pair)>;

inline vector<vector<int>> initBoard(size_t n)
{
    return vector<vector<int>>(n, vector<int>(n, 0));
}

Cord findPOI(vector<string>& board)
{
    for (size_t i=0; i < board.size(); i++) {
        for (size_t j=0; j < board.size(); j++) {
            if (board[i][j] == 'L')
            {
                return make_pair(i, j);
            }
        }
    }
    return make_pair(-1, -1);
}

NeighborsMap BuildNeighbors(const vector<string>& board, size_t s)
{
    NeighborsMap neighbors(board.size() * board.size(), hash_pair);

    for (size_t i = 0; i < board.size(); i++)
    {
        for (size_t j = 0; j < board.size(); j++)
        {
            size_t min_i = i > s ? i - s : 0;
            size_t max_i = i + s > board.size() - 1 ? board.size() - 1 : i + s;
            size_t min_j = j > s ? j - s : 0;
            size_t max_j = j + s > board.size() - 1 ? board.size() - 1 : j + s;

            auto key = make_pair(i, j);

            if (board[i][j] != 'P')
            {
                for (size_t x = min_i; x <= max_i; x++)
                {
                    if (board[x][j] != 'P' && x != i)
                    {
                        neighbors[key].push_back(make_pair(x, j));
                    }
                }

                for (size_t y = min_j; y <= max_j; y++)
                {
                    if (board[i][y] != 'P' && y != j)
                    {
                        neighbors[key].push_back(make_pair(i, y));
                    }
                }
                neighbors[key].push_back(key);
            }
            else
            {
                neighbors[key].clear();
            }
        }
    }

    return neighbors;
}

int GetNeighboursWalks(const Cord& cord, NeighborsMap& neighbors, const vector<vector<int>>& prevBoard)
{
    int sum{ 0 };
    const auto& currentNeighbors = neighbors[cord];
    for (const auto& neighbor : currentNeighbors)
    {
        sum += prevBoard[neighbor.first][neighbor.second];
    }
    return sum;
}

int findWalks(int m, int s, vector<string> board) {
    vector<vector<int>> currentBoard = initBoard(board.size());
    vector<vector<int>> prevBoard = initBoard(board.size());
    std::unordered_map<int, std::vector<Cord>> progress;

    auto poi = findPOI(board);
    NeighborsMap neighbors = BuildNeighbors(board, s);
    for (const auto& item : neighbors)
    {
        const auto& key = item.first;
        const auto& value = item.second;
        prevBoard[key.first][key.second] = value.size();
    }

    for (size_t k = 1; k <= static_cast<size_t>(m); k++)
    {
        for (size_t i = 0; i < board.size(); i++)
        {
            for (size_t j = 0; j < board.size(); j++)
            {
                auto currentKey = make_pair(i, j);
                currentBoard[i][j] = board[i][j] != 'P' ? GetNeighboursWalks(currentKey, neighbors, prevBoard) : 0;
            }
        }

        std::swap(currentBoard, prevBoard);
    }
    return prevBoard[poi.first][poi.second];
}

```

# Answer
Let $A$ be the set of available vertices (including $L$) and let $A(v)$ be the set of available vertices reachable by $v$ with a single move.

Let $M\[v,\ell\]$ be the number of walks of length exactly $\ell \ge 0$ from vertex $v \in A$.

You have that:

* $M\[v,0\] = 1 \quad \forall v \in A$;
* $M\[v,\ell\] = \sum\_{u \in A(v)} M\[u,\ell-1\] \quad \forall v \in A, \forall \ell \> 0$.

Intuitively, the second bullet means that every walk $\langle v, u, w\_1, w\_2, \dots \rangle$ of length $\ell$ from $v$ can be decomposed into an initial move to a vertex $u$ in $A(v)$, plus the walk $\langle u, w\_1, w\_2, \dots \rangle$ which has length $\ell-1$ and starts from $u$. The converse is also true (that is, if you have a walk $\langle u, w\_1, w\_2, \dots \rangle$ of length $\ell-1$ from a vertex $u \in A(v)$, then this also induces the walk $\langle v, u, w\_1, w\_2, \dots \rangle$ of length $\ell$ from $A(v)$). Since, by definition of $M\[\cdot, \cdot\]$, there are exactly $M\[u,\ell-1\]$ walks of length $\ell-1$ from $u \in A(v)$, it follows that the overall number of walks of length $\ell$ from $v$ is exactly the one given in the formula.

The value you are looking for is exactly $M\[L, \ell\]$.

Computing all sets $A(v)$ takes time $O(|A| s^2)$. Once this is done, computing each of the $O(|A| \ell)$ values $M\[v,\ell\]$ takes time $O(|A(v)|) = O(s^2)$. This leads to a dynamic programming algorithm requiring $O(|A| \ell s^2)$ time.
> 2 votes

---
Tags: algorithms, graphs, graph-traversal
---


title: Data structure for equivalence classes

text:
# Question
Title: Data structure for equivalence classes
Let $E$ be an equivalence relation defined over a set $S$. The access to $E$ is only via queries of the form $M(s\_1,s\_2) = 1$ if $s\_1$ and $s\_2$ are in the same class and $0$ otherwise. Computing $M$ is expensive (say, $O(n^2)$).

I am looking for an efficient data structure $D$ that supports queries of the form "given $s$, does $D$ contain an element $s'$ in the same equivalence class as $s$"?
A naive approach is to search element by element in $D$ and test, but is there other solution?

# Answer
The best you can do is keep track of all currently known equivalences using a Union-Find data structure. Initially, each element is in own group. Whenever you find that two elements are equivalent, you merge their groups (via a Union operation).

Then, the best you can do to answer the query you list is to enumerate over all the groups (other than the one containing $s$), find a representative $x$ for each such group, and test whether $s$ is equivalent to $x$.
> 2 votes

---
Tags: algorithms, data-structures, search-algorithms
---


title: Why is $\log_{2}n = O(n^{0.00001})$?

text:
# Question
Title: Why is $\log_{2}n = O(n^{0.00001})$?
Why is $\log\_{2}n = O(n^{0.00001})$ true?

This is obvious to me when the exponent is $\> 1$ but i'm having trouble understanding the cases where the exponent is very close to $0$. I would have to find some constants $c$ and $n\_0$ where $\log\_{2}n \le cn^{0.00001}$ for all $n \gt n\_0$.

Where I'm stumped is that $n^{0.00001} \approx 1$ and $\log\_{2}n$ approaches infinity as $n$ gets larger. It feels like regardless of whatever $c$ and $n\_0$ I choose, if $n$ was large enough, I could show that $\log\_{2}n \ge c$.

# Answer
$n^{0.00001}$ is not approximately $1$. $n^{0.00001}$ goes to infinity as $n \to \infty$.

You can see that $\log\_2 n = o( n^{0.00001} )$ by taking the limit of their ratio: $$ \lim\_{n \to \infty} \frac{\log\_2 n}{n^{0.00001}} = \lim\_{n \to \infty} \frac{n^{-1}}{0.00001 \cdot n^{0.00001} \cdot n^{-1}} = \lim\_{n \to \infty} \frac{100000}{n^{0.00001}} = 0. $$

This tells you that you can pick any value of $c\>0$, for example $c=1$. Now you just need a value $n\_0$ such that $n^{0.00001} - \log\_2 n \ge 0 \\; \forall n \ge n\_0$.

The derivative of $n^{0.00001} - \log\_2 n$ is $n^{-1}( 0.00001 \cdot n^{0.00001} - 1)$ which is non-negative as soon as $ n^{0.00001} \ge 100000$, i.e., for $n \ge 10^{5 \cdot 10^5}$.

You can then pick any value of $n\_0$ such that $(n\_0)^{0.00001} - \log\_2 n\_0$ is non-negative and $n\_0 \ge 10^{5 \cdot 10^5}$. For example $n\_0 = 2^{10^{7}}$. Indeed:

* $(n\_0)^{0.00001} = 2^{100} = 1024^{10} \> 1000^{10} = 10^{30} \> 10^7 = \log\_2 n\_0$; and
* $n\_0 = 1024^{10^6} \> 1000^{10^6} = 10^{3 \cdot 10^6} \> 10^{5 \cdot 10^5}$.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Construct a DAG from given multiple topological orderings
I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as first $n$ natural numbers. (Note that once created, the graph $G$ may have more topological orderings apart from the ones given.)
The following constraints should be met:

1. The maximum outdegree of every node should be 1
2. The number of nodes having indegree 0 should be minimum.

There can be multiple solutions, any of them should work.

What I have tried. (**Approach 1** which is wrong as it fails one example given in the answer. Please scroll to the second approach, which still I'm not able to find a mistake.)

**Approach 1**
From all the given orderings, first, create a directed graph by creating a directed edge from every node to its next node. This means if the orderings are:
$$ 1, 3, 2, 5, 4, 6 $$ $$ 3, 1, 5, 2, 4, 6 $$ $$ 1, 5, 3, 2, 4, 6 $$

I will create a directed graph with a directed edge from $1$ to $3, 3$ to $2, 2$ to $5$ and so forth.

This ensures that the number of nodes with indegree 0 remains minimum. Now, I'll remove all the cycles and make sure all the orderings are valid and finally, eliminate all the extra edges any node has. WHile doing so, I'll make sure that if there are two nodes whose edge is coming from the same node, I'll remove the edge from the node having a higher indegree, so that condition 2 is met. The graph constructed then, should look like:

This DAG created, follows both the constraints, and IMO has the minimum number of nodes of indegree as 0, although, it's not proven.

I have coded the approach and it is giving expected results for the use cases I supply, but I know that it is wrong. What am I missing here? Can anyone provide an alternative use case, which fails the above approach?

**Approach 2**
I create a directed graph $G$ by creating an edge from $a\_i $ to $ a\_j$ for all $ j \> i$ in all the orderings given. So, for the orderings:
$$ 1, 2, 3, 4, 5$$ $$ 2, 4, 1, 5, 3$$

I will create the following graph:
The first step after this is to validate all the orderings. Removing cycles separately is not required as they will be removed by this step itself.
For any ordering $$ a\_1, a\_2, a\_3, a\_4, ... a\_n $$ I will check if there exists any edge from $a\_j$ to $a\_i$ where $ j \> i$, I'll remove that edge.
Doing so, will give the following graph:
The last step is to remove extra edges from all nodes as maximum outdegree of any node can be $1$ max. I'll remove the outgoing edges such that the number of nodes having indegree $0$ is minimum. First I calculate the indegree of each node. Then for each node which has more than 1 outgoing edges, I'll remove all the edges except the one with the minimum indegree.

The final graph $G$ will look like:

This graph satisfies both the constraints. But I know this approach is wrong! Can anyone help to find why is this wrong?

# Answer
# Approach 1

For example, consider the two orders: 1, 2, 3, 4, 5 and 2, 4, 1, 5, 3.

According to your approach, we will get a cycle 1-\>2-\>3-\>4-\>1. We then remove 3-\>4 and 4-\>1, and obtain a graph:

```
     ______
    /      \
1->2->4->5->3
 \______/

```

Now 5-\>3 and 1-\>2 respectively violate the first and the second orders, so we remove them, and get

```
     ______
    /      \
1  2->4->5  3
 \______/

```

Now node 2 has 2 outgoing edges. Removing either one makes a final graph where 3 nodes (1, 2, 3 or 1, 2, 4) have in-degree 0.

However, there exists a graph

```
1->3 2->4->5

```

where both orders are satisfied but only 2 nodes have in-degree 0.

So Approach 1 is incorrect.

# Approach 2

Consider an optimal solution. Every edge in this optimal solution must be the form $(a\_i,a\_j)$ where $i\<j$ in each order. This means all edges in the optimal solution are contained in the intermediate graph. So if you then remove the outgoing edges such that the number of nodes having in-degree 0 is minimum, you will get a correct optimal solution.

However, your approach that trying to make the number of nodes having in-degree 0 minimum is incorrect.

For example, consider the three orders: \begin{align} 1, 2, 3, 4, 5, 6, 7, 8 \\ 5, 1, 6, 3, 8, 2, 4, 7 \\ 2, 7, 3, 8, 1, 4, 5, 6 \end{align}

First we can obtain the following intermediate graph:

```
    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

```

Applying your approach, we will remove 1-\>4, 2-\>4 and 3-\>4 (or 3-\>8), and there are 5 nodes with in-degree 0: 1, 2, 3, 4 (or 8), 5. However, the optimal solution would be

```
     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

```

where only 4 nodes have in-degree 0: 1, 2, 3, 5.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, dag, topological-ordering
---


# Question
Title: In a DAG, finding the path with the highest score
Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a DFS approach in which we start at the end and run the graph in the reverse way, saving at each node the best cumulative score attainable. To print the results, we start at the first node and greedily pick the next node with the highest cumulative score. However, I don't think this is the best way as we might be traversing the same paths a lot of times if we are given an unfriendly graph. Is there a better way of doing this?

# Answer
Hint: find a topological ordering, and for each vertex $v$, in the topological ordering, compute (the score of) the path with the highest score that ends at $v$.
> 4 votes

---
Tags: algorithms, graphs, graph-traversal, weighted-graphs, dag
---


title: Finding maximally far away points

text:
# Question
Title: Finding maximally far away points
Given a metric space $X$ with finitely many points, and a nonnegative integer $n$, I want to find a set of $n$ points in $X$ which maximizes the minimum distance between any two points.

What algorithms are there to do this?

# Answer
> 2 votes
The problem is NP-hard, by reduction from independent set.

If you have an undirected graph, treat the distance between two vertices $v,w$ to be $2$ if there is an edge $(v,w) \in E$, or $1$ if not. There there is an independent set of size $n$ in this graph iff there is a set of $n$ points whose minimum distance is 2.

So, your best bet is probably to use some algorithm for independent set (maybe a SAT solver, or maybe something else), combined with a binary search on the minimum distance.

---
Tags: algorithms, search-algorithms
---


# Question
Title: Design a DFA recognising the following language
Design a DFA over alphabet (a,b) such that for all it's string no prefix contain two more a's than b's and two more b's than a's and the number of a's is equal to b's. Is it possible to design a DFA in such special cases of number of a's being equal to b's ,as it is not possible to make a DFA for the general case of a's being equal to b's. If yes ,why and how to recognize such cases.

# Answer
> 0 votes
To address your first question, this DFA will do the trick:

The starting state is marked with an 'S' and it is also the only accepting state. Any string that has a prefix with 3 or more a's than it does b's will go out the right side and end up trapped in the trash state, and similarly, with b's to the left. Furthermore, it will only end up in the center if the number of a's equals the number of b's and the trash state is never visited.

The reason that we can find a DFA for this special case is that we really only need to be able to count between -3 and +3, which requires a **finite** amount of memory. The -3 and +3 come from the condition that prefixes have a and b counts within 2 of each other so if we ever hit -3 or +3 we can go to the trash state. In the general case, we may need to count arbitrarily high which requires infinite counting, not something a DFA can manage.

---
Tags: automata, finite-automata, undecidability
---


# Question
Title: Design a DFA for the language L = {w | w contain 2 a’s at any position and greater than 3 b’s at any position, w ϵ {a.b}*}/
I do not understand this question,because for saving Number of a's and b's memory is required,which FA does not provide.could anybody please explain this?

# Answer
The claim that a DFA does not have memory is incorrect, a DFA in fact has **finite** "memory" in the sense that you can design the states to have meanings in terms of some variables. (Eg. being in state 5 means you've seen at least 5 a's, so you in some sense remember that you've seen 5 a's)

Now to address the question,

starting at the state marked S and ending at the accepting state (2,4), we move between states incrementing the first index when we see an 'a' and incrementing the second when we see a 'b'. If we run out of string before reaching 2 a's and 4 b's the string gets rejected, or if we see more than 2 a's we move to the trash state.

The only strings that do get accepted are those with exactly 2 a's and at least 4 b's. The different states that we have completely encapsulate all the necessary "memory" in the sense above.
> 2 votes

---
Tags: automata, finite-automata
---


# Question
Title: Finding largest sum of $k$ elements below threshold
I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of indices is maximal under the constraint of being less than a given element $x$. My approach for this is the naive $O(n^k)$ algorithm, but this would take a lot of time for large $n$.

*This is isn't a homework problem.*

# Answer
You can use meet-in-the-middle to reduce the running time to $O(n^{\lceil k/2 \rceil})$.

For simplicity, let me assume that $k$ is even.

The idea is as follows:

* Partition $A$ into two parts.
* For each part, compute a sorted list of sums of $k/2$ elements from the part.
* For each $k/2$-sum in the first part, use binary search to find the best $k/2$-sum in the second part which conforms to the constraints.

As stated, there are several problems with the idea:

1. It assumes that the optimal solution contains exactly $k/2$ summands out of each part.
2. It runs in time $O(n^{k/2} \log n)$.
3. It uses $O(n^{k/2})$ memory.

To handle the first difficulty, there are several options. We could just repeat the entire algorithm $\sqrt{k}$ times. Alternatively, there might be deterministic ways to achieve the same goal. Here is a hybrid solution:

* Randomly partition $A$ into $k^3$ parts $P\_1,\ldots,P\_{k^3}$ (anything substantially larger than $k^2$ would work). With high probability, each element of the optimal solution is in its own part.
* Consider all possible partitions of $A$ into two parts of the form $P\_1,\ldots,P\_i$ and $P\_{i+1},\ldots,P\_{k^3}$. One of these will contain exactly $k/2$ elements of the optimal solution.

To handle the second difficulty, we need to be slightly more careful in implementation. Using merging (the familiar subroutine from mergesort), it should be possible to compute the $k/2$-sums of each part in $O(n^{k/2})$. The final step can be implemented in $O(n^{k/2})$ using a classic two-pointer technique (the first pointer goes up on the first half, the second one goes down on the second half).

There are tricks to reduce the memory required from $O(n^{k/2})$ to $O(n^{k/4})$: further divide each part into two sub-parts. You can easily go over all $k/2$-sums in the first part by considering all pairs of $k/4$-sums in its subparts. Binary search on the second part can then be implemented using the two-pointer technique.
> 2 votes

---
Tags: algorithms, optimization, arrays
---


# Question
Title: Conditions for applying Case 3 of Master theorem
In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this. $a\geq1$, $b\>1$, $f$ is a nonnegative function defined on exact powers of b. The recurrence relation for $T$ is $T(n) = a T(n/b) + f(n)$ for $n=b^i$, $i\>0$.

For the third case, we have $f(n) = \Omega(n^{\log\_ba +\epsilon})$ for some fixed $\epsilon\>0$ and that $ af(n/b)\leq cf(n)$ for fixed $c\<1$ and for all sufficiently large $n$. In this case, $T(n) =\Theta(f(n))$ since $f(n) = \Omega(n^{\log\_ba +\epsilon})$.

I was wondering if the condition that $f(n) = \Omega(n^{\log\_ba +\epsilon})$ is unnecessary since the regularity condition $ af(n/b)\leq cf(n)$ for all $n\>n\_0$ for fixed $c\<1$ and for some $n\_0$ implies that $$ \begin{align\*} f(n)&\geq m\left(\frac{a}{c}\right)^{\log\_b(n/n\_0)} \text{ where } m=\min\_{1\leq x\leq n\_0}{f(x)}\\\&\ge\left(\frac{n}{n\_0}\right)^{\log\_b(a/c)}=\Theta(n^{\log\_ba +\log\_b(c^{-1})})=\Theta(n^{\log\_ba +\epsilon}). \end{align\*} $$ This will hold as long as $f(n)$ is non-zero. Hence $f(n)=\Omega(n^{\log\_ba +\epsilon})$. Therefore we merely need to add the condition that $f(n)$ is positive for all but finitely many values of $n$ for case 3. Am I correct about this?

# Answer
> 6 votes
Yes, your sharp observation is completely correct.

---

To be compatible with the highly strict style shown at section 4.6, *Proof of the master theorem* of *Introduction to Algorithms*, here is the complete proposition and a slightly more rigorous proof. It seems that the proof in the question ignores the requirement that $f$ is defined only on exact powers of $b$.

(**Regularity implies lower-bounded by a greater-exponent polynomial.**) Let $a\geq1$, $b\>1$ and $f$ be a nonnegative function defined on exact powers of $b$. Suppose $af(\frac nb)\leq cf(n)$ for some fixed $c\<1$ and for all sufficiently large $n$. Furthermore, $0 \< f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log\_ba +\epsilon})$ for some fixed $\epsilon\>0$.

**Proof**. There exists some $n\_0\>0$ such that $af(\frac nb)\leq cf(n)$ and $0 \< f(n)$ for all $n\ge n\_0$. We can assume $n\_0$ is an exact power of $b$ since, otherwise, we can replace $n\_0$ by $b^{\lceil\log\_b{n\_0}\rceil}$.

Let $n\ge n\_0$ be an exact power of $b$. So $n = n\_0b^m$, where $m=\log\_b\frac n{n\_0}$ is an integer since both $n$ and $n\_0$ are exact powers of $b$. Applying $af(k/b)\leq cf(k)$ multiple times, we get

$$f(n) \ge \frac acf(\frac nb) \ge (\frac ac)^2f(\frac n{b^2})\ge \cdots \ge (\frac ac)^mf(\frac n{b^m})=(\frac ac)^mf(n\_0)$$

Since $$(\frac ac)^m=(\frac ac)^{\log\_b\frac n{n\_0}} =(\frac n{n\_0})^{\log\_b\frac ac}=(\frac n{n\_0})^{\log\_ba-\log\_bc}=c\_0n^{log\_ba+\epsilon}$$ where $\epsilon=-\log\_bc \> 0$ and $c\_0=(\frac1{n\_0})^{log\_ba +\epsilon}$ are two constants, we have

$$f(n) \ge c\_0f(n\_0)n^{log\_ba +\epsilon}.$$ So, $$f(n)=\Omega(n^{log\_ba +\epsilon}).\quad \checkmark$$

---

What happens if $n$ is not necessarily an exact power of b? The same result will hold if we replace $\frac nb$ by $\lfloor \frac nb\rfloor$ or $\lceil \frac nb\rceil$. The following is a version when $\lfloor \frac nb\rfloor$ is used.

Let $a\ge1$, $b\>1$ and $f$ be a nonnegative function defined on positive integers. Suppose $af(\lfloor \frac nb\rfloor)\leq cf(n)$ for some fixed $c\<1$ and for all sufficiently large $n$. Furthermore, $0 \< f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log\_ba +\epsilon})$ for some fixed $\epsilon\>0$.

---
Tags: asymptotics, master-theorem
---


# Question
Title: What is the best of given hashfunctions?
In our exam on algorithms there was a question, where given 3 hashfunctions we had to chose one and explain why it's the best.

h\_1(x,i)=(x+5\*i) mod 1000
h\_2(x,i)=(x+17\*i) mod 1000
h\_3(x,i)=(x+32\*i) mod 1000

I am really unsure about this, but I suspect that it is the second one, because it can "hit" more values. If I choose the first one for example, I will be hitting the same buckets over and over (if they are full). Question seems quite simple but my math lecture on this has been a long time ago.

# Answer
> 1 votes
The question is not well-defined, since its unclear what you mean by "best".

I suspect that the intended answer is what you said and that you are using open addressing. Then, for a given $x$, $h\_2$ would eventually return all possible values in $\\{0, \dots, 999\\}$ (since $17$ and $1000$ are coprime). $h\_1$ would only return $\frac{1000}{5} = 200$ distinct values, and $h\_3$ would only return $\frac{1000}{\textrm{gcd}(32,1000)} = \frac{1000}{8}=125$ distinct values.

---
Tags: hash-tables, hashing
---


# Question
Title: Proving a language is not regular using Myhill Nerode Theorem
Let $L = \\{\alpha\in\\{a,b,c\\}^{\*} \mid \alpha \text{ is palindrome}\\}$, show that $L$ is not regular using Myhill-Nerode relation.

I don't know how to show that $L$ has infinite equivalence classes because $\alpha$ is a palindrome. I tried to use something like this, but I don't know if its correct:

$\alpha \equiv\_{L} \beta \iff \alpha (aba)^k \in{L} \iff \beta (aba)^k \in{L}$ $\forall k \in \mathbb N$ which implies that for every k there exists an equivalence class because the repetition of aba k times.

# Answer
> 1 votes
Take $a^nb$ and $a^mb$ for n != m. Since the first can be followed by $a^n$ and the second can’t, they are in different equivalence classes. Therefore the number of equivalence classes is not finite.

C isn’t even needed.

# Answer
> 0 votes
You seem to have forgotten the letter $c$ inside your parenthesis. According to this university handout, an equivalence class requires that appending every string in the alphabet to the two equivalent inputs still makes these two inputs either both in the language or both not in the language. In other words,

$\alpha \equiv\_L \beta$ means $\alpha y \in L \wedge \beta y \in L$ for any $y$ in your three letter alphabet, or $\alpha y \not\in L \wedge \beta y \not\in L$.

$y = (aba)^k$ is not all possible string in the alphabet.

One strategy in the handout is to start with one equivalence class and append the same string to two members of the equivalence class. Then show that the resulting two strings are no longer equivalent, ie. one is in the language while the other one is not. It is a proof by contradiction by first assuming the language is regular.

---
Tags: automata, regular-languages
---


# Question
Title: Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?
My assignment asks
Let $S = \\{ w\_1\\#w\_2\\# \dots \\#w\_k | k ≥ 2; (∀i ≤ k)w\_i ∈ \\{0, 1\\}^\star ; (∃i \< k) w\_i\neq w\_{i + 1}^r$ , i.e., not every string $w\_i$ is equal to the reversal of $w\_{i+1}$. Note $S ⊆ \\{0, 1, \\#\\}^\star$.

Show that S is a CFL by a PDA, P, that accepts it.

I have been stuck on this question for approximately 20+ hours. I tried to sketch the PDA about 20 pages but still fail some cases. My friend's suggestion as store the word $w\_i$ then the next state is to compare $w\_{i + 1}$ to $w\_i$, however, what I'm struggling is how do we compare $w\_{i + 2}$ to $w\_{i + 1}$ after comparing $w\_{i + 1}$ to $w\_{i}$. This seems impossible since the stack has to be pop out an element in order to compare the previous word. Once it's empty, we can never fill up the stack with the same elements that already popped.

Another way that I found is referring to this link: https://cseweb.ucsd.edu/classes/su99/cse105/hw2sol.pdf.

On question 3, it has a construction for non-palindrome over $\\{0,1\\}^\star$. Which is similar to our case but we have a $\\#$ sign between words. I.e., we have many different strings instead of this construction only need to handle one string and compare it's left and right. I have been stuck for a long time, I think I'm missing something here. Any suggestions?

# Answer
> 2 votes
Use nondeterminism to guess an index $i$ for which $w\_i \neq w\_{i+1}$. The machine reads its input until it nondeterministically chooses a $w\_i$ and places it on the stack. Afterwards, it compares $w\_{i+1}$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.

# Answer
> 1 votes
I suggest you try some special cases. First, can you handle the special case where we force $k=2$? If not, work out how to solve that first, before handling the full problem. Next, try to handle the case where $k=3$. I recommend using the techniques in How to prove that a language is context-free? (specifically, look at the closure properties). Once you can solve those two easier versions of the problem, I suspect you should be able to solve the full problem. I would not expect you to write down a PDA for the entire thing from zero: instead, build it up from smaller pieces.

---
Tags: complexity-theory, finite-automata, context-free, pushdown-automata
---


# Question
Title: Proving correctness and optimality of a greedy algorithm
Here is a (slightly abridged) problem from Kleinberg and Tardos:

---

Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated length $\ell\_e$, which is a positive number. The *distance* from the root to a given leaf is the sum of the lengths of all the edges on the path from the root to the leaf.

Now, if all leaves do not have the same distance from the root, then the signals we send starting from the root will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to receive the signal at the same time. To make this happen, we will have to increase the lengths of certain edges, so that all root-to-leaf paths have the same length (we’re not able to shrink edge lengths). If we achieve this, then we say the tree has *zero skew*.

Give an algorithm that increases the lengths of certain edges so that the resulting tree has zero skew and the total edge length is as small as possible.

---

This problem was in the "Greedy Algorithms" chapter.

I know the solution to this problem is as follows:

Let the subtrees below the root be $L$ and $R$. If the maximum sum of the edge lengths on the path to a leaf in $L$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $R$, then increase the edge length from the root to the right subtree by the positive difference between the two.

Conversely, if the maximum sum of the edge lengths on a path to a leaf in $R$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $L$, then increase the edge length from the root to the left subtree by the positive difference between the two.

I am having trouble proving the following:

* $1)$ The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).
* $2)$ The sum of the edge lengths is minimized with this algorithm.

I have tried to prove these facts in many ways, such as induction and direct proof, but I am having a lot of difficulty doing so. The algorithm makes sense to me intuitively, but I'm having trouble explaining why it works formally.

I would greatly appreciate some help in solving this problem.

# Answer
**Notation.** Given a binary tree $T$ and vertex $v$ of $T$, let $\ell\_v$ and $r\_v$ be the left and right children of vertex $v$ in $T$, respectively. Let $T\_v$ be subtree of $T$ rooted at $v$. Let $d\_T(v)$ be the weighted distance between the root of $T$ and $v$ and $h(T) = \max\_{v \in T} d\_T(v)$. If $(u,v)$ is an edge of $T$, let $w\_T(u,v)$ be its weight. With a slight abuse of notation, define $w(T) = \sum\_{(u,v) \in T} w(u,v)$. Finally, we define the skew of $v$ as $s\_T(v) = w\_T(v, \ell\_v) + h(T\_{\ell\_v}) - w\_T(v, r\_v) - h(T\_{r\_v})$ if $v$ is an interval vertex of $T$ and $s\_T(v)=0$ if $v$ is a leaf of $T$.

> 1) The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).

We will show by induction on $i=0,1,\dots$ that, for all trees $T$ with $2^{i+1} - 1$ vertices, the algorithm returns a tree in which all vertices have skew $0$.

The base case $i=0$ is trivially true since $T$ must have exactly one vertex and the algorithm does nothing.

Suppose now that $i\>0$ and let $v$ be the root of $T$. The trees $T\_{\ell\_v}$ and $T\_{r\_v}$ have exactly $\frac{(2^{i+1} - 1) - 1}{2} = 2^i - 1$ vertices and, by inductive hypothesis, the recursive calls on $T\_{\ell\_v}$ and $T\_{r\_v}$ ensure that all vertices, except possibly $v$, have skew $0$. The reweighing of $(v, \ell\_v)$ and $(v, r\_v)$ only affects the skew of $v$ and ensures that $s(v)=0$.

> The sum of the edge lengths is minimized with this algorithm.

Let $T'$ be the tree returned by the algorithm. Suppose that an optimal zero-skew tree $T^\*$ obtained from the input tree $T$ by lengthening edges is such that $w(T^\*) \< w(T')$.

Let $(u,v)$ be an edge of $T$ (where $u$ is the parent of $v$) such that $w\_{T^\*}(u,v) \< w\_{T'}(u,v)$ and the depth of $u$ is maximized.

Since $s\_{T^\*}(u)=0$ and since $h(T\_v^\*) \ge h(T\_v) = h(T'\_v)$, the sum of the weights in $T^\*$ on each path from $v$ to a leaf in $T\_v$ must have increased by at least $w\_{T'}(u,v) - w\_{T^\*}(u,v)$. Consider the subgraph of $T^\*\_v$ induced by the edges whose weight has not been increased w.r.t. $T$ and let $C$ be the connected component containing $v$. Let $E$ be the set of edges with one endpoint in $C$ and the other in $T^\*\_v \setminus C$. Let $\Delta = \min\_{(x,y) \in E} \\{ w\_{T^\*}(x,y) - w\_T(x,y) \\}$.

Consider a new tree $T''$ that is obtained from $T'$ by reducing the weight of all edges in $E$ by $\Delta$ and increasing the weight of $(u,v)$ by $\Delta$. The tree $T''$ is a feasible solution to your problem and weighs $w(T^\*) - |E| \Delta + \Delta \< w(T^\*)$ (since $|E|\ge 2$). This is a contradiction.
> 3 votes

# Answer
The proof of the first part is quite straightforward if you strengthen the induction proposal.

**Statement**:

The algorithm applied to the tree with root $v$ (we denote it as $f(v)$) yields a zero-skew tree which has the same height as $v$.

**Proof**:

By structural induction: if $v$ has no children, it is trivially true. Otherwise, it has children $v\_l, v\_r$ and edges of length $w\_l, w\_r$ respectivetely. Without loss of generality, we assume $h(v\_l) + w\_l \geq h(v\_r) + w\_r$. Therefore, $v$ has height $h(v\_l) + w\_l$. By induction proposal, $f(v\_l)$ and $f(v\_r)$ are zero-skew with height $h(v\_l)$ and $h(v\_r)$ respectivetely. Thus, every path from $f(v)$ to its leaf from left subtree has length $$w\_l + h(v\_l)$$ and every path from $f(v)$ to its leaf from the right subtree has length $$w\_r + ((h(v\_l) + w\_l) - (h(v\_r) + w\_r)) + h(v\_r) = w\_l + h(v\_l)$$ i.e. $f(v)$ is zero-skew with height $h(v\_l) + w\_l$.
> 1 votes

---
Tags: algorithms, graphs, trees, correctness-proof
---


# Question
Title: Find a weighted median for unsorted array in linear time
For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of *weighted median* in linear time.

It is very simple to do that in exponential time.

So let's say that we have an array, each item $x$ of this array has two attributes - price $c(x)$ and weight $w(x)$. The goal is to find an item $x$ such that $$ \sum\_{y\colon c(y) \< c(x)} w(y) \leq \frac{1}{2} \sum\_y w(y) \text{ and } \sum\_{y\colon c(y) \> c(x)} w(y) \leq \frac{1}{2} \sum\_y w(y). $$

If the array was sorted by price, it would be simple:

Go from the first item one by one, count sum and if the sum becomes greater that half the total weight, then you found the desired item.

Could you give me some hint how to find such an item in linear time?

# Answer
> 10 votes
Let $A$ be an input array containing $n$ elements, $a\_i$ the $i$-th element and $w\_i$ its corresponding weight. You can determine the weighted median in worst case linear time as follows. If the array length is $\leq 2$, find the weighted median by exhaustive search. Otherwise, find the (lower) median element $a\_x$ using the worst case $O(n)$ *selection* algorithm and then partition the array around it (using the worst case $O(n)$ partition algorithm from QuickSort). Now determine the weight of each partition. If weight of the left partition is $\< \frac{1}{2}$ and weight of the right partition is $\leq \frac{1}{2}$ then the weighted (lower) median is $a\_x$. If not, then the weighted (lower) median must necessarily lie in the partition with the larger weight. So, you add the weight of the "lighter" partition to the weight of $a\_x$ and recursively continue searching into the "heavier" partition. Here is the algorithm's pseudocode (written in Latex).

```
FIND-WEIGHTED_LOWER_MEDIAN(A)
    if $n$ == 1
       return $a_1$
    elseif $n$ == 2
       if $w_1 \geq w_2$
          return $a_1$
       else
          return $a_2$
    else
       determine $a_x$, the (lower) median of A
       partition A around $a_x$
       $W_{low}$ = $\sum\limits_{{a_i} < {a_x}} {{w_i}}$
       $W_{high}$ = $\sum\limits_{{a_i} > {a_x}} {{w_i}}$
       if $W_{low} < \frac{1}{2}$ AND $W_{high} \leq \frac{1}{2}$
          return $a_x$
       else if $W_{low} \geq \frac{1}{2}$
               $w_x = w_x + W_{high}$
               B = \{ a_i \in A: a_i \leq a_x \}
               FIND-WEIGHTED_LOWER_MEDIAN(B)
            else
               $w_x = w_x + W_{low}$
               B = \{ a_i \in A: a_i \geq a_x \}
               FIND-WEIGHTED_LOWER_MEDIAN(B)

```

Now let's analyze the algorithm and derive its complexity in the worst-case. The recurrence of this recursive algorithm is $T(n) = T(\frac{n}{2} + 1) + \Theta(n)$. Indeed, we have no more than a recursive call on half the elements plus the (lower) median. The initial exhaustive search on up to 2 elements costs $O(1)$, determining the (lower) median using the select algorithm requires $O(n)$, and partitioning around the (lower) median requires $O(n)$ as well. Computing $W\_{low}$ or $W\_{high}$ is again $O(n)$. Solving the recurrence, we get the complexity of the algorithm in the worst case, which is $O(n)$.

Of course, a real implementation should not use the worst case $O(n)$ selection algorithm, since it is well known that the algorithm is not practical (it is of theoretical interest only). However, the randomized $O(n)$ selection algorithm works pretty well in practice and can be used since it's really fast.

# Answer
> 4 votes
This answer is very similar to Massimo's except with a (hopefully) simpler style/structure of phrasing it and in addition includes the solution to find the second weighted median as well.

If you want just a hint, just look at step 1), and read no further. If you want more hints, continue to next step.

## Assumptions:

Input is in two different arrays: Prices\[\], and Weights\[\] Whenever values in Prices\[\] are rearranged, values in Weights\[\] are also rearranged to keep the correspondence between indexes.

## Approach:

```
1. Using the method from either Randomized selection, or Deterministic selection
   algorithm, partition the Prices around a selected Pivot element.
2. Calculate the sum of all weights in the Left Partition as L, and the sum of
   all weights in the Right Partition as R.
3. Let P be a 'reference' to the weight of the Pivot element.
4. Calculate the total weight of all the elements, L + P + R as S
5. a) If L > S/2:
       P += R (Add weight of all elements in right partition to the Pivot)
       Change array upper bound to end at Pivot element.
       go to step 1.
   b) Else If R > S/2:
       P += L (Add weight of all element in left partition to the Pivot)
       Change array lower bound to begin at the Pivot element.
       go to step 1.
   c) Else:
      Pivot is the Median.
      i) If L + P == S/2:
         Successor of the Pivot element is also a Median.
         Linear scan the Right partition to find the element with Min Price
         as the Successor.
      ii) Else If P + R == S/2:
          Predecessor of the Pivot element is also a Median.
          Linear scan the Left partition to find the element with Max Price
          as the Predecessor.
      return the Medians
      (Done)

```

## Correctness:

Step 5.a)

> If L \> S/2, the median cannot be in the Right Partition. Because, if it be so, L will only get larger and violate the requirement that L must be less than or equal to S/2. Hence, we look for median in the Left Partition

Step 5.b)

> If R \> S/2, the median cannot be in the Left Partition. Because, if it be so, R will only get larger and violate the requirement that R must be less than or equal to S/2. Hence, we look for median in the Right Partition

Step 5.c.i)

> L + P \<= S/2 implies R = S/2 and L + P = S/2, because L + P + R = S.

Step 5.c.ii)

> P + R \<= S/2 implies L = S/2 and P + R = S/2, because L + P + R = S.

## Complexity:

The number of elements scanned to calculate L, and R is no more than the number of elements scanned to partition the array in each iteration/reduction.

Hence, the complexity of the solution is same as that of the Selection algorithm used, which is average O(n) if Randomized selection, or worst case O(n) if Deterministic selection is chosen.

In addition, 5.c.i) or 5.c.ii) do a one time scan of a maximum of n-1 elements in case there is a possibility for a second median, which doesn't add significantly to already deduced overall complexity of either average or worst case O(n)

## Notes:

The approach is easy to implement in a non recursive way, and i also have some notes not though totally relevant to the question, but could be relevant to many people who end up here: https://thoughtvalve.blogspot.com/2020/03/why-only-2-weighted-medians-at-most.html

# Answer
> 3 votes
You can do binary search for the price of `x` that satisfies the criterion. Computing the sum would take linear time each iteration (giving $O(n\log n)$ time) but you can compute the sum faster if you reuse work from previous iterations.

---
Tags: algorithms, time-complexity, arrays
---


title: Full adder carry expression

text:
# Question
Title: Full adder carry expression
I'm learning about logic circuits and I've come across full adder. In the book they derived its two carry out expressions -

Cout = x&&y || x&&z || y&&z and Cout = x&&y || (x'&&y || x&&y')&&z

I've tried to get the second equation from the first one but couldn't. Any one knows how to do that?

# Answer
From your question it is unclear what $x$, $y$ and $z$ are. However, the two formulas are equivalent. Let me use products to denote a logical "AND" and additions to denote a logical "OR" so that your first formula becomes $xy + xz + yz$

If you gather $z$ in the last two terms you get: $xy + (x+y)z$.

Notice how the second term $(x+y)z$ is true iff $z$ is true, and at least one of $x$ and $y$ is true. However, if both $x$ and $y$ are true, the whole formula is true regardless of the truth value of the second term (since the first term is $xy$). You can then replace $(x+y)$ with $(x \oplus x)$ (where "$\oplus$" denotes the exclusive OR) to obtain: $xy + (x \oplus y)z$ or, equivalently, $xy + (x'y + xy')z$.
> 1 votes

---
Tags: computer-architecture, digital-circuits, combinatory-logic
---


title: Proving the optimality of an algorithm

text:
# Question
Title: Proving the optimality of an algorithm
I proposed an algorithm and I want to prove its optimality. It is not a greedy algorithm. I have the whole searching space $\mathcal{S}$ and I only search inside a subset of this searching space $\mathcal{C} \subset \mathcal{S}$ and exclude the remaining search space. I know the logic behind excluding this should not violate the optimality of my algorithm. What kind of proof technique I should use to formally prove the optimality of my algorithm ? like contradiction or so on. Note : the optimal solution that can be produced by my algorithm is not unique.

# Answer
It's rarely possible to prove that an algorithm is optimal. You would have to show that your algorithm takes n steps, and for some reason solving the problem in less than n steps is impossible. Even for someone who is 100 times more intelligent than you and me together.

An example is finding the maximum of n random numbers, which can done in n steps, and n steps are required because if you read n-1 or fewer array elements, then you can't know whether the last one is greater than all other elements or not.
> 2 votes

---
Tags: algorithms, algorithm-analysis
---