# Question
Title: Heap structure in array, computing parent and child
I am studying data structures from *Introduction to Algorithms* by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, that means, a binary tree with all of its levels complete except possibly the lowest, which is filled from the left up to a point.

In this book it says that a common way to represent this data structure is an array, beginning from the index 1 of the array and putting from left to right the first level of the tree, then from left to right the second level of the array and so on. It states that this representation is useful because given a node $n$ of the tree lying in position $A\[i\]$ of the array, its parent and children can be easily computed as :

Parent = $A\[i/2\]$

Left child = $A\[2i\]$

Right child = $A\[2i+1\]$

I am having a hard time trying to understand why its parent and children are in these positions on the array, could someone give me an intuitive explanation of why this is the case?

# Answer
> 4 votes
While it is possible to write a formal proof, I think the best proof is by picture:

If you still want a formal proof, here it is. We start by noting that level $d$ of the tree (counting from 0) contains $2^d$ nodes, and so a simple induction shows that level $d$ occupies the indices $2^d, \ldots, 2^{d+1}-1$. Consider now the $i$th node on the $d$th level (again, counting from zero). Its children are nodes $2i,2i+1$ on level $d+1$, as the following table makes clear: $$ \begin{array}{c|c} \text{parent} & \text{children} \\\hline 0 & 0,1 \\ 1 & 2,3 \\ 2 & 4,5 \\ \cdots & \cdots \end{array} $$ The index of the $i$th node on the $d$th level is $2^d + i$. The indices of nodes $2i,2i+1$ on level $d+1$ are $2^{d+1}+2i,2^{d+1}+2i+1$. Notice that $$ 2^{d+1}+2i = 2 \times (2^d + i), \\ 2^{d+1}+2i+1 = 2 \times (2^d + i) + 1. $$ This explains the formulas for the left and right children. The formula for the parent follows similarly, since $$ \lfloor (2^{d+1}+2i)/2 \rfloor = \lfloor 2^d + i \rfloor = 2^d + i, \\ \lfloor (2^{d+1}+2i+1)/2 \rfloor = \lfloor 2^d + i + 1/2 \rfloor = 2^d + i. $$

---
Tags: data-structures, binary-trees, heaps
---


# Question
Title: Hardness of approximating Minimum Cardinality Exact Cover
The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint.

Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for a subcollection $S'$ of $S$ of minimum cardinality such that the union of $S'$ is $U$, and $S\_1 \cap S\_2 = \emptyset$ for every distinct $S\_1, S\_2 \in S'$.

We may assume that for each $u \in U$' there is a set $S\_u = \\{u\\}$ in $S$. This ensures that there exists an exact cover of cardinality at most $|U|$.

I'd like to know if MCEC is as hard to approximate as set cover, i.e. cannot be approximated to within a $\log |U|$ factor. I can show that MCEC has no constant factor approximation, reducing from $k$-Set-Cover for any constant $k$ by adding every subset of a set present in the set cover input. But having the same inapproximability as set cover would be stronger.

# Answer
> 4 votes
Suppose that we are given an instance of EXACT 3-COVER (in which every set contains 3 elements) with $m$ sets on $n$ elements; EXACT 3-COVER is known to be NP-complete. Create a new instance in which each element is replicated $t$ times, each of the original $m$ sets contains each copy of each element, and additionally all $tn$ singletons are available. When the original EXACT 3-COVER instance is a YES instance, the new instance can be exactly covered using at most $m$ sets. When the original EXACT 3-COVER is a NO instance, every exact cover of the new instance requires at least $t$ sets (since every disjoint union of the original sets misses at least one original element, and so requires $t$ singletons in the new instance).

Now let us choose $t = mn^\theta$, for some constant $\theta$. The new instance contains $N = mn^{1+\theta} \leq n^{4+\theta}$ elements, and has a gap of $n^\theta \geq N^{\theta/(4+\theta)}$ between the YES and NO instances. As $\theta \to \infty$, the ratio $\theta/(4+\theta)$ approaches $1$. We conclude that your problem is NP-hard to approximate to within $n^{1-\epsilon}$ for any $\epsilon \> 0$. In contrast, there is a trivial $n$-approximation algorithm, which just takes all the singletons.

---
Tags: algorithms, approximation, set-cover
---


# Question
Title: Estimate entropy, based upon observed frequency counts
Suppose I have $n$ independent observations $x\_1,\dots,x\_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the frequency $f\_s$ of each symbol $s \in \Sigma$ among the observations; how should I use them to estimate the Shannon entropy of the source?

---

The obvious approach is to estimate the probability of each symbol $s$ as $\Pr\[X=s\]=f\_s/n$, and then calculate the entropy using the standard formula for Shannon entropy. This leads to the following estimate of the entropy $H(X)$:

$$\text{estimate}(H(X)) = - \sum\_{s \in \Sigma} {f\_s \over n} \lg (f\_s/n).$$

However, this feels like it might not produce the best estimate. Consider, by analogy, the problem of estimating the probability of symbol $s$ based upon its frequency $f\_s$. The naive estimate $f\_s/n$ is likely an underestimate of its probability. For instance, if I make 100 observations of birds in my back yard and none of them were a hummingbird, should my best estimate of the probability of seeing a hummingbird on my next observation be exactly 0? No, instead, it's probably more realistic to estimate the probability is something small but not zero. (A zero estimate means that a hummingbird is absolutely impossible, which seems unlikely.)

For the problem of estimating the probability of symbol $s$, there are a number of standard techniques for addressing this problem. Additive smoothing (aka Laplace smoothing) is one standard technique, where we estimate the probability of symbol $s$ as $\Pr\[X=s\] = (f\_s + 1)/(n+|\Sigma|)$. Others have proposed Bayesian smoothing or other methods. These methods are widely used in natural language processing and document analysis, where just because a word never appears in your document set doesn't mean that the word has probability zero. In natural language processing, this also goes by the name smoothing.

So, taking these considerations into account, how should I estimate the entropy, based upon observed frequency counts? Should I apply additive smoothing to get an estimate of each of the probabilities $\Pr\[X=s\]$, then use the standard formula for Shannon entropy with those probabilities? Or is there a better method that should be used for this specific problem?

# Answer
Like most things of this nature the best method is best found by empirical evaluation. One thing worth noting is that most smoothing schemes can be thought of as the incorporation of a prior into your likelihood estimate. For example if you are trying to estimate the parameter $\theta$ of a binary random variable $X$ and you have data $\mathcal{D} = \\{x\_1, \ldots, x\_n\\}$ consisting of i.i.d. realizations of $X$ then your posterior takes the form

$$ \begin{align\*} P(\theta|\mathcal{D}) &\varpropto P(\theta)P(\mathcal{D}|\theta)\\ \end{align\*} $$ Assuming $P(\theta) = B(\alpha,\beta)^{-1}\theta^{\alpha-1}(1-\theta)^{\beta-1}$, i.e., a Beta distribution and letting $n\_1 = |\\{x\_i \in \mathcal{D} \colon x\_i = 1\\}|$ then we have

$$ \begin{align\*} P(\theta|\mathcal{D}) &\varpropto \theta^{\alpha-1}(1-\theta)^{\beta-1} \theta^{n\_1}(1-\theta)^{n - n\_1}\\ &= \theta^{n\_1 + \alpha - 1}(1- \theta)^{n - n\_1 + \beta - 1}. \end{align\*} $$ Notice the effect of the hyperparameters ($\alpha$ and $\beta$) is essentially to just add some constant to your counts of each possible outcome. So additive smoothing (at least all applications I've encountered) is really just a special case of Bayesian estimation.
> 3 votes

# Answer
This is an old but very nice question.

Since the expectation of any estimate from i.i.d. samples is a polynomial function of class probabilities, unbiased estimators of entropy do not exist, entropy being non-polynomial. There are bias corrections used for a maximum likelihood entropy estimator, but such an estimator is very sensitive to the small values of probabilities $\log(1/p\_i)$ being large when $p\_i$ is small.

Batu et al: *The Complexity of Approximating the Entropy*, SIAM Journal on Computing, 35(1):132-150, 2005m, available here consider this problem.

Furthermore, it is impossible to have an algorithm which outputs an estimate of the entropy with a multiplicative guarantee $\gamma,$ i.e., such that the estimate is in $(\gamma^{-1}H\_0,\gamma H\_0)$ with probability $\geq 3/4,$ where $H\_0$ is the true value of the entropy. This can be seen by considering the two distributions $$ (1,0,\ldots,0) $$ and $$ (1-\delta,\delta,0,\ldots,0) $$ on the same domain, since one has entropy zero and the other strictly bigger than zero.

This question falls under what the authors call the generation oracle model. In that case, the main result is the following:

Fix $\eta\>0,$ to be arbitrarily small. If a distribution on $\\{1,2,\ldots, n\\}$ has entropy $\Omega(\gamma/\eta),$ then a $\gamma-$multiplicative approximation to the entropy can be obtained in time $$O(n^{(1+\eta)/\gamma^2}\log n).$$

For the same class of distributions, the authors prove the following lower bound on time complexity of a $\gamma-$multiplicative algorithm:$$O(n^{1/(2\gamma^2)}).$$

For monotone and flat distributions (on a subset) they obtain better results.
> 1 votes

---
Tags: information-theory, statistics, natural-language-processing, entropy, information-retrieval
---


# Question
Title: Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable
I thought about these languages: $$L\_{1} = A\_{TM} = \big\\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\\}$$ $$L\_{2} = \overline{HALT\_{TM}} = \big\\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\\}$$

Their intersection: $$L\_{1}\cap L\_{2} = \big\\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts and doesn't halt on input } w \big\\}$$

If I assume that the intersection is decidable by TM $T$ so I can use $T$ to decide $A\_{TM}$ and that's a contradiction.

Is it true?

# Answer
Your proof is wrong. Note if $M$ accepts $w$, it must halt on $w$, so $L\_1\cap L\_2$ is the empty set, which is of course decidable.

To disprove the statement, you can set $L\_2$ to be $\Sigma^\*$, i.e. the language containing all strings. Since $\emptyset$ is Turing recognizable, $L\_2$ is co-Turing recognizable. However, $L\_1\cap L\_2=L\_1$ is undecidable.
> 3 votes

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


title: AMAT calculation

text:
# Question
Title: AMAT calculation
I was just solving an exercise when the answer of this suprised me : We have a memory hierarchy built with 2 levels of caches and a main memory, the access time of the L1 is 1 cycle, for L2 it's 10 and the main memory can be accessed in 100 cycles. We are then asked to calculate the AMAT of this memory. The miss rate of L1 is 0.05, this of L2 is 0.2.

I had never learned the formula AMAT = t\_cache + MR\_caches(t\_MM + MR\_MM\*t\_VM) so I computed a solution only with my little brain and for me it was logical that, first 95% of the data are accessed in 1 cycle, we get 0.95. Then out of these 5% left, 80% are accessed in 10 cycles, we get 0.05 * 0.8 * 10. Finally 20% of these 5% are accessed in 100 cycles, which give us 0.05 * 0.2 * 100, it's like probabilities.

