title: Do passwords need a max length?

text:
# Question
Title: Do passwords need a max length?
I understand that password storage generally uses hashing for security due to it being irreversible and that the stored hash is just compared to the hash of the password inputed by a user attempting to log in. As hashes are fixed length, does that mean that even if not specified when creating the password, all login systems would need to have some sort of maximum input length (although probably very high)? Allowing inputs larger than the output length would risk collision. This would mean that 2 different passwords could be hashed and appear to match.

# Answer
No. There is no\* limit on the length of the input to for most\* good cryptographic hash functions. As a result, password hashing can support passwords of unlimited length and do not need to impose a limit on the maximum length of the password.

Of course collisions are possible and exist, but they are believed to be exceptionally difficult for anyone to find, so for engineering purposes we can essentially ignore the possibility of collisions, assuming we have chosen an appropriate hash function. See the following:

Separately: I expect you're going to be very interested in What technical reasons are there to have low maximum password lengths?. One ancient password hash function -- which wasn't very good -- did have a maximum length limit, for reasons that aren't relevant today. No one today should be using that ancient hash any longer.

---
> 22 votes

# Answer
Yes, passwords need maximum length, but not because of collision risk (see other answers regarding collisions).

Reason for setting maximum length - possibility of denial of service attack.
Someone might start feeding petabytes into password field, pushing your setup to CPU/memory limits, which would impact other users.

Relevant note: For password hashing one SHOULD use CPU-heavy hash functions (Argon2, bcrypt ok; SHA, CRC32 not ok). It should be CPU-heavy to make brute force attacks harder/impossible, in case your database would be leaked.
> 9 votes

# Answer
> As hashes are fixed length, does that mean that even if not specified when creating the password, all login systems would need to have some sort of maximum input length (although probably very high)?

At least some hash algorithms have some limit to the input length, though those are usually astronomically high, so not an issue in any sense. E.g. SHA-256 embeds the input length as a 64-bit number in the data it internally processes. Of course SHA-256 is not a password hash, but some algorithms used for password hashing use standard hashes internally (like PBKDF), and similar considerations might also apply to the ones that don't.

Then, you might also put some limit out of logistical reasons, so you don't need to run the password hash over gigabytes of data even if some joker decides to try entering a password of such length.

> Allowing inputs larger than the output length would risk collision. This would mean that 2 different passwords could be hashed and appear to match.

But this sounds like you're thinking about the *output* length of the hash, and those are far shorter. E.g. bcrypt produces a 24 (or 23) byte hash, and something that uses SHA-256 would produce 256 bits, or 32 bytes. While those would be sufficient as password lengths, they're not really very high limits and someone using a long passphrase might get hit by them.

However, having the password longer than the hash output length doesn't matter. Hash algorithms are designed to produce a practically random output, so for a 24-byte (192-bit) hash, you'd need on the order of $ 2^{96} $ or $ 10^{30} $ inputs to have an approximately 50 % chance of two of them hashing to the same value. Due to passwords usually being composed of letters (or nearly enough) and not arbitrary bytes, the hash output also makes far better use of the space than the passwords themselves do. That is, the number of 24-character passwords is much smaller than the number of 24-byte hashes, so the length of passwords can be somewhat greater than the hash output length without that leading to a significant risk of collisions.

In any case, hash collisions within an arbitrary pair or passwords also don't matter, since the password hash is used to compare the *single* hash from the attempted login password with the single stored hash. Someone guessing passwords could in theory find one that matches the hash without being the original password, but that won't make it any easier, as each attempt would still only have a 1 in $ 2^{192} $ chance of matching.
> 8 votes

# Answer
Hashes are designed to avoid collisions as much as possible. A perfect hash would completely avoid any collision between passwords up to the length of the hash.

For typical hash lengths, that means that collisions on passwords longer than the original are so rare that they simply preclude any brute-force search.

E.g. with a hash of $128$ bits, pessimistically assuming that $2^{64}$ passwords (up to length $128$ bits, roughly $20$ characters) can hash to the same value, the probability of finding one by chance is only $2^{-64}$.

If you account for arbitrarily long passwords, the probability of collisions indeed increases, but these are just unreachable.
> 3 votes

# Answer
Indeed, all hash functions do produce output of a fixed length, regardless of the length of the input. This does mean that there's a theoretical possibility of collisions — two different inputs producing the same hash. However, for cryptographic hash functions like SHA-256, the number of possible hash values is so large (about 2 256 2 256 ) that the probability of two random inputs producing the same hash (a random collision) is astronomically small.

That said, a system could technically have a maximum password length, but this limit wouldn't be due to the risk of collisions. It would most likely be due to other considerations such as storage, performance, or usability. For instance, it could be computationally expensive to hash a very large input, or it could be impractical for users to enter a very long password.

In terms of security, the risk of collision from long inputs is not a concern in practice. The security of a hash function against collisions is typically evaluated based on its resistance to deliberate collision attacks, where an attacker tries to find two inputs that produce the same hash. This is a much harder problem than finding a collision by chance.

So while it's true in theory that allowing longer inputs increases the chances of a collision, in practice, the chances are still so low that it's not a concern for password storage. The main considerations for password security should be using a secure, slow hash function (like bcrypt or Argon2), using a unique salt for each user, and following best practices for password strength and handling.
> 3 votes

# Answer
You should never store a password, even encrypted, or salted, or salted and encrypted. So for storage, the password length wouldn't matter. Your passwords should be salted and hashed; salting makes sure that an attacker cannot use pre-calculated tables, cannot detect weak passwords, and cannot find weak passwords after stealing a database of hashes. And after hashing, short and long passwords should be hashed to hashcodes of the same length, so the hash doesn't give any information about the password.

Once the password entropy is the same as the possible entropy of your hashes, adding more characters is pointless, it won't improve the quality of the password. On the other hand, telling a user that their password is too long is also quite inconvenient.

You can set a limit but high enough that no reasonable user would ever exceed that length. For example if I have to enter a password manually, a 10,000 character password would be impossible to enter in practice. And when you set the limit, assume that other people than you will feel may feel a length is still reasonable that you feel unreasonable.

