# Question
Title: Maximum value of $\{ i \land n \mid a \leq i \leq b \}$
I was doing problems in "*Leetcode*" and found a problem that I could not solve.

Given a *non-negative* number $n$ and two *non-negative* numbers $a$ and $b$, consider every number $i$ such that $a \leq i \leq b$ and among those find the *maximum* value of $n \\& i$ where $\\&$ means *bitwise and*.

I could only solve when $a=0$ by finding the most significant bit location in $b$ and in $n$ and comparing both and find that $i$ should be $b$ or let location of most significant bit be $k$ from *right* then it must be $1111111.......1$ $(k-1)$ times.

But when $a \neq 0$ I am struck. Can anybody help me?

P.S : I am finding the question and I will post it's link by tomorrow.

# Answer
> 1 votes
Here is how to reduce this to the case you already know how to solve.

If $a = b$, there is nothing to do. Otherwise, the binary expansion of $a,b$ is of the form $a = x0\alpha$ and $b = x1\beta$, where $|\alpha| = |\beta|$. If the bit of $n$ corresponding to the differing bit of $a,b$ is $0$, then the corresponding bit of $i$ should be $1$, and vice versa (more significant bits are forced to $x$).

In the first case, we are looking for a solution in the range $x10^{|\beta|}$ to $b$, which reduces to $0^{|\beta|}$ to $b$; that you already know how to solve.

In the second case, we are looking for a solution in the range $x0\alpha$ to $x01^{\alpha}$, which reduces to $\alpha$ to $1^{|\alpha|}$; that should have a solution analogous to the case you're familiar with.

---
Tags: algorithms, dynamic-programming, bit-manipulation
---


# Question
Title: What is the fastest way to merge two B trees?
Given two B-trees of some order $m$ \- $T\_1,T\_2$, such that $y \> x$ for every pair $x \in T\_1$ and $y \in T\_2$. What is the fastest way to create a new tree that is the union of both $T\_1,T\_2$?

My current solution is naive in a sense that I create an array and insert all $T\_1$ elements, than all $T\_2$ elements. As a result I have a sorted array which I can create a new tree off of with a cost of $n \log n$

I'm thinking that there must be a better solution, something like the AVL merging question but I can't figure it out.

# Answer
> 3 votes
It is great that you have obtained a sorted array, which runs in $O(n)$ time.

Once we have $n$ elements in a sorted array, every kind of "nice" tree, that I know, can be built in $O(n)$. In particular, we can build a $B$-tree in $O(n)$ time.

Here is an example. Suppose the sorted array is $$\[1, 2, 3, 4, 5, 6, 7,8,9,10,11,12,13,14,15,16,17\]$$ and we want to build a $2$-$4$ $B$-tree. Split the array into groups of $2$ numbers, except that last group that could be $2$ or $3$ numbers. $$\\{1, 2\\}, \\{3, 4\\}, \\{5, 6\\}, \\{7,8\\},\\{9,10\\}, \\{11,12\\}, \\{13,14\\}, \\{15,16, 17\\}.$$

Had the number of groups been an odd number, great. Otherwise, distribute the elements in the last group so that the number of groups becomes odd.

$$\\{1, 2\\}, \\{3, 4\\}, \\{5, 6\\}, \\{7,8\\},\\{9,10\\}, \\{11,12, 13\\}, \\{14,15,16, 17\\}.$$

Label the groups successively as $g\_1, g\_2, \cdots, g\_7$. Let $g\_1$ be the root of the tree. Let the left child of $g\_i$ be $g\_{2i}$ if $2i\le n$ and the right child of $g\_i$ be $g\_{2i+1}$ if $2i+1\le n$. Now we have a complete binary tree where

* each node contains at least 2 number, and
* each internal node has 2 children.

That means, it is a $2$-$4$ $B$-tree.

The example above should provide enough idea so that a full algorithm for general situations should not be too difficult to figure out.

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


# Question
Title: Search Space for Population Metaheuristic Optimization Problem
Given that **x** objects (repetition allowed) can be arranged into **y** configurations, and that the population size is **N**, I am uncertain as to whether the size of the search space is **|S| = |(y^x) * N|** or **|S| = |(y^x)^N|**.

**|y^x|** comes from basic combinatorics: it is the number of ways to arrange **|x|** objects into **|y|** configurations.

As an example, suppose **x** = (1, 2, 3, 4) and **y** = (1, 2, ... 5) and **N** = 100. Clearly, **|x|** = 4 and **|y|** = 5. The **x**s are drawn from some probability distribution (*e.g.*, uniform). A configuration might look like

1 1 3 2 4

Another might be

4 3 1 1 3

for some previously-specified probability distribution. The underlying metaheuristic algorithm generates **N** = 100 such configurations randomly.

I am just unsure on how to incorporate **N**.

# Answer
There are $|x|^{|y|}$ configurations. Then you want to generate $N$ configurations. By the same reasoning, there are $(|x|^{|y|})^N$ ways to do that.
> 0 votes

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


# Question
Title: Multiple paths for a accepting string in NFA?
If a string(w) is accepted by an NFA, then corresponding to w, can there be multiple paths each starting from the start state and ending at an accepting state?

# Answer
> 1 votes
Yes, there can be many paths from the starting state to the ending state. It is not too difficult to cook up many trivial examples of when this happens, for instance

Clearly accepts the string $ab$ but it can go through either $s1$ or $s2$.

However, in DFA's this will never happen because at each state there is only a single possible transition for each character, and those fixed transitions uniquely determine the path.

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


# Question
Title: Is the complexity of problems in NP exponential at most?
I read on Wikipedia the following:

> *Since NP-complete problems are in NP, their running time is at most exponential.*

Is that correct? I thought a problem is in NP-complete if:

* the problem is also in NP (i.e. accept verification in polynomial time)
* Every problem in NP can be reduced to it in polynomial time.

These two conditions don't necessarily limit (to our knowledge) how **hard** a problem in NP Complete can be, right? (other than **bounding** the complexity of **verification** to polynomial time).

What am I missing?

# Answer
> 4 votes
Intuitively, the difficulty of all $\mathsf{NP}$-Complete problems is related: solving any single $\mathsf{NP}$-Complete problem in time $O(t(n))$ immediately yields an algorithm for any other $\mathsf{NP}$-Complete problem with a running time of $O(t(\mbox{poly}(n)))$. This shows, for example, that either all $\mathsf{NP}$-Complete problems admit polynomial-time algorithms or none of them does.

Your first statement "Since NP-complete problems are in NP, their running time is at most exponential" is **NOT** a definition of a $\mathsf{NP}$-Complete problem. It is just a property that NP-Complete problems have.

This is equivalent to saying that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. In fact it is conjectured that the containment is proper, i.e., $\mathsf{NP} \subset \mathsf{EXPTIME}$ . This would imply that there are (decision) problems that can be solved in exponential time but are not in $\mathsf{NP}$. We also know that $\mathsf{P} \subset \mathsf{EXPTIME}$, showing that we must have $\mathsf{NP} \subset \mathsf{EXPTIME}$ if $\mathsf{P}=\mathsf{NP}$.

# Answer
> 4 votes
> (other than bounding the complexity of verification to polynomial time).

This is exactly the reason the problems can be solved in exponential time. An algorithm can simply run the verification algorithm for all possible certificates to see if any one of them is a valid "solution". There are only exponentially many certificates since the definition of $NP$ limits the lengths of certificates to be polynomial. Each certificate can be checked in polynomial time, so we can iterate through all possible certificates and check them in exponential time.

Note that for this purpose, "exponential" means $2^{poly(n)}$ so e.g. $2^{n^2}$ counts as exponential.

---
Tags: complexity-theory, np-complete, np-hard
---


# Question
Title: What's the relationship of $n^n$ and $n!$ complexity with respect to EXPTIME?
We know that:

* $k^n = o(n!)$
* $n! = o(n^n)$

where $o$ refers to "little o notation" (i.e. bounds that are asymptotically **not** tight).

With that in mind:

* Are there any defined or academically established classes for problems with complexity of *at most* $O(n!)$ and $O(n^n)$?
* What is the set relationship for these classes of problems with respect to $\mathsf{EXPTIME}$ or e.g. $\mathsf{2\mbox{-}EXPTIME}$?

# Answer
$\mathsf{EXPTIME}$ is the class of problems solvable by algorithms whose running time is $O(2^{n^c})$ for some $c\>0$. In contrast, $\mathsf{E}$ is the class of problems solvable by algorithms whose running time is $O(2^{cn})$ for some $c\>0$.

These definitions show that problems solvable in time $O(n!)$ or $O(n^n)$ are in $\mathsf{EXPTIME}$, but not necessarily in $\mathsf{E}$.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: An explanation for Barendregt use of Y combinator in an equation
I am going through the following lecture notes on lambda calculus by Barendregt and Barendsen :

http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf

Here at page 12 , after introducing fixed point theorem a small exercise which is an attempt to prove the following has been posted : $ \exists G \forall X $ $GX =SGX $.

It first proceeds to the implication

$Gx$ = $SGx$

which implies : $G$ = $ \lambda x .SGx $

which implies : $G $ = $ (\lambda gx.Sgx)G$

and then it concludes that :

$G$ = $Y$ $( \lambda g x.Sgx)$ where $Y $ is the fixed point combinator .

I am unable to figure out how was G found out to be $Y$ $( \lambda g x.Sgx)$ in the last step ? How was this conclusion reached up to ?

# Answer
> 1 votes
The Y combinator satisfies the equation $Y f = f(Y f)$. Hence $g = Yf$ solves the equation $g = f g$. In your case, the function $f$ is $\lambda g x.Sgx$.

# Answer
> 0 votes
$$ \begin{align} & G=Y(\lambda gx.Sgx) & (\*)\\ & G=(\lambda gx.Sgx) Y (\lambda gx.Sgx) & \text{(by FPT (ii))} \\ & G=(\lambda gx.Sgx)G & \text{(by \*)} \end{align} $$ Therefore $G=Y(\lambda gx.Sgx) \implies G=(\lambda gx.Sgx)G$

---
Tags: lambda-calculus, combinatory-logic
---


# Question
Title: Coding Theory Optimal Code with given max length
Why do we need at least 2 Code Words of the max length in optimal Codes?

Any why do they just differ in their Prefix?

Could someone give me more insight into this?

Have to proof that for a given optimal Code C with max length L there are at least 2 Code Words of max length that just differ in their prefix.

I have nothing to start so some start would be good.

I have no given definition of optimal Code in my script and I don't know if it has to be a block code that I see in most definitions.

# Answer
> 1 votes
So first, some terminology.

A *uniquely decodable code* is a code where every string has at most one decoding.

A *prefix code* is a code where no code word is a prefix of any other. This is an interesting property because it means that the system is uniquely decodable without using lookahead.

A uniquely decodable code is *optimal* if it has minimal average code word length.

An *optimal prefix code* is, just as the name suggest, a prefix code that is also optimal.

The main result that you should know about uniquely decodable codes is the Kraft-McMillan inequality. It states that if you have an alphabet of size $r$ ($r=2$ if the codes are binary), and a uniquely decodable code with code word lengths $l\_1, l\_2, \ldots, l\_n$, then:

$$\sum\_i r^{-l\_i} \le 1$$

And, conversely, for any code word lengths that satisfy the above inequality, there exists a prefix code with the same code word lengths.

Taken together, this means that for every uniquely decodable code, there is an equivalent prefix code.

I'm going to suggest looking at the link above, and work through the proofs. This should give you the head start that you need.