What am I doing wrong ? I got an AMAT of 2.35 but the formula tells me it's 2.5.

# Answer
> 1 votes
Judging from the formula for AMAT, here is what happens:

* An attempt is made to access the data via the L1 cache. This takes 1 cycle, whether the data is there or not.
* If the data is not in the L1 cache, then an attempt is made to access it via the L2 cache. This takes 10 cycles, whether the data is found there or not.
* Finally, if the data is neither the L1 nor the L2 cache, then it is retrieved from main memory using 100 cycles.

In your case, data is found in the L1 cache with probability 0.95, not in the L1 cache but in the L2 cache with probability 0.04, and in neither caches with probability 0.01. In the first case, the access time is 1 cycle, in the second it is 11 cycles, and in the third it is 111 cycles. In total, the average access time is $$ (0.95 \times 1) + (0.04 \times 11) + (0.01 \times 111) = 0.95 + 0.44 + 1.11 = 2.50 \text{ cycles}. $$

---
Tags: memory-access
---


# Question
Title: Operating System: About user thread and kernel thread?
Is that a "thread" consists of both "user thread" and "kernel thread" as two parts?

And when I create a "thread", is that I create a "user thread" and another "kernel thread" is created "in the background" by OS also?

I'm confused because of the second picture.

The book I'm reading is "Operating System Concepts, 9th ed., SILBERSCHATZ", and it's at page 169. Thanks a lot

# Answer
> 1 votes
As the given text says, it is not necessary that for every new user thread a new kernel thread is also created. In fact different operating systems can implement this in a different way. Some OS will map every new user thread to a new kernel thread(one to one mapping), some can have a maximum limit on number of kernel threads beyond which a kernel thread will be mapped with more than one user thread(many to one). There can also be an OS which maps a single user thread to more than one kernel thread, and vice versa. This would be a many to many model.

All these models have their own pros and cons. Which model to choose would depend upon what functionality is required from OS, available hardware resources etc.

---
Tags: operating-systems
---


# Question
Title: Can Tug of war problem be solved by DP or greedy approach?
For problem explanation: https://www.geeksforgeeks.org/tug-of-war/

I know the exponential solution to the problem, but can it be improved by greedy or DP approach. If yes then please explain the ideology of the solution. Also please mention if there are exceptions to this greedy or DP solution where it may not apply.

# Answer
There is a pseudo-polynomial solution with dynamic programming which runs in $O(S n^2)$ with $S = \sum\_{i=1}^n |a\_i|$.

Namely for each possible sum $s$ (between $\sum\_{a\_i \< 0} a\_i$ and $\sum\_{a\_i \> 0} a\_i$) compute, if you can choose a subset of size $\lfloor n/2 \rfloor$ with sum $s$. Using this information you can directly find the optimal solution.

You can compute this information it in a similar way as you would for a 0/1 knapsack problem, just with one dimension more:

$$f(s, m, i) = f(s-a\_i, m-1, i-1) ~\vee~ f(s, m, i-1)$$ if $i \> 0$ and $m \> 0$, where $f(s, m, i)$ means "is it possible to choose a subset of size $m$ with sum $s$ using the first $i$ elements of the original array?".
> 1 votes

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


title: Transform calculation to memory

text:
# Question
Title: Transform calculation to memory
Theoretically, is it possible to convert the processing power of the CPU into several tens of bits of memory?

My question is unusual, but it's very interesting. I'm looking for a way to create a small (64 bit) memory department that the user could not access.

# Answer
There's a line of research that studies how to store sensitive data in the CPU's registers instead of RAM. Here's a seminal paper:

There's also work in storing sensitive data in the cache. Here are two of the seminal papers:

There's lots more work on these subjects, but this will get you started. You can find follow-up papers in the standard ways (Google Scholar, etc.).

You might also be interested in Intel SGX, TrustZone, TPMs, or related schemes for hardware support for secure computation.
> 5 votes

---
Tags: virtual-memory
---


# Question
Title: Computational complexity classes not based on input size?
Computational complexity classes, such as $P, NP, PSPACE$, etc, are defined according to the factory by which computational time **increases**, as the **input size $n$ increases.**

But this doesn’t allow us to talk about the complexity of a **particular** problem (i.e. for a particular $n$).

For example, I believe that “generalized chess”, i.e. on an $n\times n$ board, is $NP$-hard. But this only tells us something about how the computational time of generalized chess increases as $n$ goes to infinity. **It doesn’t tell us anything about how hard $8\times 8$ chess is.**

On the other hand, simply giving a number, denoting the amount of steps required to solve $8\times 8$ chess with a Turing machine, **is not very insightful.**

**Is there a different classification-scheme/framework for analysing the computational complexity of problems, that doesn’t refer to the input size $n$, that allows us to analyse e.g. the complexity of $8\times 8$ chess?**

# Answer
No, not really: there's no framework for this that turns out to be very useful. There is a reason that in theoretical work we often use asymptotic complexity.

In principle, you *could* talk about the concrete complexity of the problem of chess on a 8x8 board. One way to measure that would be to use the worst-case running time of the fastest program to solve chess on a 8x8 board: not the asymptotic running time, but the actual wall-clock time, measured in seconds. However, this has multiple problems. One problem is that it is obviously super-specific to a particular computer: if I buy a different computer, the wall-clock time might be very different, even though I haven't changed the algorithm. So now the running time is no longer a property of the algorithm; it also depends intimately on which computer I run it on.

Or, perhaps we could count the number of instructions executed. But now that will depend on the particular computer architecture; when we compile to x86, the number of instructions might be different than when we compile to ARM. So the complexity still depends on the computer.

Finally, there is the problem that it is very hard to reason about this number through theoretical analysis. Given some pseudocode, can you analyze how many instructions or how many seconds it will take to run that pseudocode? That's very hard, since the pseudocode first has to be implemented in some language, then compiled to machine language, then run. (And good luck reasoning about the effect of caches and the memory architecture on the time it takes to, e.g., perform a single read or write to memory; that's very hard to predict.) At best, it gets super messy; at worst, it's just not predictable in a reasonable way.

If you read Knuth, you'll find that he tries to do this kind of analysis. He defines an artificial computer architecture called MIX, which is fully specified. He then implements his algorithms carefully in MIX machine language, and finally mathematically analyzes the number of MIX instructions the algorithm might take. If you go through some of his demonstrations you'll see just how painful and messy it is. He ends up doing this only for some pretty simple algorithms, and the calculations are still ugly; doing that for something as complex as a chess algorithm sounds horrendously painful.

Finally, there's the problem that we don't know what is the optimal program for playing 8x8 chess. That's a famous open problem.

So, yes, in principle, it is possible to reason about running time without relying on asymptotics. In practice, it usually gets so messy that you drown in details and have a hard time extracting useful insights.
> 3 votes

---
Tags: complexity-theory
---


title: String matching

text:
# Question
Title: String matching
I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain `.` in it which can match any character. For eg. if I add strings "abcd" and "abed" then search for "ab.d" should return me both of them.

I tried to tackle this using prefix Tries. It works fine for normal string search(without dot) but for dot I have to search for every child of a node. Is there a more efficient way of solving this problem?

# Answer
This problem was considered in the following papers:

See also String matching for wildcard-based records, Given a set of string patterns, find which ones match a particular string, https://cstheory.stackexchange.com/q/36913/5038.
> 2 votes

---
Tags: algorithms, data-structures, strings, string-matching
---