Set the limit so high that no sane user will ever notice. As a bad example, one multi billion dollar company doesn't accept a password auto-generated by my iPhone. The passwords are three groups of five letters separated by hyphens. 17 characters. Their site only allowed fifteen. That's obviously very very inconvenient, annoying and error prone. Assume that I use a password generated by my software, and then I append a description of the password usage (it's stored by my device and I never enter it manually, so I don't mind if it's long), so that is easily 40 characters. Assume people using other, longer schemes as well. So if I really wanted to set a limit, it would be either something like 100 characters, or something that the software is guaranteed to handle well.

And make sure you don't have any stupid rules like "the same character must not be used more than twice". If I decided to have a 60 character password, I bet there will be characters occurring more than twice.

Another very important thing: If you change the rules, make sure that I can still enter existing passwords! If you decide to change maximum password length from 21 to 20 chars, or decide that I must use a special character, you better still let me enter my existing 21 letter password without special characters and don't lock me out.
> 1 votes

# Answer
A lot has already been said and I agree with most of it. But there is one thing I don't see mentioned:

Theoretically a collision can occur between two strings that are both much shorter than the output from the hash, so if you should use this as an argument for having a limit on the length of the passwords, you should find the collision between the shortest possible set of inputs, for most (modern) hashes that is *hard*. And if the passwords are salted I don't see any problem that can arise from a collision.

I hate sites that stop me from using whatever my password manager generated, which is a long string of random characters, because they deem it too long, simply for the inconvenience it causes me.

Yes, not setting a (short) limit means that people can log in to my account "just" by trying a password that hashed to the same string as mine, but as long as the site uses a reasonable hash (not e.g. CRC-16) chances are low that any guess they try will hash to the same as my password.
> 0 votes

# Answer
Ignoring that fact that passphrases are salted, and assuming that you are looking for a collision with one specific user.

If passphrases are randomly drawn from ASCII, then each character is represented by about 6.55 bits. As such, once the cleartext passphrase exceeds about 625 characters it is likely that more than one passphrase will hash to the same 4096-bit value.

At that point the amount of work put into guessing a candidate passphrase which will hash to the required 4096-bit value is very roughly the same as simply guessing that 4096-bit value. Any attack is likely to be thrown out because of the number of retries involved, or will become impractical because of an enforced delay between retries.

Guessing a passphrase which collides with that of /any/ user out of a large population is another matter, which is why there's an increasing emphasis on multi-factor authentication. I don't know how this eventually played out, but a few months ago there was speculation that somebody had had his Bitcoin wallet emptied simply by a random attack which struck lucky.
> 0 votes

# Answer
I suspect you're implicitly using the probability of a collision here is a proxy for the "guessability" of a working password. The issue with this is that to the extent that adding a max length constraint reduces the probability of a collision it also reduces the number of possible passwords at the same rate which in the best case exactly counteracts the effect of reducing the probability of a collision.

By definition the average number of passwords which evaluate to a given hash value (assuming a secure hash, regardless of the particular input constraints) is going to be the total number of possible inputs divided by the total number of possible outputs. Simplifying (ignoring the details of any additional password constraints), this would be $ |C|^n \over 2^m$ where $|C|$ is the number of valid characters, $n$ is the length of the string and $m$ is the number of bits of the hash.

Now for any given password the probability of randomly guessing (if the password is chosen in a secure manner this is the best you can do) a working password (one which evaluates to the same hash) from the set of all possible valid passwords will be equal to the number of passwords which evaluate to the same hash divided by the total number of valid passwords which on average would would be $|C|^n/2^m \over |C|^n $ which evaluates to $1 \over 2^m$ and the term involving the length of the password cancels out.

However, since we know the hash value was generated from a valid password the numerator in this case has to be $\geq 1$ and the probability of guessing the correct password therefore has to be $\geq {1 \over |C|^n}$. So if $n$ is small enough that $|C|^n \lt 2^m$ and therefore ${1 \over |C|^n}\gt{1 \over 2^m}$ the "guessability" of any given (secure) password in the system will begin to be defined by the maximum length constraint rather then by the number of bits of the hash and the maximum length constraint will have the effective of reducing rather than increasing the security of the system.
> 0 votes

---
Tags: hash, hashing, security, authentication
---


# Question
Title: What is the technical name for one sided tree traversal and which algorithms are good for it?
Looking at the image from Wikipedia page for tree traversal  what is the name for a traversal that follows the dashed line exactly with repeating visits to obtain: F, B, A, B, D, C, D, E, D, B, F, G, I, H, I, G, F;

Also is there a well known algorithm for this task?

# Answer
> 1 votes
Maybe you're looking for Eulerian tour on trees. You can check these:

---
Tags: binary-trees, graph-traversal
---


title: Converting CNF to GNF

text:
# Question
Title: Converting CNF to GNF
I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly stumped on how to go past that and get to Greibach Normal Form, I am given the follow grammar which is already in Chomsky Normal Form:

S-\> AB | BC

A -\> AB | a

B -\> AA | CB | b

C -\> a | b

I know the basic idea of converting to GNF is to remove left recursion but I do not understand how to go about and do this.

# Answer
> -3 votes
reduce the cfg into gnf S-\>aSb S-\> ab

---
Tags: context-free, formal-grammars, normal-forms
---


title: Discarding lists of same elements

text:
# Question
Title: Discarding lists of same elements
Suppose, I have a list of lists where multiple lists can have same elements. In my final output, I just want one list with the same element. An example is the following:

**Input:** A=\[\[1,2,0\], \[0,1,2\], \[2,1,0\], \[4,5,6\], \[6,5,4\]\]

**Desired Output:** $\[\[0,1,2\], \[4,5,6\]\]$

Can someone help me with an easy function for doing so? Thank you so much.

# Answer
This appears to be an instance of the set cover problem. There is no efficient algorithm, but you can read about standard algorithms.
> 0 votes

# Answer
Sort every sublist, then sort the main list with lexicographical ordering. The duplicates will appear next to each other.

$$\[\[1,2,0\], \[6,5,4\], \[0,1,2\], \[2,1,0\], \[4,5,6\]\]$$ then $$\[\[0,1,2\], \[4,5,6\], \[0,1,2\], \[0,1,2\], \[4,5,6\]\]$$ then $$\[\[0,1,2\], \[0,1,2\], \[0,1,2\], \[4,5,6\], \[4,5,6\]\]$$
> 0 votes

---
Tags: programming-languages, python
---


title: BFS on a graph and BFS on a tree

text:
# Question
Title: BFS on a graph and BFS on a tree
I found the following question in my book and I have no clue on what the answer should be:

> What is the condition on search graph so that BFS Algorithm for graph and BFS Algorithm for tree **generate and expand** identical nodes in the same order?

Please Note you don't have to write a proof as I will prove it myself and post under my question accordingly to help others in the future (completing your answer)

# Answer
> 0 votes
If given graph is a tree (in other words, if tnhe graph doesn't contain cycles/loop/self-edges/self-loops), then the BFS traversal (level order traversal) would be the same.

---
Tags: algorithms, graphs, trees, artificial-intelligence, game-theory
---


# Question
Title: Can someone help me fully grasp idea and time/space complexity with this code?
My understanding is the following:

Time = With the initial not state is just to check if there are no elements in the list `a`. This is done in *O(1)* time. The first loop enumerates the second list `b` with the operation `append()` which is done in *O(1)* time therefore the first loop is *O(n)*. The second loop I am confused if the sorting plays a factor since I know the sort method is *O(nlogn)* time. Within the second loop I am a bit confused about the operations as far as what it is specifically doing which I wanted to ask about although I do understand the fact that if the i-th element in `a` is \< c it goes into the if statement.

Space = Overall I think it is *O(n)* as the only additional space needed was the list `x` plus the input space and the length of `x` grows as `a` or `b` grows.

Given the following Python code:

```
a = [3, 1, 2]  # input length will be size n
b = [1, 2, 3]  # input length will be size n
c = 4

def foo(a, b, c):
    res = 0
    if not a:
        return res

    x = []
    for i, j in enumerate(b):
        x.append((j, i))

    for j, i in sorted(x, reverse=True):
        if a[i] < c:
            res += a[i] * j
            c -= a[i]
        else:
            res += c * j
            break
    return res

```

Can someone help go over what the time and space complexity is plus the idea behind it mainly?

# Answer
> 2 votes
You are completely correct in your analysis.

**Space**. You construct an array $x$ which has length the same as that of $b$, which is $n$. It contains a pair for each element in $b$, so it has size $O(n)$. The other variables do not count, hence space complexity is indeed $O(n)$.

**Time**. You correctly observed that the sorting of $x$ takes time $O(n \log n)$, and that both iterations take time $O(n)$. Everything else is arithmetic operations, which all run in $O(1)$ time. Hence, something like $O(n) + O(n \log n) + O(n) + O(1)$, which all in all results in a time complexity of $O(n \log n)$.

Well done!

# Answer
> 0 votes
The second loop is indeed tricky. Without a deeper look, it is hard to tell its time complexity tightly, because it could be that the break always occurs very early. But you are on the safe side by assuming $O(n)$ for this loop, which, fortunately, is absorbed by the $O(n\log n)$ of the sort.

The space is indeed $O(n)$, due to the filling of $x$ with $n$ elements, given that appends are done in amortized constant time.

---
Tags: time-complexity, algorithm-analysis, space-complexity
---


title: Is this considered a vertex cover?

text:
# Question
Title: Is this considered a vertex cover?
I'm unsure if this satisfies the definition of vertex cover, the graph is unweighted and undirected:

if not, an explanation would be super enlighting.

# Answer
> 1 votes
Yes, this is a vertex cover (VC).

By definition, a vertex cover of a graph G=(V,E) is a subset of nodes $U\subset V$ such that $\forall \ e \in E \ \exists u \in U$ such that $e$ is incident in $u$.

Every edge in your graph has one of its extremes in the VC, so yes

---
Tags: algorithms, graphs, reductions, vertex-cover
---


# Question
Title: How are waits in semaphores made atomic in nature?
I was going through the book Operating Systems by Galvin. First they explain Semaphores acting like a mutex.

While talking about semaphores as mutex, they mention that the wait operation of semaphores are always atomic in nature.

This is how a simple snippet of wait would look.

```
wait()
{
    while(s<=0);
    s-=1;
}

```

where the value of shared variable s is initially 1.

As we know that a thread or process can be context switched anytime irrespective of anything else. So in the above what if a thread1 context switches after line3 and another thread comes in, it would also find the value of s to be 1. So it wouldn't be waiting in the while condition.

Now to tackle the above situation Galvin says that `wait` is an atomic operation.

What I don't understand here is how can wait be atomic and how the same is implemented internally? The OS also must be using some similar operation to make a function atomic and if we already have that algorithm which is used by OS then why use semaphores at all?

What are the ways in which a system ensures atomicity?

# Answer
> 2 votes
A possible implementation is to have the semaphore counter protected by a spinlock, in order to avoid concurrent accesses (a spinlock manages a lightweight critical section). When the value is found positive, it is decremented and that's it. Otherwise, the process is set in a waiting state and control is passed to the scheduler.

A spinlock works by busy waiting, which must be avoided in general. But in this particular case, the critical section being extremely short, the probability of long stalls is negligible. It takes a processor instruction that performs a read-modify-write atomically (needs to be guaranteed by the hardware interacting with memory, even through caches and in the case of memory shared between multiple processors). For instance, the x86 platform supports an InterlockedIncrement instruction.

https://devblogs.microsoft.com/oldnewthing/20130913-00/?p=3243

---
Tags: operating-systems, concurrency, synchronization, mutual-exclusion, semaphore
---


title: Recognizing whether a graph is a k-tree

text:
# Question
Title: Recognizing whether a graph is a k-tree
The $k$-vertex complete graph, $K\_k$, is a $k$-tree. A *$k$-tree* with $n+1$ vertices $(n \geq k)$ is constructed from a $k$-tree on $n$ vertices by adding a vertex adjacent to all vertices of one of its $K\_k$ subgraphs, and only to those vertices.

Is there an algorithm to recognize whether a graph is a k-tree? What is its time complexity? Are there efficient algorithms for special cases, particularly for k = 2, 3, 4, etc.?

# Answer
> 1 votes
Two facts:

* The $k$-trees are exactly the chordal graphs where every maximal clique has $k+1$ vertices and every minimal separator has $k$ vertices (or it's $K\_k$ or $K\_{k+1}$)
* In chordal graphs, the maximal cliques and the minimal separators can be enumerated in linear time (see e.g. this paper)

In conclusion, there is a linear time algorithm for recognizing $k$-trees, for any $k$.

---
Tags: graphs
---


# Question
Title: Dragon book exercise 4.4.5, why is aaaaaa not recognized by the recursive descent parser?
```
S → aSa | aa
generates all even-length strings of a’s

We can devise a recursive descent parser with [backtrack] for this grammar.
If we choose to expand by production S → aa first,
then we shall only recognize the string aa.
Thus, try S → aSa first.

a) Show that this recursive descent parser recognizes
inputs aa, aaaa, and aaaaaaaa, but not aaaaaa.

```

The matching goes as follows:

> aaaaaa → aSa
> aaaaa → aaSaa
> aaaa → aaaSaaa

... until matching against `aSa` fails when

> aa → aaaaSaaaa

If we try `S → aa` right now, it matches, but the extra `aaaa` after `S` have nothing to match against anymore and thus fail.

So we backtrack a step and try to match `S → aa` one step earlier, but again we have leftover `aa`.

Backtrack even further, back to

> aaSaa

When we try `S → aa` at this level, the routine finishes with a successful match.

Why then does the book say that `aaaaaa` is not recognized by this parser?

# Answer
When you look at the parser's process, you see the entire text to be parsed, and naturally make judgements based on that knowledge. But that's not the way the parser works. So your strategy makes it easy for you to parse utterances, but not easy for you to understand the parser.

Remember that the question is about a recursive descent parser with backtracking. In a RD parser, each non-terminal has a parsing procedure; that procedure which attempts each possible production for that non-terminal in order. If a production matches, the procedure returns success. Otherwise, it resets the input cursor and tries the next production. If no production succeeds, it returns failure, and its caller will perform the next fallback.

A good way to actually understand a parser (in my opinion) is to write one in some concrete programming language. Or, if you are trying to educate a class, to encourage your students to do that. In this simple case, you should be able to write the parser in a few minutes. (Instrumenting it so that you can see what's going on takes only a little bit longer, but I'll leave that as an exercise.)

Here's a quick Python implementation which uses a seekable I/O object to allow fallback. (`io.StringIO` will work, for example.)

```
def match_a(inp):
    return inp.read(1) == 'a'

def match_end(inp):
    return inp.read(1) == ''

def match_S(inp):
    fallback = inp.tell()
    if match_a(inp) and match_S(inp) and match_a(inp): return True
    inp.seek(fallback)
    if match_a(inp) and match_a(inp): return True
    return False

def match(inp):
    return match_s(inp) and match_end(inp)

```

So we can give it a quick try and see if the Dragon Book's question is valid:

```
for n in range(17):
    print(n, match(io.StringIO('a' * n)))

0 False
1 False
2 True
3 False
4 True
5 False
6 False
7 False
8 True
9 False
10 False
11 False
12 False
13 False
14 False
15 False
16 True

```

As advertised, it works with $aa$, $aaaa$ and $aaaaaaaa$, and fails on $aaaaaa$. Since I ran it a bit extra, there's actually a pretty good hint about what language is being recognised here. (Interestingly, it's not a context-free language.)

OK, what's going on? Again, you could get some more information by instrumenting the parser and examining the log of calls and returns. I'm going to try to explain the failure to parse $aaaaaa$ in narrative, but if you have any doubts, do try adding logging to the sample code. (The call and result log is at the end of the question, but it is quite long.)

First of all, note that at no point does the parser know anything about what's coming in the input stream, not even how long it is. It only knows about the next character. So the first thing it does (since it always tries $ S\to a S a$ first) is to recursively call itself until that production fails, which will happen on the seventh recursion, not the third one. That's the point where the $S$ recogniser is called at the end of input. After the first alternative fails, that instance will then fall back to trying $S\to a a$, but since the parser has reached the end of input, that one will fail, too.

So then the seventh recursion reports failure back to the sixth recursion, which falls back to $S\to a a$. That also fails, because there is now only one available $a$. So now it falls back to the fifth recursion, which attempts its next alternative ($S\to a a$), which this time works because there are two $a$s at the current input.

That allows the fifth recursion to return success to its caller, the fourth recursion, which can then try to complete the $S\to a S a$ production by reading the last $a$. Alas, that doesn't work because after the $S$ succeeded, it left the input buffer at the end. So now the fourth recursion again resets the input cursor and tries its next alternative ($S\to a a$), which of course will work, so the fourth recursion can report success back to the third recursion.

Let's take stock here. The current call stack contains three recursions, each one waiting for $S$ to return, and a fourth recursion, which is about to report that it matched $S\to a a$ with the fourth and fifth input character. You and I can see that that's not the correct parse -- there aren't enough input characters left to satisfy the pending recursive calls -- but the parser is unaware of that.

The third recursion can read the last $a$, letting it satisfy $S\to a S a$ (covering the third through the sixth input character) so it returns *success*. And that's wrong, because the correct parse needs to match $S\to a a$ at the third position. But that correct parse will never be found, because once a matching production is found, the rest of the alternatives will never be tried.

Thus, when the third recursion returns to the second recursion, the second recursion finds that it can't complete $S\to a S a$. But it has no way of telling the third recursion to try some other alternatives. It doesn't even know that the third recursion had some untried alternatives. All it can do is *fail itself*, falling back to $S\to a a$. That will work, and the first recursion will then complete $S\to a S a$, but it will complete at position 4. So the top-level recogniser will reject the parse, since it didn't match the entire input.

In other words, the parse will only succeed when the parser happens to backtrack to the second production at precisely the right stack depth, so that the next time it backtracks is also at precisely the right stack depth, and so on until it backtracks at precisely the middle of the input (without ever being able to know that it's at the middle). That might be enough of a hint to construct an argument by induction. (But part *b* of that question is marked with a star, so the Dragon authors didn't feel it was trivial.)

Here's the call trace for the parse of $aaaaaa$; since I did this in Python, positions count from 0, not 1. (I guess I could have started with 1, but I didn't. It shouldn't be too hard to reproduce the log, though.)

```
Trying {S_ -> S $} at 0
  Trying {S -> a S a} at 0
    Trying 'a' at 0
    Matched 'a' at 0
    Trying {S -> a S a} at 1
      Trying 'a' at 1
      Matched 'a' at 1
      Trying {S -> a S a} at 2
        Trying 'a' at 2
        Matched 'a' at 2
        Trying {S -> a S a} at 3
          Trying 'a' at 3
          Matched 'a' at 3
          Trying {S -> a S a} at 4
            Trying 'a' at 4
            Matched 'a' at 4
            Trying {S -> a S a} at 5
              Trying 'a' at 5
              Matched 'a' at 5
              Trying {S -> a S a} at 6
                Trying 'a' at 6
                Failed 'a' at 6
              Failed {S -> a S a} at 6
              Trying {S -> a a} at 6
                Trying 'a' at 6
                Failed 'a' at 6
              Failed {S -> a a} at 6
            Failed {S -> a S a} at 5
            Trying {S -> a a} at 5
              Trying 'a' at 5
              Matched 'a' at 5
              Trying 'a' at 6
              Failed 'a' at 6
            Failed {S -> a a} at 5
          Failed {S -> a S a} at 4
          Trying {S -> a a} at 4
            Trying 'a' at 4
            Matched 'a' at 4
            Trying 'a' at 5
            Matched 'a' at 5
          Matched {S -> a a} at 4
          Trying 'a' at 6
          Failed 'a' at 6
        Failed {S -> a S a} at 3
        Trying {S -> a a} at 3
          Trying 'a' at 3
          Matched 'a' at 3
          Trying 'a' at 4
          Matched 'a' at 4
        Matched {S -> a a} at 3
        Trying 'a' at 5
        Matched 'a' at 5
      Matched {S -> a S a} at 2
      Trying 'a' at 6
      Failed 'a' at 6
    Failed {S -> a S a} at 1
    Trying {S -> a a} at 1
      Trying 'a' at 1
      Matched 'a' at 1
      Trying 'a' at 2
      Matched 'a' at 2
    Matched {S -> a a} at 1
    Trying 'a' at 3
    Matched 'a' at 3
  Matched {S -> a S a} at 0
  Trying $ at 4
  Failed $ at 4
Failed {S_ -> S $} at 0
'a' * 6 : Fail

```
> 4 votes

# Answer
because in $S(2)$ can match $aaaa$ so $S(2)$ can't match $aa \to S(1)$ can't match $aaaa$.

why $S$ only match $a^{2^n}$ ? $\to$ why $\frac{2^{n}}{2}-1$ can match $aa$ but $S(\frac{len}{2}-1)$ can't match $aa$ in not like $a^{2^n}$ .

The reason may like it?
> 0 votes

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


# Question
Title: C language tokenizer output for static integer array
Unable to find out how the C-language lexical analyzer would tokenize the declaration of a static array. Say, int i\[3\]= {1,2,3};

The lexical analyzer would need to differentiate between just an integer identifier i, and a static array of size 3.

Am confused how the lexical analyzer would tokenize.

Tried Holub's book, among others, but couldn't find anything.

# Answer
> 2 votes
In my answer I assume you are acquainted with formal grammars, especially, the Backus Naur form.

The lexical analyzer, alone, could never state the sentence you provided actually belongs to C. Telling whether it belongs or not to the language, is a joint duty of the lexical and syntactical analyzers.

On one hand, the purpose of the lexer is telling whether a given sequence of characters corresponds to some keyword or pattern. On the other hand, the purpose of the syntactical analyzer is telling whether a sequence of symbols and characters is admitted by the grammar.

A simple grammar $\mathcal{G}$ (unrelated to the C language) generating this kind of construct could be:

* $S \rightarrow T \text{ } id \text{ } A = \\{ L \\}$
* $A \rightarrow \[ L \] $
* $L \rightarrow num \text{ } |\text{ } LL $
* $LL \rightarrow LL\text{ },\text{ } num\text{ }|\text{ } num$
* $T \rightarrow int\text{ } |\text{ } float\text{ } | \text{ }double$

(Assuming `id` corresponds to the lexical language of ids, etc.)

The lexer would tokenize the string generating 14 tokens, that is:

* (`int`, INT)
* (`i`, ID)
* (`[`, LBRACKET)
* (`3`, INTEGER)
* (`]`, RBRACKET)
* (`=`, ASSIGN)
* (`{`, LCURLY)
* (`1`, INTEGER)
* (`,`, COMMA)
* (`2`, INTEGER)
* (`,`, COMMA)
* (`3`, INTEGER)
* (`}`, RCURLY)
* (`;`, COLON). (For suitable constants INT, INTEGER, ID, COMMA, etc.)

At parse time the parse would tell the sentence belongs to the language, and could distinguish the meaning of each lexem by its left and right context (that precedes and follows it.)

I hope this explanation will help.

---
Tags: lexical-analysis
---


# Question
Title: reduce independent Set into independent Set of distance 4 between all vertices
I want to prove the following problem is NP-complete:

**4-Spaced-Set:** Assume you have a undirected graph $G=(V,E)$, and a positive integer $k$. Let's say a set of vertices $A \subseteq V$ is $4$-spaced if the distance between any two distinct vertices in $A$ is at least $4$. There is also a vertex weight function $w:V\to\mathbb{N}$. The question is whether there exists a $4$-spaced subset of the vertices with total weight $\sum\_{u\in S}w(u)\geq k$?

I want to prove this problem is NP-Complete. I was able to find a YES instance and a certificate which proves it can verified in polynomial time so it is NP. However I am having trouble trying to reduce Independent Set to this problem in order to prove that is NP-Hard as well. Here is my attempt, please let me know what I did wrong, and how to proceed?

Initiliaze a new graph $G'$ where you add edges to make sure that no two vertices at a distance less than 4 from each other can be in the same independent set. Start with the original graph G. Add edges between vertices at a distance 2 from each other: For any pair of vertices u,v at a distance 2 from each other, add an edge between u and v. Add edges between vertices at a distance 3 from each other such that for any pair of vertices u,v at a distance 3 from each other, add an edge between u and v. graph $G′$ will have an independent set of size k if and only if the original graph G has a 4-spaced set of size k therefore by transitivity of reduction, all problems $A \in$ NP reduce to this problem. Therefore this problem is NP-Hard.

# Answer
For an input to independent set, subdivide each edge twice, add a new vertex that is incident to every subdivision-vertex.

Now, the distance between two vertices in the new graph is 4 if and only if they correspond to two non-adjacent vertices in the input graph.
> 2 votes

---
Tags: np-complete, reductions, np-hard
---


# Question
Title: Doubts in backtracking function animation, for call sequence flow
In the slides' based animation given for backtracking, here (with code here, in the web-page); have few doubts, in the code restated below, and the execution as shown in the call #5.

```
#include <stdio.h>
char *next;
int calls = 0;

int eat(char c) {
  calls++;
  if (*next == c) {
    next++;
    return 1;
  }
  return 0;
}

int e() {
    char* save = next;
    if(eat('(')&&e()&&
    eat('+')&&e()&&eat(')'))
        return 1;
    else next = save;
    if(eat('(')&&e()&&eat('*')
    && e()&&eat (')'))
        return 1;
    else next = save;
    if (v())
        return 1;
    else
        next = save;
    return 0;
}
int v() {
    char* save = next;
    calls++;

    if (eat('x')) return 1;
    else next = save;

    if (eat('y')) return 1;
    else next = save;

    return 0;
}

void main()
{
  next = "((((x*x)*x)*x)*x)";
  printf("%i\n", e());
  printf("%i\n", calls);
}

```

Request correction, and comments, for my analysis, and doubts, below:

1. In the code, the two operators, i.e. '+', '\*'; are of equal precedence. Though, am confused if am correct in describing the grammar for the code.

*e -\> (e + e) | (e * e) | v*

*v -\> **x** | **y***

2. For the call #5, unable to understand how the execution flow jumped to the the second *if* statement, though tried multiple times to figure out the same.

# Answer
> 1 votes
It took me a few minutes to figure out what functions $e()$ and $v()$ do but after some careful reading I got to the conclusion they implement a recursive descent parser whose language $\mathcal{L}$ is the one made of arithmetic expressions on identifiers $x$ and $y$.

Regarding your first question, I don't think operators $\*$ and $+$ share the same precedence; the language accepted by the parser corresponds to arithmetic expressions having fully specified parenthesis (adding numbers to the language matched by $v()$, "$1+2\*3$" is clearly not in $\mathcal{L}$, while "$(1+(2\*3))$" is). To my understanding $e()$ implements the rules of regular arithmetic, that is, $\*$'s precedence is greater that $+$'s. I reached this conclusion observing that missing parenthesis are not allowed and precedence is not enforced by the parser but rather by properly nested parens. Consequently, a bottom-up grammar generating this kind of precedence is $\mathcal{G}$:

* $E \rightarrow E + T \text{ }|\text{ } T$
* $T \rightarrow T * F \text{ }|\text{ } F$
* $F \rightarrow (E) \text{ }|\text{ } num$

(with some adjustments you can easily get the LL1, that is top-down, version.)

Regarding your second question, the parser (via call 4) first tries to consume a sequence of characters of the shape $( \text{ } E \text{ } + \text{ } E \text{ })$ (but fails because no parenthesis is present), then (via call 5) it tries to consume $(\text{ }E \text{ }\*\text{ }E\text{ })$ failing for the same reason. Eventually, it will try to consume $x$ via function $v()$ in call 6, with success.

I hope this explanation helps.

---
Tags: compilers, backtracking
---


# Question
Title: Change of associativity for a given right-recursive grammar
In section 3.7.1, of the book titled: Compiler design in C, by Allen I. Holub (made available freely online, by the author here, & the page #19 of errata, here), have on page #176, the mention of grammar, for a right-recursive list:

```
stmt_list -> stmt stmt_list | stmt
stmt -> A | B| C

```

while on the previous page, the left recursive version is given:

```
stmt_list -> stmt_list stmt| stmt
stmt -> A | B| C

```

*(But, am concerned here with the right-recursive version.)*

The figure 3.4, on page #176, shows the corresponding parse tree for a right-recursive list(grammar).

On page #177, there is code listing 3.1 for: Left Associativity with a Right-Recursive Grammar; given below:

*Code listing 3.1*

```
1 stmt_list()
2 {
3  /* Code is generated as you create the tree, before the subtree is
4  * processed.
5  */
6
7   remember= stmt();
8
9   process_stmt(remember);
10
11  if(not_at_eoi())
12       stmt_list();
13  }
14
15  stmt()
16  {
17       return(read());
18  }

```

Want to adapt the above grammar for practical usage, so as to see it's ramifications.

Hence, modify the above to handle arithmetic expressions, with two precedence classes of operators, i.e. addop, mulop; with addop having two operators: {+,-}; & mulop having having two operators {\*,/}. The *precedence of mulop operators* \> *precedence of addop operators*. Also, in each precedence class, associativity, can be either left-to-right, or right-to-left; as the implementation in code. As am considering, the right-recursive grammar, as in the book; so have:

```
expr -> term + expr | term - expr | term
term -> factor * term | factor / term | factor
factor -> digit factor | digit
digit -> 0|1|2|...|9

```

The corresponding right-recursive grammar, now has two possible implementations:

1. left-to-right associativity of the operators, in the same precedence class, shown below in *First*.
2. right-to-left associativity of the operators, in the same precedence class, shown below in *Second*.

*Code listing: First*

```
1 expr()
2 {
3     remember= term();
4     process_stmt(remember);
5     if(not_at_eoi())  expr();
6 }
7 term()
8 {
9     remember= factor();
10    process_stmt(remember);
11    if(not_at_eoi()) term();
12 }
13
14 factor()
15 {
16    remember= digit();
17    process_stmt(remember);
18    if(not_at_eoi()) factor();
19 }
20 digit()
21 {
22    return read();
23 }

```

So, by the code *First*, for the below arithmetic expression:

```
200+300+400-50*10/5*2

```

the parse tree would have the sequence of operators, of the same precedence class, processed by left-to-right associativity, as shown by the order imposed by the enclosing parenthesis:

```
((200+300)+400)-(((50*10)/5)*2))
=> 900 - ((100)*2)
=> 700

```

But, in the next listing (3.2), the author by the below code states to achieve, right-to-left associativity, in the right-recursive grammar.

After the below listing, will state code: *Second*, that will give for my arithmetic expression handling grammar, with two precedence classes of operators (addop, mulop); the Right-to-left associativity of operators, in the same precedence class.

*Code listing (3.2)*

```
1 stmt_list()
2 {
3  /* Code is generated as you create the tree, before the subtree is
4  * processed.
5  */
6
7   remember= stmt();
8
9   if(not_at_eoi())
10          stmt_list();
11
12  process statement( remember);
13  }
14
15  stmt ()
16  {
17       return( read() );
18  }

```

*Code listing: Second*

```
1 expr()
2 {
3     remember= term();
4     if(not_at_eoi())  expr();
5     process_stmt(remember);
6 }
7 term()
8 {
9     remember= factor();
10    if(not_at_eoi()) term();
11    process_stmt(remember);
12 }
13 factor()
14 {
15    remember= digit();
16    if(not_at_eoi()) factor();
17    process_stmt(remember);
18 }
19 digit()
20 {
21    return read();
22 }

```

So, now (as per the book) the given arithmetic expression:

```
200+300+400-50*10/5*2

```

would have the parse tree, with Right-to-left associativity. Hence, would have the sequence of operators processed as shown by the order imposed by the enclosing parenthesis:

```
((200+(300+(400-((50*(10/(5*2)))))
=> ((200+(300+(400-((50)))
=> 850

```

*Have main issue with being unable to see how the change of associativity occurs with change of position, of the line:*

```
process_stmt(remember);

```

*, wrt the recursive call.*

---

Also, as an off-topic, want to state that: as the gcc compiler follows for the given two (precedence) classes of operators, & inside the two precedence classes having left-to-right associativity, so get the expected answer, on compilation of a program for the above arithmetic expression as:

```
700

```

# Answer
It took me quite a while to figure what the author of the book was pointing out and specifically what you are asking for, but I think I eventually managed to get it.

The author stated that lists are associative, while intuitively this is correct I don't think this is necessarilly a useful thing to know; especially at this stage of learning. I think an handy way to reason about associativity in this context is to simply focus on what is processed first. In general, left associativity implies processing elements on the left of something (generally an operator) before you process the rest. Conversely, right associativty implies processing right elements and than switch back to left elements, finishing the computation.

A simple example could be following: $1+2+3$ corresponds to $(1+2)+3$; $+$ is left associative because elements on its left are processed (summed) first. Conversely, $1^{2^3}$ (that is 1^2^3) is right associative and involves the computation of right elements w.r.t. the `^` symbol first, backtracking to left elements only after.

To the best of my knoledge other books like the `Red Dragon Book` (by Alfred Aho et al.) and `Modern Compiler Design in (C|Java|ML)` (by Andrew Appel) postpone this discussion after having tackled lists and covert it only after the reader is acquainted with bottom-up parsing.

The point of switching from a right-recursive to a left-recursive grammar, in bottom-up parsing is gaining efficiency and making the parser faster: this is due to the fact reductions will occur in the order that keeps the stack as empty as possible.

In the context of top-down parsing, like in your case, you need to hack the parser, forcing it to analyze the input in the proper way, forcing the processing of some branches before others are tackled. The author acknowledges this is a maintainance problem (pg. 177, bottom) and in my eyes this is a case of premature optimization.

If you have read the chapter covering compiler-compilers you should know that once the grammar has been designed the compiler-compiler (let it be top-down or bottom-up) will generate the code for matching the language you defined. In that case, are you going to hack the output parser for enforcing the proper processing order? What I am suggesting is the following: do not focus on this topic too much because (as the author mentions) in chapter 4 he/she will show a way for getting rid of recursion and provide a grammar that matches the language. I think the take-away is: changing from left to right recursion you can tell which elements are processed first, and that could be a handy trick for forcing some computation order.
> 2 votes

---
Tags: compilers, recursion
---


# Question
Title: Is there an efficient algorithm to find whether an integer is a prime power?
There's a sentence in the current version of the Wikipedia page for Shor's algorithm which states: *we can use efficient classical algorithms to check if $N$ is a prime power*. No reference is provided to support it.

Is this true? I've tried to look around for such an algorithm but didn't find much.

There is this website providing code to solve this problem, which states that the time complexity is indeed $O(\log N)$, but they also don't provide references, so I'm not sure how reliable it is. The idea of the algorithm seems to be to simply loop over all primes smaller than $\sqrt N$, and each time try to divide until you get to $1$. The reasoning seems sound, but I'm not sure how you verify the complexity of this procedure.

# Answer
> 10 votes
Note that if a number $N$ is a power of a prime $p$ it will be of the form:

$$N=p^i \ ,$$

Since $p$ is prime, $p \geq 2$ which implies $i \leq \log\_2 N$.

We can compute the $i$th roots of $N$ for each $2\leq i \leq \log\_2 N$ and check if the resultant number is integer, and eventually if it is a prime. The complexity of these two steps is higher than $O(\log N)$ but they are ignored in practice.

The complexity of the computation of roots should be equal to that of arithmetic operations like the multiplication, but it is hard to give a precise estimate of it (depends on number representation, precision, etc).

For checking the primality, if needed, you can use the Miller-Rabin primality test which takes $O(k\log N)$, where $k$ is the number of iterations needed. Since you check for numbers $\leq \sqrt N$, it will be $O(k\log \sqrt N)=O(k\log N)$, so as you can see the asympthotic analysis leads to higher complexities.

The fact is that often you can avoid the majority of these steps because at a certain point you can exclude that a number is integer for instance

# Answer
> 17 votes
See:

Daniel J. Bernstein. *Detecting perfect powers in essentially linear time*, Mathematics of Computation 67 (1998), 1253–1283.

Here, "linear" means "linear in $\log N $". Specifically, the complexity is $\left(\log N\right)^{1 + o(1)}$ as $n \rightarrow \infty$.

---
Tags: integers, factoring
---


# Question
Title: Can halting problem solved by soft computation?
As far as I know, the halting problem means we can't create a program that checks whether another program is stuck or halt based on given input. This means, the program expects two inputs and one boolean output.

For example in a Python language, there's program called `is_halt.py` expecting one input integer. Let's say the input integer is `N`. If `0<=N<10` then stuck, else then halt.

I tried ChatGPT which is working on soft computation.

Prompt (Input):

```
#I have this Python Program:

integer_input = int(input("Input an integer: "))
while integer_input >= 0 and integer_input < 10:
  print(1)
print(0)

#If I input the integer with 7 into the program, will the program halt or stuck?

```

Answer (Output):

```
The program will get stuck in an infinite loop when you input the integer 7. The loop condition while integer_input >= 0 and integer_input < 10: will always evaluate to True because 7 satisfies both conditions (7 >= 0 and 7 < 10). As a result, the print(1) statement will be executed repeatedly, and the program will not reach the print(0) statement. To avoid the infinite loop, you need to update the value of integer_input within the loop to eventually break out of it.

```

As you see, the ChatGPT 3.5 answer is able to check whether the program is stuck or halt based on given input.

Does it mean, the halting problem is solved by soft computation?

# Answer
> 2 votes
> As far as I know, the halting problem means we can't create a program that checks whether another program is stuck or halt based on given input.

No, the Halting Problem means that we can't create a program that checks for *all possible programs* and *all possible inputs* whether the program will terminate for that input.

You have found a program which can check that for *one* program and *one* input. I am sure, ChatGPT can do that for *many* programs and *many* inputs. But that's not enough.

You have to test ChatGPT with *every possible program*. That includes every program that has ever been written in the entire history of humankind. And every program that *will* be written for all eternity. It even includes programs that *have never been* written and *will never be written*, but *could theoretically be written*. It includes the program I just made up in my head and have already forgotten again.

And you have to test every possible program with every possible input.

There are many programs for which it is trivial to decide whether they halt or not. As mentioned in another answer, programs which contain no loops will always halt. Programs which contain only bounded loops will always halt. Programs with structural recursion where the structure always gets "smaller" will always halt. For programs with trivial infinite loops, it is trivial to decide whether they will halt.

There are many tools which check whether programs halt. Microsoft Research's *Terminator* is a well-known tool for termination checking. A variant of it is actually used to check termination of Windows Drivers to make sure that Windows Drivers cannot freeze the kernel.

But all of these tools and all of these tricks can *only* decide termination for *some* programs. Not all of them.

Terminator is proven to be *sound*, which means that when it says a program will halt, then the program will definitely halt. However, Terminator is *not* complete, meaning there are programs which halt for which Terminator cannot decide that they halt.

In many use cases, this is an acceptable trade-off: your goal is to prevent Windows Drivers from running into an infinite loop. As long as you can guarantee that you don't allow a driver with an infinite loop, then it is okay if you occasionally disallow a driver which doesn't have an infinite loop. The cost of a false negative is that the developer has to change their code so that Terminator can understand it. The cost of a false positive is a potential Windows Bluescreen. You'd much rather have the former than the latter.

# Answer
> 4 votes
No. ChatGPT is still just a program, although a rather large one.

# Answer
> 3 votes
The halting problem does not mean that it is impossible to tell if a particular program halts or not. For example, any loop-less program will terminate, and it is a very easy matter to check the absence of loops. The halting problem says that no algorithm can work for *any program*.

A human could do better than an algorithm on some programs because he has more creativity and more freedom to "change the rules", so the day IA becomes intelligent (if ever ?), this might be the case as well.

Anyway, a human can be stuck on difficult problems. E.g. the Syracuse conjecture. And undecidable problems remain out of reach.

# Answer
> -1 votes
One common misconception about the halting problem is that it is totally possible to make a program that will determine whether some (most?) programs halt. However if you give ChatGPT (or any other program) harder examples things will inevitably break down very quickly.

---
Tags: halting-problem, python
---


# Question
Title: Proving the correctness of a greedy algorithm for the Circular Scheduling Problem
Consider the following variation on the Interval Scheduling Problem You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start and end times. (Note that certain jobs can begin before midnight and end after midnight; this makes for a type of situation different from the Interval Scheduling Problem.) Given a list of n such jobs, your goal is to accept as many jobs as possible (regardless of their length), subject to the constraint that the processor can run at most one job at any given point in time. Provide an algorithm to do this with a running time that is polynomial in n, the number of jobs. You may assume for simplicity that no two jobs have the same start or end times.

I have made an algorithm, but I'm having a hard time proving its correctness. The algorithm is , Select the interval with the least no of intervals overlapping it, remove all the overlapping intervals, and recurse on the remaining intervals.

Here is my proof attempt at proving the correctness of this algorithm:- Let O be an optimal set of intervals which doesn't contain the interval I1, which has the least no of intervals intersecting with it. Consider the set S(I1) that is the set of intervals that intersect with I1. If no elements of S(I1) are in O, then a larger optimal set can be created by adding I1 to O hence, lets consider the case when atleast one Interval , say I2 in S(I1) which is also in O. Now consider O \ {I2} . If none of the elements in O \ {I2} belong to S(I1), then I can exchange I2 with I1 and still have an optimal solution. So lets consider the case when there exists some element in O such that it is in S(I1). Call it I'. as I' lies in O, I' doesn't lie in S(I2). We have |S(I1)| \<= |S(I2)| and I' is such that I' lies in S(I1) but not in S(I2). For the inequality to hold , there must exist atleast one interval I'' that is in S(I2) but not in S(I1). This is the point where I'm stuck though, I can't make an exchange argument as I don't know if I'' intersects with other members of O.

# Answer
> 1 votes
Your algorithm is not correct.

Consider intervals \[1,7\], \[8, 14\], \[15, 21\], \[22,28\], \[13,16\], \[2,9\], \[3,10\], \[4,11\], \[17,23\], \[18,24\], \[19, 25\].

Your algorithm chooses \[13,16\] first, as it only overlaps with two other intervals. Then it will only be able to choose two more non-overlapping intervals; one ending before 13, and one starting after 16. The optimal solution chooses 4 intervals, as for example \[1,7\], \[8,14\], \[15,21\], and \[22,28\].

For an actually correct greedy algorithm it might be easier to think of the non-cyclic case first, so no jobs that go over midnight, and then consider choosing jobs based on their finish time. Once you’re convinced about this go to the cyclic case. If you get stuck in the middle, feel free to make a new question.

---
Tags: algorithms, algorithm-analysis, proof-techniques, greedy-algorithms, intervals
---


# Question
Title: Books to prepare before reading Knuth's The Art Of Computer Programming (TAOCP)
Many people say that TAOCP is not supposed to be read as a book (actually a volume of books), but if I decide to go that way, which math/computer science books/topics do I need to study to help me follow it? There is a related question on stackoverflow but I would like to read the suggestions of cs.se users.

# Answer
Don Knuth is a teacher, and is always very thorough when he writes. So one should expect that he states all prerequisites in his books.

To ascertain that, I went to look in my own issue of the first volume.

Indeed the preface states some prerequisites on page v, which he sums up into "*the single requirement that the reader should have already written and tested at least, say, four programs for at least one computer*".

Starting page viii, he gives a few words regarding mathematical content. "*the material has been organized so that persons with no more than a knowledge of high school algebra may read it, skimming briefly over the more mathematical portions; yet a reader who is mathematically inclined will learn interesting mathematical techniques \[...\]*". He calls his organization a dual level of presentation.

Later he confirms that "*a knowledge of elementary calculus will suffice for most of the mathematics in these books, since most of the other theory that is needed is developed herein ...*"

Hence my best advice is to find out what you need by first reading the prefaces of the various volumes of TAOCP in the library. I suggest adding some lighter reading, such as comics. You may need it.

A word of warning though. Knuth tends to be too optimistic regarding the brains of other people.
> 15 votes

# Answer
I endorse everything in babou's answer, but I'm going to suggest one book which may be helpful.

"Concrete Mathematics: A Foundation for Computer Science" by Graham, Knuth and Patashnik is a textbook in a way that TAOCP isn't. Moreover, in a sense, it is a summary of the maths that Knuth used throughout his career (apart from the formal language stuff; people forget that Knuth's greatest research contribution to computer science is actually the theory of LR parsing) in convenient textbook form.
> 5 votes

# Answer
One can read it easily if one has

1. A solid background in highschool math (algebra + geometry)
2. A calculus course
3. Discrete mathematics book completed
4. Concrete mathematics completed
5. Ability to write code in one language like python, test yourself by solving first 25 problem from project Euler, if you can do it, go ahead
> 0 votes

---
Tags: books
---


# Question
Title: Where is File Allocation Table in FAT32 file system stored?
I had been reading about File systems recently and came across the File Allocation Table in FAT systems. As per my understanding the File Allocation Table contains entries of the various files stored in the partition. This includes things starting cluster, ending cluster, file name etc (I still didn't understand exactly which all data is stored in File Allocation Table. I am aware that the information held in the table will vary with files systems.)

Some resources say that File Allocation Table is stored in the first sector of the partition. But I have also read on wikipedia that each entry made to File Allocation Table in a FAT32 system requires 32-bit or 4 bytes. Also, it said that the maximum number of files that can be stored in FAT32 system in a single folder is 65534. Thus, assuming we have 65534 files in a folder we get 65534\*4= 262136 bytes ~262 kb. This means that already half of the sector is filled with File Allocation Table. Thus, I don't understand how the entire file allocation table can be accommodated just within the first sector. Unless it is continued somewhere else or stored entirely somewhere else.

# Answer
The first five fields of the BPB (BIOS Parameter Block) in any FAT filesystem contains are following fields:

* The first three bytes are the boot jump; this contains `EB 3C 90` (the `3C` may be different), which is 8086 machine code to jump over the disk format information for convenient booting.
* The 8-byte OEM identifier.
* A 2-byte little-endian word, which is the number of bytes per sector.
* 1 byte meaning the number of sectors per cluster.
* A 2-byte little endian word, which is the number of reserved sectors.

There's more, but this is all you need to know to answer the question. The File Allocation Table follows the reserved sectors, so the first FAT sector is equal to the reserved sector count.
> 2 votes

---
Tags: filesystems
---


# Question
Title: How are closures supposed to interact with variable binding and resolving?
I am currently reading the Crafting Interpreter book and I have a question about the Resolving and Binding chapter

The author gave this example to illustrate the problem with the implementation at that point in the book.

```
var a = "global";
{
  fun showA() {
    print a;
  }

  showA();
  var a = "block";
  showA();
}

```

The problem being that this prints

```
global
block

```

The argument the author is making is that, once the variable is captured as a closure, it should not be possible to change it, hence the second call to `showA()` should not give a different result from the first call.

The author makes the claim this is an issue to be fixed and the chapter is dedicated to fixing it.

But is this really an issue? If I run the JavaScript version of the code

```
var a = "global";
{
  function showA() {
    console.log(a);
  }

  showA();
  var a = "block";
  showA();
}

```

I get exactly the output the author claims to be wrong. That is:

```
global
block

```

Is the author mistaken to claim this is a bug? Or the author is correct and JavaScript has this bug?

# Answer
The scope of variables created with the `var` keyword in JS is pretty unintuitive, at least if you're already familiar with how other languages handle scope. You can get some more info on how closures and scope interact in JS on this page --\> Closures - JavaScript | MDN

In this case, the problem is that a pair of curly brackets doesn't really create a new scope. Therefore, the second declaration of `a` gets converted to an assignment to the first one. In contrast, this code:

```
var a = "global";
function showA() {
  console.log(a);
}
{
  showA();
  let a = "block";
  showA();
}

```

in which I have moved the definition of `showA()` out of the brackets and declared the second `a` with `let` , works "as intended" (i.e. it prints `global` twice).

Importantly, this behaviour isn't a *bug*, as it conforms to the specifications of JavaScript. But it runs counter to how most other languages work (apparently including how Mr. Nystrom intends his language to work in the book you're reading).
> 3 votes

---
Tags: variable-binding
---


# Question
Title: Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?
I want to implement a delaunay triangulator by using incremental building, which is purported to be $O(n \log(n))$ I am a little puzzled about 2 things.

Ever resource I read on the matter says:

1. Make 3 points that are large enough to contain all other points.
2. For each point, find the face that contains it, split that face to add the new point to the set, flip edges as needed to maintain the Delaunay condition.

But no resource I can find says how to actually generate those 3 points in a robust manner and no resource I can find says how to efficiently find the point face inclusion. A naive strategy to find the triangle that contains a point is linear in the number of triangles, that would not lead to $O(n\log n)$ so what am I missing?

# Answer
> 3 votes
These parts of the algorithm are discussed in the book *Computational Geometry* by de Berg et al. I will provide a summary here. Let $P$ be the set of input points.

> 1. Make 3 points that are large enough to contain all other points.

This is not sufficient1. We need to find three points (some of them not in $P$) such that the triangle of them contains all points in $P$ **and** the Delaunay triangulation is still correct after removing any the points not in $P$. In particular, the second condition means any additional points should not lie inside a circle defined by three points in $P$.

The book chooses $p\_{-2},p\_{-1},p\_0$ as the vertices of the triangle, where

* the point $p\_0$ is the leftmost highest point of $P$,
* the point $p\_{-1}$ lies far enough to the right on a horizontal line below all points of $P$ to lie outside every circle defined by three points of $P$ and such that the clockwise order of the points in $P$ around $p\_{-1}$ is equal to their lexicographic order,
* the point $p\_{-2}$ lies far enough to the left on a horizontal line above all points of $P$ to lie outside every circle defined by three points of $P\cup \\{p\_{-1}\\}$ and such that the counter-clockwise order of the points of $P\cup \\{p\_{-1}\\}$ is equal to their lexicographic order.

While it is possible to compute coordinates satisfying these requirement for $p\_{-1}, p\_{-2}$, these coordinates can be quite large, as triples that are almost collinear define a large circle. So, it is better to only use the points symbolically, by adapting the operations that may involve these points. The property that the (counter-)clockwise order around these points is equal to the lexicographic order is useful here. The book provides the details on how to implement this.

> 2. For each point, find the face that contains it

For this, we maintain a point location structure $\mathcal{D}$ that is a DAG where the leaves correspond to triangles in the current triangulation and internal nodes to previous triangles that are now destroyed. Initially, $\mathcal{D}$ contains the triangle $p\_{-2}p\_{-1}p\_0$. When inserting a point from $P$ or flipping an edge, the new triangles become leaves in $\mathcal{D}$ and we draw an arc from the destroyed triangle(s) to the new ones that replace them in the triangulation.

We can find the triangle containing a point $p$ by starting at the root of $\mathcal{D}$, testing which of the child triangles contains $p$, until we reach a leaf node containing $p$, which corresponds to the triangle we need to find. Note that each internal node in $\mathcal{D}$ has at most three children, so the time required is linear in the depth of this DAG, or in other words, the number of triangles that contain the point $p$ and are placed before it.

Is the running time of this point-location method better than a linear search? If the DAG would be balanced, then its depth would be $O(\log n)$. This, however, is not necessarily the case, as there are insertion orders of $P$ that create an unbalanced DAG. Fortunately, there are "good" insertion orders and a random one is "good enough" in the sense that the total time required for point location with $\mathcal{D}$ is $O(n\log n)$ in expectation when given a random insertion order for $P$. See the book for a proof.

---

1. Another option would be to try and "repair" the triangulation after removing a point. This seems more complicated than ensuring no errors are made in the first place.

# Answer
> 0 votes
Isn’t your problem simply: given a list of points $L$, create 3 new points such that all points in $L$ are enclosed by the triangle formed by the new 3 points?

If so, that can be done in linear time quite easily. For example if $b, t$ are the minimum and maximum $y$-coordinates in $L$ respectively, and $l, r$ are the minimum and maximum $x$-coordinates respectively, then $$ A = (l-1, b-1),\\ B = ((l+r)/2, t+1),\\C = (r+1, b-1) $$ should work as the new vertices.

---
Tags: graphs, computational-geometry, discrete-mathematics, triangulation
---


# Question
Title: Is it possible to avoid encoding the state in streaming ANS?
regular ANS collects all the data into one big integer and provides optimal compression. In cases where all the symbol probabilities are powers of two, it is just as good as huffman coding (because huffman coding is also optimal in this case).

Streaming ANS lets us avoid the need to use a BigInteger or other expensive operation for a little compression loss. trying to understand it, I wrote a simple encoder:

```
const FREQ: &[u64] = &[1, 1, 2]; //frequency of each symbol
const T: u64 = 1; //encoding precision, increasing increases compression but decreases performance

pub const CUMUL: [u64; FREQ.len() + 1] = { //cumulative sums of previous frequencies
    let mut r = [0; FREQ.len() + 1];
    let mut i = 1;
    while i < r.len() {
        r[i] = r[i-1] + FREQ[i-1];
        i += 1;
    }
    r
};
pub const M: u64 = CUMUL[CUMUL.len() - 1];

#[derive(Debug)]
pub struct RansState {
    value: u64,
    bitstream: Vec<bool>,
}

impl RansState {
    pub fn new() -> Self {
        RansState {
            value: M * T,
            bitstream: Vec::new(),
        }
    }

    pub fn encode(&mut self, symbol: usize) {
        self.stream_out(symbol);

        let block_id = self.value / FREQ[symbol];
        let slot = self.value % FREQ[symbol] + CUMUL[symbol];

        self.value = block_id * M + slot;
    }

    pub fn decode(&mut self) -> usize {
        let block_id = self.value / M;
        let slot = self.value % M;

        let symbol = CUMUL.iter().position(|x| slot < *x).unwrap() - 1;

        self.value = block_id * FREQ[symbol] + slot - CUMUL[symbol];

        self.stream_in();

        symbol
    }

    pub fn finish(mut self) -> Vec<bool> { //write the current state into the bitstream and output it
        assert!(self.value >= M * T); //this assertion holding means it's possible to elide one bit, but how could you elide all of them?
        while self.value > 0 {
            self.bitstream.push((self.value & 1) != 0);
            self.value >>= 1;
        }
        self.bitstream
    }

    pub fn start(bitstream: Vec<bool>) -> Self { //extract the initial state from the bitstream
        let mut r = Self { value: 0, bitstream, };
        while r.value < M * T {
            r.value <<= 1;
            r.value += r.bitstream.pop().unwrap_or(false) as u64;
        }
        r
    }

    fn stream_out(&mut self, symbol: usize) {
        while self.value >= FREQ[symbol] * 2 * T {
            self.bitstream.push((self.value & 1) != 0);
            self.value >>= 1;
        }
    }

    fn stream_in(&mut self) {
        while self.value < M * T {
            self.value <<= 1;
            self.value += self.bitstream.pop().unwrap_or(false) as u64;
        }
    }
}

```

It seems to work, and it approaches optimal compression for large streams (provided T is also sufficiently large). But I couldn't figure out how to get around the need to encode the final state of the encoder (which is the initial state of the decoder).

I noticed it's possible to elide one bit from the encoding because we know that M * T \<= value \< M * T * 2, but I can't see how all bits could be elided.

I looked around at some other implementations and they all seem to do a similar thing. But this seems to contradict ANS having strictly better compression than huffman, if we have symbol frequencies that are powers of two, the ANS encoding is always a few bits larger than the huffman encoding.

# Answer
> 0 votes
That extra word is the equivalent of having an additional symbol that represents the end of file marker, or storing the size of the decoded block in a header. The "overhead" of $O(1)$ bits can also be understood as $o(1)$ bits per symbol, and is therefore is negligible for the purpose of understanding the compression *rate*.

This is the sense in which ANS is always better than or equal to Huffman coding.

It doesn't necessarily mean that ANS is more appropriate than Huffman coding for your specific application; sometimes, for extremely low-bandwidth applications (e.g. submarine communication), the precise number of bits in each message matters a great deal.

---
Tags: information-theory, data-compression, entropy, huffman-coding
---


# Question
Title: What strings are accepted by the described DFA?
Could someone clarify what strings are accepted by the described DFA?

> Draw a DFA for the set of all strings with two consecutive 0’s followed by two consecutive 1’s over Ʃ= {0,1}

# Answer
> 0 votes
This describes all strings consisting only of 0s and 1s that contain the substring "0011".

For example, these are some accepted strings:

* **0011**
* 0**0011**0
* 11**0011**

These strings are not accepted:

* 010101
* 0
* 001001011

---
Tags: finite-automata
---


title: CFG for L {a^nb^m | n <= m+3}

text:
# Question
Title: CFG for L {a^nb^m | n <= m+3}
I need a Context Free Grammar for this language. I could come up with this solution:

```
S -> AB
A -> aA | ε
B -> bbbB | ε

```

But, this grammar is clearly wrong, since the number of a's can still exceed the number of b's. How do I draw a link between the two variables A and B such that $n\leq m+3$?

P.S. It is a humble request to anyone who downvotes this question to please specify the reason in the comments below

# Answer
Based on gnasher729's comment, I came up with the following CFG that I believe meet the requirements:

$$ S \to AAAB \\ A \to a \\;|\\; \varepsilon\\ B \to aBb \\;|\\; Bb \\;|\\; \varepsilon $$
> 3 votes

# Answer
It is hard to come up with a CFG directly. A better approach can be, making a PDA and converting the PDA to CFG. Refer to this answer.
> 0 votes

# Answer
S-\> aSb | bbb A grammar G=(V,T,S,P) is defined as V=s T=a,b S=s P=aSb|bbb
> 0 votes

---
Tags: context-free
---


# Question
Title: Is it possible to automatically detect which variable is not used in future and free those memory?
What I need is similar to garbage collection but a bit different, consider the following code:

```
int* large_arr = new int [1000000];
...
int b = large_arr[0];
int c = large_arr[1] * large_arr[2];
//after here large_arr is never used
int d = b + c;
...

```

So whether it's possible for compilers to detect after the comment line, the variable large\_arr is not used in future and we can free those memories. For me it's an important practical issue. I want to know if this kind of optimization has been studied and what's the name of that.

# Answer
> 1 votes
The C/C++ languages mandate that you explicitly delete the heap-allocated memory, and a standard compiler or IDE will not insert the statement for you.

Determining if some variable is still used from a certain point is a basic task for a compiler, though in certain cases it is not possible to determine the "tightest" place.

This kind of considerations belongs to *static analysis*.

---

Consider this example:

```
int* large_arr = new int [1000000];
int n; cin >> n; n= 2 * n + 1;
if (n == sum_of_proper_divisors(n))
{
   process(large_arr);
}
delete [] large_arr;

```

What would a compiler do ? What would you do ?

---
Tags: compilers, program-optimization
---


# Question
Title: Role of a variable in problem definition in time complexity
I am a research scholar in the field of algorithms and complexity theory. The problem that I am currently working is the $\[1,j\]$-domination problem. Given a graph $G = (V, E)$, with $n = |V|$, the problem asks to compute a minimum dominating set $D$, such that all the vertices outside the solution set $D$ have at most $j$ neighbours in $D$.

Let's say I have an algorithm for some particular graph class $C$ with the running time $2^j \cdot \text{poly}(n)$. Can I say that the problem is polynomial time solvable for graph class $C$?

My main question is, should I always consider $j$ to be a constant, can't it be some function of $n$ that ruins everything?

# Answer
> Can I say that the problem is polynomial time solvable for graph class $C$?

Yes, you can say that if you want to.

> Should I always consider j to be a constant, can't it be some function of n that ruins everything?

This is something we usually state explicitly, however, if you call the problem the $\[1, 5\]$-Dominating Set, then, obviously $5$ is a constant. If you say $\[1,j\]$-Dominating Set, you should clarify whether $j$ is considered to be a constant.

Typically, I would write $\[1,j\]$-Dominating Set is polynomial time solvable when $j$ is a fixed integer. The problem is solvable in time $2^j n^{O(1)}$ whenever $j$ is considered as part of the input.

If $j$ is considered a *parameter*, then in *parameterized complexity* the problem would be fixed-parameter tractable.

---

In other words: Is $j$ part of the input to your algorithm? Or is your algorithm "hardcoded" with a fixed $j$ somewhere?
> 3 votes

# Answer
Let the running time of an algorithm be $T(m,n)=a^mp(n)$. If $m$ is a growing function of $n$, then

$$T'(n)=T(m(n),n)=2^{m(n)}f(n)$$ which can very well be exponential. To keep a polynomial behavior, you need

$$m(n)=O(\log(q(n)))=O(\log(n)).$$
> 0 votes

---
Tags: algorithms, graphs, polynomial-time
---


title: "evenly connected" graph

text:
# Question
Title: "evenly connected" graph
An undirected graph $G=(V,E)$ is "evenly connected" if for every $v\in V$ there's a (not neceserally simple!) path to all the other vertices, **with even number of edges**.

Let $G=(V,E)$ be an undirected graph where $3\leq |V|, 2\leq |E|$. We want the minimal number of edges we need to add to $G$ in order to make the graph evenly connected

Proposed algorithm:

1. Find the number of connected components. Lets denote it as $K$.
2. Check if there's a cycle with an odd amount of edges in $G$. If there is, return $K-1$; else, return $K$.

The algorithm is true, but I can't figure out why. It was asked as part of a multiple choice question, so it's something you need to "see" is true, but I don't really see why.

# Answer
For now assume that the graph is connected. If the graph contains an odd cycle $C$, then you can build an even walk between any two vertices as follows: Let $v$ the first vertex of $C$. Then for any two vertices $u, w$. Let $P$ be an arbitrary path from $u$ to $v$ and $P'$ be a path from $v$ to $w$. Let $W$ be the walk resulting from the concatenation of $P$ and $P'$, and let $W'$ be the walk resulting from concatenating $P,C$ and $P'$. Then either $W$ or $W'$ is even.

On the other hand, if $G$ does not admit an odd cycle, then $G$ is bipartite, and there exist only odd walks between the vertices of one side, and the vertices of the other. We can fix this problem by adding a single edge to any path of length two creating a triangle in $G$.

Finally, if $G$ is not connected, we can make it connected by adding $K-1$ edges connecting different components arbitrarily. Since we cannot introduce cycles by adding a single edge between two components, we still have to add one more edge if $G$ does not contain an odd cycle.
> 3 votes

# Answer
the solution is at least K-1. If there is that cycle, denote as "d" one of the vertices in that cycle. Now for every a and b in V, there must be a path a-\>d-\>b. If that path has even vertices is ok, else you make one cycle resulting in an odd+odd=even number of vertices. Note that that cycle is always in the same connected component.

But this doesn't prove the fact that if there isn't that cycle, the solution is K.
> 1 votes

---
Tags: graphs
---


# Question
Title: Can anyone help explain why the time complexity for this is O(n)
So ive already tried lookig at it but i just get O(nlogn) which is not correct there were some clues like using a geometric series where 1/2+2/4+3/8+i/2^i\<2 but idk how to implement that what should i do.

```
 for i = 1, . . . , n do

        j = n

        while j > i do

           j = j/2
            Do smth

return sum

```

# Answer
> 1 votes
Assuming that the `do smth` instruction runs in constant time, and ignoring the `return sum` instruction since `sum` is undefined, the overall time complexity is asymptotically upper bounded by the number of iterations of the inner loop. This is monotonically increasing with $n$, so let $2^k$ be the first power of two that greater than $n$ (notice that $2^k \le 2n$).

For a fixed value of $i$, the inner loop does at most $ 1+ \log\_2 \frac{n}{i} \le 1+ \log\_2 \frac{2^k}{i}$ iterations. Summing over all values of $i$: $$ \begin{align\*} \sum\_{i=1}^{2^k-1} \left( 1+ \log\_2 \frac{2^k}{i} \right) &\le 2^k + \sum\_{i=1}^{2^k-1}\log\_2 \frac{2^k}{i} \le 2^k + \sum\_{j=0}^{k-1} \sum\_{i=2^j}^{2^{j+1}-1} \log\_2 \frac{2^k}{i} \\ &\le 2^k +\sum\_{j=0}^{k-1} 2^j \cdot \log\_2 2^{k-j} = 2^k + 2^k \sum\_{j=0}^{k-1} \frac{k-j}{2^{k-j}} \\ &= 2^k + 2^k \sum\_{j=1}^{k} \frac{j}{2^j} \<2^k + 2 \cdot 2^k = 3 \cdot 2^k \le 6n, \end{align\*} $$ where we used the fact that $\sum\_{j=1}^{k} \frac{j}{2^j}$ is an Arithmetico-geometric series of ratio $\frac{1}{2}$ (which was the hint you got).

# Answer
> 1 votes
The inner loop is repeated $k$ times, as long as it holds: $\frac{n}{2^k}\>i$, i.e.:

$$\frac{n}{2^k}\>i \iff \frac{n}{i}\>2^k \iff \log\_2 \left(\frac{n}{i}\right) \> k \ .$$

So we have $\log\_2 \frac{n}{i}$ iterations of each outside loop, which means that the total number of iterations is: \begin{align\*} \sum\_{i=1}^n\log\_2 \left( \frac{n}{i} \right) &= \log\_2 \left( \prod\_{i=1}^n \frac{n}{i} \right) = \log\_2 \frac{n^n}{n!} = n\log\_2 n - \log\_2 (n!) = n\log\_2 n - \frac{\log (n!)}{\ln 2}\\ \small{\text{Stirling formula}}\longrightarrow &= n \log\_2 n - \left(n \frac{\ln n}{\ln 2} - \frac{n}{\ln 2} +O(\log n)\right) \\ &= n \log\_2 n - \left(n \log\_2 n -\frac{n}{\ln 2} +O(\log n)\right) \\ &=\frac{n}{\ln 2} + O(\log n)= O(n) \end{align\*}

# Answer
> 0 votes
Steven's answer's the best but that's too smart and tricky, I'll just use induction if I see this in exam :)

proposition: Since $\sum\_{i=1}^n\lg (n/i) = \sum\_{i=1}^n(\lg n - \lg i )=n\lg n - \sum\_{i=1}^n \lg i = n\lg n - \lg (n!)$, we propose

$$ n\lg n - \lg (n!) \le cn $$ for $n\ge n\_0 \> 0,c\>0$

induction: assume proposition holds for $k\ge n\_0$, then because $\lg ((k+1)!)=\lg ((k+1)k!)=\lg (k+1)+\lg (k!)$ and

$$ (k+1)\lg (k+1)=k\lg (k+1) + \lg (k+1)\\ \< k( \lg k + 1/k) + \lg (k+1)\\ = k\lg k+ 1 + \lg (k+1) $$

where we used $\lg (k+1) - \lg k \< 1/k$ \[1\], we have

$$ (k+1)\lg (k+1) - \lg ((k+1)!) \< k\lg k - \lg (k!) + 1 \\ \le ck + 1 \\ \le ck + c = c(k+1) $$

for $c\ge 1$.

base case:

consider $n\_0=2$, we have $2\lg 2 - \lg (2!)=2-1=1\le c2$, for $c\ge 1/2$.

Finally, since proposition is the definition of the Big-$O$ notation, we've proven the run time $\sum\_{i=1}^n\lg (n/i)=O(n)$.

\[1\]nice trick

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


# Question
Title: The language of chains with twice as many $a$s as $b$s is regular?
I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem:

> Let $L$ be the language of all words that have twice as many $a$s as $b$s. Is it regular? Is it context-free?

I attempted the following. First, let $p\>0$ be the pumping length. Observe that $ba^{2p}b^{p-1}$ is in the language, because $b$ occurs $p$ times and $a$ occurs $2p$ times. Let $xy = ba^{2p}$ and $z = b^{p-1}$. According to the pumping lemma, if $L$ is regular then $y$ can be repeated indefinitely many times while keeping the resulting word in the language. In particular, if $L$ is regular, then

$$xy^{2}z = ba^{4p}b^{p-1}$$

is in the language. This is clearly a contradiction, because $4p \neq 2p$. Then the language is not regular.

I have two questions. The first is rather general: is the preceeding proof correct? The second is: how does the fact that a language is regular relate to whether it is context-free? I know a language is context-free if there is a context-free grammar that produces it. Context-free grammars are homomorphic to automatons, and so are regular languages, and hence it should follow that if a language is not a regular language then it cannot be a context free grammar, correct?

Thanks in advance.

# Answer
> 0 votes
These are two really different questions, so your second question really should be asked separately.

```
 Is the preceding proof correct?

```

Not completely. The lemma says that for some $p$, every word at least $p$ long can be pumped, meaning it can be written as $xyz$ such that all words in $xyy^\*z$ are in the language. But it doesn't say you can pick $x,y,z$ at will, which you seem to be doing.

```
How does the fact that a language is regular relate to whether it is context-free?

```

A language is regular if and only if

* a regular expression describes it
* a finite state automaton accepts it
* a regular grammar generates it

A language is context-free if and only if

* a pushdown automaton accepts it
* a context-free grammar generates it

As a result:

* Every finite automaton is a pushdown automaton, but not vice versa.
* Every regular grammar is a context-free grammar, but not vice versa.
* All regular languages are context-free, but not vice versa.

Context-free languages have a different pumping lemma.

---
Tags: formal-languages, regular-languages, automata, formal-grammars, regular-expressions
---


# Question
Title: How does this swap instruction achieves mutual exclusion, progress and bounded waiting if it does?
```
do

{
key=true;
while(key==true)
{
swap(&lock,&key);
}
critical section
lock=false;
Remainder Section
}while(true);

void swap(boolean *a, boolean *b)
{
boolean temp=*a;
*a=*b;
*b=temp;
}

```

How do I prove if it satisfied mutual exclusion, progress and bounded waiting?

The swap is built into hardware and is atomic.

1. Mutual Exclusion

Definition:

No two cooperating processes can enter into their critical section at the same time. For example, if a process P1 is executing in its critical section, no other cooperating process can enter in the critical section until P1 finishes with it.

2. Progress

Definition:

If no process is in its CS and there are one or more processes that wish to enter their CS, this selection cannot be postponed indefinitely.

No process in remainder section can participate in this decision.

3. Bounded Waiting

Definition:

After a prcess P has made a request to enter its CS, there is a limit on the number of times that the other processes are allowed to enter their CS, before P's request is granted.

**Tests**

```
Mutual Exclusion is achieved in my opinion.

P0 tries to enter CS.
Sets key=true
swaps lock and key; now key=false and lock=true(LOCKED)
since key=false, it gets to CS.

Say P1 context switched appeared and wants to enter CS.
Sets key=true.
Swaps lock and key. Both are true as CS is locked at the moment.

So, mutual exclusion is achieved.

Progress is achieved in my opinion.
Say P0 is in remainder section.
lock=false
P1 wants to enter CS.
key=true
Swap lock with key
lock=true and key=false
Loop breaks and P1 enter CS

Bounded waiting is not achieve in my opinion.
P0 exits CS.
lock=false
P0 wants to enter CS again.
It can enter forever.

```

Correct me if I'm wrong. And please share better ways to prove it if you've them. These are some tough concepts of computer science and it'd be great if we could make this even 1% easy to future learners.

# Answer
> 0 votes
1. Mutual exclusion: the `while` loop is only executed with `key=true` so it can only set `lock=true`. As the `swap` is atomic, only one process can get a `false`, which is immediately "consumed". Only at the end of the critical section is the `false` restored. That `false` acts as a unique token.
2. Progress: if `lock=false`, the first process that performs a `swap` will enter.
3. Bounded waiting: the other processes can indeed lock out the given process by always taking the token first when it is available.

---
Tags: operating-systems
---


# Question
Title: Finding the subset of a dictionary that has the minimum edit distance to a given string
I'm looking for the most efficient way of solving an Levenshtein edit distance problem.

We are given as input:

> 1. A set of strings `S` of size `n` \<= 8, with average length `m` \<= 50
> 2. A target string `t` of length `l` \<= 50

Our task is to 'align' `t` with `S` i.e:

> Find the subset `s*` of `S`, where `concat(s*)` has the minimum Levenshtein edit distance (among all the subsets) with `t`

Some thoughts:

1. For 2 strings of length `l1` and `l2`, we could use the standard dynamic programming algorithm which has `O(l1*l2)` time complexity
2. Brute forcing this would require us to compute `editDistance(t, concat(s')) for each subset s'`. This would be approximately `O(l.m.n!)`
3. This could be optimized a bit by memoizing the results i.e if we are computing `editDistance(t, S[1, 2, 3, 4])` we could re-use the computation from `S[1, 2, 3]`)
4. The other option I could think of is to construct a Trie or DAWG (Directed Acyclic Word Graph)