One of the questions that you asked, whether the two maximum-length code words differ only in the prefix, is true for optimal *prefix* codes, but doesn't have to be true for uniquely decodable codes in general. But as noted, for every uniquely decodable code, there is an equivalent prefix code.

---
Tags: coding-theory, proof-assistants
---


# Question
Title: Solving a maze with DFS vs "wall following"
Consider a problem where a "robot cleaner" is placed on a room modeled as a grid. Each cell in the grid can be empty or blocked and all accessible cells are connected, meaning, all empty cells will be **accessible** by the robot regardless of its starting position.

We are told that the robot cleaner can only take one of four actions:

* move forward
* turn left (90 degrees, without moving)
* turn right (90 degrees, without moving)
* clean the current cell in the grid

We are asked to design an algorithm for the robot to clean the **entire room**.

---

My question is: Can this problem be framed as a **maze solving** problem? I mention this because a common strategy (if the maze is simply connected) for maze solving is to be a "wall follower" (e.g. always try right, or always try left), and I wonder if **wall following** would work here.

More generally, why would "wall following" be a good strategy for either problem? Isn't it **enough** to do **DFS** (with backtracking) *even* if we pick an **arbitrary** order of directions that are "left to explore" from each grid position? (or explore directions at a given position in **any** order?)

# Answer
Try it on some simple examples. You'll quickly see why wall following is not sufficient.
> 1 votes

---
Tags: depth-first-search, maze
---


# Question
Title: Is there a way to hash a turing machine?
If we have a Turing machine with various $\delta(q\_i, a\_i) = (q\_j, a\_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which can later be decoded to give us back the deltas) ? It doesn't matter if all the natural numbers map one-to-one to all the Turing machines.

# Answer
Sure. Any Turing machine can be represented as a bit string (print out the description of the Turing machine). Any bit string can be encoded as a natural number (prepend a 1 bit, and view it as a binary representation of a number).
> 2 votes

---
Tags: turing-machines, computability, discrete-mathematics, hash-tables, hashing
---


# Question
Title: Pattern matching on function application
Suppose we have a function `f :: a -> b` and a function `g :: b -> a` such that `f . g = id`. You might say that `g` is the "inverse" of `f` (and vice versa). Could we then pattern match on something like `f x` on the left hand side by replacing occurences of `x` with `g x` on the right hand side? For example:

```
-- Here, (- 3) is the "inverse" of (+ 3), or more generally, (- n) is the "inverse" of (+ n)

subtractThree (x + 3) = x
subtractThree x = (x - 3)

```

This just randomly came to my mind and I'm wondering if there is something fundamentally wrong with this.

Edit: This is my first post here and I'm unsure whether this is the right kind of question for this community. Please don't hesitate to close this if this doesn't belong here.