# Question
Title: Coloring grid with flexible number of colors and flexible number of occurrence per color
Suppose we have an $m \times n$ grid or table, with $m$ being the number of rows and $n$ being the number of columns. The user can select the number of colors (let's say $k$ colors) and how often each color is allowed to occur (i.e., we have a vector of numbers of occurrence of the colors $(i\_1, i\_2, \dots, i\_k)$). The only constraints that apply are pretty obvious: $\sum\_j i\_j = nm$ and $i\_j \leq ⌈nm/2⌉$ for $1 \leq j \leq k$.

I would like to color the vertices/cells in a way that no two adjacent vertices/cells have the same color (adjacence is defined as up, down, left or right; i.e., it is allowed to have the same color on a cell that is on the diagonal of the current cell). If possible, there should be no strict segregation of colors along the field, i.e., each color should be distributed over the field as "randomly" as possible.

So far I've implemented a brute force algorithm based on random selection of the coordinates of the colors. However, this approach is too inefficient.

One thought of mine was to first randomly arrange the colors in a linear list (i.e., as if we would have a $1 \times (nm)$ grid), then to take out the first $n$ elements and re-arrange them into the first row, randomly shuffling the colors until the condition is fulfilled. Then taking the next $n$ elements, arranging them as a second row and shuffling the elements until all conditions are fulfilled, and so on. This way, I would still have a random component, but at each step I would only need to deal with one row, and I might realise at an earlier time point that I got stuck and need to restart. However, I'm not sure whether this approach would really improve the performance.

Is there a better way to achieve the result? And is there a way to early determine whether a valid solution for a given input exists at all?

# Answer
You're asking for a $k$-coloring of a grid graph (with some extra constraints on how many times each color is used).

One approach is to encode this as an instance of SAT or integer linear programming (ILP), and let a SAT/ILP solver look for a solution for you. For instance, you could introduce zero-or-one variables $x\_{r,s,t}$, where $x\_{r,s,t}=1$ if row $r$ column $s$ has color $t$, and then write down constraints to capture that this is a valid coloring (i.e., $x\_{r,s,t} + x\_{r',s',t} \le 1$ when $(r,s)$ and $(r',s')$ are adjacent, $\sum\_t x\_{r,s,t} = 1$, and $\sum\_{r,s} x\_{r,s,t} \le i\_t$), then feed it to an ILP solver.

Related (but different): Number of ways to fill a 2xN grid with M colors, Counting Colorings of a Grid.
> 1 votes

---
Tags: colorings
---


title: What can give physical access to CPU?

text:
# Question
Title: What can give physical access to CPU?
If an attacker has an unlimited physical access to CPU, but does not have access to memory, including RAM, can he attack and gain access to the user's data?

I heard the opinion that this is impossible according to the laws of physics, even with an electron microscope. It's true?

# Answer
If you have unlimited physical access to the CPU, then you can send your own instructions into it, including instructions to read from arbitrary memory addresses. Looking at the voltages on the data bus then shows you exactly what's in that word of memory.

Remember, any data the computer is able to use, has to be accessible by at least one CPU. That's just how it works. So access to the CPU gives you theoretical access to everything else.

(*Note: this is an answer to the question in the body, not the question in the title.*)
> 2 votes

---
Tags: cpu
---


# Question
Title: What is the level of the material contained in the book Data Structures and Algorithm Analysis in C++ (4th Ed) by Weiss?
The question is pretty much explained in the title. I have the necessary discrete math background and would like to learn algorithms and data structures in the process (of coding) - so the book quoted in the title seems a good read. Since the author states clearly in the preface that the book is suitable for an advanced data structures course or a 1st year graduate course on algorithm analysis, my question seems answered already. But I guess my real question is how much material is contained in the book and how advanced it is, say compared to the following resources:

Two MIT graduate-level courses - Advanced Algorithms (http://people.csail.mit.edu/moitra/854.html) by Ankur Moitra and Advanced Data Structures (https://courses.csail.mit.edu/6.851/spring12/) by Eric Demaine.

PS: I want to become a C++ programmer (generically speaking) with a strong algorithm and data structures background. Not really sure what material I should dive into. Any suggestions on this are also very welcome!

# Answer
> -1 votes
Once I skimmed through a dozen of textbooks, looking for ones better explaining sorting and data structures (i.e. no graphs, string algos and so on).

Weiss was the best one according to my criteria. In particular, it describes more advanced techniques for hash tables, which are heart of most real use cases. Although even this book doesn't include Robin Hood hashing - learn it from Wikipedia pointers.

More info: https://www.quora.com/How-do-I-learn-data-structure-and-algorithm-in-C++-I-know-the-basics-by-myself-Can-you-suggest-any-e-books-for-me-to-use/answer/Bulat-Ziganshin

Another extremely important topic: https://www.quora.com/What-are-good-resources-to-learn-concurrent-programming-in-C++/answer/Bulat-Ziganshin

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


title: How to distinguish between bits?

text:
# Question
Title: How to distinguish between bits?
I read a post about differences between synchronous and asynchronous transmission modes.
That post has a picture about how bits flows from terminal to computer in async mode.

But how computer can distinguish between `1`s and determine what `1` does actually mean. Is it parity bit, is it start/stop bit or maybe it's start of `idle` bits? Or just part of data is being transmitted?

# Answer
> 5 votes
If the computer starts in the middle of the stream, it has no way to know—it will be completely confused.

Fortunately, that's not how the protocol works. The computer and terminal have to sync up before they can communicate. There are a few different ways of doing that, but once they're in sync (which includes agreeing on how long each 1 or 0 should last), they both follow a set pattern.

In this example:

* The terminal starts out holding the line high (sending constant 1s) to indicate that it has nothing to say.
* When the terminal has something to say, it brings the line low for a moment (sending a 0). That's the "start" bit.
* The terminal then sends seven bits for the character: always exactly seven, since it's using ASCII, which is a seven-bit encoding.
* After those seven bits, it sends one additional bit for error checking. This is a 1 if there were an odd number of 1s in the character, and a 0 otherwise. This is the "parity" bit.
* Finally, it pulls the line high again to indicate that it once more has nothing to say.

The computer keeps track of which "mode" the connection is in at all times. If it sees a zero, it might record it as part of the data, or might switch from "idle" mode to "start listening for data" mode, or check the parity: it all depends on what it's seen before.

---
Tags: computer-networks, bit-manipulation
---


# Question
Title: How does storing encrypted password provide secure authentication?
It's universally accepted that storing an unencrypted password for automated authentication is a very bad idea, for the saved password can be used by malware, etc.

There is a number of systems that store encrypted passwords for the purpose of automated authentication elsewhere. For example, one can configure `git` to automate authentication during `git push`. My question is: how do such system manage to authenticate securely?

Specifically, here are two possibilities:

1) The local system stores the encrypted password, and when needed, sends it to the remote system. The remote system accept the encrypted password for authentication.

However, in this case the encrypted password leads to exactly the same vulnerability as unencrypted password: malware can use the unencrypted password to authenticate itself. For example, if your password was "brown fox" and it was stored as a hash 14921776, and the remote system would accept 14921776 as a valid authentication certificate, then malware can just look up 14921776 in the encrypted password file in the local system and use it as is.

2) Suppose now that the remote system does not accept the encrypted password for authentication. In the above example "brown fox" needs to be communicated between local and remote system; the hash 14921776 won't do.

How does the local system would provide automated authentication in that case? All the local system knows that the hash of the password is 14921776, but it cannot unhash it into "brown fox", and therefore cannot send the valid password to the remote.

# Answer
Actually, storing an unencrypted password can be OK in certain circumstances, depending on what the password is used for and the threat model you are trying to defend against.

In any case, if you are authenticating to a remote system, you probably should be using public-key cryptography instead of a password if you possibly can.

Some relevant readings:
> 1 votes

# Answer
In this case unfortunately there is no 100% "secure" solution against malware or another user which works on the same privileges level as intended user does. If you can read password they can too...

There are few possible things that could make this more secure.

First of course is passphrase like SSH does to private key management although it would need prompting it every time or once during some kind of cache session. Setting cached password for only some limited time and removing it automatically after that is one of solutions used too. Of course UNIX chmod 400, hiding files (leading .(dot)) are another helpful steps, storing password in encoded format is too.

You confused few things here too, hash is one way function so it is totally different thing to encryption.
> 0 votes

---
Tags: authentication, cryptography
---


# Question
Title: Finding the maximum substring for which a given predicate is true
Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$. Assume that $F$ satisfies the following:

* If $F(g) = \text{true}$, then any proper sub-string of $g$, above a certain cutoff length $L$, also evaluates true.
* Strings below the cutoff length evaluate to false

What is the best strategy to find $s$ which minimizes the function evaluations?

Naive approaches:

* Sequential search of the string $\mathcal{O}(N^2)$ function evaluations.

I suspect there must be a better way but anything I look up just sends me to Kadane's algorithm. I would appreciate it if anyone has any references which might be useful or know the answer.

# Answer
Let's denote $\[\exists s: F(s) \wedge |s| = x\]$ as $B(x)$. First property of $F$ implies that for any $x \> L$

$$B(x) \implies B(x-1)$$

Which by induction implies:

$$B(x) \implies \forall i \in \[L, x\] : B(i)$$

In other words, if you know that $B(x)$ is true, you don't have to examine lower values of $x$. And if $B(y)$ is false, you know that higher values of $y$ can't give you true, as it would contradict that $B(y)$ is false.

Now you can find maximal $x$ (such that $B(x)$ holds) using binary search. For each iteration of the search, $B(i)$ can be verified in $\mathcal{O}(N)$ calls to $F$: you just need to call it for every substring of fixed length $i$.

In total, this gives you $\mathcal{O}(N \log N)$ calls to $F$.
> 3 votes

---
Tags: algorithms, strings, substrings
---


# Question
Title: Sources on dictionary learning and related algorithms
In the context of signal processing and sparse representation of signals, there is a topic called dictionary learning which is basically about how to's of the selection of basis functions used for sparse representation. I am looking for sources explaining the topic with a section on dictionary learning algorithms and probably a comparison made among them.

# Answer
> 1 votes
The best resource, in my opinion, is eDx - Sparse Representations in Signal and Image Processing: Fundamentals by Michael Elad.

---
Tags: algorithms, reference-request, image-processing
---


# Question
Title: What's wrong with the following argument that $NP \subset coNP$?
What's wrong with the following argument that $NP \subset coNP$?

let $L \in NP$; then there exists an NTM $N$ that decides $L$ in $f(n)$ time where $f(n) = O(n^k)$ for some natural number $k$.

Define $H = $ on input $z$:

1. run $z$ on $N$ for at most $f(|z|)$ steps.
2. if $N$ accepted, reject. If hasn't accepted, accept.

Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

If $z \in L(H)$ then $N$ hasn't accepted $z$ after $f(|z|)$ steps. If $z \in L$ then $N$ would have accepted it after $f(|z|)$ steps.

Is the problem here that computing $f(|z|)$ may not take polynomial time, in $|z|$? It seems like it should.

# Answer
This is not true:

> Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

It might be $z \in \bar{L}$, but the machine will not be stopped anytime!
> 0 votes

---
Tags: complexity-theory, computability, p-vs-np
---


# Question
Title: Can this Arrow-Ring puzzle be encoded as an integer programming problem?
I would like to write a solver for these kind of Arrow-Ring puzzles. However, I can't encode all the constraints correctly.

I noticed that Sudoku can be solved using integer programming and I am hoping it can be done for this kind of puzzle as well. Let's take a look at the rules:

> * Draw a line to make a single loop. Lines pass through the centers of cells, horizontally, vertically, or turning.
> * The loop never crosses itself, branches off, or goes through the same cell twice.
> * The numbers show how many black cells there are in the direction of the arrow.
> * The loop does not pass through the black cells or the cells with numbers, and black cells cannot touch horizontally or vertically.

The first constrant seem the most difficult, that we should require a single closed loop. And I wonder if integer programming is even the best way to solve these, but it's a start.

The third constraint (with numerical hints) is the most clear and for simplicity, they could also be replaced by black squares. However, if you already know how to encode these as integer programming problems, go for it.

Lastly, are there other algorithms that are efficient for finding loops in graphs with constrants? Wikipedia suggests this could be a Hamiltonian Path or an SAT problem.

# Answer
You can encode this problem using a SMT solver like z3, which translates it to a SAT instance.

Let each $c\_{x, y}$ be a free variable for a cell that isn't an arrow. A cell can be one of the following (encode them as integer states or as one-hot states).

1. Black.
2. Horizontal.
3. Vertical.
4. Top-right turn.
5. Right-bottom turn.
6. Bottom-left turn.
7. Left-top turn.

If you can find an assignment of the above for each $c\_{x, y}$ variable, you've found a solution.

Obviously we still need to encode all requirements. First introduce four helper variables for each $c\_{x, y}$ to see if it is connected to its top/left/bottom/right neighbour. This is a bit laborious, but it comes down to logic statements such as "I'm vertical and bottom neighbour is either vertical, top-right turn or left-top turn".

Introduce a requirement that each cell $c\_{x, y}$ must be connected to at least one neighbour.

Introduce a requirement for each arrow block to say that the number of cells equal to black in the direction it's pointing in must match its number.

Introduce a requirement that no two adjacent $c\_{x,y}$ are black.

With all these requirements you know that each free cell is either black, or part of **a** connected loop. The final struggle is to ensure that there is a **single** connected loop. This can be done by assigning a single free variable to denote a leader cell, and then using the previous established connections to ensure that each cell is either black or the leader cell, or connected to the leader cell, or connected to a cell connected to the leader cell.

---

All in all this is quite a tricky and laborious translation into an SMT solver. If you intend to implement this I strongly suggest reading through some example problems from this excellent z3 guide. It has a ton of translations of various problems into a format a SMT solver can understand.
> 1 votes

---
Tags: arrays, integer-programming, board-games, hamiltonian-path
---


# Question
Title: Median of two sorted arrays of different size in logarithmic time?
The solution given in Cormen is as follows:

Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary search on A only, then how will we get the median if it lies in B. Also the pseudo code is less than understandable. Can anybody simplify it to me.

# Answer
> 4 votes
Given two sorted arrays $A\[1\],\ldots,A\[\ell\]$ and $B\[1\],\ldots,B\[m\]$, the goal is to find the median. Let's assume for simplicity that $n := \ell+m$ is odd, and that all elements are distinct. Therefore we are looking for the element which has exactly $\frac{n-1}{2}$ below it in both arrays.