But, I'm not an expert on this, so I might be missing a better solution. How would we do this efficiently?

Thanks in advance!

# Answer
> 0 votes
Try all possible permutation and combination of the set $S$. There are exactly $\sum\_{r = 1} ^{8} \mathsf{8Pr}$ such possibilities for $n = 8$. This sums to exactly 109600.

For each subset $s^\*$ of $S$, find the edit distance to target string $t$ using the standard DP algorithm. This will take time $l\_S \times l$ where $l\_S$ is the total length of all the strings in $S$ and $l$ is the length of string $t$. Since $l\_S$ could be $400$ and $l$ could be $50$, the total running time is ~ $ 2 \times 10^9$.

You can further optimize the algorithm. In the standard DP algorithm, the algorithm stores the minimum edit distance of all the pairs of suffixes of two given strings $a$ and $b$. In the current problem, the string $t$ is fixed; however $concat(s^\*)$ varies depending on subset $s^\*$. However, note that some suffixes of $concat(s^\*)$ overlaps for different $s^\*$. You can show that there at most $S\_l \cdot (nC0 + nC1 + nC2 + \dotsc + nCn)$ possible different suffixes of the concatenated string $concat(s^\*)$ over all possible subsets $s^{\*}$ for $n = 8$. This sums to at most $S\_l \cdot 2^{8} \leq 102400$. Thus, the algorithm only needs to find edit distance of $102400 \times 50$ possible pairs of suffixes. Thus, the algorithm can be implemented in ~ $5 \times 10^{6}$ computation steps, which is doable in $1$ sec on regular personal computers.