# Answer
If you are given that $g(f(x))=x$ for all $x$ and $f,g$ are pure functions, then your proposed transformation works. However, the condition $f(g(x))=x$ is not sufficient: consider $f,g:\mathbb{N} \to \mathbb{N}$ given by $g(x)=2x$, $f(x)=\lfloor x/2 \rfloor$. (I'm not sure which your `g . f` notation was intended to capture.)
> 2 votes

---
Tags: functional-programming
---


# Question
Title: Calculating direct sum of 2 binary numbers
If we have say,key=‘0110‘ and =‘1100‘, how will ⊕key mod 2 be calculated and what will be the answer equal to?

# Answer
> 0 votes
The operation $\oplus$ is the same as bitwise XOR. The same symbol is used for direct sum, but there is otherwise absolutely no relation.

---
Tags: arithmetic, binary
---


# Question
Title: How is Memory Segmentation done in 8086?
Basically what I know is that 8086 can address up to 1 MB of locations which are divided in 4 segments(code, data, extra and stack) 64 KB each. But 64 KB * 4 is 256 KB, which doesn't add up to 1 MB(1024 KB). So what about the rest of space.

# Answer
> 1 votes
The four segments you mentioned are not static - these are in fact registers that can point to any 64kb zone in the 1MB memory. By changing the value of these registers we can point to other fragments of the memory.

The exact computation of the effective address is performed using 2 registers: a segment register (CS,DS,SS,ES) and an offset register (usually BX, SI, DI, BP). Each one of those registers is 16bit. To get the 20bit effective address (`EA`) the CPU performs `EA = SEGMENT_REG * 10h + OFFSET_REG` (mod 20bits). It is easy to see that by changing the SEGMENT\_REG/OFFSET\_REG (0000h-FFFFh), the above equation allows one to span the entire 1MB memory address space (00000h-FFFFFh).

# Answer
> 0 votes
The leftmost four bits of a segment register are used to extend 16-bit memory addresses, yielding 20-bit addresses. $2^{20}$ bytes is 1 MB.

---
Tags: computer-architecture
---


# Question
Title: Bob has to find Alices hidden gold by questioning yes/no questions
Suppose that Alice has $n$ places to hide the gold $v\_1, ..., v\_n$ and that Bob knows the probability of each place.

Bob has to ask Alice a series of *yes/no* questions to find the gold.

I have done it this way:

1. We order the places by probability highest to lowest.
2. *Repeat the following:*
    1. Divide them by *two* so we have two sets *High* and *Low* sets
    2. Bob asks whether the gold is in *High*.
    3. Repeat with the places in the correct set.

My professor told me that we have to get that he questions on average $H(V)$ questions, where $H(V)$ is the *entropy*.

But with this I have $2.576$, which is close to $H(V)=2.47$ but it's not $H(V)$.

Are there any better ways?

# Answer
> 2 votes
Consider any strategy for Bob. For each item $v\_i$, let $x\_i$ be binary string composed of the answers that Alice gives to all questions (0 is No, 1 is Yes). You can check that $x\_i$ is a prefix code. If $p\_i$ is the probability of item $v\_i$, then the optimal strategy is the one that minimizes $$ \sum\_i p\_i |x\_i| $$ over all prefix codes $x\_i$ (every prefix code can be translated back to a strategy).

Huffman gave an algorithm which finds the best strategy. The cost $T(V)$ of this strategy satisfies $$ H(V) \leq T(V) \< H(V) + 1. $$ If all $p\_i$ are of the form $1/2^j$, then $T(V) = H(V)$, and otherwise $T(V) \> H(V)$.

Huffman's strategy is "bottom-up", whereas the strategy that you describe is "top-down". It is not optimal in general, but (if you implement halving properly) it is guaranteed to have cost at most $T(V) + 1$, even with an arbitrary ordering of the weights.

(Since you haven't described your halving strategy, I cannot describe an example in which Huffman coding beats your strategy.)

While prefix codes cannot in general reach the entropy exactly, they do reach the entropy in the limit when solving many instances at once. That is, suppose that Alice is actually hiding $N$ items, each chosen according to $V$. Huffman's algorithm produces a strategy whose cost per item is less than $H(V) + 1/N$. In the limit $N\to\infty$, you do get $H(V)$.

---
Tags: coding-theory, entropy
---


# Question
Title: Is it possible to make a Turing Machine that accepts the language $\{\alpha\alpha\alpha | \alpha \in \{a, b\}^∗\}$?
I'm having a lot of problems trying to make a Turing Machine that accept that language, is it even possible to make it? and if so, how can I proceed to make the Turing Machine?

# Answer
> 1 votes
Here is a particularly simple algorithm for the slightly simpler language $\\{\alpha\alpha \mid \alpha \in \\{a,b\\}^\*\\}$; a similar approach works in your case.

The Turing machine starts by checking whether the input is empty (if so, accept) and whether it has even length (otherwise, reject). Next, we are going to find the midpoint of the input. The idea is to put a "chip" on each end of the input, and at each step, advance each chip toward the middle, until the two chips coincide. If done correctly, we can mark the middle of the input, which is the starting point of the second copy of $\alpha$. All that remains to be done is to check that the first half of the input is identical to the second half, which can be done using a simple iteration.

---
Tags: turing-machines
---


# Question
Title: Doubts on the behavior of Unit Type in a type system
I have a doubt about the Unit Type in the context of Type Theory and its use in different case scenarios.

To start with, a Unit Type can be seen as a nullary Product Type, namely Unit, with one only value term which is the empty tuple, `()`. Also, there exist a **unique** map from any type to the Unit.

Now, it happens that the use of the Unit Type goes beyond such trivial definition, and is in fact used in the definition of Algebraic Data Types, which are Sums of Product Types. Specifically, it is possible to represent the concept of an Enumerated Type using a Sum of Unit Types, e.g. in StandardML we might have:

```
datatype suit = HEARTS | CLUBS | DIAMONDS | SPADES

```

where HEARTS, CLUBS, DIAMONDS and SPADES are nullary Product Types and therefore all isomorphic to the Unit.

My doubt is the following: if there exist only one element of Unit, how can the type system distinguish between the four distinct instances used in the Sum Type above (five instances if we also consider the empty tuple...)? I understand that they can be considered all equal to each other up to isomorphism, but they are extensionally different and in fact, even by considering only the `suit` we are supposed to pattern-match on them...

# Answer
The short answer is that isomorphic types are not equal, despite behaving identically, and so the type system can distinguish between them. In a nominal type system, like the one you describe, types are essentially identified by their names, even if they are structurally equivalent. This is the case for the five unit types you describe: they are structurally equivalent, but nominally unequal, and so they are treated as distinct.

Note that the pattern matching aspect is orthogonal: you can think of the five unit types as existing in isolation. In most type theories, you can take the sum of any two types, even two that are (nominally) equal, e.g. `Unit + Unit`. You will still be required to pattern match, and will have two cases: the left `Unit` and the right `Unit`. The nominal aspect is unimportant, although many programming languages will use the names to distinguish between the different cases like this, instead of the indices of the summands (in particular, in languages where you are only allowed to take sums of distinct nominal types, like Standard ML).
> 2 votes

---
Tags: type-theory, type-checking
---


# Question
Title: Relation/use of irrational or transcedental numbers in computer science?
I'm wodering about the relationship between the theory that studies irrational/transcendental numbers and computer science. For example, I found this paper (but was unable to get the full text) Pseudo-random number generator based on irrational numbers

I found the paper because I started looking for a RNG that uses the property that irrational/transc. numbers don't have repeating decimals. I wanted to know in what other ways we can use or have a motivation to study irrational/transcendental numbers, because of their use in CS.

I'm ignorant on the matter, so I appreciate if someone more knowledgeable can provide examples when the two subjects connect themselves. Like the paper above.

# Answer
On the surface that does not strike me as a high-quality paper. I wouldn't recommend it.

I don't think irrational/transcendental numbers are a good approach to building PRNGs. Building PRNGs is tricky business. There are standard PRNGs; I suggest using one of them, rather than trying to invent your own. They all ensure that the output is extremely unlikely to repeat within any reasonable time period.

There is no one theory of irrational/transcendental numbers, and not just one connection to CS; irrational numbers show up in a variety of areas of CS. It's not feasible to give you a complete list; such a list would be far too long. If you just want one example, you might read about the Fibonacci numbers and their connection to the golden ratio (which is an irrational number).
> 1 votes

# Answer
Sometime we can just identify real numbers with their binary expansions. This more or less works well as long as we can exclude the dyadic rationals. As binary expansions of dyadic rationals are clearly not pseudorandom, this means that talking about "(pseudo)random real numbers" makes sense.

Some topics that come up in this context are normal numbers and diophantine approximations. Ted Slaman is a renowned researcher working in this area, and he recently gave a talk on the topic which is available on Youtube here:

https://www.youtube.com/watch?v=V1i6Mn4C5I4&t=6s
> 0 votes

---
Tags: number-theory, applied-theory
---


title: Are these problems NP-Complete?

text:
# Question
Title: Are these problems NP-Complete?
I got 2 decision problem that I need to answer if they are in P or they are NP complete:

> 1.Just like subset sum: given the integers or natural numbers ${\displaystyle w\_{1},\ldots ,w\_{n}}$ does any subset of them sum to precisely ${\displaystyle W}$?

but now instead of $W$:

> does any subset of them sum to $W'$ such: $W-10 \leq W'\leq W+10$ ?

I think this problem is NP complete.

My idea was to create a reduction from subset sum to this problem: I thought to add the all the number between -10 to 10 : {-10,-9,-8....,0,1,2,....10} to ${\displaystyle w\_{1},\ldots ,w\_{n}}$ and now i can find any $W'$.

> 2.Just like 3-dimensional matching: Let X, Y, and Z be finite, disjoint sets, and let T be a subset of X × Y × Z. That is, T consists of triples (x, y, z) such that x ∈ X, y ∈ Y, and z ∈ Z. Now M ⊆ T is a 3-dimensional matching if the following holds: for any two distinct triples $(x\_1, y\_1, z\_1) ∈ M$ and $(x\_2, y\_2, z\_2) ∈ M,$ we have $x\_1 ≠ x\_2, y\_1 ≠ y\_2$, and $z\_1 ≠ z\_2$.

But now:

> each vertex can be in only 3 triples.Is there a $M' ⊆ M$ that is a perfect matching?

I think this problem is in P .to prove this I thought about (hopefully polynomial) algorithm:

`a.take a random vertex and find all the matches that he's in .`

`b.If the vertex is in only 1 match,put this match in M' and delete it form M.
otherwise do nothing.` (and delete all the vertex in this match from the hypergraph and all the matching they are in)

repeat a and b 3 times.It should take $O(3|X||Y||Z||M|)$.

Is my answers right?

# Answer
> 2 votes
Your first problem is $\mathsf{NP}$-Complete. Membership to $\mathsf{NP}$ is trivial. To see that it is $\mathsf{NP}$-hard, you can reduce it from Subset Sum. Let $\langle S\_1, W\_1 \rangle$ be an instance of Subset Sum. Define $S\_2$ as the multiset obtained by multiplying each number in $S\_1$ by $100$, and $W\_2 = 100 W\_1$. The instance for your problem is $\langle S\_2, W\_2 \rangle$.

If there is a set $C\_1 \subseteq S\_1$ such that $\sum\_{x \in C\_1} x = W\_1$, then let $W'$ be the sum of the elements in corresponding subset for $S\_2$. We have $W' = \sum\_{x \in C\_1} 100x = 100 \cdot W\_1 = W\_2 \in \left\[W\_2-10, W\_2+10\right\]$.

If there is a set $C\_2 \subseteq S\_2$ such that the sum $W' = \sum\_{x \in C\_2} x$ of its elements satisfies $W\_2-10 \le W' \le W\_2+10$, then pick $y = W' - W\_2$, so that $W' = W\_2 + y$ and $y \in \[-10, 10\]$. We must have $y=0$ since $W' = W\_2 + y = y \pmod{100}$ and $W'$ must be a multiple of $100$. This shows that $W' = W\_2$ and that the corresponding subset of $S\_1$ has a sum of $\sum\_{x \in C\_2} \frac{x}{100} = \frac{W'}{100} = \frac{W\_2}{100} = W\_1$.

Your second problem is already known to be $\mathsf{NP}$-Complete even when when no vertex occurs in more than three triples. See problem SP1 in "Garey & Johnson, Computer and intractability: a guide to the theory of NP-completeness".

---
Tags: graphs, computability, np-complete, matching
---


# Question
Title: Solving Independent Set through Vertex Cover
I have an Independent Set problem, in which I have to check if given graph has a IS of given size $k$. I've already written a Vertex Cover algorithm a while back and I hope I can reuse it here. Those algorithms are closely related, since if graph $G = (V, E)$ has IS of size $k$ iff it has VC of size $V - k$. So am I right that I can I just use my VC algorithm with $k' = V - k$?

I've read this and this question and after that I've started doubting that this is that simple.

# Answer
> 1 votes
It is that simple, those questions are talking about fixed parameter tractable algorithms w.r.t. the size $k$ of an independent set/vertex cover. Your algorithm will work just fine setting $k' = |V| - k$. Clearly, the new value $k'$ also affects the running time of your algorithm.

---
Tags: algorithms, vertex-cover
---


# Question
Title: Do dynamic/static languages associate types or classes to values or variables?
In Practical Foundation of Programming Languages by Harper

> There have been many attempts by advocates of dynamic typing to distinguish dynamic from static languages. It is useful to consider the supposed distinctions from the present viewpoint.
>
> 1. Dynamic languages associate **types** with **values**, whereas static languages associate **types** to **variables**. Dynamic languages associate **classes, not types**, to **values** by tagging them with identiﬁers such as num and fun. This form of classiﬁcation amounts to a use of recursive sum types within a statically typed language, and hence cannot be seen as a distinguishing feature of dynamic languages. Moreover, static languages assign types to expressions, not just variables. Because dynamic languages are just particular static languages (with a single type), the same can be said of dynamic languages.
> 2. Dynamic languages check types at run-time, whereas static language check types at compile time. Dynamic languages are just as surely statically typed as static languages, albeit for a degenerate type system with only one type. As we have seen, dynamic languages do perform class checks at run-time, but so too do static languages that admit sum types. The difference is only the extent to which we must use classiﬁcation: always in a dynamic language, only as necessary in a static language.

What do the first two sentences in the first part try to say:

* What do dynamic languages associate with values: **types or classes or both**?
* What is the significance of associating types or classes to **values or variables**? Do static languages associate types to variables but not to values? Do dynamic languages associate types or classes to variables besides values?

Thanks.

# Answer
> 1 votes
In those bullets, Harper is addressing common misconceptions about static versus dynamic typing. Each of those bullet points starts with a misconception, and then continues with Harper's clarification.

So, the first misconception is:

> Dynamic languages associate types with values, whereas static languages associate types to variables.

Harper disagrees, and instead says that dynamic languages associate *classes* to values. This comes from a type-theoretic perspective, where it is useful to reserve the notion of a "type" to a particular form of static classification of expressions. In the textbook, Harper defends this perspective by demonstrating that "dynamic types" and "static types" can coexist, and in this way, the two concepts are orthogonal. In particular, there is a special static type which Harper calls **dyn**, and values of type **dyn** are given a tag at runtime which identifies their *class*, i.e. their "dynamic type". (By the way, it's worth mentioning that this tagging mechanism is exactly how dynamic types are implemented in modern languages.) In dynamically typed languages, it is often the case that the static types do not carry very much information, for example all expressions might actually have the static type **dyn**.

The interest in "values versus variables" comes from the "dynamic versus static" perspective on types. If we associate "types" with values, then we can only determine their "type" at runtime. But if we associate types with variables, then we can determine the type of the variable statically. Harper is just trying to point out that there doesn't need to be an issue of "this versus that": dynamic types and static types do not lie on the same spectrum. Simply put, from the perspective of type theory, "dynamic types" are not types.

To sum up, if we take a type-theoretic perspective and make a distinction between types and classes, then we can make this statement: *all languages associate types with both variables and values*. In fact, we can make an even stronger statement, which is this: *all languages associate types with expressions*. Variables and values are just two different forms of expressions.

---
Tags: programming-languages, type-theory, type-checking
---


title: Inorder Successor in Binary Search Tree

text:
# Question
Title: Inorder Successor in Binary Search Tree
This is the problem that I have to solve:

> given a node in a binary search tree, find the node with the smallest key that is greater than the key of the given node..

The algorithm that is often given is this one:

```
bst_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x = y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

```

(you can find further explanations of the problem here.)

Now, I was wondering if this can be another solution:

```
bst_successor(x)
    {
            if(x == NULL)
                    return NULL;
            if(x.right != NULL)
                    return abr_min(x.right)
            y = x.p;
            while(y != NULL && y.key < x.key)
            {
                    y = y.p;
            }
            return y;
    }

```

# Answer
Your code is correct if the key of one node is never equal to the key of a different node.

Otherwise, you code fails to return the correct inorder-successor of the node at the bottom of the following graph.
> 1 votes

---
Tags: algorithms, binary-trees
---


# Question
Title: Bounds on update time in the RMQ problem subject to $O(1)$ query time?
In the static RMQ problem, one has to answer queries about the minimum in a range of a fixed array. A classic variation allows updates of the form $A\_i \leftarrow x $.

My question is : How fast can we update if we must answer queries in $O(1)$?

I can think of a solution which works in $O(\sqrt{n})$ per update :

We can answer queries in $O(1)$ using a sparse table. Since each element is a part of $O(n)$ ranges in the sparse table, we can clearly update a sparse table of an array of size $n$ in $O(n)$. Now, divide into $\sqrt{n}$ blocks. For each block, maintain the prefix and suffix minimums and also a sparse table. Clearly, a block can be updated in $O(\sqrt{n})$. On the upper level, maintain another sparse table which can answer minimum over a range of blocks. Clearly this can also be done in $O(\sqrt{n})$ and the query time is still $O(1)$. The memory used and precomputation done are both $O(n \log{n})$.

Can we do better, say $\text{polylog}(n)$, perhaps using more memory and/or precomputation? Is there a known lower bound?

# Answer
You can divide the whole range into $n^{\frac{1}{3}}$ blocks, and for each block apply your $O\left(\sqrt{n}\right)$ approach. Then you can get $O\left(\sqrt{n^{\frac{2}{3}}}+n^{\frac{1}{3}}\right)=O\left(n^{\frac{1}{3}}\right)$ update time with constant query time.

Recursively, you can get $O\left(n^\epsilon\right)$ update time with constant query time for any **constant** $\epsilon\>0$.
> 0 votes

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


title: Haskell type of lambda expressions

text:
# Question
Title: Haskell type of lambda expressions
I'm new to Haskell and have some general questions.

**Question 1:** The Haskell expression `(\x -> \x -> x)` is the same as the λ-term `λx.λx.x` The type of this expression is `p1 -> p2 -> p2`. What does this mean?

**Question 2:** `λyx.x` is shorthand for `λy.λx.x`. In Haskell `(\y x -> x)` is shorthand for `(\y -> \x -> x)`. Do `(\x x -> x)` and `(\x -> \x -> x)` have the same type in Haskell and why?

# Answer
> 2 votes
Contrary to Church's lambda calculus, Haskell is *typed*.

# Answer 1

When types are denoted with lower-case letters (such as `p1` and `p2`) that indicates a *type variable*. When types are denoted with capital letters (e.g. `Bool` or `Int`) they're concrete types.

The type `p1 -> p2 -> p2` indicates a function in curried form. You can think of it as a function that takes a `p1` value as input and returns a new function of the type `p2 -> p2`, or you can think of it as a function that takes `p1` and `p2` as inputs, and returns `p2` as output. The right-most type indicates the return type.

The types `p1` and `p2` are here unconstrained, which means that they can be literally any type - `Bool`, `Int`, or your own custom type(s). They can also be equal. For example, both `p1` and `p2` could be `Bool`.

The interpretation of `p1 -> p2 -> p2` as a function that takes `p1` as input and returns a function with the type `p2 -> p2` makes most sense. What really happens is that in the expression `\x -> \x -> x` the second `x` *shadows* the first `x`. If you think of the expression as `\x -> (\x -> x)`, you can see that the returned function is `\x -> x`, and that it doesn't matter what the 'leftmost' `x` was. Thus, the type of the leftmost `x` is irrelevant because the value is never used. It'd be more idiomatic to write the expression as `\_ -> \x -> x`. The underscore is Haskell's *wildcard* placeholder, indicating that there's a variable there, but we don't care about it.

In the expression `\x -> x`, however, the input value is being returned unmodified, so that the type *must* be `p2 -> p2` \- i.e. the output type must be the same as the input type.

The expression `\x -> x` is the *identity function*, and it's already built into Haskell as the function `id`. Likewise, a function that ignores its input and instead always returns the same result is called `const`. Thus, the expression `\x -> \x -> x` is equivalent to `const id`.

# Answer 2

The expression `\x x -> x` is invalid in Haskell. It would indicate a (curried) function that takes two arguments, but returns a value. Which one of them? Keep in mind that they could be different.

In Haskell, variables are bound to input arguments, but the binding must be unambiguous. That's the way that the language works, but it's quite a standard design.

For an example of a language that behaves differently you might look to Erlang, where a function that receives two arguments with the same variable name indicates a *pattern-match* where the match only succeeds if the arguments are equal to each other. Erlang is the only language I'm aware of that does it that way, but I only know a handful of languages...

---
Tags: haskell
---


title: Problem related to set partitioning

text:
# Question
Title: Problem related to set partitioning
Let $A\_j=\\{(a^i\_j,b^i\_j)~:~ 0 \leq i \leq n,\text{and } a^i\_j,b^i\_j \in \mathbb{Z}^+\\}$

Given sets $A\_1,\ldots, A\_{p}$ and a positive integer $k$, the problem is to check whether there exists one element $(a^{i\_j}\_j,b^{i\_j}\_j)$ from each $A\_j$ such that $\sum\_{j}^{} a^{i\_j}\_j \geq k$ and $\sum\_{j}^{} b^{i\_j}\_j \geq k$.

It looks like the problem is related to set partitioning problem, however, I am not sure how to get a reduction from set partitioning problem. Can someone help me to find the algorithm to solve this problem?

# Answer
Let $OPT\[t, x\]$ be the maximum value of $\sum\_{j=1}^t b\_j^{i\_j}$ that can be attained by selecting one element $(a\_j^{i\_j}, a\_j^{i\_j})$ from each of the first $t$ sets with the constraint that $\sum\_{j=1}^i a\_j^{i\_j} \ge x$. If the constraint cannot be satisfied, let $OPT\[t, x\] = -\infty$.

According to the above definition we have $OPT\[0, 0\] = 0$ and $OPT\[0, x\] = -\infty$ for $x \> 0$.

For $t\>0$ we have: $$ OPT\[t,x\] = \max\_{i=1, \dots, n} \left( b\_t^i + OPT\[t-1, \max\\{x-a\_t^i, 0\\}\] \right). $$

The answer to your problem is "yes" if and only if $OPT\[p, k\] \ge k$.

Since there are $O(p \cdot k)$ subproblems, each of which can be solved in $O(n)$ time, the overall time complexity of this algorithm is $O(p \cdot k \cdot n)$.

To show that your problem is NP-hard, you can notice that it is a generalization of partition problem: given a set $S = \\{x\_1, \dots, x\_m\\}$ of $m$ non-negative integers, decide whether there is a subset $S'$ of $S$ such that $\sum\_{x \in S'} x = \frac{1}{2} \sum\_{x \in S} x$.

To see this, define $n=2$, $p=m$, $A\_j = \\{ (x\_j, 0), (0, x\_j) \\}$, and $k = \frac{1}{2} \sum\_{x \in S} x$.
> 1 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


title: Language of context-sensitive grammar

text:
# Question
Title: Language of context-sensitive grammar
I have the following context-sensitive grammar:

$$ \begin{align\*} &S \to xSy \mid a \mid b \\ &Xa \to aa \\ &Xb \to bb \\ &Y \to a \end{align\*} $$

I know what it does, as it always ends in $a$ and is preceded by 3 $a$s or 3 $b$s. I'm just not sure how to write this in set notation and would appreciate any help. Would it be something like this? $$ L = \\{a^n,b^m \mid n \ge 1, 0 \< m \le 3 \\} $$

# Answer
There are basically two possible types of derivations:

1. Ones that start $S \to^\* X^naY^n$.
2. Ones that start $S \to^\* X^nbY^n$.

Derivations of the first type will produce $a^{2n+1}$, those of the second type will produce $b^{n+1} a^n$.
> 0 votes

---
Tags: formal-languages, context-sensitive
---


# Question
Title: Finding all rows of 2 variables using Gaussian Elimination
Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution.

During the elimination, I can combine rows together, to produce new rows with different number of variables. Is there a method to find all possible rows that contain exactly 2 variables? For example, I may want to find all equalities between variables. This is equivalent to finding all rows that contain exactly 2 variables. Is it possible to do this without trying all (exponentially many) combinations of rows?

For example if I have:

Row 1: A xor B xor C = 1

Row 2: A xor B xor D = 1

I can combine row 1 and row 2 to say that C xor D = 0

If I have a large amount of rows, and they require large combinations of large rows to produce smaller rows, is it trivial or hard to find all rows of size 2? Can I do better than adding random pairs to the system and checking it still has a solution?

# Answer
> 1 votes
If I understand you correctly, you have a matrix $M$ over $GF(2)$ (the field with two elements), and want to find all linear combinations of rows which have weight exactly $2$.

Using Gaussian elimination, you can bring your matrix into echelon form. This makes it easy to determine, for any particular row, whether it is in the span of the rows of $M$. Since there are only $\binom{n}{2}$ many rows of weight $2$, the entire algorithm will run in polynomial time. (It is likely that this can be optimized further.)

---
Tags: linear-programming
---


# Question
Title: Worst case running time of lexicographical sorting of a list of n strings each of length n using merge sort
This same question has been asked here so many times by several people. This is a problem which was asked in an entrance exam.

And I am having difficulties in digesting the correct answer of this problem. Why is my approach incorrect?

**Here is my approach:**
The divide part of the merge sort recursively divides the list of strings into sub-lists with half number of strings each.

Then the merge part takes sorted lists from two of its child node and merge them into its own sorted list. This merging propagates upwards towards the root and the entire list is eventually sorted.

**The merging works this way:**
The two child-lists together have $(n1+n2) = O(n)$ strings. And for comparing two strings as the part of merging, we need to compare at most $n$ positions (since the strings are of length $n$).

So the merging takes $\theta(n\*n) = \theta(n^2)$

Now the recurrence equation looks like: $T(n)= 2T(n/2) + \theta(n^2)$

Using master method $n^{log\_22}=n$
And $f(n)=\theta(n^2)=\Omega(n^{log\_22})$

Which is case 3 of Master method. so $T(n)=\theta(f(n))=\theta(n^2)$ should be the correct answer.

# Answer
**The mistake and correction**

$$T(n)= 2T(n/2) + \theta(n^2)$$

As you intended, $T(n)$ is the worst time of mergesorting $n$ strings of length $n$. Then, $T(n/2)$ on the RHS means the worst time of mergesorting $n/2$ strings of length $n/2$. So during the mergesort, the length of strings shrinks from $n$ to $n/2$!

What should have been done is using a different variable to express the number of strings at the start of each mergesort. Let us define $T(m, n)$ to be the cost of mergesorting $m$ strings of length $n$. Now, we will have

$$T(m, n)= 2T(m/2, n) + \theta(mn),$$

from which we can deduce $$T(m,n) = \theta(nm\log m).$$

---

**Another correct approach**

Mergesort of $n$ items takes $\theta(n\log n)$ time, assuming a unit cost of comparison. In fact, mergesort uses $\theta(n\log n)$ comparisons. Now that it costs $\theta(n)$ to compare two strings of length $n$ at worst time, the worst time of mergesort of $n$ strings of length $n$ should be $\theta(n\cdot n\log n)$.
> 2 votes

---
Tags: time-complexity, asymptotics, runtime-analysis, mergesort
---


# Question
Title: What is the single type in a dynamic typing language?
Regarding static typing and dynamic typing, Practical Foundation of Programming Languages by Harper says:

> There have been many attempts by advocates of dynamic typing to distinguish dynamic from static languages. It is useful to consider the supposed distinctions from the present viewpoint.
>
> 1. Dynamic languages associate types with values, whereas static languages associate types to variables. Dynamic languages associate classes, not types, to values by tagging them with identiﬁers such as num and fun. This form of classiﬁcation amounts to a use of recursive sum types within a statically typed language, and hence cannot be seen as a distinguishing feature of dynamic languages. Moreover, static languages assign types to expressions, not just variables. Because **dynamic languages** are just **particular static languages (with a single type)**, the same can be said of dynamic languages.
> 2. Dynamic languages check types at run-time, whereas static language check types at compile time. Dynamic languages are just as surely statically typed as static languages, albeit for a degenerate type system with only one type. As we have seen, dynamic languages do perform class checks at run-time, but so too do static languages that admit sum types. The difference is only the extent to which we must use classiﬁcation: always in a dynamic language, only as necessary in a static language.
> 3. Dynamic languages support heterogeneous collections, whereas static languages sup- port homogeneous collections. The purpose of sum types is to support heterogeneity, so that any static language with sums admits heterogeneous data structures. A typical example is a list such as
>
> ```
>  cons(num[1]; cons(fun(x.x); nil))
>
> ```
>
> (written in abstract syntax for emphasis). It is sometimes said that such a list is not representable in a static language, because of the disparate nature of its components. Whether in a static or a dynamic language, lists are type homogeneous, but can be class heterogeneous. All elements of the above list are of type dyn; the ﬁrst is of class num, and the second is of class fun.
>
> Thus, the seeming opposition between static and dynamic typing is an illusion. The question is not whether to have static typing, but rather how best to embrace it. Conﬁning one’s attention to **a single recursive type** seems pointlessly restrictive. Indeed, many so- called untyped languages have implicit concessions to there being more than one type. The classic example is the ubiquitous concept of “multi-argument functions,” which are a concession to the existence of products of the type of values (with pattern matching). It is then a short path to considering “multi-result functions,” and other ad hoc language features that amount to admitting a richer and richer static type discipline.

So "dynamic languages are just particular static languages (with a single type)". What is the single type in a dynamic language?

For example, Python is said to use the reference model of variables, as opposed to the value model of variables. References are not explicit.

* Is it because of references that a list in Python can have elements of different "types", i.e. achieving heterogeneous collections in the quote?
* Is the "single type" in Python the type for all the references? Is it the same for other dynamic typing languages, i.e. is the "single type" in a dynamic typing language the type for all the references? Or is reference just an implementation option of the single type in a dynamic language, and there might be other implementation options?
* Do references which refer to values of different "types" have the same type?

Thanks.

# Answer
The "single type" for Python is called "object" and described in https://docs.python.org/3/reference/datamodel.html:

> Objects are Python’s abstraction for data. All data in a Python program is represented by objects or by relations between objects. (In a sense, and in conformance to Von Neumann’s model of a “stored program computer”, code is also represented by objects.)
>
> Every object has an identity, a type and a value. An object’s identity never changes once it has been created; you may think of it as the object’s address in memory... An object’s type determines the operations that the object supports (e.g., “does it have a length?”) and also defines the possible values for objects of that type... The value of some objects can change. Objects whose value can change are said to be mutable; objects whose value is unchangeable once they are created are called immutable.

Of course, note that "type" and "value" are not used here in the same way as in Harper's book: Python's "type" is what Harper calls "class".
> 4 votes

# Answer
You are able to distinguish between types in a type system, because you admit at least a universe of types, in within types exist (e.g. Product types, Sum types, etc...).

On the other hand, if you have only one type in your universe, then it doesn't matter how you call it or what it is: is the only thing that exists, therefore you can't compare it with anything else.
> 1 votes

---
Tags: programming-languages, type-theory, type-checking
---


# Question
Title: Is longest-path with a specific source and destination impossible in polynomial time?
The problem of finding the longest path in a graph is known to be not be possible in polynomial time, that I am aware of. I am also aware that using DFS or BFS can give the shortest distance between a given origin and destination in a graph. Is it possible to find a longest path from a source vertex to a destination vertex in polynomial time?

# Answer
> 2 votes
The longest-path problem is $\mathsf{NP}$-hard even when a source vertex $s$ and a target vertex $t$ are specified. To see this, you can reduce an instance of (the decision version of) longest path on a graph $G =(V,E)$ with no source/destination specified to (the decision version of) this variant by:

* Adding to $G$ a new path $\langle u\_0, \dots, u\_n \rangle$ of length $n = |V|$, and connecting $u\_n$ to each of the vertices $v \in V$ via the edge $(u\_n, v)$; and
* Adding to $G$ a new path $\langle z\_0, \dots, z\_n \rangle$ length $n$, and connecting each of the vertices $v \in V$ to $z\_0$ via the edge $(v, z\_0)$.

Call the resulting graph $G'$. It is easy to see that there is path of length $k$ in $G$ if and only if there is path from $u\_0$ to $z\_n$ of length $2n + k$ in $G'$.

This shows that, if $\mathsf{P} \neq \mathsf{NP}$ your variant does not admit any polynomial-time algorithm.

If $\mathsf{P} = \mathsf{NP}$, then there is a polynomial time algorithm for the decision version of longest path (given a graph $G$, two vertices $s$ and $t$, and an integer $k$, decide whether there is a path from $s$ to $t$ in $G$ of length at least $k$), which is $\mathsf{NP}$-Complete.

Your version of longest path can then solved in polynomial time by first finding the length $k$ of a longest path $P$ and then recursively guessing the next vertex of $P$: delete $s$ from $G$ and check, for every neighbor $u$ of $s$, whether there exists a path $P'$ from $u$ to $t$ in $G-s$. When you find a $u$ for which the answer is affirmative, solve the problem recursively on $G-s$ to find $P'$ and construct $P$ as $s \circ P'$, where $\circ$ denotes concatenation.

---
Tags: graphs, algorithm-analysis, graph-traversal, polynomial-time
---


# Question
Title: Face recognition system with a sparse dataset
I have a dataset of 100 ID's, each ID with only a single unique face image. How can I develop an effective face recognition system to recognise only these faces?

I was thinking Deep Learning but the dataset is so sparse. It would be 100 classes each with a single data point (the image).

# Answer
> 1 votes
You can apply transfer learning. Leverage one of the existing datasets and deep learning networks that can classify faces e.g. celebrities.

Add/remove layers on top of the feature extraction layers and use your small data set. Provided that the base dataset / network is large and rich enough you should be able to apply it to your dataset.

See https://cs231n.github.io/transfer-learning/

---
Tags: machine-learning, artificial-intelligence, computer-vision, data-sets
---


# Question
Title: Big-O notation for the given function whose runtime complexity grows faster than the input
I struggle to determine the runtime complexity of a function I thought of while trying to solve this LeetCode quiz. The quiz itself goes like this:

*Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.*

*For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 are the first 11 ugly numbers (n=1 up to n=11). On the other hand, 14 does not classify as an ugly number because it has the factors of 2 and 7. The same goes for 33, which has factors of 3 and 11.*

If hypothetically, I come up with a function `isUgly(i)` which can determine whether a given number classifies as an ugly number in O(1) time, I can just brute-force it by testing for every number from 1 to infinity. What would be the algorithmic complexity of such implementation the with respect to the value of `n`?

```
int nthUglyNumber(int n):
  nth = 1
  for i = 1..INFINITY:
    if (isUgly(i)):
      nth++;
    if (nth == n):
      return nth;

boolean isUgly(int i):
  # a function that runs in O(1) time that can determine
  # whether a number classifies as an ugly number by returning true / false

```

The function will return 12 for n=10, and 1536 for n=100 and based on our brute force implementation the function has to iterate 12 and 1536 times to come up with those answers.

We can generalise that if the function returns x for some n, it will have to iterate x times. Therefore, is it acceptable to conclude that this function runs in O(fn(n)) time?

NOTE: There exist a more efficient solution to the problem **but that is not what I'm interested in**. I am here to understand how to describe the algorithmic complexity of the definition above.

# Answer
Yes, if you write a loop like that, and $u(n)$ is the $n$th ugly number, your runtime will be $O(u(n))$.
> 0 votes

# Answer
If you express the runtime relative to the input value, it is O(f(n)). But often we describe the runtime relative to the input size; for k bit input it is $O(f(2^k-1))$.

Now I guess the m-th ugly number is greater than $2^{m^{1/3}}$, so this grows quite quickly. It would grow so fast that divisibility by 2,3 and 5 only cannot be checked in constant time.

Since others will be interested in an efficient solution: an ugly number is either 1 or a smaller ugly number multiplied by 2, 3 or 5. Algorithm:

```
Create a priority queue q.
Add 1 to the queue q.
For k = 1 to m
    Extract the smallest number u from the queue q.
    u is the k-th ugly number.
    Add 2u, 3u and 5u to the queue q.

```

This takes O(m log m) time And O(m) space. Time and space can be greatly reduced by finding a good lower and upper bound for u(m), counting the ugly numbers less than the upper bound in a double loop, and only adding numbers less than the upper bound to the priority queue.

PS You can’t classify a number as ugly in constant time.

PPS. Finding the first n ugly numbers can be done in O(n) operations except that the numbers involved might get large by merging arrays 2k, 3k and 5k in some range. Finding the n-th ugly number might be possible faster than O(n), but that’s tricky.
> 1 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same
Suppose we have a symmetric matrix $A \in \mathbb{R}^{n \times n}$ that has $n-2$ equal eigenvalues and the other two are distinct.

Question: What would be the complexity of its inversion?

On the one hand, if all eigenvalues are the same, then the matrix is equal to $aI$. Therefore, the inversion is $O(n)$.

On the other hand, if we can't assume anything than the inversion is $n^{2+\epsilon}$ where $\epsilon \approx 0.37$.

Note: Eigenvalues and eigenvectors are not given.

# Answer
If the matrix has two distinct eigenvalues, you can find them using power iteration.

Let $\lambda\_1,\lambda\_2$ be the 2 eigenvalues, where $|\lambda\_1| \> |\lambda\_2|$. Then you can use power iteration to find $\lambda\_1$. Next, set $A' = A - \lambda\_1 \text{Id}$. $A'$ is a symmetric matrix with eigenvalues $\lambda\_2,0$, so power iteration on $A'$ reveals $\lambda\_2$.

The running time depends on the exact values of $\lambda\_1,\lambda\_2$; power iteration converges geometrically with ratio $|\lambda\_2|/|\lambda\_1$, so if $|\lambda\_2$ is sufficiently smaller than $|\lambda\_1$, you can obtain a very precise estimate with a fairly small number of iterations; if they are very close, power iteration will be ineffective.

I don't know how to generalize this handle a matrix with three distinct eigenvalues.
> 1 votes

---
Tags: complexity-theory, matrices, linear-algebra
---


title: Defining Grammar for Given Language

text:
# Question
Title: Defining Grammar for Given Language
I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-sensitve grammar, or unrestricted grammar. It also asks that if the grammar is regular or context-free, to write out the exact grammar. I'm not having trouble with two out of the 4 pieces of language. For instance, the easiest one is as follows:

$\\{a^n$ where $n\ge0$, $n\pmod 3 \not= 1\\}$ can be described by the regular grammar $A \rightarrow aA \mid a$

However, the language I am struggling with is:

$$\\{a^n b^m \text{ where } n\>1, m\ge1, n\>m\\}$$

and

$$\\{a^{2n} b^{3n}\text{ where }n\ge1\\}$$

I believe that the first language is context-free because I know that the language $a^nb^n$ is context-free from prior examples and can be described by the grammar $A \rightarrow aAb \mid ab$, however, in this version, $b$ is taken to the $m$ power rather than the $n$ and the bounds for $m$ and $n$ are different, and I'm not sure how that affects the grammar that describes it. Frankly, I'm not sure where to start with the latter piece of language... I don't know how to determine what type of grammar describes it, let alone the grammar itself if it is context-free or regular.

Could anyone help, or at least point me in the right direction?

# Answer
Both of your languages are context-free and not regular. The first one can be generated using the following grammar: $$ S \to a S \mid a S b \mid aab $$ The second one can be generated using the following grammar: $$ S \to aaSbbb \mid aabbb $$

You can show that these languages are not regular using the pumping lemma or using Myhill–Nerode theory. Let me briefly indicate how to do so using the pumping lemma.

For the first language, suppose it were regular. Let $p$ be the constant promised by the pumping lemma. Then the word $a^{p+1} b^p$ is in your language. According to the lemma, it can be written as $xyz$, where $|xy| \leq p$ consists solely of $a$'s, and $y \neq \epsilon$. But then $xy^0z$ is not in your language.

The second language is even simpler, and left to you.
> 1 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: Defining nullable symbols and the first set of a grammar
I'm practicing for an upcoming exam and am being tripped up by a review problem. The problem gives the following grammar:

$$S \rightarrow AB\\$$$ $$A \rightarrow \epsilon | a | (T)$$ $$T \rightarrow T, S | S$$ $$B \rightarrow b$$

As far as I can tell, the only nullable symbol is $A$. It is the only non-terminal whose production contains the null symbol $\epsilon$. I don't think $S$, which contains $A$ in it's production, is a nullable symbol since the same production also contains $B$, which is not a nullable symbol, and both $A$ and $B$ would need to be nullable for $S$ to also be nullable. Is $A$ really the only nullable symbol in this grammar, or am I misinformed?

As for the first set, frankly, I'm just having trouble following my professor's notes for creating the first set. Could anyone help here or point me to a good resource for this?

Thank you all so much.

# Answer
> 2 votes
A nonterminal $X$ is *nullable* if you can generate the empty word from it. For example, since $A \to \epsilon$, we see that $A$ is nullable, while since the only production involving $B$ is $B \to b$, we see that $B$ is not nullable.

In class, you were shown algorithms for determining which nonterminals are nullable. These algorithms are important for computers implementing parsers. Human beings can also use these algorithms to determine which nonterminals are nullable, but (i) outside of a classroom setting, humans never have the urge to determine which nonterminals are nullable, (ii) often it can be determined by "direct inspection".

The first set of a nonterminal consists of all initial terminals in words generated by $X$ (including $\epsilon$, if $X$ is nullable, at least in some definitions). For example, since the only word generated by $B$ is $b$, then $\mathrm{FIRST}(B) = \\{ b \\}$. Similarly, the productions of $A$ immediately imply that $\mathrm{FIRST}(A) = \\{ \epsilon, a, (\\}$. Continuing, since $S \to AB\\$$ is the only production of $S$, then since $A$ is nullable and $B$ isn't, $\mathrm{FIRST}(S) = \\{ a,(,b \\}$. This is the same as $\mathrm{FIRST}(T)$. Here I am implementing the FIRST algorithm in my head, without ever looking at it. Algorithms are necessary for computers, not necessarily for humans.

Summarizing, I suggest focusing on the definitions of *nullable* and *FIRST* rather than on the algorithms that can be used to compute them. It is much more important to understand what you're doing (and why) then to memorize some algorithm which you will never ever use in the future.

---
Tags: formal-grammars
---


title: Prove that a finite language is regular

text:
# Question
Title: Prove that a finite language is regular
I want to prove that $L(G) = \\{01; 11110; 10101; 000\\}$ is regular.

Is it correct if I write there exists a regular expression, which is: $(01|11110|10101|000)$?

How can I also prove it using a DFA?

# Answer
The regular expression is correct.

You can use a trie-like structure, i.e.
> 4 votes

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


# Question
Title: Check if a row is in the span of a matrix
Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations:

A xor B xor C = 1

A xor B xor D = 1

X xor A xor Z = 0

etc...

For a new external row, I want the ability to tell if it is a linear combination of the rows of the matrix, or not. I could do this by computing the augmented matrix, and solving it with Gaussian Elimination.

For example I want to know if this is true or not:

X xor B = 1

Now, suppose I have a lot of rows to test (8 billions). I do not wish to recompute a new augmented matrix each time. I heard there is a way to compute the echelon form once and use it to determine whether a given row is in the span of the matrix or not, but I cannot figure out how.

How easy is it to determine whether a given row is in the span of a matrix in echelon form?

# Answer
> 1 votes
Let your vector be $x$, and let the first row be $r$.

If $x\_1 = 1$ and $r\_1 = 0$, then $x$ is not in the span.

If $x\_1 = 0$ and $r\_1 = 1$, then $r$ cannot be part in any linear combination that results in $x$, so we can remove $r$ and continue.

If $x\_1 = 0$ and $r\_1 = 0$, then we can remove the first column and continue.

If $x\_1 = 1$ and $r\_1 = 1$, then for $x$ to be a linear combination of the rows, $r$ must be one of the rows in the linear combination. So we can replace $x$ with $x \oplus r$, remove the first row and column, and continue.

---

You can also present this algorithm in an iterative manner.

Let $i$ be the index of the first $1$ in $x$. For $x$ to be in the span, there must be a row whose first $1$ is also at index $i$. Find this row $r$, replace $x$ with $x \oplus r$, and continue, until eventually $x = 0$.

---
Tags: linear-programming
---


# Question
Title: Algorithm to partition students in two groups maintaining brotherhood (related to COVID19 pandemic)
I need to find an algorithm for the following problem. Any idea to which kind of algorithm to look for as starting point is welcomed. Should I look for a graph algorithm? Combinatorial problem? Mathematical or dynamic programming?

# Objective:

I have a set of 48 classes with 25 students each. I need to divide each class in two groups, lets call them A and B. There are the following constrains:

* Some students have brothers/sisters in other classes. I need that all brother/sister be in the same partition A or B. This should be a hard condition that must be fulfilled by the solution.
* A second constrain is that girls and boys should be equally divided in the both partitions of **each class**. If class 12 has 11 boys and 14 girls; the partition should be: partition 12A with 6 boys and 12 girls and partition 12B with 5 boys and 12 girls. This constrain is not hard, it may be violated by the solution slightly.

## What if the number of constrains increases a lot.

In the comments, it is suggested to use a greedy algorithm, because it is easy to move students with no constrains (no siblings) from one partition to another. What to do if the number of constrains is very high. For some reason we have a lot of constrains of the type: studentA can't be in the same partition of studentB, ... What algorithmic approach is best?

# Some numbers:

There are around 1200 students, divided in 16 `years`. Each year has 3 classes. The ratio girls and boys is, as expected, 1:1. There should be between 500 and 600 brother/sister relations.

# Background:

Due to the COVID19 pandemic it is possible that next school year, students may be separated in two groups. These groups will alternate going to school and staying at home. To easy the logistics for parents, it may be desirable to have all siblings in the same group, going to school or staying at home.

# Answer
The *very general problem* is (weakly) NP-complete if you want the optimal solution, however, in general there aren't arbitrarily large sibling cliques.

The problem can always be modeled as an integer linear program (ILP).

If you just want a *good enough* solution, then I would start with a greedy algorithm, followed by local search. You can always keep the local search (with random restarts) running over the night in hope for ever better solutions.

Since you seem to have added some more constraints in comments, if the constraints are really hard constraints, you can *consider* using an off-the-shelf ILP solver.

---

For illustrative purposes, I picked the first I could (cvxpy) find in a programming language I am familiar with (Python). I am not familiar with ILP solvers, so I have no idea if this is a good choice. (Note that it is not actually a solver, but an interface for several solvers.)

So I wrote a short example just to get you started. It can be done in about 50 lines.

There are $2 \cdot N$ variables:

1. $N$ variables representing the $N$ students
2. $N$ variables representing their genders (linked through a constraint)

There are *two* constraints:

1. siblings need to be in the same partition
2. a helper-constraint to make the balancing of genders simpler

The optimization is basically to optimize (minimize)

$$2 \cdot (N/2 - \sum{s})^2 + (N/2 - \sum{g})^2,$$

where $\sum{s}$ is the number of students put in partition 0 and $\sum{g}$ is the number of *girls* put in partition 0.

**caveat emptor**

```
from collections import namedtuple, Counter
import random
import cvxpy as cp

Student = namedtuple("Student", "name level gender")

def generate_students(N=100):
    # generate random data
    students = [Student(i, 1, random.choice("MF")) for i in range(N)]

    siblings = []
    for i in range(0, N // 2, 3):
        siblings += [(i, i + 1), (i, i + 2), (i + 1, i + 2)]
    return students, siblings

def create_variables(students):
    """Return stud_var and gender_var.

    These will be constrained to be set to the same value, i.e.

    stud[i] == gender[i].

    This is to ensure that we can easily count gender-difference in
    addition to "normal" difference.

    """

    stud_vars = [cp.Variable(1, boolean=True) for s in students]
    gender_vars = [cp.Variable(1, boolean=True) for s in students]
    return stud_vars, gender_vars

def create_constraints(stud_vars, gend_vars, students, siblings):
    stud_const = [stud_vars[l] == stud_vars[r] for (l, r) in siblings]
    link = [stud_vars[i] == gend_vars[i] for i in range(len(stud_vars))]
    return stud_const

def create_objective(stud_vars, gend_vars):
    mid = len(stud_vars) // 2
    objective = cp.Minimize(
        2 * (mid - cp.sum(stud_vars)) ** 2 + (mid - cp.sum(gend_vars)) ** 2
    )
    return objective

students, siblings = generate_students()
stud_vars, gender_vars = create_variables(students)
constraints = create_constraints(stud_vars, gender_vars, students, siblings)
objective = create_objective(stud_vars, gender_vars)
prob = cp.Problem(objective, constraints)

result = prob.solve()
if result is None:
    exit("Could not find feasible solution.")

print(round(result))
print(Counter(int(round(e.value[0])) for e in stud_vars))

def get_gender_count(partition):
    lst = [
        students[idx].gender
        for (idx, s) in enumerate(stud_vars)
        if round(s.value[0]) == partition
    ]
    return Counter(lst)

print("Partition 0:", get_gender_count(0))
print("Partition 1:", get_gender_count(1))

# for idx, e in enumerate(stud_vars):
#    print(students[idx], "\tPartition", int(round(e.value[0])))

for (l, r) in siblings:
    lv = int(round(stud_vars[l].value[0]))
    rv = int(round(stud_vars[r].value[0]))
    assert lv == rv

```

Running the snippet output:

```
(e375) [ubuntu ~/textnik]$ time python textnik.py
297.0
Counter({0: 52, 1: 48})
Partition 0: Counter({'F': 27, 'M': 25})
Partition 1: Counter({'F': 25, 'M': 23})

real    0m4,060s
user    0m4,926s
sys 0m1,189s

```

meaning that it put 52 students in one group and 48 in the other, with 27/25 F/M in the first group and 25/23 F/M in the other group.

All the siblings should be in the same group by constraints.
> 2 votes

---
Tags: algorithms, graphs, dynamic-programming, combinatorics
---


# Question
Title: Is grammar that describes an equation in prefix (Polish) notation always unambiguous?
I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \\, 5 \\, * \\, 4 \\, 3$ using the following grammar and rightmost derivation:

$$Expr \rightarrow + \\, Expr \\, Expr \\, | \\, * \\, Expr \\, Expr \\, | \\, 0 \\, | \\, \dots \\, | \\, 9 \\,$$

While I have no trouble taking the derivation and creating its parse tree, the question also asks whether the grammar is ambiguous. In the scope of what I've been taught, my only tool for proving ambiguity has been to find a different parse tree for whatever leftmost or rightmost derivation I have, thus proving multiple valid parses and ambiguity. However, I have not been told how to *prove* unambiguity. I am fairly confident that the grammar described above is unambiguous based partially on intuition, and partially because it's designed for prefix notation. I tried to generate new trees for a given string to prove ambiguity, but since the operator is always leftmost, I could not find any string in which multiple parse trees could be created. If I am mistaken, please let me know.

My question is this: Is it possible for grammar that describes strings using prefix (Polish) notation such as the one above to ever be ambiguous? My intuition tells me that it will always be unambiguous, but I was wondering why this might be the case.

# Answer
> 1 votes
Your question is easy to answer. Take your grammar, and add the following rules: $$ \begin{align\*} &S \to T \mid \mathit{Expr} \\ &T \to \mathit{Expr} \end{align\*} $$

Your particular grammar, however, does seem unambiguous.

Here is how I would try to prove it. First, show the expressions are self-delimiting: no expression is a prefix of another one.

Now, when trying to parse an expression, you can determine which rule should be applied first by looking at the first symbol. In the interesting cases, you then have to partition the input into two expressions. The self-delimiting property should make this possible in a unique way.

---
Tags: formal-grammars, notation, ambiguity
---


# Question
Title: Time complexity of Vertex Cover vs Clique for fixed k
I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$:
\- Vertex Cover algorithm running in $O^\*(1.47^{V - k})$ (optimized recursive algorithm)
\- Clique algorithm running in $O({V\choose k})$ (simple enumerate subsets of $V$ and check algorithm)

How can I determine which one has a lower time complexity? I'm not very familiar with algorithms for NP-complete problems and $O^\*$ notation. Would plotting those functions suffice? I think that VC algorithm can have any polynomial $n^{O(1)}$ as a multiplication because of the $O^\*$ notation and this could affect the running times, but I'm not sure.

# Answer
For any fixed $k$, $O(\binom{V}{k}) = O(V^k)$ is polynomial, whereas $O^\*(1.47^{V-k}) = O^\*(1.47^V)$ is exponential. Exponentials grow much faster than polynomials.

Plotting the curves is not so helpful, since these are asymptotic statements.

That said, if you're interested in *particular* $V$ and $k$, then your best option is to empirically check which of these algorithms is faster. Asymptotic notation is not helpful here, since it hides constant factors, and these could make a big difference for concrete values of $V$ and $k$.
> 2 votes

# Answer
Vertex Cover is fixed-parameter tractable. There is a simple $2^k n$ algorithm to find a VC of size $k$. This should beat the naive algorithm. The current state of the art is something like $1.24^k n$.

Under some assumptions there is no algorithm for k clique with running time $f(k) n^c$.

If your graph has some special structure the results can be improved.
> 1 votes

---
Tags: complexity-theory, time-complexity, big-o-notation, vertex-cover
---


# Question
Title: Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)
You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern: X1,X2,X3...Xn,Xn,...X3,X2,X1 where Xi is some character of S. The only constraint is that no adjacent character should be the same except Xn, that is Xi != X(i+1) for all 1\<=i\< n.

Input: The string: S
Output: The integer: 2n
Constraint: 1\<=|S|\<=10^3

Sample input 1: "acdbdea"
Sample output 1: 4
Explanation: "adda" is the longest subsequence following the given pattern.

Sample input 2: "abbacdeedc"
Sample output 2: 6
Explanation: "cdeedc" is the longest subsequence following the given pattern.

Sample input 3: "taker"
Sample output 3: 0
Explanation: No subsequence follows the given pattern.

---

This question was asked in a coding interview and I didn't know how to solve it. I understood how to find the longest palindromic subsequence but don't know how to implement the distinct adjacent character part. Please help. Pseudocode is fine.

# Answer
**Golden Rule**

Here is the golden rule of dynamic programming.

*When solutions to smaller subproblems cannot be combined into solutions to larger subproblems because of missing information, extend the subproblems by **adding parameters** that give that missing information.*

---

**First attempt**

$S$ is a sequence of $n$ letters or, $S\[0:n\].$

Let $L\[i\]\[j\]$ be the length of the longest palindromic subsequence of $S\[i:j\]$. It is easy to figure out the base cases and, by increasing $i$ and/or decreasing $j$, the recurrence relations for $L\[i\]\[j\]$.

Now add the condition of even length. Let $E\[i\]\[j\]$ be the length of the longest even-length palindromic subsequence of $S\[i:j\]$. We can figure out the base cases and the recurrence relations for $E\[i\]\[j\]$, similar to those of $L\[i\]\[j\]$.

Now add the condition of distinct adjacent letters, i.e., no letter can appear twice in a row except the letter at the center. Let $D\[i\]\[j\]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S\[i:j\]$. As you might have noted, we cannot figure out the recurrence relations for $D\[i\]\[j\]$, since extending such a subsequence to a longer one might introduce repeated letters.

The golden rule comes to rescue. Add another parameter that classifies the letter at the end of the longest subsequence found so far, so that we can determine how to extend that subsequence properly.

Let $D\[i\]\[j\]\[\lambda\]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S\[i:j\]$ that ends in letter $\lambda$. That is, we will compute $D\[i\]\[j\]\[\text{'}a\text{'}\]$, $D\[i\]\[j\]\[\text{'}b\text{'}\]$, $D\[i\]\[j\]\[\text{'}c\text{'}\]$, $\cdots$, $D\[i\]\[j\]\[\text{'}z\text{'}\]$.

* The final answer is the larger of $\max\_\lambda D\[0\]\[n-1\]\[\lambda\]$ and $0$.
* Suppose the first $\text{'}a\text{'}$ in $S$ at or after $S\[i\]$ appears at $S\[\vec {i\_{\text{'}a\text{'}}}\]$. Suppose the first $\text{'}a\text{'}$ in $S$ appears at $S\[\overleftarrow{j\_{\text{'}a\text{'}}}\]$ before $S\[j\]$ searched backwards. $\vec {i\_{\text{'}a\text{'}}}$ or $\overleftarrow{j\_{\text{'}a\text{'}}}$ is set to $-1$ if $\text{'}a\text{'}$ is not found respectively. We have, for $j\ge i+2$,

$$D\[i\]\[j\]\[\text{'}a\text{'}\] = \begin{cases} \max(2, 2 + \max\_{\mu\not=\text{'}a\text{'}}D\[\vec {i\_{\text{'}a\text{'}}}+1\]\[\overleftarrow{j\_{\text{'}a\text{'}}}\]\[\mu\])& \text{ if } 0\le \vec{i\_{\text{'}a\text{'}}} \lt \overleftarrow{j\_{\text{'}a\text{'}}},\\ -1 & \text{ otherwise,}\\ \end{cases} $$ where $\mu$ runs through all lowercase English letters.
* The base case is $$D\[i\]\[i\]\[\text{'}a\text{'}\] = 0.$$

Generalizing $\text{'}a\text{'}$ to variable $\lambda$, we can write the recurrence relation and base case for $D\[i\]\[j\]\[\lambda\]$.

Note that with the extra information embodied in the $\lambda$ parameter, it is easy to deduce the recurrence relation.

While this attempt is successful, we can do better.

---

**Second attempt**

We can simplify the subproblems.

Let $F\[i\]\[j\]$ be the length of the longest such subsequence that starts at $S\[i\]$ and ends at $S\[j\]$. Then we have

$$F\[i\]\[j\] = \begin{cases} \max(2, 2 + \max\_{\mu\not=S\[i\]}F\[\vec{i\_\mu}\]\[\overleftarrow{j\_\mu}\])&\text{ if } S\[i\] = S\[j\],\\ -1 & \text{ otherwise,}\\ \end{cases} $$ where $-1$ stands for "Not Found". For all lowercase English letter $\mu$, $S\[\vec{i\_\mu}\]$ is the first $\mu$ that appears after $S\[i\]$, and $S\[\overleftarrow{j\_\mu}\]$ is the first $\mu$ that appears before $S\[j\]$ searched backwards. If one of them cannot be found, the term $F\[\vec {i\_\mu}\]\[\overleftarrow{j\_\mu}\]$ is ignored.

The final answer is the larger of $\max\_{i, j} F\[i\]\[j\]$ and 0.
> 1 votes

---
Tags: dynamic-programming, strings, subsequences
---


# Question
Title: Can uniqueness of strings (each with an equal number of 1's and 0's) be decided in logspace?
Let `k` be a positive even integer.

Given a list of `(k choose k/2)` `k`-sequences, each with an equal number of `1`'s and `0`'s, is distinctness decidable in logspace if we're only allowed to read the input once?

In more detail:

Let a sequence have `k` bits.

Let each sequence have an equal number of `1`'s and `0`'s.

There are `(k choose k/2)` such sequences.

Suppose I have a list of sequences.

Suppose there are `(k choose k/2)` sequences in the list.

Can we decide each sequence is distinct from the others in logspace?

If we can read the input multiple times, we can use two logspace counters - and ensure each sequence is not equal to the sequences that follow.

What if we're only allowed to read the input once?

# Answer
Hint: let $n={k \choose k/2}$. Consider the state of the algorithm after reading $n/2$ of the sequences. How many possible states are there, that it could be in at that point?
> 1 votes

---
Tags: complexity-theory, space-complexity
---


title: Algorithm Analysis of Three nested loop

text:
# Question
Title: Algorithm Analysis of Three nested loop
I'm trying to figure out Time function and Big O of a nested loop code,

```
public static int example5(int[ ] first, int[ ] second) { // assume equal-length arrays
  int n = first.length, count = 0;
  for (int i=0; i < n; i++) { // loop from 0 to n-1
    int total = 0;
    for (int j=0; j < n; j++) // loop from 0 to n-1
      for (int k=0; k <= j; k++) // loop from 0 to j
      total += first[k];
  if (second[i] == total) count++;
}
  return count;
}

```

According to my calculations the time function should lie in $n^4$, but the right answer is $n^3$.
Here are my solution steps,

1. Constant operations = **2 times**
2. i-loop = 0 to n-1 = **n times** (although it's 2n+2, but I would pick the most higher order term)
3. Constant operation = **1 time**
4. j-loop = 0 to n-1 = n x n times = **$n^2$ times**
5. k-loop = 1+2+3+...+n-1+n = n x n x $n\frac{n+1}{2}$ times = **$\frac{n^4 + n^3}{2}$ times**

What I'm doing wrong, can someone please point out.

# Answer
Three for loops gets you to n^3.

EDIT:

for (int i=0; i \< n; i++) // first n ..etc.. for (int j=0; j \< n; j++) // second n ...etc...

Outer two are n, that makes n^2 so far. Next look at inner loop:

for (int k=0; k \<= j; k++) // third n

Innermost counts as another n for big O purposes even if running k to j instead of k to n. You're still on the order of n^3.

For that inner loop you're doing 1 + 2 + 3 ... loops as j iterates, so strictly speaking it's not exactly n^3 iterations, but n * n * (n+1)/2, but for big O purposes don't let that throw you off, it's n^3, the (n+1)/2 piece is just another layer of n. If n was 1,000,000 you'll end up with "on the order of" 10^18 loops.

Hope this helps.
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, algorithm-analysis, runtime-analysis
---


# Question
Title: Buying ingredients for a cake from many different stores and need to minimise the number of stores - algorithm name?
So let's say I'm baking a cake and it has a few ingredients (including multiples):

```
ingredients = {sugar, sugar, baking powder, chocolate, flour, egg, egg}

```

I can go to a bunch of different stores to buy the ingredients. Each store has a different collection of ingredients to offer:

```
store_1 = {sugar, vanilla extract, olive oil, chocolate}
store_2 = {chocolate, chocolate, flour, egg}
store_3 = {flour, baking powder, sugar, sugar, sugar, egg}

```

Problem: I want to buy all the ingredients for the cake from the **minimum** number of stores

I'm sure this is a common problem with existing algorithms, but I can't seem to find anything besides the bin packing problem. It is a similar problem but not quite the same.

Any ideas would be appreciated.

# Answer
> 1 votes
If it was not for multiples the problem would be Set Cover. With multiples, a natural name would be Multiset Cover though I cannot say I have encountered this name before.

Obviously, Multiset Cover has Set Cover as a special case. Hence (the decision variant of) it is NP-hard and you will not find a truly efficient algorithm. On the other hand, Multiset Cover can be seen as a special case of integer linear programming in the same way that cover problems generally can.

# Answer
> 0 votes
It's called the set multicover problem. Each element e has an integer demand requirement d(e). When your d(e) all = 1 you're back to vanilla cover problem.

One algorithm to solve is Exact Set Multi-Covering (ESMC):

https://www.sciencedirect.com/science/article/pii/S0304397509003880

The authors also have a more recent paper "Dynamic programming based algorithms for set multicover and multiset multicover problems" on the topic.

---
Tags: algorithms, optimization
---


# Question
Title: How to find a condition which leads to deadlock in non-reentrant locks
A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

* A. x=1,y=2
* B. x=2,y=1
* C: x=2,y=2
* D: x=1,y=1

Though, answer is option D but is there any possibility to have deadlock in other 3 options. If yes, then what it is because not able to visualize other options. Kindly explain.

# Answer
> 1 votes
A single thread can get itself deadlocked by locking the same lock twice without an unlock in between. Which is obviously a stupid thing to do.

Why A-C are not solutions: Read the question carefully. It asks for the MINIMUM value of x and y. Since x=1, y=1 can lead to deadlock, the others are not MINIMUM values. Of course you can have a deadlock in every case, but x, y are not minimum values.

---
Tags: operating-systems
---


# Question
Title: Disjoint union of NP-hard problem and P problem is NP-hard
> Let $Σ = \\{0, 1\\}$ and let $A, B ⊆ Σ^\*$ be languages. Prove that if $A$ is NP-hard, $B$ is in P, $A ∩ B = ∅$, and $A ∪ B ≠ Σ^\*$, then $A ∪ B$ in NP-hard.

How can I go about proving $A ∪ B$ is NP-hard given the conditions? Any help would be appreciated.

# Answer
> 4 votes
Let $L$ be any language in NP. Since $A$ is NP-hard, there is a polytime reduction $f$ such that $x \in L$ iff $f(x) \in A$. We want to convert $f$ to a polytime reduction $g$ such that $x \in L$ iff $g(x) \in A \cup B$.

What prevents $f$ from working? Let's consider three cases:

* $f(x) \in A$. In this case, $f(x) \in A \cup B$ as well.
* $f(x) \notin A$, and also $f(x) \notin B$. In this case, $f(x) \notin A \cup B$ as well.
* $f(x) \notin A$, but $f(x) \in B$. In this case, $f(x) \in A \cup B$. This is the problematic case.

The difficult case is $f(x) \in B$. Fortunately, since $B$ is in P, we can test whether this case happens. When it does, we would like to output something which is not in $A \cup B$. Here it is helpful (and necessary!) that $A \cup B \neq \Sigma^\*$. Indeed, we can pick some arbitrary $z \notin A \cup B$, and choose this as our output when $f(x) \in B$.

Here is what the updated reduction looks like: $$ g(x) = \begin{cases} z & \text{if } f(x) \in B, \\ f(x) & \text{otherwise}. \end{cases} $$ Does this work? Let us prove that it does.

If $f(x) \in B$, then *since $A$ and $B$ are disjoint*, we are guaranteed that $f(x) \notin A$, and so $x \notin L$. In this case $g(x) = z \notin A \cup B$, as needed.

If $f(x) \notin B$ then $g(x) = f(x)$, and moreover $g(x) = f(x) \in A \cup B$ iff $f(x) \in A$ iff $x \in L$, again as needed.

Finally, note that $g$ can be implemented in polynomial time, since $f$ can be so implemented, and $B$ is in P.

# Answer
> 3 votes
Given an instance $x$ of $A$, reduce it to an instance $y$ of $A \cup B$ as follows:

* Check (in polynomial time) if $x \in B$, if the answer is yes, then $x \not\in A$ since $A \cap B = \emptyset$. Pick any $y \in \Sigma^\* \setminus (A \cup B)$ (which is non-empty by hypothesis).
* If $x \not\in B$, then $x \in A \cup B \iff x \in A$. Pick $y=x$.

---
Tags: complexity-theory, np-hard
---


# Question
Title: Would it be possible for a new technology to make RAM obsolete?
If a new technology is invented for storage devices, which is the same as or speeder than RAM (bandwidth&lanecy), is it possible to make RAM obsolete and consider the storage device as the main memory?

if that happened data and program would run directly from the storage device, or the RAM or its concept (especially as temporary space) must be part of the storage device such as at the beginning addresses.

# Answer
> 2 votes
There is nothing special about RAM. Before electronic computers were invented, mechanical data sorters and tabulators used punched cards as their main (and only) memory. Early electronic computers used many different technologies for their main memory, including vacuum tubes, acoustic delay lines filled with mercury, the screen of a cathode ray tube and tiny rings of magnetic material looped around wires. If a memory technology was developed that was just as reliable as solid-state RAM and at the same time significantly faster and/or cheaper then it could certainly replace RAM and make it obsolete.

---
Tags: computer-architecture, memory-hardware
---


title: Sums of $2^{-l}$ that add to 1

text:
# Question
Title: Sums of $2^{-l}$ that add to 1
Consider the following problem:

> You are given a finite set of numbers $(l\_k)\_{k\in \\{ 1, ..., n \\}}$ such that $\sum\_{k=1}^n2^{-l\_k}\<1$. Describe an algorithm to find a set $(l'\_k)\_{k\in \\{ 1, ..., n \\}}$ such that $\forall k \in \\{ 1, ..., n \\}:l'\_k\le l\_k$ and $\sum\_{k=1}^n2^{-l'\_k}=1$.

(For what it's worth, this is a problem arising from Information Theory, where the Kraft-McMillan Theorem gives that the result above yields a more efficient binary code than the one with codeword lengths $(l\_k)$.)

Here are my initial thoughts. We can consider $\sum\_{k=1}^n2^{-l\_k}$ as a binary number e.g. $0.11010011$ and then we need to reduce the value of some $l\_k$ values whose digit position is preceded by a $0$. So for instance, with the initial $0$ in the $\frac{1}{8}$ position of the example number I gave, we want to decrease the value of some $l\_i=4$ to $l'\_i=3$ to add $\frac{1}{8}$ and subtract $\frac{1}{16}$ to the sum. We then have $0.11100011$, so we've moved the problematic $0$ along a digit. When we get to the end we presumably have something like $0.11111110$, and then need to reduce the value of the longest codeword by 1 to get the overflow to $1.00000000$.

However, I encounter two problems: there may not be such an $l\_i=4$, for instance, if the $1$ in the $\frac{1}{16}$ digit place arises as the sum of three $l\_i=5$ numbers. Additionally, if we multiple have $0$ digits in a row then we presumably need to scan until the next $1$ and then decrement a corresponding $l\_i$ multiple times, but it's conceivable that I would "run out" of large enough $l\_i$ codewords that I can manipulate in this way.

Can anyone describe an algorithm with a simple proof of correctness?

A follow-up problem: how do we generalise this algorithm to bases other than $2$?

# Answer
> 3 votes
Here is a very simple algorithm. We will require the following lemma.

**Lemma.** Suppose that $1 \leq \ell\_1 \leq \cdots \leq \ell\_k$ and $\sum\_{i=1}^k 2^{-\ell\_i} \geq 1/2$. Then there exists $r \in \\{1,\ldots,k\\}$ such that $\sum\_{i=1}^r 2^{-\ell\_i} = 1/2$.

**Proof.** Let $r$ be the first index such that $\sum\_{i=1}^r 2^{-\ell\_i} \geq 1/2$. Since the $\ell\_i$ are non-decreasing, there are integers $A,B$ such that $$ \begin{align} \sum\_{i=1}^{r-1} 2^{-\ell\_i} &= \frac{A}{2^{\ell\_r}}, & \sum\_{i=1}^r 2^{-\ell\_i} &= \frac{B}{2^{\ell\_r}}. \end{align} $$ Moreover, $A \< 2^{\ell\_r-1}$ and $B \geq 2^{\ell\_r-1}$. Since $B-A=1$, we conclude that $B = 2^{\ell\_r-1}$, and so $\sum\_{i=1}^r 2^{-\ell\_i} = 1/2$. $\quad\square$

This suggests the following algorithm. We can assume that your sequence is sorted, that is, we are given a sequence $\ell\_1 \leq \cdots \leq \ell\_k$ such that $\sum\_{i=1}^k 2^{-\ell\_i} \leq 1$. We now consider three cases:

1. $\sum\_{i=1}^k 2^{-\ell\_i} = 1$. In this case, there is nothing to do.
2. $\sum\_{i=1}^k 2^{-\ell\_i} \leq 1/2$. In this case, we can decrease each $\ell\_i$ by $1$.
3. $1/2 \leq \sum\_{i=1}^k 2^{-\ell\_i} \leq 1$. Applying the lemma, we find $r$ such that $\sum\_{i=1}^r 2^{-\ell\_i} = 1/2$, and so $\sum\_{i=r+1}^k 2^{-\ell\_i} \leq 1/2$. We thus have to solve the same kind of problem for the second half $\ell\_{r+1},\ldots,\ell\_k$, aiming at $1/2$ rather than $1$.

To implement this recursion more cleanly, we add a parameter $s$, and our goal is to correct a sequence satisfying $\sum\_i 2^{-\ell\_i} \leq 2^{-s}$ to one satisfying $\sum\_i 2^{-\ell\_i} = 2^{-s}$ by only decreasing elements.

---

Here is how the algorithm works in the case of the sequence $1,2,4,7,8$, which matches your example. The sum in your case is more than $1/2$, so we separate the sequence into two parts: $1$ and $2,4,7,8$. We only handle the second, aiming at a sum of $1/2$.

The sum in the case of $2,4,7,8$ is more than $1/4$, so we separate the sequence into two parts, $2$ and $4,7,8$, and only handle the second, aiming at a sum of $1/4$.

The sum in the case of $4,7,8$ is less than $1/8$, so we decrement each element, obtaining the sequence $3,6,7$, whose sum is more than $1/8$. We separate it into $3$ and $6,7$, and only handle the second, aiming at a sum of $1/8$.

We decrement $6,7$ twice, obtaining the sequence $4,5$ whose sum exceeds $1/16$. We separate it into $4$ and $5$, and decrement the latter once.

Putting everything together, we obtain the sequence $1,2,3,4,4$.

---

In the $q$-ary case, we have to change the problem somehow, since the result is not true in general. For example, take $q = 3$ and consider the sequence $1, 1$.

---

Here is another simple algorithm, based on the following lemma.

**Lemma.** Suppose that $0 \leq \ell\_1 \leq \cdots \leq \ell\_k$ and $\sum\_{i=1}^k 2^{-\ell\_i} \< 1$. Then $\sum\_{i=1}^{k-1} 2^{-\ell\_i} + 2^{-(\ell\_k-1)} \leq 1$.

**Proof.** Since the $\ell\_i$ are nondecreasing, we can write $\sum\_{i=1}^k 2^{-\ell\_i} = A/2^{\ell\_k}$, where $A \< 2^{\ell\_k}$. Replacing $\ell\_k$ with $\ell\_k-1$ increases the sum by $1/2^{\ell\_k}$. Since $A+1 \leq 2^{\ell\_k}$, the sum remains at most $1$. $\quad\square$

This suggests the following simple algorithm: repeatedly decrement the largest $\ell\_i$. The algorithm necessarily terminates since at most $\sum\_i \ell\_i$ iterations can take place.

Let us apply this on our example above: $$ \begin{align} &1,2,4,7,8 \to 1,2,4,7,7 \to 1,2,4,6,7 \to 1,2,4,6,6 \to 1,2,4,5,6 \to \\ &1,2,4,5,5 \to 1,2,4,4,5 \to 1,2,4,4,4 \to 1,2,3,4,4 \end{align} $$ This algorithm can be implemented easily using a heap. However, it is slower (in general) than the preceding algorithm, if the latter is implemented correctly. For example, the sequence $\ell$ takes $\ell$ steps in this algorithm, but could be handled by a single iteration of the preceding algorithm.

---
Tags: correctness-proof, information-theory, arithmetic, binary
---


# Question
Title: Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn)
Focusing on the 2D plane:

Lawson's Flip Algorithm works in worst-case $O(n^2)$ flips. I have seen it mentioned that (other?) flip-based algorithms work in expected $O(nlogn)$ time for two dimensions. What is a simple example of an algorithm like this (perhaps with proof of complexity)? How would this be found?

Edit: If there are none in expected $O(nlogn)$, are there average-case $O(nlogn)$ flip-based algorithms?

# Answer
The proof that edge flipping is expected to perform well goes back to this paper below as well as a couple related one around the same time-frame:

Guibas, Leonidas J., Donald E. Knuth, and Micha Sharir. "Randomized incremental construction of Delaunay and Voronoi diagrams." Algorithmica 7.1-6 (1992): 381-413.

A relatively concise algorithm and proof is given in the paper below by Edelsbrunner and Shah which describes a flip-based algorithm that runs in expected O(n log n) time.

Edelsbrunner, Herbert, and Nimish R. Shah. "Incremental topological flipping works for regular triangulations." Algorithmica 15.3 (1996): 223-241.

The algorithm involves adding points to the triangulation one at a time and using some history of the construction process to locate the new points. The paper is slightly more general, dealing with regular triangulations for which the Delaunay triangulation is a special case.
> 0 votes

---
Tags: algorithms, computational-geometry, randomized-algorithms
---