Given an element in one of the arrays, it is easy to find whether it is the median, smaller than the median, or larger than the median. For example, suppose that the element in question is $A\[i\]$. There are $i-1$ elements below it in $A$. If it were the median, then there would be exactly $j := \frac{n-1}{2} - (i-1)$ elements below it in $B$, which would put it between $B\[j\]$ and $B\[j+1\]$. Checking whether this holds, there are three cases:

1. $B\[j\] \< A\[i\] \< B\[j+1\]$. In this case $A\[i\]$ is the median.
2. $A\[i\] \< B\[j\]$. In this case there are fewer than $j$ elements below $A\[i\]$ in $B$, and so there are fewer than $\frac{n-1}{2}$ elements below $A\[i\]$. In other words, $A\[i\]$ is *smaller* than the median.
3. $A\[i\] \> B\[j+1\]$. Symmetrically, in this case $A\[i\]$ is *larger* than the median.

Suppose that the median belongs to the array $A$. Using the test described above, we can find it using binary search: we start with the middle element of $A$. If it is the median, we're done. If it is larger than the median, we continue with the middle element of the first half of $A$, and if it smaller than the median, we continue with the middle element of the second half of $A$. Continuing in this way, we will eventually find the median in at most (roughly) $\log\_2 \ell$ steps.

What if the median doesn't belong to $A$? Our algorithm will get stuck. Since this is an identifiable situation, this suggests an algorithm which finds the median:

1. Try to find the median in $A$ using binary search.
2. If the binary search algorithm gets stuck, find the median in $B$ using binary search.

Note that if the first step fails, the second must succeed. The overall running time is $O(\log \ell + \log m) = O(\log n)$.

---
Tags: algorithms, arrays, statistics
---


# Question
Title: Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?
I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching.

However, I am using python-graph-tool, which only has max-cardinality max-weight matching, which from what I understand, only finds the max-weight matching of the max-cardinality matchings. However, it may be the case that a truly max-weight matching will not always be a max-cardinality matching (this is especially true on graphs that can have negative edge weights).

Are there any tricks I could use to still get what I need? For example, could I transform my graph $G \to G'$ so that by obtaining a max-card-max-weight matching on $G'$ I could obtain a max-weight matching on $G$? Or will I have to find another algorithm? Are there any good algorithms suited to the task?

# Answer
Suppose that the original graph is $G = (V,E)$. Let $V’$ be a copy of $V$, and create a new graph $G’$ with vertex set $V \cup V’$ and the following edges:

* The original edges of $G$.
* For every edge $(a,b) \in E$, we add a zero-weight edge $(a’,b’)$, where $a’,b’$ are the counterparts of $a,b$ in $V’$.
* A matching connecting $V$ to $V’$ (i.e., each vertex in $V$ is connected to its counterpart in $V’$) with zero-weight edges.

Every matching of $G$ can be extended to a perfect matching of $G’$ with the same weight.

A useful feature of this reduction is that it preserves sparsity — that is, denoting by $n,m$ the number of vertices and edges in $G$, and by $n’,m’$ the same parameters for $G’$, we have $n’+m’ = O(n+m)$.
> 3 votes

---
Tags: algorithms, graphs, matching
---


# Question
Title: In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?
In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex format. can we use $a^n b^n c^n d^n$ format for our guesses?

# Answer
> 3 votes
You cannot force the guesses in any way.

That said, in your case you can emulate a witness of this form. Let’s first replace your $n$ with $m$, reserving $n$ for the input length. Suppose that your algorithm runs in time $t(n)$. Then you can only go through the first $t(n)$ guesses, so without loss of generality you can assume that $m \leq t(n)$. Since $t(n)$ is polynomial, $\log t(n) = O(\log n)$, and so you have enough space on the tape to store $m$. You therefore proceed as follows:

* Guess $m$ (by guessing $\log t(n)$ bits).
* Simulate the guesses $a^mb^mc^md^m$ using a counter that goes up to $m$ and another one that goes up to 4.

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


# Question
Title: Is the inverse of MST cycle property always true? Why?
I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees.

I have found many potential solutions to this problem, which use the cycle property of MSTs, that is (quoting Wikipedia): *For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to a MST.*

It is obvious to me how this property can be used to determine which edges can definitely *not* belong to *any* of the graph's MTSs, but I have doubts if the inverse of the cycle property is also true, that is if: *For every cycle C in the graph, if the weight of an edge e of C is **less or equal to** the individual weight of **any** other edge of C, then this edge belongs to **at least one** MST*.

In other words, is edge e not being the heaviest edge in every cycle containing e only a necessary condition, or a sufficient condition to e belonging to an MST?

If the above is false, then all I would want to see is a counterexample. If however this is true, could anybody prove why it is so?

# Answer
If you want to test whether a *specific* edge belongs to some MST, you can use the following property.

**Claim.** An edge $e$ belongs some MST if and only if for every $\epsilon \> 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to *all* MSTs.

**Proof.** We first show that if $e$ belongs to some MST then for every $\epsilon \> 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to all MSTs.

Suppose that MSTs in the original graph have weight $w$. When we decrease the weight of $e$ by $\epsilon$, only trees containing $e$ have decreased weight. Since $e$ belongs to some MST, the new graph has MSTs of weight $w - \epsilon$, and all of them contain $e$.

We complete the proof by showing that if $e$ doesn't belong to any MST then for small enough $\epsilon \> 0$, if we decrease the weight of $e$ by $\epsilon$ then $e$ still belongs to no MST. Indeed, suppose that MSTs in the original graph have weight $w$, and the lightest spanning tree containing $e$ has weight $w+\delta$ for $\delta \> 0$. If we decrease the weight of $e$ by less than $\delta$, it still belongs to no MST. $\qquad \square$

I'll let you figure out how to use the claim to test whether $e$ belongs to some MST; it suffices to find one MST in one graph. The same approach seems wasteful if you want to test all edges. I'll leave you to ponder whether any optimization is possible in that case.
> 7 votes

# Answer
Yuval Filmus's ingenious answer, which shows a way to test whether a specific edge belongs to some MST, does not answer OP's question and request. The question is whether edge $e$ not being the heaviest edge in every cycle containing $e$ only a necessary condition, or a sufficient condition to $e$ belonging to an MST. The request is a counterexample or a proof.

Here is my positive answer with proof, where I have actually proved that an edge is not in any MST if and only if it is is the unique heaviest edge in some cycle. In another word, for any edge $e$, $e$ is not the unique heaviest edge in any cycle if and only if $e$ belongs to an MST.

Here is a closely-related interesting fact. For any edge $e$, $e$ is not a heaviest edge in any cycle if and only if $e$ belongs to every MST. Together with the positive answer, this fact implies immediately the claim in Yuval Filmus's ingenious answer: An edge $e$ belongs some MST if and only if for every $ϵ\gt0$, if we reduce the weight of $e$ by $ϵ$ then it belongs to all MSTs.
> 2 votes

---
Tags: algorithms, graphs, correctness-proof, minimum-spanning-tree
---


# Question
Title: Logical characterization of P versus NP problem (and references for least fixed point logic)
Wikipedia says the following (and more) about the logical characterization of the P versus NP problem here:

> Thus, the question "is P a proper subset of NP" can be reformulated as "is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?"

My question is, has there been any work done to tackle the P versus NP problem from this logical angle, by reasoning about existential second-order logic and first-order logic with least fixed point?

And more generally, what are some good references for learning about least fixed point logic?

# Answer
Your second question first. The context of your question is called descriptive complexity theory. In this context, I would suggest the book Finite Model Theory by Heinz-Dieter Ebbinghaus and Jörg Flum. As far as I recall it thoroughly covers both logics and their connection to P, respectively NP.

Now to your first question. Of course, as soon as both complexity classes had been characterized by logics, there were hopes to settle the P=NP question this way. Yet by now the problem has eluded this approach for several decades. One would need to pick some problem from NP and show that it is not expressible in FO(LFP) (first-order logic with least-fixed point operators). Essentially the only tool for proving non-expressibility are Ehrenfeucht–Fraïssé games. These games are notoriously hard to analyze in the presence of non-monadic second-order variables, which are needed in the case of FO(LFP). See also the paper https://eccc.weizmann.ac.il/report/2013/065/ by Yijia Chen and Jörg Flum.
> 5 votes

---
Tags: logic, p-vs-np, first-order-logic, fixed-point
---


# Question
Title: Explanation of implication-introduction rule
I read in Proofs and Types by Girard et alii. the following excerpt that talks about the calculus of natural deduction:

> Now a sentence at a leaf (of the deduction tree) can be dead, when it no longer plays an active part in the proof. Dead sentences are obtained by killing live ones. The typical example is the $\implies$-introduction rule:
>
> $$ \dfrac{\stackrel{\[A\]}{\stackrel{\vdots}{B}}}{A \implies B} $$
>
> It must be understood thus: starting from a deduction of B, in which we choose a certain number of occurrences of $A$ as hypotheses (the number is arbitrary: 0,1,250,$\ldots$), we form a new deduction of which the conclusion is $A \implies B$, but in which all these occurrences of $A$ have been dicharged, ie. killed. There may be other occurrences of $A$ which we have chosen not to discharge.
>
> This rule illustrates very well the illusion of the tree-like notation: it is of critical importance to know when a hypothesis was discharged, and so it is essential to record this. But if we do this in the exmaple above, this means we have to link the crossed A with the line of the $\implies$I rule; but it is no longer a genuine tree we are considering.

May I ask you for an explanation and example of this situation?

# Answer
> 5 votes
Every assumption that is introduced between brackets has to be discharged at some point for the proof to be complete. Otherwise, we could prove that $A$ is true for any given $A$ as follows.

```
[A]¹
───
 A

```

This proof is incorrect, we have not discharged the initial assumption. The following proof of $A\to A$ would be correct, as it discharges the assumption (and the implication introduction rule is necessary to do so!).

```
 [A]¹
 ───
  A
───── (discharging ¹)
A → A

```

Now, let's compare two derivations of $A \to A \times A$ and $A \to A \to A \times A$. On the first one, we will discharge the two occurrences of $A$ at the same time (on the same deduction step). On the second one, we will discharge the two occurrences on two separate steps.

**First proof**

```
  [A]¹   [A]²
  ─────────
    A × A
───────────── (discharging ¹ and ²)
  A → A × A

```

**Second proof**

```
 [A]¹    [A]²
 ──────────
   A × A
───────────── (discharging ¹, note that ² is still alive!)
  A → A × A
──────────────── (discharging ²)
 A → A → A × A

```

Maybe looking at this from the perspective of the simply-typed lambda calculus is more illuminating. Instead of tracking superscripts, variable names represent which assumptions are we choosing to discard at each point. Note the difference between the two proofs, and how the introduction rule of the implication corresponds to a lambda abstraction, while the introduction rule of the conjunction corresponds to a pair type.