---
Tags: algorithms, dynamic-programming, strings, string-matching, edit-distance
---


title: Is variable a constant or a parameter

text:
# Question
Title: Is variable a constant or a parameter
I am working on the $\[1,j\]$-dominating set problem defined in this paper. In section 4, they study the problem complexity on degenerate graphs and prove that the problem is W\[1\]-hard for the parameter solution size. The reduction follows from a well-known W\[1\]-hard problem, multicoloured independent set (MCIS). For a parameterised reduction to work, the parameter in the reduced instance ($k'$) must be a function of the parameter in the original instance ($k$). But, here the parameter $k'$ is given to be at most $2k+j-1$, so is $j$ in the $\[1,j\]$-domination problem constant?

# Answer
It can be considered constant as long as it is mentioned in the problem name. The intuition behind this is that since $j$ is in the name of the problem, different values of $j$ imply different problems, and hence, we can design a different algorithm for each, i.e. the algorithm itself can depend on $j$.

---

Note that here it is quite important to consider $j$ as constant and consider other parameters, since the problem is clearly para-NP-hard if $j$ is not in the problem name, but the parameter itself, since $\[1,1\]$-dominating set is the dominating set problem, which is NP-hard.
> 0 votes

---
Tags: algorithms, graphs, np-hard
---


# Question
Title: What's the standard technique to test if the algorithm satisfies mutual exclusion, progress and bounded waiting or not?
Sorry if this is a stupid question. But it really intrigued me. Same resources at different algorithms are telling different ways to test these stuffs.

Here's an algorithm and how I'd test for its 3 things.

```
Process Larry:

do{
        while(turn!="Larry");
            critical section
        turn="Jim";
            remainder section
        }while(TRUE);
    }while(1);

```

**Mutual Exclusion:**

No two cooperating processes can enter into their critical section at the same time. For example, if a process P1 is executing in its critical section, no other cooperating process can enter in the critical section until P1 finishes with it.

```
1) Initially turn="Larry".
2) Larry and Jim both want to enter critical section.
3) But only Larry succeeds because turn="Larry".
So, mutual exclusion is achieved.

```

**Progress:**

```
1) Larry Enters his critical section.
2) Larry Finished his critical section.
3) Larry sets the turn to Jim.
4) Jim Enters the critical section/
5) Jim Finished his critical section.
6) Jim sets the turn to Larry.
7) Jim quickly finishes his remainder section whereas Larry is stuck indefinitely in his remainder section.
8) Jim can't access the critical section again till Larry doesn't access Critical Section and set turn to Jim.

```

Thus it fails to achieve Progress.

**Bounded Waiting:**

```
1) Let turn="Larry".
2) Larry executes his critical section.
3) Larry wants to execute his critical section again.
4) But it immediately sets turn="Jim".
5) Larry executes his remainder section.
6) Even if Jim doesn't want access to critical section, Larry won't be able to access the critical section.

```

Now,I want to test these 3 conditions for another algorithm, which is given below.

```
Initially both the flags are false; flag[0]=flag[1]=F.
P_0
while(true)
{
    flag[0]=T;
    while(flag[1]==T);//wait if P_1's turn
    critical section
    flag[0]=F
}

P_1
while(true)
{
    flag[1]=T;
    while(flag[0]==T);//wait if P_0's turn
    critical section
    flag[1]=F
}

```

How do I follow a specific approach to test it? Or does it not exist? I want a mental model to think about testing these 3 things in each algorithm.

# Answer
> 0 votes
A "mental model" as you say would be on the same lines as you proceeded with your example. The testing for the 3 conditions should focus on "breaking them", as a single false case is sufficient for non satisfaction. Additionally you can even check for deadlocks, which will imply no progress. This is evident in your 2nd algorithm where if you perform a context switch after any one process executes the first line, then both the flags are set and no process can continue further i.e. deadlock.

# Answer
> 0 votes
It is correct that different sources provide different ways for telling whether an algorithm satisfies a property or not, because there's not standard way for deciding so. Let me point out an example: Peterson's Algorithm for arbitrarilly many processes is proved correct (satisfies mutual exclusion) in three different ways in the following three books: `The Art of Multiprocessor Programming` (by Maurice Herlihy and Nir Shavit), `Distributed Algorithms` (by Nancy Lynch) and `Concurrent Programming: Algorithms, Principles, and Foundations` (by Michel Raynal). This is due to the fact that the same property can be justified by more than one fact.

What you are really asking is: "Is there a general strategy that will prove or disprove an algorithm $A$ satisfies some property $P$?". In your case you are thinking about Mutual Exclusion (ME), Progress (dead-lock freedom? Starvation freedom?) and Bounded Waiting.

The precise recipe for telling whether some of this properties holds does not exist, this is due to the fact that each concurrent program takes advantage of different properties for getting the desired result. Consequently, the same strategy might hold for one or two algorithms and fail for other. You have to reason about the property you think the algorithm satisfies and reason about the facts that force it to hold or not.

There is still something you can do... In general, when trying to prove safety properties like ME, you will use a proof by contraddiction; that is, you assume two distinct processes are in critical section (CS) and reason backward until you reach some absurd conclusion. This will force you to conclude that the property must hold and that mutual exclusion is achieved.

It is an implied fact that if two processed can not enter CS contemporarilly then they can not stay in CS contemporarilly, however the standard definition for ME follows. Let $\mathcal{P}$ be a set of processes executing $A$ such that $|\mathcal{P}|\ge2$.

$ME:$ "at most one process is in CS". $$\forall p,q\in\mathcal{P}.\lnot(pc\_p=CS \land pc\_q = CS \land p\neq q)$$

Contrarilly to ME, progress is a liveness property so you are forced to prove that it doesn't matter for how long the algorithm will run, the property will always hold. That requires again a different set of tools, because you can not simply observe that some *finite* execution satisfies the property; you need to show it will hold forever. This is informally achieved observing the presence of some regularity in the interleaving of accesses to the CS, however from a formal perspective it is quite challenging because it depends on the exact shape of progress you want to prove or disprove.

Regarding Bounded Waiting (BW) I'm not saying anything, I'm not acquainted enough with that property to point out anything. In the book `Distributed Algorithms` (by Nancy Lynch), chapter 8, several algorithms are analyzed w.r.t. the properties you ask and I've seen the author employes recurrence relations to imply whether or not BW is satisfied or not.

I hope this explanation will help you.

---
Tags: concurrency, mutual-exclusion, critical-section
---