**First proof**

```
   a : A   a : A
   ─────────────
   (a,a) : A × A
 ────────────────────
 λa.(a,a) : A → A × A

```

**Second proof**

```
     a : A   b : A
     ─────────────
     (a,b) : A × A
   ────────────────────
   λb.(a,b) : A → A × A
 ───────────────────────────
 λa.λb.(a,b) : A → A → A × A

```

*(I am using a lambda interpreter I wrote to generate these derivation trees. It may be useful for you if you are interested in the connection between propositional intuitionistic logic and lambda calculus.)*

# Answer
> 3 votes
I recommend Mario Román's answer, particularly the connection to the lambda calculus, but I'll add a third perspective.

I dislike the natural deduction notation, but I do like the natural deduction rules of inference. Instead, I prefer a notation more like the one used in the sequent calculus, and nothing stops us from using that notation with the rules of natural deduction.

With a sequent-like notation, instead of using brackets and ellipses to indicate hypothetical, we simply keep track of the hypotheses at each step. For example, the implication introduction rule looks like: $$\dfrac{A\vdash B}{\vdash A\implies B}$$ where the propositions to the left of the turnstile ($\vdash$) are the hypotheses for the propositions to the right. More likely, we'd also indicate that there can be other hypotheses by including a (meta)variable for a list of additional propositions traditionally notated with $\Gamma$. That is, we'd write implication introduction as: $$\dfrac{\Gamma,A\vdash B}{\Gamma\vdash A\implies B}$$ In my opinion, it is much easier to understand (and clearly express) the rules of logic using this sequent-like notation (particularly once quantifiers are involved). It does produce a lot of duplication of the hypotheses that the natural deduction notation avoids, but, in practice, you aren't actually going to be making these derivations that often, but instead are going to be looking at them to better understand logic. (When you really do want to make these types of derivations, there's tooling nowadays that can easily handle this duplication.)

Mario Román's derivations using this notation look like: $$\dfrac{\dfrac{}{A\vdash A}\qquad\dfrac{}{A\vdash A}}{\dfrac{A,A\vdash A\land A}{\dfrac{A\vdash A\land A}{\vdash A\implies A\land A}}}\qquad\text{ and }\qquad\dfrac{\dfrac{}{A\vdash A}\qquad\dfrac{}{A\vdash A}}{\dfrac{A,A\vdash A\land A}{\dfrac{A\vdash A\implies A\land A}{\vdash A\implies (A\implies A\land A)}}}$$ where the extra step on the left is a use of contraction. Type theoretically, this looks like: $$\dfrac{\dfrac{}{x:A\vdash x:A}\qquad\dfrac{}{x:A\vdash x:A}}{\dfrac{x:A,x:A\vdash (x,x):A\times A}{\dfrac{x:A\vdash (x,x):A\times A}{\vdash \lambda x:A.(x,x):A\to A\land A}}}\ \text{and}\ \dfrac{\dfrac{}{x:A\vdash x:A}\qquad\dfrac{}{y:A\vdash y:A}}{\dfrac{x:A,y:A\vdash (x,y):A\times A}{\dfrac{x:A\vdash \lambda y:A.(x,y):A\to A\times A}{\vdash \lambda x:A.\lambda y:A.(x,y):A\to(A\to A\times A)}}}$$

---
Tags: proof-assistants, natural-deduction
---


# Question
Title: Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive
I'm stuck on this problem:

Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ $$f^{-1} = \left\\{\begin{array}{rcl} x & \mbox{if} & f(x) = y \\ \uparrow & \mbox{otherwise}\end{array}\right.$$ is partial recursive.

So to prove that a function is partial recursive I have to show that I can build it from basic recursive functions (successor, projection and constant) by applying composition, primitive recursion and then minimization.

I don't know what form $f$ has, but I think I can use it to construct $f^{-1}$. The only problem is that I don't know what to write...

# Answer
You can partially compute $f^{-1}(y)$ as follows:

> for $x$ from $0$ to $\infty$:
>
> if $f(x) = y$ then return $x$

If you don't like for loops, you can use the following implementation:

> 1. $x \gets 0$
> 2. if $f(x) = y$ then return $x$
> 3. $x \gets x + 1$
> 4. goto step 2
> 1 votes

---
Tags: computability, proof-techniques
---


# Question
Title: Difficulty understanding the faster multiplication hardware
This is a picture of faster multiplication hardware taken from **Computer Organization and Design (5th Edition)**. I'm having some difficulty understanding it. I was trying to simulate this for a test multiplication of : 1011 x 101. Firstly, `P0` is simply the LSB of the (`Mplier0 * Mcand`) which gives `P0 = 1` The two operands of the upper rightmost adder would be then, 1011 (`Mplier0 * Mcand`) and 0000 (`Mplier1 * Mcand`) which would produce the result 1011 with `P1 = 1`. This 1011 would then be one of the inputs of the second stage adder. The other input of the second stage/level adder would come from the upper 2nd rightmost adder. Which gives 1011 (`Mplier2 * Mcand`) + 0000 (`Mplier3 * Mcand`) = 1011. So the two inputs of the second stage adder are both 1011. Finally the output of this second stage adder will be 1011 + 1011 = 10110. The penultimate result is 1011011. But the correct answer is 110111. What am I doing wrong here?

# Answer
> 4 votes
You want to multiply x by y, where both are 32 bit numbers.

The result is the sum of 32 numbers. The first number is x if bit #31 of y is 1, and 0 if bit #31 of y is 0. This number is shifted by 31 bits. The second number is x if bit #30 of y is 1, and 0 if bit #30 of y is 0. This number is shifted by 30 bits. And so on. The last number is x if bit #0 of y is 1, and 0 if bit #0 of y is 0. This number is shifted by 0 bits.

So you have 32 numbers to add. You use 16 adders in parallel to add the first and second, the third and fourth, the fifth and sixth number and so on. You get sixteen 34 bit results. Next you use 8 adders in parallel to each add two of these sums. Then 4 adders in parallel, then 2 adders in parallel, then one adder to get the final result.

Obviously you figure out how big each result can be, and where you would be adding zeroes (which obviously don't need adding). In total you need 31 adders, five levels deep, so the delay for the multiplier is about five times that of a 32 bit adder.

(BTW. There are methods that can get the result faster and I think with less hardware).

---
Tags: computer-architecture, multiplication
---


# Question
Title: How does computer store non-repeating decimal very accurately?
Maybe it is not accurate at all, but it looks very accurate for me. I'm making a scientific calculator for my portfolio, and I found an interesting phenomenon.

Because computers store decimals not accurately but approximately, I thought that ***asin(sin(30rad))*** wouldn't give 30rad, and ***sqr(sqrt(7))*** wouldn't give 7, etc..

However, it seems that every kind of calculations like above gives an accurate result. (I used **cmath** header of c++, and I checked that python **math** modules also gives the same)

This consequence seems even arcane to me. Does the computer really store those non-repeating deicmals? or is it just a matter of implementation of math libraries, like substituting a special symbol for them?

# Answer
> 6 votes
It may be that sqr (sqrt (7)) is *displayed* as 7, but it isn't actually exactly equal to 7. That's something you need to check. What you see is not always what you get. It may be that sqr (sqrt (7)) *is exactly* 7, by "coincidence" (not really coincidence, more like "unpredictable with my limited knowledge").

Take any floating point number x, 1 ≤ x \< 4. When the square root is calculated, you get another floating point number y, 1 ≤ y ≤ 2. There are fewer floating point numbers (about half as many) 1 ≤ y ≤ 2 as floating point numbers 1 ≤ x \< 4. If you square two numbers y and y', that calculation doesn't know how y and y' were created. So there are about half as many floating point numbers sqr (sqrt (x)), 1 ≤ x ≤ 4, as original numbers in that interval. So for about half the numbers, sqr (sqrt (x)) ≠ x.

The other way round, calculating sqrt (sqr (x)), you can probably prove that the result must be equal to x if both operations are calculated with high quality. If the squaring operation produces a relative error epsilon, then the square root operation divides that relative error by two.

PS. Yuval checked that for x = 7, sqr (sqrt (x)) is *not* equal to x. If you checked all integers from 1 to 10,000 except those that are squares, I'd expect that sqr (sqrt (x)) equals x in about half the cases that you check.

# Answer
> 3 votes
If you compute the square root of 7 and then square it, you won’t get exactly 7. Here is what I get in python:

> \>\>\> math.sqrt(7)\**2
>
> 7.000000000000001

And here is what you get if you print the value instead:

> \>\>\> print math.sqrt(7)\**2
>
> 7.0

What happened? When printing a floating point value, the default precision is 12 decimal digits (in python). Since `math.sqrt(7)**2` differs from 7 in the 15th digit, when rounding to 12 digits we just get 7, giving you the illusion that there is no error.

# Answer
> 0 votes
Let's play with "bc -l"

* IEEE single : 1 (sign) + 8 (exp) + 23 (mantissa) \[+1 hidden\]
* IEEE double : 1 (sign) + 11 (exp) + 52 (mantissa ) \[+1 hidden\]

sqrt(7) = 10.10100101010011111111010100111010010111110001110100110110111100011\ 10011101010011111100110000111111100001101111010001000001101010101001... (binary)

With single precision, we store 23bits :

**SQ7S** = 10.1010010101001111111101 \[next truncated bits are 010011...\] (no additional rounding needed)

With double precision, we store 52 bits :

**SQ7d** = 10.101001010100111111110101001110100101111100011101001 \[next trucated bits are 1011...\]

Due to the default "round to nearest-even" rounding rule, this double precision number will be rounded up to :

**SQ7D** = 10.101001010100111111110101001110100101111100011101010

Calculating the square :

**SQ7S** * **SQ7S** = 110.111111111111111111111 \[00100...\] = 6.999999523... (decimal)

**SQ7D** * **SQ7D** = 111.00000000000000000000000000000000000000000000000000 \[1011...\]

rounded to : **SQ7D** * **SQ7D** = 111.00000000000000000000000000000000000000000000000001 = 7.000000000000000888... (decimal)

**So : Neither single nor double precision IEEE float gives exact result to sqr(sqrt(7)), but the double precision result is closer, of course.**

(I have also tried with x87-style long double, 64bits mantissa, and it is still wrong)

---
Tags: floating-point
---


# Question
Title: Is it possible for a maximum weight edge of a cycle being included in MST?
Let C be a cycle in a simple connected weighted undirected graph. Let "e" be an edge of maximum weight on C Which of the following is TRUE?

(A) No minimum weight spanning tree contains e.
(B) There exists a minimum-weight spanning tree not containing e.
(C) no shortest path, between any two vertices, can contain e.
(D) None

This was a question for which I gave the answer A because I thought using Kruskal's algo & since the maximum weight edge is lying on the cycle, we will always have an opportunity to select an edge with lesser weight.

# Answer
> 4 votes
The answer to the question in the title, "is it possible for a maximum weight edge of a cycle being included in MST?", is "not necessarily".

**The correct answer to the multiple-choice question is (B).**

**A counterexample to (A)**: Let $G$ be an triangle with weight $1$, $1$ and $1$. Let $e$ be any edge of $G$.

The answer by raindrop says (A) is correct. However, he/she also points out that "A possible exception is if multiple edges have the same maximum weight, e.g. there are multiple maximum edges on $C$ which qualify to be labeled $e$. In that case, a minimum weight spanning tree may contain $e$". Let me repeat the condition about $e$ in OP's post is **Let "$e$" be an edge of maximum weight on $C$**. The article "**an**" in "**an edge**" does indicate that possibility. Since we are in math or computer science, one counterexample or one exception is enough to prove the fallacy of a statement.

**Proof of (B)**: Let $m$ be an MST of $G$. If $e$ is not in $m$, we are done. Now suppose $e$ is in $m$. If we remove $e$ from $m$ (but do not remove $e$'s vertices), $m$ will be split into two trees, which we name $m\_1$ and $m\_2$. As a cycle that connect $m\_1$ and $m\_2$ by $e$, $C$ must also connect $m\_1$ and $m\_2$ at another edge, which we name $e'$. Then $m\_1$ together with $m\_2$ and $e'$ is an MST of $G$ that does not contain $e$.

**A counterexample to (C)**: Let $G$ be an triangle with weight 1, 1 and 1. Let $e$ be any edge of $G$. The shortest path between $e$'s two vertices contains one edge, $e$ itself.

**(D) is wrong since (B) is correct**.

# Answer
> 1 votes
Yes, the answer is A.

Given a connected weighted undirected graph $G$. Let there be a cycle $C$ with $n$ vertices. Let the vertices connected in $C$ be labeled $v\_i$. Let there be a maximum weight edge, labeled $e$, where the vertices on either side of $e$ is labeled $v\_1$ and $v\_n$ respectively.

```
   2 ---- n-1
  /         \
 /           \
1-------------n
       e

```

Suppose that the MST for $C$ contained edge $e$. In this case, either edge $v\_1v\_2$ or edge $v\_{n-1}v\_n$ has been omitted from the cycle in favor of edge $e$ to produce the MST. However, since edge $e$ is the maximum weight on the cycle, those other edges are guaranteed to have a smaller weight than $e$. In this case the total weight of those spanning trees which omit $e$ will be lower than the weight of our MST. This is a contradiction. Therefore, the MST for $C$ cannot contain edge $e$.

A possible exception is if multiple edges have the same maximum weight, e.g. there are multiple maximum edges on $C$ which qualify to be labeled $e$. In that case, a minimum weight spanning tree may contain $e$.

---
Tags: minimum-spanning-tree
---


# Question
Title: How to find the optimum solution of Weighted set cover in O(2^n)
A weighted set cover problem is:

> Given a universe $U=\\{1,2,...,n\\}$ and a collection of subsets of $U$, $\mathcal S=\\{S\_1,S\_2,...,S\_m\\}$, and a cost function $c:\mathcal S\to Q^+$ , find a minimum cost subcollection of $\mathcal S$ that covers all elements of $U$.

How to design a deterministic algorithm to solve weighted set cover in $O(2^n)$ (just find the optimum solution)?

If I simply use exhaust searching to look through all possible cover (which is actually equals to $2^m$) and find the one with minimum weight, it will cost $O(2^m)$ but not $O(2^n)$.

# Answer
> 1 votes
Use dynamic programming. For every $i \in \[m\]$ and every $V \subseteq U$, compute the minimal weight of sets among $S\_1,\ldots,S\_i$ needed to cover $V$.

Here is pseudocode, which uses $w\_i$ for the weight of $S\_i$:

1. Set $T\[V\]\[0\] \gets \infty$ for all $\emptyset \neq V \subseteq U$, and $T\[\emptyset\]\[0\] = 0$.
2. For $i = 1,\ldots,m$:
    * Set $T\[V\]\[i\] \gets T\[V\]\[i-1\]$ for all $V \subseteq U$.
    * Set $T\[V \cup S\_i\]\[i\] \gets \min(T\[V \cup S\_i\]\[i\], T\[V\]\[i-1\] + w\_i)$ for all $V \subseteq U$.
3. Return $T\[U\]\[m\]$.

---
Tags: algorithms, complexity-theory
---


# Question
Title: How do non-deterministic algorithms work on current machines?
I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms *do not* rely on any randomness whatsoever? In which case, this Wikipedia article which mentions Fermat's little theorem includes generating random numbers. I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?

Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time? If not, what bearing would this have on the P=NP problem?

# Answer
> 4 votes
> Is it right that non-deterministic algorithms do not rely on any randomness whatsoever?

Yes and no. Non-determinism just means that there in the computation there is a choice that needs to be made based on information not available to the algorithm. There are multiple solutions to this choice, one of which is randomness - for example in random pivot quicksort.

> I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?
>
> Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

There are four main approaches (to my knowledge) for dealing with non-determinism: parallelism, randomness, backtracking and superstates.

1. Parallelism: whenever a choice needs to be made split the program and investigate all choices in parallel.
2. Randomness: use randomness to choose a single choice out of all.
3. Backtracking: deterministically choose a choice (e.g. the first one) and continue computation with that choice. When that choice wasn't correct go back and choose the second options, etc.
4. Superstates: track all possible states the program can be in, and whenever input is received apply that input to all possible states, merging states and rejecting states eagerly.

Note that not all approaches are always valid and/or feasible. Parallelism is rarely feasible as it requires a lot of physical resources and not much non-determinism, randomness is only correct if each choice is *correct*, and it's just a matter of performance.

To directly implement a NFA either 3 or 4 is used. Another example of 4 are full CFG parsers that can handle ambiguity such as an Earley parser.

> Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time?

By necessity, because the resulting output can have an exponential number of states.

---
Tags: algorithm-analysis, finite-automata, nondeterminism
---


title: Is the language $a^nwa^n$ regular?

text:
# Question
Title: Is the language $a^nwa^n$ regular?
The given description of language is:

> $\Sigma=\\{a,b\\}$ and $L=\\{a^nwa^n:n\geq 1,w\in\Sigma^\*\\}$

I felt its regular as we can always interpret $aabaa$ in string $aaabaaa$ as $w$. That is we can always interpret $a^n(a+b)^\*a^n$ as $a(a+b)^\*a$. So isnt it correct to call this language regular. The book calls it not regular without any explanation. So I was just confused, what is correct.

# Answer
Your language is regular, since it is identical to $a\Sigma^\*a$.

Indeed, by definition of $L$, every word of the form $a\Sigma^\*a$ is in $L$ (take $n = 1$). Conversely, every word in $L$ starts and ends with $a$ (and is of length at least 2), and so is of the form $a\Sigma^\*a$.
> 2 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Two criteria for an edge to belong to all MSTs
Let $G$ be a connected undirected graph, with integral positive weights on the edges, and let $e\_1$ be an edge of $G$. As part of an assignment I proved the following Lemma 1:

> The edge $e\_1$ appears in any MST of $G$ iff $e\_1$ is a light edge in any cut $C$ that it crosses.

Is it equivalent to the following Lemma 2?

> An edge $ = (, )$ appears in all MSTs of $$ iff every cycle including $$ has an edge $′$ with $() \< (')$.

The latest is clearly a negation of the red rule for MSTs. I think they are equivalent but can't prove it.

# Answer
There is a serious typo/mistake in the OP's (original) question. The title say "Two criteria for an edge to belong to all MSTs". However, the lemma 1 talks about "appears in any MST". To be consistent with the title and with lemma 2, let us modify the lemma 1 as:

> An edge $e$ appears in all MSTs iff $e$ is the unique lightest edge in the cut-set of some cut which $e$ crosses.

According to the title of the question, we may assume the OP's intention is to prove the two criteria for an edge to belong to all MSTs is equivalent without any reference to MST. (If reference to MST is allowed, both criteria are equivalent to the statement, the edge belongs to all MSTs. Hence both criteria are equivalent to each other as well.)

Let us state the equivalence of the two criteria clearly.

> Let $G$ be a weighted connected undirected graph and $e$ an edge in $G$. The following two properties of $e$ are equivalent.
>
> * (**unique-cut-lightest**) there is a cut of $G$ such that $e$ is the unique lightest edge that crosses the cut.
> * (**non-cycle-heaviest**) every cycle containing $e$ contains an edge heavier than $e$.

It turns out we do have a simple proof of the above equivalence.

**Unique-cut-lightest $\Rightarrow$ non-cycle-heaviest**: Let $c$ be a cycle that contains $e$. As a cycle, $c$ must contains another edge in that cut-set. Name that edge $e'$. Since $e$ is the unique lightest edge in that cut-set, $e'$ is heavier than $e$.

**Unique-cut-lightest $\Leftarrow$ non-cycle-heaviest**: Let the vertices of $e$ be $u$ and $v$. Let us remove $e$ and all edges that is heavier than $e$ in all cycles that contains $e$ from $G$ (keeping all the vertices, however), obtaining a new graph $G'$ that share the same vertices as $G$ but with less edges. There is no path from $u$ and $v$ in $G'$; otherwise, any such path together with $e$ is a cycle in $G$ that contains no edge that is heavier than $e$, which contradicts the assumption. So $u$ and $v$ are in different connected components of $G'$. Divide the vertices of $G'$ into two sets, the vertices in the connected component of $u$ and all the other vertices. These two sets of vertices is a cut of $G$ as well. $e$ crosses that cut since $u$ is in the connected component of $u$ and $v$ is not. Since all edges other than $e$ crossing that cut is one of the removed edges, $e$ is the unique lightest edge crossing that cut.
> 2 votes

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


# Question
Title: Determining if given languages are regular or recursively enumerable
I came across following problem:

> Suppose $L\_1$ and $L\_2$ are two languages, $M$ is a Turing machine
> $L\_1 =\\{M|M$ accepts at most 2016 strings$\\}$
> $L\_2=\\{M|M$ accepts at least 2016 strings$\\}$
> If $L=L\_1\cap L\_2$, then which one of the below is correct?
> A) $L'$ is recursively enumerable
> B) $L\cap L'$ is recursively enumerable
> C) $L\cup L'$ is recursively enumerable
> D) $L$ is recursively enumerable

The solution given was:

> $L\_1$ by definition is regular language (“atmost”). $L\_2$ by definition is recursively enumerable (“at least”). Recursively enumerable languages are closed under regular intersection. Hence, $L = L\_1 ∩ L\_2$ is recursively enumerable. Thus option D. Recursively enumerable languages are not closed under complementation. Hence $L’$ is not recursively enumerable. Hence option A is wrong. And since $L’$ is not recursively enumerable, options B and C are also wrong.

**My doubt**

I am struggling with how $L\_1$ is regular and $L\_2$ is recursively enumerable, that is with first two sentences:

> $L\_1$ by definition is regular language (“atmost”). $L\_2$ by definition is recursively enumerable (“at least”).

Usually language definition specifies criteria on format of input string which will allow us to reject or accept it. But here the definition specifies how many strings the language has or its corresponding Turing machine accepts.

I found this similar sounding problem, in which the answer gives membership algorithm and hence proving language in that problem is indeed recursively enumerable. But I feel this does not applies in my problem. Correct? Or the problem is incorrect in telling number of strings languages can accept instead of format of acceptable strings?

# Answer
> 5 votes
Your intuition is entirely correct; this solution is nonsense. $L\_1$ isn't a regular language; it's not even a *decidable* language, by Rice's Theorem, and also not recognizable (aka recursively enumerable).

$L\_2$ is in fact recognizable. The following algorithm recognizes it:

> Take an encoded Turing machine $M$ as input. First simulate it on every input of length ≤ 1 for 1 step, then on every input of length ≤ 2 for 2 steps, and so on. Keep track of how many distinct inputs it's ever accepted. If this number ever exceeds 2016, return True.

But as it turns out, none of this matters to the actual problem. Note that (C) is taking the union of a language with its complement, and the union of any language with its complement is $\Sigma^\*$. This language is regular, thus decidable, thus recognizable. So the correct answer is (C).

EDIT: Of course, the intersection of a language with its complement is $\varnothing$, which is also regular, thus decidable, thus recognizable. So (B) is also true.

---
Tags: formal-languages, regular-languages, undecidability, semi-decidability
---


# Question
Title: Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is **not** recursively enumerable
So I tried to prove that $D =\\{x \in \mathbb{N} | \Phi\_x(x)\uparrow\\}$ is **not** recursively enumerable in the following way:

* let's suppose that $g$ is the computable function that represents $D$ $$g(x) = \left\\{\begin{array}{rcl} 1 & \mbox{if} & \Phi\_x(x)\downarrow\ \\ 0 & \mbox{if} & \Phi\_x(x)\uparrow\ \end{array}\right.$$
* let's suppose that it exists a Turing machine of index $i\_0$ such that $g = \Phi\_{i\_0}$, than it is possible to define the function: $$g'(x) = \left\\{\begin{array}{rcl} \uparrow & \mbox{if} & g(x)=1=\Phi\_{i\_0}(x) \\ 0 & \mbox{if} & g(x)=0=\Phi\_{i\_0}(x) \end{array}\right.$$
* so $g'$ is also computable thus there is a Turing machine of index $i\_1$ such that $g' = \Phi\_{i\_1}$, but then we will have that: $$\Phi\_{i\_1}(i\_1)\downarrow \iff g'(i\_1) = 0 \iff g(i\_1) = 0 \iff \Phi\_{i\_1}(i\_1)\uparrow $$ $$\Phi\_{i\_1}(i\_1)\uparrow \iff g'(i\_1) \uparrow \iff g(i\_1) = 1 \iff \Phi\_{i\_1}(i\_1)\downarrow $$

which is a contraddiction. So an index $i\_1$ doesn't exists that is the index $i\_0$ that computes $g$ doesn't exists, that is $g$ is not recursive so $D$ is **not** recursive enumerable.

I'm quite confused on this topic, so tell me if I made any kind of error.

# Answer
> 2 votes
As Andrej states, what you've (correctly) done is show that $D=\\{x:\Phi\_x(x)\uparrow\\}$ is not *recursive*. However, there are plenty of sets which are recursively enumerable but not recursive, so you're not done yet: you need to show that $D$ is not the domain of any partial recursive function.

*REMARK: Some texts define a set to be r.e. if it is the **range** of a **total** recursive function, or is empty. This is slightly less elegant since it requires a separate clause to handle $\emptyset$; it also generalizes less well if one looks into higher computability theory. However, regardless of what definition your book gives, the equivalence between them should be a very early exercise.*

There are a couple ways to do this:

* You could argue directly: suppose $D$ is the domain of $\Phi\_i$. Can you use the recursion theorem to cook up a $j$ such that $\Phi\_j(j)\downarrow\iff \Phi\_i(j)\downarrow$? Do you see why this gives a contradiction?
* Alternately, note that $D$ is the complement of the *Halting Problem* $H=\\{x: \Phi\_x(x)\downarrow\\}$. Two early results in computability theory are that (i) $H$ is r.e. but not recursive and (ii) if a set and its complement are r.e., then they are each recursive. Do you see how to prove each of these facts, and apply them to the current problem? *(Note that this approach isn't actually much different than the first one, since the recursion theorem is used in proving (i).)*

*REMARK: Some texts define the Halting Problem differently, some common alternate candidates being $\\{x: \Phi\_x(0)\downarrow\\}$ and $\\{\langle x, y\rangle:\Phi\_x(y)\downarrow\\}$. It's a good exercise to show that these are all r.e. and Turing equivalent (indeed $1$-equivalent!) to each other.*

By similar arguments you can show that minor variations of $D$ are also not r.e. - e.g. can you show that $\\{x: \Phi\_x(17)\uparrow\\}$ is not r.e.?

---

Responding to the comments: one may be tempted to try to enumerate $D$, or things like $D$, by looking at *approximations given by stages*. E.g. we could let $D\_s=\\{x:\Phi\_x(x)\[s\]\uparrow\\}$; this is the set of indices of machines which on their own input don't halt *in fewer than $s$ steps*. The $D\_s$s are r.e. - indeed, uniformly recursive - and approximate $D$ "from above" in the sense that $D=\bigcap\_{s\in\mathbb{N}} D\_s$. However, this ultimately isn't relevant to this problem since the intersection of infinitely many r.e. sets need not be r.e.

---
Tags: computability, proof-techniques
---


# Question
Title: Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$
How can I express this language $L = \\{0^n 1^{2n} \mid n ≥ 0\\}$ as a context-free grammar?

I am new to this field and I am not sure what should I do. Please help me.

# Answer
As Yuval commented, this is a very basic exercise so you should probably go over the basic definitions. One simple answer for this particular question is: $$S\rightarrow0S11|\varepsilon$$
> 0 votes

---
Tags: formal-languages, automata, context-free, formal-grammars
---


# Question
Title: Will we ever achieve a $O(n)$ general purpose sorting algorithm (or at least better than $O(n\log(n)))$?
I've been thinking about this question ever since I learnt about the $O(n\log(n))$ sorting algorithms such as MergeSort, QuickSort (average case is pretty much worse case with a good choice of a pivot) and HeapSort. I've been thinking how can we possibly achieve a greater class of efficiency in worst case? Can we do so using specific hardware implementations? A sort that requires a large amount of space? There is indeed RadixSort and BucketSort, but those are only $O(n)$ in specific use cases.

# Answer
To expand on what blue-dino wrote, is it indeed impossible to make a general sorting algorithm with worst-case (or even average-case) complexity which is better than $O(n\log(n))$. In this case "general sorting algorithm" refers to the comparison based model of sorting - it means that the only operation our sorting algorithm is allowed to make is a comparison between two elements which tells us what element is bigger/smaller (or equality), but we get no further information.

The proof of this lower bound is based around building a "comparison-tree" with all possible sortings of a group of $n$ different elements, and proving that there will always be a branch of length $O(n\log(n))$, which corresponds to a similarly long computation or run of the algorithm. As I mentioned beforehand, such length can also be proven to be the average length of a branch in the comparison tree, therefore providing a lower limit to the average complexity as well.
> 3 votes

# Answer
No, n lg n is a theoretical lower bound for general sorting. You can get linear time for special cases. A proof of this fact can be found on cormen.
> 1 votes

---
Tags: asymptotics, sorting, efficiency
---


# Question
Title: Comparing variable image to static image
What are Levenshtein distance algorithms, but for images?

I will have one static image (the target: what it should look like) and one variable image (actual: what the user has created)

For example,

Target:

The following should be classified as "close enough"

Actual:

But the following should be classified as "incorrect" (even though it has 2 strokes and fills the '|' part)

I will be using this as a guide for users new to the English alphabet to practice on writing.

I will, of course, have other checks in place such as counting the number of strokes made (2 for 'K', 1 for '|', 1 for '\<') and also checking to see if the area covered is reasonable (filling whole area should not be identified as "correct").

The user "drawing" will only be in black and white (not greyscale).

I suppose I could train a neural network (like handwriting recognition) but only to identify if it is "close enough". I think this is overkill as this only requires checking to see if it matches a single image and not selecting the best-matching image from a set.

# Answer
I think you're really asking for a distance metric on images. Based on your examples, I would suggest the L2 distance (sum of squares of differences in pixel intensities) or L1 distance; possibly after aligning the images. This looks like it should b effective for the examples you list.
> 0 votes

---
Tags: algorithms, computer-vision, image-processing
---


title: Time complexity calculation

text:
# Question
Title: Time complexity calculation
I was calculating the time complexity of the following recurrence relation given that T(1) = 1 :

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

I was calculating the value and this is where I reached:

T(n) = logn + 2log(n/2) + 4log(n/4) + 8log(n/8) + .....+ 1

I have tried solving this by opening log but I'm unable to reach O(n). I don't want any other method like substitution or root tree to be used. I want to use simple maths and reach O(n), please let me know if you have a clue about it.

# Answer
Suppose that $n = 2^k$, and that the logarithm is base 2. Then $$ T(2^k) = \log (2^k) + 2 \log(2^{k-1}) + 4 \log(2^{k-2}) + \cdots + 2^{k-1} \log 2 + 2^k T(1) \\ = k + 2(k-1) + 4(k-2) + \cdots + 2^{k-1}(k-(k-1)) + 2^k T(1) \\ = (1+2+4+\cdots + 2^{k-1})k - (2^1 \cdot 1 + 2^2 \cdot 2 + \cdots + 2^{k-1}(k-1)) + 2^kT(1). $$ The first summand is equal to $(2^k-1)k$. The second is equal to $$ (2^1 + \cdots + 2^{k-1}) + (2^2 + \cdots + 2^{k-1}) + \cdots + (2^{k-1}) = \\ (2^k-2^1) + (2^k-2^2) + \cdots + (2^k-2^{k-1}) = \\ (k-1)2^k - (2^1 + 2^2 + \cdots + 2^{k-1}) = \\ (k-1)2^k - (2^k-2) = (k-2)2^k + 2. $$ In total, we get $$ T(2^k) = (k2^k - k) - (k2^k - 2^{k+1} + 2) + 2^k T(1) = 2^{k+1} - k - 2 + 2^k T(1). $$ In terms of $n$, this is $$ T(n) = (2 + T(1))n - \log n - 2. $$
> 1 votes

# Answer
Fix the one error in the calculation, and order the terms with the largest first: $T(n) = n + \log 2 n/2 + \log 4 n/4 + \log 8 n/8 ... $

Now replace $\log n$ with the larger $n^{1/2}$ and you get

$T(n) ≤ n + 2^{1/2} n/2 + 2^{1/4} n/4 + 2^{1/8} n/8 ...$

$T(n) ≤ n (1 + 2^{-1/2} + 4^{-1/2} + 8^{-1/2} ...)$

That's a geometric series that converges to $n / (1 - 0.5^{1/2})$
> 0 votes

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Induction on typing derivation in refinement types system
From the text Principles of Type Refinement page 14:

The author introduces in definition 2.2.7 the rule:

$$ \dfrac{\Pi \vdash t : R \qquad R \le S}{\Pi \vdash t : S} $$

and gives the following contravariant form:

$$ \dfrac{\Omega \le \Pi \qquad \Pi: t : R}{\Omega \vdash t:R} $$

where $\Omega,\Pi \sqsubset \Gamma$ and $\Omega \le \Pi$ is interpreted as if the type assigned to each variable in $\Omega$ is a subtype of the type assigned to the same varaible in $\Pi$.

The author then states that this rule is admissible in the refined simply typed lambda calculus and that this can by shown by induction on typing derivations.

I'm used to natural and structural induction. But what does it mean to perform induction on typing derivations? Can you given an example?

# Answer
It's a form of structural induction.

As we see on page 12 of the text, the typing relation is defined *inductively* by four rules.

For example, the rule *abs* says that given a deduction $\Gamma, x:r \vdash t : S$ we can form the new deduction $\Gamma \vdash \lambda x.t : R \to S$.

Compare with how, given a natural number $n$ you can form a new natural number $n+1$.

To prove a proposition $P(n)$ about an arbitrary natural number by induction you note that $n$ is either

1. $0$, or
2. $m+1$ for some $m$

In the first case, you prove $P(0)$ directly. In the second, you assume you have a proof of $P(m)$ and use this to prove $P(m+1)$.

Similarly, to prove a proposition about an arbitrary derivation $\Delta$ of the type judgement $\Pi \vdash t :R$ you note that $\Delta$ is either

1. $ \dfrac{}{\Pi \vdash x : R}\textsf{ var}$ and $t=x$ a variable
2. $\dfrac{\Pi \vdash s : S \to R, \Pi \vdash u : S }{\Pi \vdash s(u) : R}\textsf{ app}$ and $t=s(u)$, an application, for some derivations $\Delta\_1, \Delta\_2$ of the type judgements $\Pi \vdash s : S \to R, \Pi \vdash u : S $
3. $\dfrac{\Pi, x:r \vdash s : S}{\Pi \vdash \lambda x.s : R \to S}\textsf{ abs}$ and $t=\lambda x.s$, an abstraction, for some derivation $\Delta\_1$ of the type judgement $\Pi \vdash s : S$
4. $\dfrac{\Pi \vdash t:S, R \leq R}{\Pi \vdash t : R}\textsf{ sub}$, for some supertype $S$ of $R$ and a derivation $\Delta\_1$ of $\Pi \vdash t : S$

In the first case, you prove $P(\Delta)$ directly, and in the other three you assume $P(\Delta\_1)$ and $P(\Delta\_2)$ and then prove $P(\Delta)$.

There is an example in the proof of lemma 2.3.10 of the text, page 33.
> 3 votes

---
Tags: type-theory, induction
---


# Question
Title: Is deep learning appropriate to approximate dynamic programming problems?
I have a problem which can be completely solved using dynamic programming, but in a very intractable way (On^4, where n is around 1000). I won't get into the details of the problem since it's a bit complicated, but it involves comparing properties of subsequences of a single string, where the property of subsequence (xi... xj) is related in a complex way to the property of subsequence (xi... xj + 1). I am fine with getting an approximation of the correct answer, but obviously would like to maximize correctness and minimize compute.

I have a well-defined metric for how good an answer is, but I have no idea what approach I should be using to solve it. I was thinking about turning it into a reinforcement learning problem for a deep neural network, as a way of avoiding having to find the best algorithm myself. I realized that I have no intuition for the kind of "algorithmic" problems for which deep reinforcement learning fits well. For instance, playing Go well was considered an "algorithmic" problem and has been advanced by using deep reinforcement learning, but the fact that it is nontrivial to teach multiply makes me think that certain seemingly simple problems might be out of reach. Is there a good way to think about what problems are well suited for deep reinforcement learning?

# Answer
> 1 votes
A good start would be to understand what reinforcement learning is; and identify which problems are reinforcement learning problems and which aren't. Deep reinforcement learning is only relevant if you have a reinforcement learning problem; otherwise, it's almost certainly not relevant. Among other things, reinforcement learning deals with a stateful system. You don't seem to have a stateful system so it's not clear to me why you think reinforcement learning would be relevant.

Since you haven't told us what the problem is, it's hard to imagine how we can tell you how to solve it; all I can share is general principles. In general, deep reinforcement learning isn't magic that you use whenever a problem is too hard for normal methods; it is useful for a specific purpose, and I don't see any reason to expect it to be effective or applicable here.

---
Tags: dynamic-programming, neural-networks, approximation, reinforcement-learning, neural-computing
---


# Question
Title: Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?
I am trying to prove the algorithm for Question 5 in this practice exam.

I am trying to prove this algorithm with the following three claims:

1. Suppose we have a graph G, a minimum spanning tree T, and a set of edges A that is a subset of T. Suppose that we also have a cut C = (S, V - S) that respects A, and edge e = (u, v) is a light edge for that cut. Then, A $\cup$ { e } is also a subset of some minimum spanning tree T'.
2. Suppose we have a graph G with |V| vertices that has a minimum spanning tree. Suppose we also have a set of |V| - 1 edges = \<$e\_1$, $e\_2$, ..., $e\_n$\>, such that each edge is a light edge for some cut C, and these edges do not form a cycle. This set of edges must form a minimum spanning tree.
3. The algorithm given will generate a set of acyclic |V| - 1 edges each of which is light for at least one cut; thus, it will generate a minimum spanning tree.

The first and third claims are easy to prove, but I am unable to prove the second claim. This is what I have so far:

> Trivially, the set of edges must form a spanning tree - it is not possible to have |V| - 1 edges and no cycles without connecting all |V| vertices.
>
> This spanning tree must also be a minimum spanning tree: suppose we have a new empty set of edges A. A is trivially a subset of some minimum spanning tree for G. A $\cup$ { $e\_1$ } is also a subset of some MST by Claim 1 (because $e\_1$ is a light edge for cut C which trivially respects the empty set A).
>
> Now let us examine edge an edge $e\_2 = (u, v)$ that is incident to one vertex touched by $e\_1$. We can assume without loss of generality that there is currently no edge incident to $v$. \[I can't prove that $e\_2$ is safe to add\].

I was wondering if this claim is even correct - and if so, how I can go about proving it.

# Answer
The answer to the question in the title, "Is a set of acyclic $|V|-1$ light edges always a Minimum Spanning Tree?" is no. That is, the second claim in the question is not true. Hence, the third claim is not true, either.

Here is **a simple counterexample**. Let $H$ be a graph the complete graph with 4 vertices, $\\{a,b, c,d\\}$ and weights, $ab\rightarrow 1$, $cd\rightarrow 1$, $ac\rightarrow 2$, $ad\rightarrow 2$, $bc\rightarrow 2$, $bd\rightarrow 2$. The weight of a minimum spanning tree $\\{ab, ac, cd\\}$ is $1+1+2=4$. Consider the spanning tree made by the 3 edges, $\\{ac, bc, bd\\}$, each of which is light for the cut $\\{a, b\\}, \\{c,d\\}$. However, the weight of this spanning tree is $2 + 2 + 2 = 6$, which is greater than $4$.

One might be wondering why it might be so hard to come up with a counterexample. Part of the reason might be that if the weights of edges of $G$ are different, then $G$ has only one minimum spanning tree, which includes all light edges for every cut.
> 3 votes

---
Tags: graphs, correctness-proof, minimum-spanning-tree
---


# Question
Title: Can the program determine the frequency of the CPU or is it impossible?
In order to understand the question, imagine a simple situation. Alice tells Bob that her CPU's frequency is X Hz. Bob does not take her word for it. Bob can not meet with Alice and check what frequency her processor really has. Can Bob send her a soft program that accurately determines the frequency of Alice's CPU? Is such a program possible or not in principle?

# Answer
In these days of superscalar, multicore, virtualisation, power scaling, managed operating systems, and so on, what does "CPU frequency" even mean?

Note that it may be possible for Alice to convince Bob that she has compute power capable of performing X operations of a known type in a given time, as you find in a proof-of-work system. If it is a problem for which parallel algorithms are believed not to be feasible, he may be convinced that it happened on a single compute device, and not (say) a cloud or cluster.

But for all Bob knows, Alice may have an asynchronous device which doesn't even have a clock speed.
> 2 votes

# Answer
In certain very specific situations, you might be able to use software-based attestation. See, e.g., the following seminal paper:

Roughly speaking, it tries to prove that Alice's processor is at least as fast as claimed (but the actual guarantees are more interesting and the properties and assumptions are more complex). Read the paper for details to see if it is what you are looking for.
> 1 votes

---
Tags: cryptography
---


# Question
Title: Can you automatically generate a parser for a type using type theory some how?
Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?

# Answer
> 2 votes
In programming languages, we usually distinguish concrete syntax, where a program is represented as a linear list of symbols, from abstract syntax, where programs have a tree structure.

The vast majority of PL theory, including most type systems, happens after parsing, working with abstract syntax.

So, it's impossible to generate a parser simply from type rules or definitions, because there are arbitrarily many concrete syntaxes that could correspond to any abstract syntax. The choice is a purely human one.

In some languages, like Haskell, the description of a data type can be used to generate parsers and printers for types, using the `deriving` mechanism of the typeclass system. But it chooses a syntax that corresponds to the Haskell one by convention, and they could have chosen to define it any other way.

---
Tags: formal-grammars, type-theory, parsers, homotopy-type-theory
---


title: Time Complexity to find height of a BST

text:
# Question
Title: Time Complexity to find height of a BST
Below is a question I was asked in an Interview

What is the best case time complexity to find the height of a Binary Search Tree?

I answered it explaining using the below algorithm

> **$\mathrm{height}(v)$**
>
> if $v$ is a leaf, return 0
>
> otherwise, return $\max(\mathrm{height}(v.\mathit{left}), \mathrm{height}(v.\mathit{right})) + 1$

So, in best case, my recurrence would become

$$T(n)=2T\left(\frac{n}{2}\right) + c.$$

Here $T(\frac{n}{2})$ is for each of the recursive calls, and $c$ for all the rest. So even best case complexity is $O(n)$.

Now, in the worst case, my recurrence would become

$$T(n)=T(n-1)+c,$$

and this would be a case of a skewed BST. Still, here complexity remains $O(n)$.

So, in all cases, the time complexity to find the height of a BST remains $O(n)$.

Is my claim correct?

# Answer
> 9 votes
Your algorithm runs in linear time on *all* inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number of nodes.

The argument above is better than using recurrences, since it is more immediate. It also shows that if you had an arbitrary tree (not necessarily binary), the algorithm would still run in linear time.

---
Tags: algorithms, algorithm-analysis, trees, binary-trees, search-trees
---