# Question
Title: Finding the uniqueness of longest increasing subsequence
I have a problem related to a common dynamic programming problem LIS. I got LIS function that takes `arr` as an input and returns the `length` of the longest increasing subsequence.

```
def LIS(arr):
    n = len(arr)

    # initialize LIS values for all indexes
    lis = [1]*n

    # Compute optimized LIS values in bottom up manner
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j]:
                if lis[i] < lis[j] + 1:
                    lis[i] = lis[j]+1

    # return the maximum of all LIS
    return max(lis)

```

Now my problem is to modify the given LIS function to check whether the longest increasing subsequence is unique. For example: arr = \[2,6,5,7,9,1\], it has LIS 4 and it has no unique solution because LIS could be {2,6,7,9} or {2,5,7,9}.

Here is my attempt to this question. Inside the main condition check in the above function, I checked if there are two or more values in `lis` which are less than the current pointer, then it is not unique. This worked for some examples but didn't work for all. So, I was wondering what is the actual condition to check the uniqueness in this situation? Any hint would be appreciated.

```
if arr[i] > arr[j]:
                if lis[i] < lis[j] + 1:
                    lis[i] = lis[j]+1
                if lis[j] == lis[j-1]:
                    unique = false

```

# Answer
What you did is, eh, checking whether there is a unique increasing subsequence of some kind, not necessary of the longest length. For example, your algorithm will claim non-uniqueness when it is checking the element $9$ in the array $\[8, 7, 9, 1, 2, 3\]$. However, the unique LIS is $\[1, 2, 3\]$.

The goal is whether the longest increasing subsequence (LIS) is unique. For each current element during the loop, we can keep track of whether there is only one possible LIS that ends at the the current element. Then we will check whether the LIS (of the whole array) ends at only one index and whether the LIS ending there is unique.

```
def is_lis_unique(arr):
    arr.append(float('infinity'))  # the LIS must end at this last number.
    n = len(arr)

    # Length is 1 for all subsequences of single element.
    lis = [1] * n
    # `unique_lis[i]` will tell whether the LIS that ends at index `i` is unique.
    unique_lis = [True] * n

    # Compute LIS values in bottom up manner
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j]:
                if lis[i] < lis[j] + 1:
                    lis[i] = lis[j] + 1
                    unique_lis[i] = unique_lis[j]
                elif lis[i] == lis[j] + 1:
                    # Another LIS has been found!
                    unique_lis[i] = False

    return unique_lis[-1]

print(is_lis_unique(([3, 4, 5, 1, 2])         # True
print(is_lis_unique([8, 7, 9, 1, 2, 3]        # True
print(is_lis_unique([8, 7, 9, 1, 2, 4, 3]))   # False

```

The code above is a Pythonic implementation. A "number" that is greater than all numbers is appended to the given array so that the LIS must end at that number. This is a trick to simplify the code.

---

**Exercise**: Given an array of integers of length $n$, compute the number of increasing subsequences of the longest length efficiently.
> 1 votes

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


# Question
Title: How many page frames does the system have for user process?
**Operating System MCQ Question:**
If a system has 1 GB RAM with a page size of 8KB and operating system occupies 16 MB of RAM, how many page frames does the system have for user process?
a. 129024
b. 120924
c. 131072
d. 119864

# Answer
User space = 1 GB- 16 MB = 1008 MB
Page Frame = 1008 MB / 8 KB = 129024
> 0 votes

# Answer
RAM = user + OS

totalSpace/pageFrames = pageSize

First, find out how much user space you have by subtracting out the 16 MB from 1GB. Then take that difference and divide it by the page size to get the number of frames.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: Number of ways to delete edges from an undirected tree such that each subtree has exactly 1 fruit
An undirected tree has $n$ nodes and some nodes contain a fruit. How many ways can we remove edges from the tree such that each sub-tree has exactly one node with fruit in it?

I found this question in an algorithm book without any hint.

**My approach :** Let $C\[i\]$ be the number of ways we can cut the edges if node $i$ was the root of that sub-tree. I am stuck here.

# Answer
> 2 votes
Root the tree at an arbitrary vertex. For each node $v$, we compute two quantities:

* $C\_v$: the number of solutions for the subtree rooted at $v$, assuming that $v$ doesn't contain a fruit.
* $D\_v$: the number of solutions for the subtree rooted at $v$, assuming that $v$ does contain a fruit.

(In fact, we do not need $C\_v$ for nodes $v$ containing a fruit.)

Let's start by computing $D\_v$. Let the children of $v$ containing a fruit be $a\_1,\ldots,a\_n$, and its nodes containing no fruit but whose subtree contains a fruit be $b\_1,\ldots,b\_m$; we don't care about the rest of the children, since any solution must not cut any edge involved in them. (A child $w$ is of the third type if $C\_w = 0$.) Any solution must cut each $(v,a\_i)$ edge. For each $(v,b\_j)$ edge which is not cut, we need a solution in the subtree rooted at $b\_j$ which behaves as if $b\_j$ contained a fruit. Hence $$ D\_v = \prod\_{i=1}^n D\_{a\_i} \prod\_{j=1}^m (C\_{b\_j} + D\_{b\_j}). $$

Computing $C\_v$ is similar. Define $a\_1,\ldots,a\_n,b\_1,\ldots,b\_m$ as before; once again, we don't care about the rest of the children. This time one of the edges from $v$ to one of its children must connect it to a fruit-bearing vertex. This can be either $(v,a\_i)$ or $(v,b\_j)$, and in the latter we do not artificially add a fruit to $b\_j$. Therefore $$ C\_v = \prod\_{i=1}^n D\_{a\_i} \prod\_{j=1}^m (C\_{b\_j} + D\_{b\_j}) \left(n + \sum\_{j=1}^m \frac{C\_{b\_j}}{C\_{b\_j} + D\_{b\_j}} \right). $$

---
Tags: dynamic-programming
---


# Question
Title: Is it possible to encode contradictory horn clauses without goal clauses?
Intuitively, this seems impossible (because negation is forbidden in the head), but i am not sure.

A naive (and wrong) example is

```
p :- p

```

But, this just means

```
¬p or p

```

We can get the assignment `p=true`, so no contradiction.

Could you give me an example of contradictory horn clauses without goal clauses if it is possible (e.g. in propositional logic or predicate logic)? I did not find any explanation about this intuitive property of horn clauses on the internet.

Thanks.

# Answer
If you only allow propositional letters `p`, `q`, `r`, ... and Horn clauses of the form `q :- p₁, ..., pᵢ` then what you are asking for is not possible: we may satisfy any such set of Horn clauses by setting all the propositional letters to `true`.

If you allow anything that is equivalent to `false`, then things get easy, becaue `false` is a Horn clause (with zero premises).
> 1 votes

---
Tags: logic, propositional-logic, knowledge-representation, prolog, logic-programming
---


# Question
Title: C: iterate over a unicode (utf-8/utf-16) string, conditionally modify individual characters, and store it as new string
C's char array can hold an ASCII string, such that a user can query individual characters by indexing the char array, modify them or do what ever they want to, its pretty straight forward. I have browsed through many questions+answers on stack(exchange|overflow) on topic of unicode strings in char arrays but haven't found good interface for iterating over and manipulating such strings. So what am I looking for:

1. A way to iterate over unicode string in C, and print each character
2. Test each character to belong to a certain set of unicode characters
3. Modify all unicode characters in the string that belong to that set and store the result as a new string.

# Answer
> 1 votes
Unicode characters are "Extended grapheme clusters", made out of one or more Unicode code points. Unicode code points are integers with values from 0 to 0x10ffff, often stored in an array of bytes in UTF-8 encoding as 1 to 4 bytes.

You can look up "UTF-8" encoding to see how to recognise Unicode code points in a char array, and change your code accordingly. For example, you could reverse a string by starting at the end, recognising the last code point (1 to 4 bytes), and then copying the whole code point, unreversed.

The Unicode standard describes all kinds of character classes if you want to analyse text. Be warned that the same character (and "same" means "must be treated exactly the same by any code") can be represented by different sequences of code points.

Best is to find and use a suitable library. Unicode without a library is very, very complex. For example, the single character "UK flag" is made of the code points "U+1F3F4, U+E0067, U+E0062, U+E0065, U+E006E, U+E0067, U+E007F"

---
Tags: c
---


title: Timesharing and the MMU

text:
# Question
Title: Timesharing and the MMU
Imagine we are running a program on a modern operating system, such as Linux or Windows. After running for some time, the program's time slice is up. A different program (process) starts to run again. That is, we have had a context switch. During a context switch, does the MMU have to be updated?

Maybe what I am really asking is, is the virtual page table in the MMU apply to every process or just the process that is currently running.

# Answer
Sorry for the late answer. The Memory Management Unit doesn't hold page tables. It holds a TLB (Translation Lookaside Buffer). The TLB holds translations of virtual addresses to physical addresses that were done recently. It isn't managed by the OS (like any cache) but can be flushed by loading the CR3 register on x86.

I don't know if you are familiar with x86. The x86 computers have timers that throw interrupts. When a timer interrupt happens, the OS will give a time slice to another process and reschedule the timer. To change process, the OS will change the CR3 register to point to a new PML4 (first level of page table on x86-64). When it does that, the TLB is flushed by the processor. It thus allows to remain consistent.

Every core of the processor runs only one process/thread and, yes, every core has its own CR3 register. When the context switch occurs, the new process has its own page tables and they are swapped simply by reloading CR3. The page tables are stored in RAM and managed by the OS.

Hope this clears any misconceptions you have.
> 0 votes

---
Tags: operating-systems, virtual-memory
---


# Question
Title: A query regarding the definition of Polynomial Hierarchy and PSPACE
If a $\mathsf{PSPACE-Complete}$ problem (say $\mathsf{TQBF}$) has an algorithm that has the runtime $\mathsf{NP^{NP}}$ it follows that $\mathsf{PSPACE=\Sigma^P\_2}$.

Does that also imply $\mathsf{\Sigma^P\_2 = \Pi^p\_2}$? Moreover, does that imply $ \mathsf{\Delta^p\_2\subset \Sigma^P\_2}$ or is that question still open?

# Answer
Since PSPACE is closed under complementation, if $\mathsf{PSPACE} = \Sigma\_2^P$ then $$ \Sigma\_2^P = \mathsf{PSPACE} = \mathsf{coPSPACE} = \mathsf{co}\Sigma\_2^P = \Pi\_2^P. $$ We *always* have $\Delta\_2^P \subseteq \Sigma\_2^P$. I'm not sure if you can deduce the opposite inclusion under your assumption.
> 1 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Uniform convergence of union of hypothesis
Let $H\_{1}$ and $H\_{2}$ are two hypothesis classes over some domain $X$1.

If both $H\_{1}$ and $H\_{2}$ have the uniform convergence property, then do $H\_{1}$ U $H\_{2}$ have uniform convergence?

# Answer
> 1 votes
Let's start with the definition.

A hypothesis class $\mathcal{H}$ has *uniform convergence* if for every $\epsilon,\delta\>0$ there exists $m = m(\epsilon,\delta)$ such that the following holds for all distributions $\mathcal{D}$ on tagged samples: If we sample at least $m$ elements according to $\mathcal{D}$, then with probability $1-\delta$, $$ \sup\_{h \in \mathcal{H}} |L\_S(h) - L\_{\mathcal{D}}(h)| \leq \epsilon, $$ where $L\_S(h)$ is the empirical loss of $h$ on $S$, and $L\_{\mathcal{D}}(h)$ is the population loss of $h$ with respect to $\mathcal{D}$.

Now suppose that $\mathcal{H}\_1$ has uniform convergence with rate $m\_1(\epsilon,\delta)$, and $\mathcal{H}\_2$ has uniform convergence with rate $m\_2(\epsilon,\delta)$. If we sample at least $\max(m\_1(\epsilon\_1,\delta\_1),m\_2(\epsilon\_2,\delta\_2))$ elements, then with probability $1-\delta\_1$, $$ \sup\_{h \in \mathcal{H}\_1} |L\_S(h) - L\_{\mathcal{D}}(h)| \leq \epsilon\_1, $$ and with probability $1-\delta\_2$, $$ \sup\_{h \in \mathcal{H}\_2} |L\_S(h) - L\_{\mathcal{D}}(h)| \leq \epsilon\_2. $$

Now it's your turn. Can you find $\epsilon\_1,\epsilon\_2,\delta\_1,\delta\_2$ such that the two statements above imply that the following holds with probability $1-\delta$? $$ \sup\_{h \in \mathcal{H}\_1 \cup \mathcal{H}\_2} |L\_S(h) - L\_{\mathcal{D}}(h)| \leq \epsilon. $$

---

Some authors want $m$ to be polynomial in $1/\epsilon,1/\delta$, that is, $m(\epsilon,\delta) \leq C/(\epsilon\delta)^C$ for some $C\>0$. In this case you also need to show that for your choice of $\epsilon\_1,\epsilon\_2,\delta\_1,\delta\_2$, the value $\max(m\_1(\epsilon\_1,\delta\_1),m\_2(\epsilon\_2,\delta\_2))$ is polynomial in $1/\epsilon,1/\delta$ if $m\_1,m\_2$ have this property.

---
Tags: machine-learning, vc-dimension, empirical-research
---


# Question
Title: Why do we consider the + |V| in big-O notation in the time complexity of BFS
It is agreed upon that the time complexity of BFS is $O(|V| + |E|)$.
Breath first search usually is used within a connected component. The connected component with the least $|E|$ given a fixed $|V|$ is a tree graph where $|E| = |N| - 1$. Therefore $O(|E|) \ge O(|V|)$ given a connected component.
Why is the runtime complexity of BFS not $O(|E|)$ instead of $O(|V| + |E|)$?

# Answer
> 1 votes
In any graph, the BFS is usually run using a boolean array to check if a vertex has been previously explored or not. The boolean array will always be created of size $n = |V|$. Even if the graph is not connected, you will need to create this array of size $|V|$, and in the general case, the graph does not necessarily verify $|E| \geqslant |V|$.

That is the reason why we consider a complexity of $\mathcal{O}(|E| + |V|)$ and not only $\mathcal{O}(|E|)$.

---
Tags: graphs, big-o-notation
---


# Question
Title: What is the subset of CFGs called where each expansion must be the same?
I was wondering about a kind of grammar where we can expand rules of the form `A -> X|Y|...` with `A` being a nonterminal and `X` and `Y` being strings of nonterminals or terminal symbols, but the expansions of `X` and `Y` (and all other rules under `A`) must all be the same. Is there a name for this? It feels like it is probably a subset of the class of context free grammars, in which `X` and `Y` could be different or could even contain `A` or be empty (which should both also not be allowed for this grammar).

# Answer
> 2 votes
Every such language is finite and regular. Basically, we can think of the grammar as working as follows: we first make a decision for each non-terminal about which way it will expand; then that determines a single word that is accepted in this way. If there are $n$ non-terminals, and each rule as at most $k$ alternatives, then there are at most $k^n$ different ways to make those decisions, so at most $k^n$ words accepted by the grammar. Thus the language is finite, and therefore regular. I'm not aware of any "name" for this variant of context-free grammars.

---
Tags: formal-languages, context-free, formal-grammars, chomsky-hierarchy
---


# Question
Title: How to get the highest score in this game?
I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this game. At every $i$-th round the players have to choose one value among $A\[i\]$, $B\[i\]$ and $C\[i\]$, which is going to be the score they will get in that round. Considering that the players cannot choose the same array consecutively, how should the players choose the optimal array combination that leads to the highest total score (sum of the scores they get at each round)?

So far I've come up with the solution of selecting at each round the highest possible value among $A\[i\]$, $B\[i\]$ and $C\[i\]$, but this takes $O(n^2)$. I also thought about setting the problem in matrix form to apply linear programming, something like $\max\_{x} \sum b\_{i,j}(x)$ such that $Ax = b$, where $A$ is a $n\times 3$ matrix (where the columns are the arrays $A, B$ and $C$), and $x$ is a $3 \times n$ matrix of 0's and 1's, but I'm not sure of this approach.

# Answer
> 4 votes
Let $a\_i$, $b\_i$, $c\_i$ be the maximum number of points that you can get by picking A\[i\], B\[i\], C\[i\] in the last round.

Obviously $a\_1 = A\[1\]$, $b\_1 = B\[1\]$, $c\_1 = C\[1\]$.

And equally obvious is that $a\_i = A\[i\] + \max(b\_{i-1}, c\_{i-1})$, $b\_i = B\[i\] + \max(a\_{i-1}, c\_{i-1})$ and $c\_i = C\[i\] + \max(a\_{i-1}, b\_{i-1})$. Just calculate each value in turn, then choose the largest of $a\_n$, $b\_n$ and $c\_n$.

If you had not 3 arrays but k, this would run in $O(n \cdot k^2)$ if you do it in the obvious way, or $O(n \cdot k)$ if you are clever: You want the maximum of k values except value j, for each 1 ≤ j ≤ k. Just find the largest of all k values. That is also the maximum of (all but one values), unless you remove that value from your list, so one maximum needs to be recalculated.

---
Tags: algorithms, optimization, dynamic-programming, discrete-mathematics, linear-programming
---


# Question
Title: Determine if the following arithmetics are sentences
How would you determine if these arithmetics are sentences or not?

```
-(x + 2) > y
i++ == 2
i++ == 2 is this sentence True where i = 1

```

I understand it as if the expression can be determinated as true/false, and there are no free variables, it is a sentence. But in my mind only the last one is a sentence since the variable i is bounded to be 1 and the expression can be true/false, whereas the other do not really have an limitation on their variables.

# Answer
According to ref here:

> A formula in first-order logic with no free variable occurrences is called a first-order sentence. These are the formulas that will have well-defined truth values under an interpretation.

So only $\exists i. i++ == 2$ is a sentence (closed formula), otherwise is (open) formula. And unlike most programming languages, in logic with identity we normally just use $=$ as identity relation symbol in the alphabet and we add functional symbols if needed to express functions such as ++ in your case...
> 1 votes

---
Tags: logic, arithmetic
---


title: Read regular Expression from NFA

text:
# Question
Title: Read regular Expression from NFA
Good evening everyone! Can someone help me with the following task? So we have this NFA:

I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{\*}b^{+})^{\*}$ Unfortunately I don't understand how this is possible. If I look at the NFA, then we can accept a word that only includes one a without any b's. But the regular expression in the solution does not make that possible. Or am I missing something? I also converted the NFA to a DFA however that didn't help much.

Thanks!

# Answer
> 2 votes
The RE is wrong. It also includes abcb which is not in the language of the automaton.

# Answer
> 1 votes
The direct edge (a) from initial state 1 to final state 3 is not included in the RE.

---
Tags: regular-languages, finite-automata, regular-expressions
---


# Question
Title: Are there still researches on new Data Structures? If so, what are some examples / scenarios?
And I assume these new data structures are more context/field-specific?

# Answer
> 1 votes
Yes, there is. For instance, you can look at the SODA conference to find several examples of research papers published on data structures. Many of these are sophisticated and even esoteric. The field is too broad to summarize here.

---
Tags: data-structures, research
---


# Question
Title: Find an integer such that linear equation becomes divisible by another given integer
Given integers a, b, and c all \<=n, is there an efficient algorithm to find an integer y such that a | c + b\*y? One brute force approach will be to check for all y = 0 to n
and if there is a solution, there must be a solution within this range.
That will be O(n)

# Answer
> 1 votes
Yes. You are asking how to solve a linear congruence $by \equiv -c \pmod a$. The solution is to compute the modular inverse of $b$ modulo $a$ using the extended Euclidean algorithm, multiply both sides of the equation by that modular inverse, and then read off the solution. This can be done in $O(\log^2 n)$ time.

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Finding the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to given string s
I got stumped by this question during a coding challenge and I haven't come up with promising ideas for how to solve it. I am looking for hints or approaches to solve the problem, not necessarily the code.

> Given a string `s` find the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to `s`. Strings may contain only lowercase English letters.
> **Examples:**
> For `s = "cbaba"`, the output should be `smallestPalindrome(s) = "cbabc"`
> For `s = "abcbc"`, the output should be `smallestPalindrome(s) = "abdba"`
> **Trickier test cases:**
> `input: "xgdfcs"`, `output: "xgeegx"`
> `input: "aazzzzba"`, `output: "abaaaaba"`
> `input: "aiyudauzzzzuaduyie"`, `output: "aiyudavaaaavaduyia"`

> **Guaranteed constraints**:
> `4 ≤ s.length ≤ 5x10^5`.

My previous approach was to:

1. Check if word is a palindrome by moving two pointers (`i`, `j`) at both ends of the word towards the middle.
2. If the two characters don't match, either set `i`-th character equal to the `j`-th, viceversa, OR set both equal to some character that appears later in the alphabet.

...but I couldn't figure out how to decide which option in step 2) should be taken. Maybe there's a better approach to it.

I'm trying to avoid posting the name of the company that posed me this question to prevent future interviewees from knowing the answer in advance, so you can assume I found the question here:

> **Source**: https://codelearn.io/training/detail/33520

# Answer
Let's assume the length is even for now. Split the word up into two equal parts, $w = lr$. Let $l^R$ be the reverse of $l$.

If $l^R = r$, we are done immediately. Otherwise, if $r \< l^{R}$ we can set $r$ equal to $l^R$. The more involved case is when $l^R \< r$. In that case we will need to increment $l$ by one (view the lowercase English words as a base-26 number - this exactly matches lexicographic order), after which we can set $r$ equal to the reversed left hand side and we'll still be lexicographically bigger.

Now if our original word was odd in length we apply the exact same process, except when we shouldn't increment $l$ by one but start the increment one more to the right: at the middle element instead.

Some example code in C:

```
void increment_base26(char* s, int len) {
    int i = len - 1;
    while (i >= 0) {
        if (s[i] == 'z') s[i] = 'a'; // Wrap around and carry.
        else { s[i] += 1; break; }
        i -= 1;
    }
}

void reverse(char *s, int len) {
    for (int i = 0; i < len - 1 - i; ++i) {
        char t = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = t;
    }
}

void next_lexicographic_palindrome(char* s) {
    int len = strlen(s);
    int half = len / 2; // Rounds down.
    int half_plus_mid = half + (len % 2);
    reverse(s, half);                                // Compute l^R.
    int cmp = strncmp(s, s + half_plus_mid, half);   // Compare l^R and r.
    if (cmp > 0) memcpy(s + half_plus_mid, s, half); // l^R > r, can just copy over l^R.
    reverse(s, half);                                // Undo l^R -> l.
    if (cmp >= 0) { return; }                        // Simple cases l^R >= handled.
    increment_base26(s, half_plus_mid);              // Increment left + mid.
    reverse(s, half);                                // Copy over the new l^R to r.
    memcpy(s + half_plus_mid, s, half);
    reverse(s, half);
}

```
> 1 votes

# Answer
This is a very interesting problem, here is my implementation in Python

Maybe we can combine those 2 cases in 1 scenario :

```

def increase_one(input_):
    s = list(input_)
    for i in range(len(s)-1,-1,-1):
        if s[i]=='z':
            s[i]='a'
        else:
            s[i]=chr(ord(s[i])+1)
            break
    return ''.join(s)

def run(string):
    if not string:
        return ""

    left,right = 0,len(string)-1
    length = len(string)

    index = length//2
    if length%2==1:
        left,right = string[:index],string[index+1:]
        if right<left[::-1]:
            return left+string[index]+left[::-1]
        else:
            new_left = increase_one(string[:index+1])
            return new_left+new_left[:-1][::-1]
    else:
        left,right = string[:index],string[index:]
        if right<left[::-1]:
            return left+left[::-1]
        else:
            new_left = increase_one(left)
            return new_left+new_left[::-1]

if __name__=='__main__':
    print(run('cbaba'))
    print(run('abcbc'))
    print(run('xgdfcs'))
    print(run('aazzzzba'))
    print(run('aiyudauzzzzuaduyie'))

```
> 0 votes

---
Tags: algorithms
---


# Question
Title: Maximum-weight matching with a bounded number of fractional edges
In graphs with odd cycles, the maximum weight of a fractional matching may be higher than that of a standard matching. For example, in a cycle of length 3, where all edges have weight 1, the maximum-weight matching contains a single edge so its weight is 1, but the maximum-weight fractional matching contains 50% of each edge so its weight is 1.5. So, allowing some edges to be fractional can improve the total matching weight.

Suppose we want to allow only a limited number of edges to be fractional (e.g. at most three edges). What is a polynomial-time algorithm for finding a maximum-weight fractional matching with this constraint?

When the bound on the number of fractional edges is 0, the problem can be solved by Edmonds' algorithm in time $O(n^2 m)$ (where $n$ is the number of vertices and $m$ the number of edges). When the bound is $m$, the problem can be solved in polynomial time by solving a linear program. Based on this, I believe that for any limit between 0 and $m$, the problem should be solvable in polynomial time. But so far I could not find any polynomial-time algorithm.

---

EDIT: xskxzr commented on a paper by Bourjolly and Pulleyblank, which is indeed closely-related. Its focus is on minimum fractional vertex cover (min-FVC), which is the dual of maximum fractional matching (max-FM; the linear program of min-FVC is the dual of the linear program of max-FM). What I understood from their paper is the following:

* There is an algorithm (in Section 4) for finding a max-FM in a general graph in time $O(|V| |E|)$.
* The same algorithm finds sets of vertices $V\_0,V\_1$ that have a weight of $0$ ($1$) in any min-FVC.
* They can find a set $F$ of vertices that have a fractional weight in any min-FVC.
* They have an algorithm (in Section 5) for finding a min-FVC in which only the vertices of $F$ are fractional; therefore, the number of fractional vertices is minimized, subject to finding a globally-minimum FVC. The run-time, if I understand correctly, is $O(|V| |E|)$.

This raises two follow-up questions:

1. Suppose we are given an integer $k$, which is smaller than $|F|$, and we want to find an FVC with at most $k$ fractional vertices. The size of this FVC will, by definition, be larger than the min-FVC. Can we find an FVC of minimum cardinality, subject to the constraint of at most $k$ fractional vertices? Ideally, the run-time should not depend on $k$.
2. Is it possible to find a set of edges that must have a fractional weight in every max-FM? Is it possible to find a max-FM in which only these edges are fractional?
3. Is it possible to solve problem 1 for max-FM?

# Answer
Let $S$ be the subset of edges that are "really fractional" (i.e., in (0, 1)) in the optimal solution. Since you only allow a constant number of edges to be fractional, you can try every possibility of $S$. Given $S$, let $V(S)$ denote the vertices incident to edges in $S$, you can then remove all edges incident to $V(S)$ but not in $S$. Now you can do maximum fractional matching on $S$ and maximum integral matching on edges not in $S$ seperately.
> 2 votes

---
Tags: algorithms, matching
---


# Question
Title: LQR optimal control of accumulator via dynamic programming
Let

$$ x\_{k+1} = x\_k + u\_k, \qquad x\_0 = 5 $$

where $k \in \\{ 0,1,2,3 \\}$, define the return function

$$ - \sum\_{k=0}^3 \left( x\_k^2 + u\_k^2 \right) $$

with the following inequality constraints on the control inputs

$$0 \leq x\_k + u\_k \leq 5$$

where $u\_k \in \Bbb Z$. I would like to apply dynamic programming to find an optimal control sequence $u\_0^\*, u\_1^\*, u\_2^\*, u\_3^\*$ that maximizes the return function.

My idea was to convert the maximization problem of the return function into a minimization problem of the cost function and apply backward dynamic programming. However, I do not know how to find the minimized cost at each stage. Can anyone please help?

# Answer
> 2 votes
### Problem Restated

The problem is to find the minimum of the cost defined by,

$$\sum\_{k=0}^3 x\_k^2 + u\_k^2$$ with the initial condition $x\_0=5$ and relation $0\le x\_{k+1}=x\_k+u\_k\le5$.

### Simple Arithmetic

$$ x\_0=5\ \stackrel{u\_0=-3}{\xrightarrow{\hspace{2em}}}\ x\_1=2\ \stackrel{u\_1=-1}{\xrightarrow{\hspace{2em}}}\ x\_2=1\ \stackrel{u\_2=-1}{\xrightarrow{\hspace{2em}}}\ x\_3=0\ \stackrel{u\_3=0}{\xrightarrow{\hspace{2em}}} $$

The cost of the state transition above is

$$(5^2+(-3)^2) + (2^2+(-1)^2)+ (1^2+(-1)^2) + (0^2+0^2)=5^2+16=41$$

---

Here is the simple arithmetic that shows 41 is the minimum cost. Note that a square number is always non-negative.

1. If $x\_1=0,1,4,5$, then $u\_0=-5, -4, -1, 0$. $$\ \sum\_{k=0}^3 x\_k^2 + u\_k^2\ge x\_0^2+(u\_0^2+x\_1^2)\ge 5^2 + 17$$
2. If $x\_1=3, x\_1=2$, then $u\_0=-2, -3$. $$\ \sum\_{k=0}^3 x\_k^2 + u\_k^2= 5^2 + 4 + 9 + (u\_1^2+x\_2^2 + u\_2^2 + x\_3^2+u\_3^2)\\\=5^2 + 13 + (u\_1^2+x\_2^2 + u\_2^2 + x\_3^2)\ge 5^2 + 13 + 3=5^2+16.$$

Why does the last inequality hold? We know $x\_1\ge2$. Among the numbers $u\_1, x\_2, u\_2, x\_3$, there are at least 3 numbers that are either $1$ or $-1$, or one of them is bigger than $1$ or smaller than $-1$, i.e., a number whose square is no less than $2^2=4$. $\checkmark$

Tracing the proof above, we can see that the optimal control sequences are

* $u\_0^\*=-3$, $u\_1^\*=-1$, $u\_2^\*=-1$, $u\_3^\*=0$ (as shown above).
* $u\_0^\*=-3$, $u\_1^\*=-1$, $u\_2^\*=0$, $u\_3^\*=0$.

### Brute-Force Programming

As Yuval observed, it is a short programming exercise to brute-force the $6^4=1296$ possible feasible solutions. For example, here it is in Python.

```
min_cost = 999999999999999999  # a number too big
x0 = 5
control_sequence = []
for x1 in range(6):
    cost0 = x0 ** 2 + (x1 - x0) ** 2
    for x2 in range(6):
        cost1 = cost0 + x1 ** 2 + (x2 - x1) ** 2
        for x3 in range(6):
            cost2 = cost1 + x2 ** 2 + (x3 - x2) ** 2
            for x4 in range(6):
                cost3 = cost2 + x3 ** 2 + (x4 - x3) ** 2
                if min_cost > cost3:
                    min_cost = cost3
                    control_sequence = [[x1 - x0, x2 - x1, x3 - x2, x4 - x3]]
                elif min_cost == cost3:
                    control_sequence.append([x1 - x0, x2 - x1, x3 - x2, x4 - x3])

print(min_cost)
# 41

print("Optimal Control sequences: ", control_sequence)
# [[-3, -1, -1, 0], [-3, -1, 0, 0]]

```

### Dynamic Programming

To use dynamic programming, we need to find many overlapping problems, with optimal structure that will lead to recurrent relations. Here we have the natural general problems in the form of the following.

How can we compute the function of minimum cost below? $$f(s, t, x\_0)=\min\_{0\le x\_{k+1}=x\_k+u\_k\le s\text{ for all }k}\sum\_{k=0}^t x\_k^2 + u\_k^2$$ where all variables are integers, $0\le x\_0\le s$, $0\le t$.

The original problem is the case when $s$ = 5, $x\_0=5$ and $t=3$.

Once $x\_1$ is chosen, the cost for the remaining state transitions is none other than the cost of $t$ state transitions starting from $x\_1$. That is,

$$f(s, t, x\_0) =\min\_{0\le x\_1\le s}\ \left((x\_0^2 + (x\_1-x\_0)^2) + f(s, t-1, x\_1)\right)$$

The above recurrent relation enables us to use a nested loop to compute $f$.

1. For $t=0$, $f(s, t, x)=x^2$ for all $x$, $0\le x\le s$.
2. Suppose for some $t$, we have computed $f(s, t-1, x)$ for all $x$, $0\le x\le s$. Use the above recurrence relation to computed $f(s, t, x)$ for all $x$, $0\le x\le s$.

To find the optimal control sequence, keep track of the choices of the variables made for each $f(s,t,x)$ in the loop.

# Answer
> 1 votes
$$ \begin{bmatrix} x\_1 \\ x\_2 \\ x\_3 \\ x\_4 \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}}\_{=: {\bf L}} \begin{bmatrix} u\_0 \\ u\_1 \\ u\_2 \\ u\_3 \end{bmatrix} + x\_0\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $$

or, more succinctly,

$$ {\bf x} = {\bf L} {\bf u} + x\_0 {\bf 1}\_4 $$

Since the final state cost is zero, we define weight vector ${\bf w} := \begin{bmatrix} 1 & 1 & 1 & 0 \end{bmatrix}^\top$. Hence, the optimal control input sequence can be found via

$$\boxed{\begin{array}{ll} \underset{{\bf u} \in \Bbb Z^4}{\text{minimize}} & x\_0^2 + \left\\| \mbox{diag}({\bf w}) \left( {\bf L} {\bf u} + x\_0 {\bf 1}\_4 \right) \right\\|\_2^2 + \left\\| {\bf u} \right\\|\_2^2 \\ \text{subject to} & {\bf 0}\_4 \leq {\bf L} {\bf u} + x\_0 {\bf 1}\_4 \leq x\_0 {\bf 1}\_4\end{array}}$$

which is an instance of integer regularized least squares.

Using Python (with NumPy and CVXPY),

```
import cvxpy as cp
import numpy as np

x_0 = 5

L = np.array([( 1, 0, 0, 0),
              ( 1, 1, 0, 0),
              ( 1, 1, 1, 0),
              ( 1, 1, 1, 1)])

w = np.array([1, 1, 1, 0])
W = np.diag(w)

# optimization variables
u = cp.Variable(4, integer=True)

# build state vector
x = (L @ u) + (x_0 * np.ones(4))

# build cost function
cost = cp.sum_squares(x_0) + cp.sum_squares(W @ x) + cp.sum_squares(u)

# create optimization problem
prob = cp.Problem( cp.Minimize(cost),
                 [ np.zeros(4) <= x, x <= x_0 * np.ones(4) ] )

# solve optimization problem
solution = prob.solve(solver = cp.ECOS_BB)

print("Optimal input sequence: ", np.round(        u.value, 2))
print("Optimal state sequence: ", np.append([x_0], x.value   ))
print("Minimal cost:           ", np.round(     cost.value, 2))

```

which outputs the following

```
Optimal input sequence:  [-3. -1.  0. -0.]
Optimal state sequence:  [5. 2. 1. 1. 1.]
Minimal cost:            41.0

```

Hence, one optimal solution is the following

$$ u\_0 = -3, \qquad u\_1 = -1, \qquad u\_2 = u\_3 = 0 $$

Note that this optimal solution is **not** unique. For details, please consider reading John's answer.

---
Tags: optimization, dynamic-programming, optimal-strategy
---


title: Compare growth rate two functions

text:
# Question
Title: Compare growth rate two functions
Suppose $f\_1(n)=n\log^\*n$,$f\_2(n)=n\log h$ that $h$ is number of vertices of convex hull.

Can we conclude that $$f\_1+f\_2=O(f\_2)?$$ ****Edited**:**

Note that, $h$ is a function accroding to $n$ that $h\leq n$, and according to the input $n$ it can be less than $n$ such as constant.

$n\log h$ is running time of an ouput sensetive algorithm for finding convex hull.

# Answer
$h$ is the number of vertices of *what* convex hull?

If $h$ is a constant, then $f\_2 = \mathcal{O}(f\_1)$ because $\log^\*n\underset{n\rightarrow +\infty}{\longrightarrow}+\infty$.

If I try to interpret more than you wrote, and consider $h$ to be the number of vertices of the convex hull of a set of $n$ points, then you could still have $f\_2 = \mathcal{O}(f\_1)$, because $h$ could be equal to $3$, even with $n$ arbitrary big.
> 1 votes

---
Tags: time-complexity, asymptotics, computational-geometry
---


# Question
Title: How do you get the Bound g(n) of the graph?
We all know that We estimate our running time by drawing a graph and Big O and Big Theta is our worst and average running time respectively and we graph our function like :

$ O(g(n))= f(n)$ and create a range $0\<f(n)\<cg(n)$

and for $\Theta(g(n))$ $0\<c\_21g(n) \<f(n)\<c\_2g(n)$

here What does g(n) means precisely and how do you get the value of g(n) ? For example, for the Big O, What is the role of g(n) and what does it do ?

EDIT : Sorry, I wasn't able to write my problem clearly but I know you have somehow understood that what I was trying to explain.

My question/problem was we know that from growth of function of running time that for $O(g(n))= f(n)$, we have $0\<f(n)\<cg(n)$ and my question is What does it really mean by g(n) and why is it used here ? I have encountered this equation from a algo book but the writer didn't explain about g(x) nor it's usage. that's why I've asked my question here because I'm curious to know about the use of g(x) in that equation.

# Answer
> 0 votes
$g$ represents a function of $n$. Its value depends on the problem you are studying.

For example, consider the following algorithm:

```
Input: an integer array t of size n, an integer x
Ouput: a boolean, equal to true iif x is in t
for each element y in t do
    if x = y then
       return true
done
return false

```

In this algorithm, $n$ is the size of the given array, and it represents the *size of the problem*, meaning that the running time will depend on $n$ (at least if we consider integer arithmetic to be in constant time).

If $f(n)$ denotes the running time of the algorithm for an array of size $n$, then the algorithm analysis can show that $$f(n) \in \mathcal{O}(n)$$ That means that $f(n) \in \mathcal{O}(g(n))$, with $g(n) = n$. We can't conclude that $f(n) \in \Theta(n)$, because the algorithm could take a constant time to return a value (for example if the first integer of the array is equal to $x$).

I suggest you read more content of your book(s) to understand correctly how to do an algorithm analysis.

Also, please note that $\mathcal{O}(g(n))$ or $\Theta(g(n))$ does not represent a function, but a set of functions. That's why it would be preferable to write $f(n) \in \mathcal{O}(g(n))$ instead of $f(n) = \mathcal{O}(g(n))$. At the least, choose $f(n) = \mathcal{O}(g(n))$ over $\mathcal{O}(g(n))=f(n)$.

---
Tags: asymptotics
---


# Question
Title: The Closure Of Regular Language Under Reordering Alphabets
For a regular language $A$ with the alphabet $\\{a, b\\}$. Is $L$ a regular language, where $L$ contains strings of $A$ but sorted with $a$ and $b$?

In other words, formula: $L = \\{ a^{\\#\_a(x)}b^{\\#\_b(x)} \mid x\in A\\}$, where $\\#\_a(x)$ is the number of $a$'s and $\\#\_b(x)$ is the number of $b$'s.

$A$ is a regular language. Is $L$ a regular language?

I found some examples and counterexamples:

When $A = a\*$, $L=a\*$ is regular.

When $A = (ab)^\*$, $L=\\{a^n b^n \mid n \ge 0\\}$ is not regular.

However, I still couldn't convince myself that in a general case when the star operator $(...)^\*$ in $A$ contains both $a$ and $b$, $L$ is not regular.

Any idea about this question?

# Answer
> 1 votes
When $A$ is equal to the starred regular $\\{a,b\\}^\*$ then $L$ equals $a^\* b^\*$, which is again regular. So in general the existence of both $a$'s and $b$'s does not imply nonregularity.

(Thank you nir shahar for the correction.)

---
Tags: regular-languages
---


title: Complexity of calculating sin(nx)

text:
# Question
Title: Complexity of calculating sin(nx)
Suppose we are give a natural number $n$, the value of $\sin(x)$ and $\cos(x)$. How efficiently can we compute $\sin(n x)$?

My Thoughts :
The $\sin (n x)$ expansion will have $O(n)$ terms. The power terms will take $\log(n)$ time each to compute. But there will be a term $nC\_n/2$ so if $n=10$ this will be $10/5$. How to find the complexity of this term? Is it $\Theta(2^n)$? Is there any alternate algorithm to compute it more efficiently? This way it looks around $2^n n\log n $.

# Answer
Start with Euler's identity: $$e^{ix} = \cos x + i \sin x$$ where $i^2 = -1$.

Therefore:

$$\cos (nx) + i \sin(nx) = e^{inx} = \left( \cos x + i \sin x\right)^n$$

So the complexity of computing $\cos (nx)$ is the complexity of raising a single complex number to the power of $n$, then taking the real part.
> 1 votes

# Answer
You multiply y = nx and calculate sin(y), so practically the same time complexity as sin(x).

If n is large, say x is around 0.5 and n = 100,000, then nx will have significant rounding error. In that case, since sin (x + 2kpi) = sin(x), you would use some tricks to calculate (nx - 2kpi) with high precision to avoid rounding errors.

How do you do that? Calculate k = nx / 2pi, rounded to an integer. Don’t worry about precision. Go to the internet to find a better approximation to pi by finding p1 = pi rounded to double precision, and p2 = pi - p1.

Let p’ = p1 with bits removed so that 2p’ x k can be calculated without rounding error, and let p’’ = p1 - p’ + p2, so p’ + p’’ is very close to pi.

Calculate t = 2p’ k without rounding error, then use a “fused multiply-add” operation to calculate nx - t with high precision, then add 2p’’ k. The result is y = nx - 2kpi with high precision, then you calculate sin y. Total time: The time for sin(y) plus half a dozen additional operations. And it will work with high precision if nx is large.
> 0 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Does this online problem have a specific name?
I came across the following family of online problems:

Given a sequence of values of length n, the maximum value and the minimum value of the sequence, our goal: Given min and max, we want to find a good/best element in an online that if an element of the sequence satisfies some criteria based on min and max accept it and stop the execution, otherwise continue receiving more values.

Does this particular family of problems have a name? it appears to me as some extension of secretary problem with more information/assumptions on the input, or some variant of knapsack problem where you have capacity for 1 item only but I don't know if it has a particular name.

# Answer
> 3 votes
Since the goal is to select a single element without receiving further input from a given stream of input, this problem sounds like the optimal stopping problem.

> In mathematics, the theory of optimal stopping or early stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance (related to the pricing of American options). A key example of an optimal stopping problem is the secretary problem.

---
Tags: online-algorithms, optimal-strategy
---


# Question
Title: Algorithm for finding MST in linear time
Are there any algorithm for finding MST of given graph $G$ in linear time?

I found this paper at this link But I can't understand it running time is linear or not.

# Answer
To the best of my knowledge, the best algorithm for computing a minimum spanning tree runs in time $O(m \alpha(m,n))$, where $n$ is the number of vertices, $m$ is the number of edges, and $\alpha$ is the inverse Ackermann function. See Rahul Simha's page on MST for a description of the algorithm and references to the literature.

What Pettie and Ramachandran showed in the paper you link to is that there is no gap between the query complexity of the MST problem and its computational complexity. That is, if there is a decision tree making $X$ comparisons in the worst case, then they can convert it into an algorithm running in time $O(X)$. Compare this to the situation for 3SUM, where the query complexity is $\tilde{O}(n)$, while the computational complexity is conjectured to be $\tilde\Omega(n^2)$.
> 1 votes

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


title: Vertex cover in a special graph

text:
# Question
Title: Vertex cover in a special graph
We say that an undirected graph $G=(V, E)$ is special if for every vertex $v\in V$ and edge $\\{u, w\\}\in E$, it holds that $\\{v, u\\}\in E$ or $\\{v, w\\}\in E$. In other words, a graph is special if for every vertex $v$, the set of the vertices that are not neighbors to $v$ is an independent set.

Is the vertex cover problem still hard when restricted to special graphs? I tried considering the standard NP-hardness proof of the vertex cover problem, but the output graph is far from being special.

# Answer
> 1 votes
Your graph is a complete multi-partite graph, on which the solution is easy (choose all vertices except the ones in the largest part).

To see this, define a relation $\sim$ on $V$: $x \sim y$ if $\\{x,y\\} \notin E$. Clearly $x \sim x$, and if $x \sim y$ then $y \sim x$. If $x \sim y$ and $y \sim z$ then $x \sim z$: indeed, otherwise, $\\{y,z\\}$ is an edge but neither $\\{x,y\\}$ nor $\\{x,z\\}$ are. Thus $\sim$ is an equivalence relation. Denoting its equivalence classes by $V\_1,\ldots,V\_r$, the graph is a complete multi-partite graph with parts $V\_1,\ldots,V\_r$.

---
Tags: graphs, np-hard, vertex-cover
---


title: Matrix Multiplication Verification

text:
# Question
Title: Matrix Multiplication Verification
This question relates to the 2nd edition of *Probability and Computation* by Mitzenmacher and Upfal.

The authors then use the Law of Total Probability

My question concerns the line that begins with $\leq$. Shouldn't that be replaced with $=$ because the authors proved that the event $\mathbf{AB} \bar{r} = \mathbf{C}\bar{r}$ is equivalent to the event $$r\_{1} = - \frac{\sum\_{j=2}^n d\_{1j} r\_{j}}{d\_{11}}$$ ?

# Answer
I'm assuming that all matrices in question are $n \times n$.

Suppose that $A=B=0$ are zero matrices and $C=I$ is the identity matrix. Then $$ \Pr\[ABr = Cr\] = \Pr\[r = 0\] = 2^{-n}. $$
> 0 votes

---
Tags: matrix-multiplication
---


# Question
Title: Find MST after decrease weight of some edges
We are given an undirected weighted graph $G=(V,E)$ that contains at most $2n$ edges, as well as an MST of $G$.

If we decrease the weight of exactly $n$ edges, is it possible to compute an MST of $G$ in $O(n)$?

If it's not possible, are there any lower bound that show us, it can't be done in linear time?

# Answer
> 1 votes
Suppose that you could solve your problem in time $T(n)$.

Given an arbitrary weighted graph on $n$ vertices and $m \leq 2n$ edges, replace all weights by some large weight $M$ which is larger than all weights in the original graph. Find a spanning tree for the new graph in linear time (using BFS/DFS); since all weights are the same, this is also an MST. Now apply your procedure twice to find an MST for the original graph, in time $O(T(n))$.

Therefore your problem isn't easier than finding an MST for a graph with $n$ vertices and at most $2n$ edges, which is not expected to be solvable in linear time. However, no nontrivial lower bounds are known, to the best of my knowledge.

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


# Question
Title: How much faster is the ideal machine without the memory structural hazard versus the machine with the hazard?
I am learning computer architecture and organization. I have the following doubt. Given below is a question along with its solution as seen in number 5 of some homework assignment solutions. But I think that solution is wrong.

> Consider an instruction pipeline for the MIPS32 processor where data references constitute 42% of the instructions, and the ideal CPI ignoring memory structural hazards is 1.25. How much faster is the ideal machine without the memory structural hazard versus the machine with the hazard?
>
> a. 1.34
> b. 1.26
> c. 1.38
> d. None of the above
>
> Correct answer is (a).
> Speedup = (Ideal CPI x Pipeline Depth) / (Ideal CPI + Stall cycles per instr)
> So, Speedupideal= 1.25 x Depth / (1.25 + 0) = Depth
> And, Speedupreal= 1.25 x Depth / (1.25 + 0.42 x 1) = 1.25 x Depth / 1.67
> Required answer = 1.67 / 1.25 = 1.34 (approx.)

The solution calculates Speedupideal and Speedupreal and then it divides them. I don't understand how it gives the answer. I think the solution is wrong. Moreover, the solution says that the stall cycles per instruction are 0.42 * 1 which I think it got from the data references but I don't understand how it got stall cycles per instruction from data references.

As I am a beginner my concepts are not very clear so some help will be appreciated.

# Answer
> 0 votes
1. If stall cycles are not given we can take 1 stall cycle by default.
2. We do not need to find the speed up for both ideal and real to get our answer we can simply find the time taken by pipeline with hazard and without hazard and divide it to get our answer. Source: explanation given by made easy gate faculty. Hope it helps :)

---
Tags: computer-architecture, cpu-pipelines, mips
---


# Question
Title: Deploying circles on 2D space to cover most of points
My question is related to this one

Minimize number of circles to cover set of points

In a 2D space, I have a set of points. I can deploy up to $k$ circles with radius $r$ to the space, and my goal is to maximize the number of points that will be put inside these circles. There are two cases: a) Either the circles cannot overlap b) Or they can.

I am completely stuck here. I appreciate your help.

# Answer
> 1 votes
Here is a start (for the case where you allow overlap):

For every point $v$, start by drawing a circle with radius $r$ such that $v$ is at its center.

Now, observe the following nice property: Let $d$ be a point in space such that it is contained in $m$ of the **drawn** circles. Then, placing a circle with radius $r$ with its middle at $d$ would cover those $m$ points.

Hence, your algorithm should *start* by "drawing" the $n$ circles, and applying an algorithm to find all intersections between the drawn triangles and to get the number of intersections in them.

---
Tags: computational-geometry
---


# Question
Title: Searching through an unsorted array with a better than O(n) complexity?
This question kind of puzzled me, it was presented as a homework assignment for 2nd year undergrads and one of them approached me in case I could give him some pointers, but the problem is I couldn't even think of the answer myself.

They start with an unsorted array of integers and they're to find an element (there could be any number of them, guaranteed to be at least one) whose value is less than that of its neighbors, recursively.

Due to the nature of the problem the array can't be sorted, yet they asked them for a better than linear time solution. How could such a thing be?

He told me they explained binary search in class, but it doesn't apply, just like any other search algorithm based on sorted arrays; still, apparently he tried to do the assignment traversing the array (after all, numbers meeting that criteria could be anywhere, it's not like you can discard part of it), but his teachers added a couple of unit tests to ensure that the search algorithm is both recursive and not O(n).

They gave them two examples:

* \[1, 2, 3, 4\] -\> Only the 1 would meet that criteria.
* \[1, 3, 4, 1, 1\] -\> All three 1s would meet that criteria.

And they also gave them hints:

* It can be solved similarly to how binary search works, via divide and conquer, having the function receive the array, and two integers that mark the beginning and end of a subarrays.
* If the subarray size is 1, that's that location is good to go.
* If its size is 2, the **biggest** of them is the one.
* If its size is \>= 3, you're to check the middle one and its neighbors, if it's smaller than the neighbors you're done, otherwise you'd choose the interval **based on the comparison**.

The emphasis is mine, but, what the hell?

I mean, if an array is size 2, let's say, \[1, 2\], the one being *smallest* should be the chosen index, not the biggest; leaving that aside though, given the description of the problem, how is that comparison going to allow you to discard some part of the array? Which partitions would you take when the whole thing is unsorted?

My days of working with these kinds of algorithms are long gone, but I couldn't figure out what they wanted them to do. Is there something I'm missing? How could this be of logarithmic complexity?

# Answer
> 1 votes
Your example $1,3,4,1,1$, in which you state that all $1$s are less than their neighbors, suggests that by "less than" you actually mean "at most". Any array contains an element whose value is at most that of its neighbors — just take any minimal value of the array.

As you mention, if the array has length $1$ or $2$ then the problem is easy (when the array is $x,y$, you choose the minimum of $x,y$). Given an array $A$ of length $n \geq 3$, let us split it as follows: $B, x, y, z, C$, where $B,C$ are subarrays of lengths $\lfloor \frac{n-3}{2} \rfloor, \lceil \frac{n-3}{2} \rfloor$. We consider three cases:

* If $y \leq x$ and $y \leq z$ then we choose $x$.
* If $y \> x$ then we recurse on $B,x$, an array of length $\lfloor \frac{n-1}{2} \rfloor$.
* If $y \> z$ then we recurse on $z,C$, an array of length $\lceil \frac{n-1}{2} \rceil$.

The procedure terminates in $\log\_2 n$ steps, and so runs in time $O(\log n)$.

---

If you are actually looking for an element which is *strictly* less than its neighbors, you cannot do better than linear time. Indeed, consider any algorithm that makes at most $n-2$ queries. We run the algorithm, and whenever the algorithm accesses an array element, we always answer $1$. We claim that at the end, the array cannot output any index. Indeed, suppose that it inputs $i$. Since the algorithm makes at most $n-2$ queries, there is some index $j \neq i$ it hasn't queried. The queries made by the algorithm are consistent with an array in which $A\[j\] = 0$ and $A\[k\] = 1$ for all $k \neq j$, in which the only correct answer is $j \neq i$. Therefore at least $n-1$ queries are necessary.

# Answer
> 0 votes
You are right.

For example, if the array is:

```
      |  0  if i=52
a[i]= |  1  if 1<=i<=100 and i<>52

```

, it is impossible to use the binary search. You cannot recognize the half containing the single local minimum by a\[\] at its end and middle points. They all have the same meanings for both halves.

So, there is an error in the formulation of the task.

(BTW, it would be **much** better to put an exact formulation of the task in the question)

---
Tags: arrays, search
---


# Question
Title: Model of computation as "reverse engineered function"?
A *model of computation* is currently defined on wikipedia as:

> a model which describes how an output of a mathematical function is computed given an input.

Is it therefore correct, at least as a rough approximation, to conceive of a model of computation as "reverse engineering a function"?

# Answer
> 2 votes
The Wikipedia definition is rather hard to understand, since it isn't formal. If you're looking for an informal definition, you should think of a model of computation as synonymous with a programming language. There is absolutely no connection to reverse engineering.

In theory of computation, we are often interested in computing Boolean functions on strings. That is, the function gets as input some string, and outputs either Yes or No. For simplicity, let us assume that the input is a binary string, and the output is a bit which represents the answer.

A model of computation specifies how *programs* correspond to *functions*. Assuming that a program is also a binary string, a model of computation is a function $M$ that accepts as input two binary strings, a *program* and an *input*, and outputs a single bit. The function computed by a program $p$ is given by $x \mapsto M(p,x)$.

For example, we can take as our model of computation the C language, with some input/output convention in which the input is a binary string and the output is a bit. The value of $M(p,x)$ is then the output of the C program $p$ when run on the input $x$ (if $p$ is not valid, we can let $M(p,\cdot)$ compute some arbitrary fixed function, say $M(p,x) = 0$).

The most popular model of computation in theory of computation classes is the Turing machine model (which is actually a collection of closely related models). When describing algorithms, we are usually implicitly working over a different model of computation, the RAM machine (once again, really a class of similar models).

All reasonable models of computation are *equivalent* in the sense that they define the same set of functions, known as the *computable functions* (another term is *recursive functions*). They differ in the resources needed to compute functions, what is known as *computational complexity*.

---
Tags: computation-models
---


# Question
Title: How to interpret the regular expression 0*10|01(01)*?
I'm having some trouble understanding the regular expression $0^\*10|01(01)^\*$. The expression matches strings like $00010$. But for some reason, I wasn't able to find a string that matches the $(01)^\*$ at the end. An equivalent expression with capturing groups to demonstrate the order of evaluation would be very much helpful.

# Answer
> 1 votes
For a regular expression $r$, the regular expression $r^\*$ matches all words of the form $w\_1 \ldots w\_n$, where $w\_1,\ldots,w\_n$ are matched by $r$ (possibly $n = 0$). For example $01$ matches only the word $01$, and so $(01)^\*$ matches the words $\epsilon, 01, 0101, 010101, \dots$

---
Tags: regular-expressions
---


title: DFA for even number of 1's

text:
# Question
Title: DFA for even number of 1's
My attempt at solution-:

Solution by a teacher-:

Both are giving same answer, is the one that I made correct?

# Answer
Your DFA doesn't match the empty string.

Note that if $L$ is regular, then infinitely many DFAs accept $L$. There is no unique answer for "DFA that accepts $L$". However, there is a *canonical* answer: there is a unique DFA with the minimum number of states that accepts $L$, known as the *minimal DFA*. Your teacher drew the minimal DFA for your language.

(Curiously, there is no "minimal NFA": there are regular languages for which there are several inequivalent NFAs with the minimum number of states.)
> 1 votes

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


# Question
Title: Best compression algorithm for CNF SAT instances in DIMACS
For a CNF SAT instance in the DIMACS format what is the best algorithm to compress it? What is the best algorithm for 3-SAT instances in particular?

In 2020 SAT competition used .xz which if I understand correctly relies on the LZMA algorithm.

Brotli probably would not be optimal as it has a pre-defined dictionary of English words and our text does not contain any English words.

# Answer
> 0 votes
It is unlikely you're going to find a single answer about a single answer that is optimal for all possible 3SAT instances, so the question seems to be based on a faulty premise.

Also, what is "best" is typically a matter of opinion, as often there are multiple criteria that we can trade off (e.g., compression ratio, simplicity, speed of compression, speed of decompression), and it is a matter of personal values how you want to weight those criteria.

---
Tags: satisfiability, data-compression, 3-sat
---


# Question
Title: Minimizing number of MxM squared tiles in an infinite grid covered by any part of a shape
Without restriction (e.g. continuity or convexity are not guaranteed), we're given an `W x H` raster-based shape that needs to be placed on an infinite tiling of `M x M` squares. The shape can placed at any integer positional offset within those squares.

The goal is to minimize the number of squares containing *any* part of that shape.

For example, this shape (shown in orange) can be placed in a way that occupies seven squares on a tiling of `10 x 10`:

However, a more optimal placement is an offset of (+2, 0) which occupies six squares by leaving the central bottom square unoccupied:

Can the brute-force solution (`O(W * H * M * M)`) be improved upon? How / why not?

# Answer
> 1 votes
I found an algorithm. The TL;DR is that we can efficiently precompute a parallel image that indicates whether each position in the image contains any occupied pixels if we were to start a subgrid at that position (going down and to the right, chosen arbitrarily), and determining which collection of those positions produces the minimum total number of occupied subgrids can then be done in simple iteration.

* Compute a "row occupancy" grid which extends to the "left" of the image by M additional pixels. Each pixel in this grid is TRUE if any pixel within M pixels to the right of it (including itself) is nonempty. This can be done in `O(HW)` time because you can iterate each row backwards, keeping track of how long it's been since the last time you saw an occupied pixel
* Compute a "grid occupancy" grid, which is computed similarly. This grid extends "above" the top of the image by M additional pixels as well as to the left by M additional pixels. The algorithm is the same as the prior step, except applied to the row occupancy grid - count from the bottom up, keeping track of the last time you saw an occupied row, marking TRUE when the last occupied row was within the last M pixels.

The grid-occupancy-grid now contains a TRUE if any pixels are present in the square extending down and to the right by M pixels. With this grid, you can iterate through all possible `M x M` offsets, summing up how many TRUE pixels are at `(x + M * N, y + M * N)`, for all legal `N`. This final pass visits each pixel in the grid-occupancy-grid exactly once, so the overall runtime is `O((H + M) * (W + M))`

---
Tags: tiling
---


# Question
Title: Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?
Is there a way to tell if ANY machine on ANY input will halt in fewer than n steps OTHER than running the machine for n steps?

I've read the similar questions and answers such as here, but I wanted to make sure that they were talking about *any* machine on *any* input, not a *particular* machine or on a *particular* input.

If it is possible, I'd love for someone to explain intuitively how it's possible generally. Is it done by simulating the Turing machine more efficiently, or is it done by analyzing the Turing machine syntactically and deducing that it must run in n or fewer steps? I'm also curious how it's possible in the specific case, but that is not this question.

I'm trying to come at it from Rice's Theorem, here. It's clearly a decidable property, even generally, since you can run the machine for n steps, but is it decidable by any method other than that?

# Answer
> 2 votes
Theoretical answer: If you only count the "number of steps", yes, there is. See the linear speedup theorem. (Intuition: I can build a new algorithm where each step does twice as much work, then it will only need about half as many steps. You can think of this as basically exploiting a flaw with using "number of steps" as our way to measure the speed of an algorithm.)

Practical answer: I expect there probably is no algorithm that is appreciably faster in practice (in terms of worst-case time to finish running), and that works on every machine and every input. I have no proof for this.

---
Tags: turing-machines, halting-problem, rice-theorem
---


# Question
Title: Does allowing a mutable transition function in Turing machine make it more powerful?
as the title says does having a mutable transition function make the Turing machine more powerful

by mutable I mean we have a set of transition functions that we can choose one of them arbitrary based on the current state and symbol

in definition of Turing machine from wikipedia instead of $\delta$ we have

a set $\Delta = \\{\delta\_1, \delta\_2, \delta\_3, ..., \delta\_n\\} $ that is a subset of all possible transition functions and

$O = \\{o\_1, o\_2, o\_3, ...\\}$ where $o\_i = \delta\_j$

$\delta : \mathbb{N} \rightarrow O$

$\delta(i) = o\_i$ is the actual transition function and $o\_i$ is defined for current state and symbol and machine start from $\delta(1)$ and then $\delta(2),\delta(3),...$

# Answer
First, let's simplify your definition of a "hyper-Turing machine".

A hyper-Turing machine is a 7-tuple $M = (Q, \Gamma, b, \Sigma, \delta, q\_0, F)$, where

* $\Gamma$ is a finite set of tape alphabet symbols
* $b \in \Gamma$ is the "blank symbol"
* $Q$ is a finite set of states
* $\Sigma \subseteq \Gamma \setminus \\{b\\}$ is a finite set of input symbols
* $q\_0 \in Q$ is the initial state
* $F \subseteq$ is a finite set of "accepting states"
* $\delta : \mathbb{N} \times (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \\{L, R\\}$ is the "transition function"

Note that in OP's original question, we instead had some finite set $\Delta \subseteq (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \\{L, R\\}$ and some function $\delta : \mathbb{N} \to \Delta$. However, without loss of generality, we can always take $\Delta = (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \\{L, R\\}$, since this set is finite. Then we have $\delta : \mathbb{N} \to (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \\{L, R\\}$, but by Currying, this is equivalent to $\delta : \mathbb{N} \times (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \\{L, R\\}$.

The semantics are that the hyper-Turing machine keeps track of the number of transitions it has made so far. If the machine has made $n$ transitions so far, the symbol at the head is $v \in \Gamma$, and the current state is $q \in Q \setminus F$, then let $(q', x', d) = \delta(n, q, v)$. The Turing machine first replaces the character at the head location with character $v$. It then moves the head in direction $d$. It then transitions to state $q$.

It turns out that

> Thm. Any function $\mathbb{N} \to \mathbb{N}$ can be computed by a hyper-Turing machine.

What does it mean for a function $f : \mathbb{N} \to \mathbb{N}$ to be computed by a hyper-Turing machine $M$? It means that there is some hyper-Turing machine over input alphabet $\Sigma = \\{1\\}$ such that for all $n \in \mathbb{N}$, if the hyper-Turing machine is run on input $1^n$, then the Turing machine eventually halts, and when it halts, the tape has $1^{f(n)}$ on it.

Proving this is quite simple. Simply consider the following pseudocode:

For each $i \in \mathbb{N}$:

1: Walk $i$ steps to the right. Then, walk $i$ steps back to the left. From this information, we know whether the string is $1^i$. 2: If the string is $1^i$, then erase the string, write the string $1^{f(i)}$, and halt, taking a total of $i + f(i)$ steps. Otherwise, simply walk back and forth for a total of $2 \cdot (i + f(i))$ steps, then continue with the loop.

So all functions $\mathbb{N} \to \mathbb{N}$ are hyper-Turing computable. Using a bit more creativity, it's possible to extend the original argument to show that given any alphabet $\Sigma$, all functions $\Sigma^\* \to \Sigma^\*$ are hyper-Turing computable. This, of course, involves pushing across the bijection $\mathbb{N} \to \mathbb{N}$, though it requires a bit more creativity than the last case.

So all functions are hyper-Turing computable. Hence, hyper-Turing computability is a rather useless notion.
> 0 votes

# Answer
Having a transition function of transition functions is the same thing as having a single transition function.

Fix an alphabet $\Sigma$ and a set of states $S$. A *transition function* on $S$ is a map $S \times \Sigma \to S$.

You are proposing to use $n$ transition functions \begin{align\*} \delta\_1 &: S \times \Sigma \to S \\ &\vdots \\ \delta\_n &: S \times \Sigma \to S \\ \end{align\*} together with a "meta-transition" function $\tau$ which takes as input the index $i$ of the current $\delta\_i$, a state $s \in S$ and a symbol $a \in \Sigma$, and returns the next index $j = \tau(i, s, a)$ so that next time we use $\delta\_j$.

The above information is equivalent to a single transition function $\bar{\delta} : \bar{S} \times \Sigma \to \bar{S}$ where we now use as the state set $$\bar{S} = \\{(i, s) \mid 1 \leq i \leq n \land s \in S\\}$$ and define $$\bar{\delta}((i,s), a) = (\tau(i,s,a), \delta\_i(s,a)).$$ That is, it makes no difference to say that the $i$-th transition function $\delta\_i$ was used in state $s$ and to say that $\bar{\delta}$ was used in the combined state $(i,s)$.
> 0 votes

---
Tags: turing-machines, hypercomputation
---


# Question
Title: Can there be a computer without software (only hardware)?
Can there be a computer without software (only hardware) which can produce meaningful output?

* "Software" would be for example an operating system (whether in the level of "firmware" or not).
* "Meaningful output" would be for example anything useful for the user, but a practical example might be the solution to any "mathematical exercise" (addition/subtraction/multiplication/division and so forth).

# Answer
> 4 votes
Thats called a logic circuit. It computes stuff. No software here, only physical logic gates involved.

Even though technically a computer *is* a logic circuit...

# Answer
> 3 votes
Despite your attempt at more precise specification, it seems to me there is still a problem with understanding what you call software.

Even without requiring Turing power, I assume that your computer is a little bit more than a logical circuit computing always the same result, and does manipulate some data, if only as input. Then, how do you distinguish data and software. One important point of theory of computing is precisely that there is no such distinction, thanks to Gödel numbering.

For example, a computer C running a program P on input x can be seen as a "*raw computer*" (i.e., without software) running on an input which is a pair \<P,x\>.

Conversely and more to the point, consider a would be "*raw computer*" C that performs some useful computation on some data x to produce a result f(x). Now you can cut you data into a pair of 2 pieces x=\<x1,x2\>, and view x1 as a program run by your *raw computer* C on input x2, to produce f(\<x1,x2\>), i.e. f(x). So C is now a computer that uses software x1 to compute on input x2. This is related to techniques called partial evaluation.

Then, whether you have achieved an example of a useful *raw computer* depends only on the way you look at it. It's all in the eyes of the beholder.

I expect there are other ways to discuss this. For example, a purely hardware circuitry could be represented in a harware description language, and this linguistic representation could then be interpreted by a circuit description emulator. Then you might say that the circuit is hardware, while its linguistic description is software. But, again, where is the distinction. Software is always represented physically in computers, even though it is linguistic in nature, exactly like our circuitry which is physical with a linguistic representation. And that applies as well to parts of the circuit. Is a given part of the circuit a piece of hardware, or just a physical representation of a software written in a circuit description language ("language" is the important word).

# Answer
> 1 votes
There have been completely mechanical computers which would still be considered computers (in the sense that they are turing-complete at least), but are arguably all hardware.

For example, Konrad Zuse developed mechanical logic gates (though the computers he built did use phone relays, it would be possible to produce a completely mechanical computer with them).

Ultimately the software just tells the hardware what to do in a way that is easy to modify. The CPU can run a large number of different commands, but ultimately you could translate each instruction into only the circuitry that would perform each of the instructions. For more on that, you can look into FPGAs.

# Answer
> -1 votes
I vaguely remember that one of the three RSA guys designed a chip that could factor 512 bit numbers by setting the composite number as an input, then you wait a while, and it outputs a factor. No software at all. Source was private conversation with some guys who designed huge computer chips for a living. And it wasn't exactly a "chip", you needed a complete 12" wafer for that.

---
Tags: computer-architecture, computation-models
---


# Question
Title: What are pointers in low-level language like C
I was trying to understand pointers by watching YouTube videos. However, I could not understand

* How do they work?
* Why do we use them?
* When do we use them?

# Answer
> 6 votes
In general, a pointer is a variable which holds the address of a variable. You can use https://godbolt.org/ to find out the assembly equivalent of a pointer. For example,

```
void func(){
    int* pointer;
    int a = 3;
    pointer = &a;
}

```

compiles to

```
pushq   %rbp
movq    %rsp, %rbp
movl    $3, -12(%rbp)
leaq    -12(%rbp), %rax
movq    %rax, -8(%rbp)
nop
popq    %rbp
ret

```

This is a full function so there is some useless stuff. The useful stuff is the following:

```
movl    $3, -12(%rbp)
leaq    -12(%rbp), %rax
movq    %rax, -8(%rbp)

```

The first line puts 3 in the variable `a` which is allocated on the stack. The second line uses the `lea` instruction to put the address of the variable `a` in RAX. The third line puts RAX in the pointer called `pointer`.

Now for the stuff I called useless earlier. When you enter a function in C++/C, it will:

1. Push RBP on the stack;
2. Put RSP in RBP;
3. Decrement RSP of the allocated stack space for the function.

After those 3 steps, the variables local to the function are accessed using negative relative offsets from RBP. In this case, the substracting RSP part has been optimized away.

This is how pointers work at the low level. They are allocated on the stack if they are local to the function. If they aren't, then they are allocated in the data segment of the executable. This segment will be accessed by default using a relative offset from RIP (the instruction pointer).

Now that excludes smart pointers and stuff like that which are best practice nowadays. A useful program (excluding libraries) is probably using C++ and some variant/custom smart pointers nowadays. Otherwise, this developer is wasting time to end up with a buggy/crashing program. As to libraries, most of the time, the allocation is left to the user of the library by calling some allocating functions.

> Why do we use them?
>
> When do we use them?

I think those 2 questions ask the same thing. In general, pointers are used because they allow to allocate memory. You cannot allocate memory in C++/C without receiving a pointer to the allocated memory. This is due to the underlying way that the operating system works. The user mode program makes a syscall asking for space in RAM and the OS returns a pointer to the beginning of the space it allocated.

This allows for dynamic programming where you don't know the size of everything at compilation time.

This allocated space will also survive exiting the local scope of the function where it was allocated. This is useful especially if you are working in several threads which is often the case in real world applications.

I would tend to say that statically allocated pointers are used mostly with arrays. The name of the array in C++/C is a pointer to the first member of the array. Otherwise, they are used for dynamic allocation because it cannot be done differently due to the way the underlying OS works.

> How do they work?

This is hard to explain in one small answer. The statically allocated pointer is a variable allocated on the stack. It contains the address of another variable or of an array member. It can even contain an absolute address. For example, one can write:

```
unsigned int* pointer = (unsigned int*)0x8000;

```

The pointer called `pointer` now points to address 0x8000. By typing `*pointer = 3;`, address 0x8000 now contains 3. This is to avoid of course in a user mode program but can be useful when writing an OS from scratch. This is undefined behaviour in a user mode program because no one knows if the address 0x8000 in the virtual address space has been allocated for your program. Accessing this address could do anything including a page fault and killing your program.

# Answer
> 3 votes
While the answer of user123 covers a number of the technicalities well, I think a small memory illustration may be useful. You can generally think of a pointer as an index into physical memory. Let's see a little bit of what that might look like:

Empty Memory:

\[####\]\[####\]\[####\]\[####\]\[####\]\[####\]\[####\]\[####\]
64 68 72 76 80 84 88 92

Here I use a '#' to represent a byte (8 bits, each of which can be 0 or 1). I have separated them in groups of four because that is the size of an int and unsigned int in C. Unsigned int ranges from 0 to 4,294,967,295 and int from -2,147,483,648 to 2,147,483,647. We haven't initialized any memory here, but there still are bits there, they're pretty random because they are simply whatever that memory was last used for (or even more random in a freshly booted system). Below each set of four, I am writing the address of the memory. Suppose I allocate an integer array of length 2. The operating system will give back a pointer, say myPointer, that contains the start of the allocated block of memory, in this case suppose it is 72.

So now I have the pointer myPointer with a value of 72.
myPointer = 72
\*myPointer dereferences myPointer, so this gives us the value of the thing being pointed to. In order to do this operation we need to know what type we're trying to read. Let's take a close look at the memory from 72-79, 8 bytes:
\[11111101\]\[11110000\]\[11100111\]\[00100100\]\[00100110\]\[00111000\]\[10011000\]\[00000011\]
72 76
A bunch of random bits. If we try to read the first number as an unsigned integer (so we read the first 4 bytes starting from 72, i.e. \[11111101\]\[11110000\]\[11100111\]\[00100100\], we get 4260423460, but if we read it as a signed integer (same for bytes) we get -34543836 (I think at least, though I guess this could theoretically be different in some implementations of C/C++ http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2218.htm ) Here we will read by default as a signed integer, since we allocated an integer array and thus have an integer type pointer.

Ok, suppose we follow best practice and initialize our memory, we can do it with dereferencing as follows: \*myPointer = 0;
\*(myPointer+1) = 0;
Why 1 you ask? Don't we need to move over 4 bytes? Yes, but C and C++ know the type of the pointer and while doing pointer arithmetic they automatically multiply the increment by the size of the type (4 for integers, and since this was an integer array we will have an integer pointer), so here\ (myPointer+1) is 76 and (myPointer+2) is 80. There is more coverage regarding dereferening of pointers here: https://stackoverflow.com/questions/4955198/what-does-dereferencing-a-pointer-mean Anyway, after proper initialization to zero, the memory is all zeros:
\[00000000\]\[00000000\]\[00000000\]\[00000000\]\[00000000\]\[00000000\]\[00000000\]\[00000000\]
72 76

As a convenient shorthand we can write \*(myPointer+j) as myPointer\[j\] in C and C++, which is the notation you will usually see for accessing arrays. Since addition is commutative, myPointer+j is the same as j+myPointer, so it is also the case that myPointer\[j\] is the same as j\[myPointer\], though this later form is not intuitive and you're highly unlikely to see it in real code.

This answer is incomplete, but was too long to make as a comment, apologies for the partial answer.

---
Tags: memory-management, memory-access, c
---


# Question
Title: Why does this algorithm to calculate number of pronic numbers in an interval work?
I am given $A$ and $B$, where $A$ is less than or equal to $B$, and they are in the range of $\[1, 100000000\]$. I want to calculate the number of pronic numbers in that interval $\[A, B\]$. These numbers are numbers $n$ such that $k \times (k + 1) = n$ for some $k$. The following algorithm works, but I am having a lot of trouble understanding the intuition behind it. Can one explain to me why it works?

```
def pronic(num) :

    # Check upto sqrt N
    N = int(num ** (1/2));

    # If product of consecutive
    # numbers are less than equal to num
    if (N * (N + 1) <= num) :
        return N;

    # Return N - 1
    return N - 1;

# Function to count pronic
# numbers in the range [A, B]
def countPronic(A, B) :

    # Subtract the count of pronic numbers
    # which are <= (A - 1) from the count
    # f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);

```

# Answer
First of all, denoting the number of pronic integers in $1,\ldots,m$ by $N\_m$, the number of pronic integers in $A,\ldots,B$ is $N\_B - N\_{A-1}$: this counts the number of pronic integers in $1,\ldots,A-1,A,\ldots,B$, minus their number in $1,\ldots,A-1$.

Next, a formula for $N\_m$. It is the unique integer $x$ such satisfying $x(x+1) \leq m \< (x+1)(x+2)$: the pronic integers in $1,\ldots,m$ are $1\cdot(1+1),2\cdot(2+1),\ldots,x\cdot(x+1)$. Roughly speaking, $x \approx \sqrt{m}$, and this suggests checking whether $\lfloor \sqrt{m} \rfloor$ might work. The main observations are $$ m = \sqrt{m}^2 \< (\lfloor \sqrt{m} \rfloor + 1)^2 \< (\lfloor \sqrt{m} \rfloor + 1)(\lfloor \sqrt{m} \rfloor + 2) $$ and $$ m = \sqrt{m}^2 \geq \lfloor \sqrt{m} \rfloor^2 \> \lfloor \sqrt{m} - 1 \rfloor \lfloor \sqrt{m} \rfloor. $$ If $\lfloor \sqrt{m} \rfloor (\lfloor \sqrt{m} \rfloor + 1) \leq m$ then $x = \lfloor \sqrt{m} \rfloor$ works, and otherwise $x = \lfloor \sqrt{m} \rfloor - 1$ does.
> 0 votes

---
Tags: algorithms, number-theory
---


title: The complement of coNP with oracle

text:
# Question
Title: The complement of coNP with oracle
I was assuming the following equivalence in one proof:

$L \in NP^B \iff \overline{L} \in coNP^B$

here $NP^B$ is the class $NP$ with oracle acess to oracle $B$ and similarly $coNP^B$.

Is this correct? Does it matter if I give oracle acess to $B$ or to $B^c$?

# Answer
Here is a definition of $\mathrm{NP}^B$. A language $L$ belongs to this class if there exists a polynomial $p$ and a polytime oracle function $f$ (that is, a polytime function which has access to an oracle) such that $$ x \in L \iff \text{there exists $y$ of size at most $p(|x|)$ such that } f^B(x,y), $$ where the notation $f^B(x,y)$ means that we run $f$ with $B$ as the oracle.

Similarly, a language $L$ belongs to $\mathrm{coNP}^B$ if there exist $p,f$ as before such that $$ x \in L \iff \text{for all $y$ of size at most $p(|x|)$ it holds that } f^B(x,y). $$

Using this, it should be easy to show that $L \in \mathrm{NP}^B$ iff $\overline L \in \mathrm{coNP}^B$: given $(p,f)$ witnessing membership of $L$ in $\mathrm{NP}^B$, the pair $(p,1-f)$ witnesses the membership of $\overline L$ in $\mathrm{coNP}^B$, and vice versa.

---

Given oracle access to $B$, we can simulate oracle access to $\overline{B}$ as follows: whenever the oracle function queries $\overline{B}$, we query $B$, and reverse the answer. This increases the running time by at most a constant factor, and so a polytime oracle function with access to $\overline{B}$ can be simulated by a polytime oracle function with access to $B$. Therefore $\mathsf{NP}^B = \mathsf{NP}^{\overline{B}}$.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Intuitive understanding of the Boolean Hierarchy
I am trying to understand the Boolean Hierarchy. the formal definition of the Boolean Hierarchy is as follows:

* $BH\_1 = NP$
* $BH\_{2k}$ is the class of languages which are the intersection of a language in $BH\_{2k-1}$ and a language in $coNP$.
* $BH\_{2k+1}$ is the class of languages which are the intersection of a language in $BH\_{2k}$ and a language in $NP$.
* $BH$ is the union of the $BH\_i$

I am clear with the formal definition but not many sources explain it intuitively. Lets decipher it as follows:

* $BH\_1 = NP\_0$
* $BH\_2 = NP\_0\cap coNP\_1$
* $BH\_3 = (NP\_0\cap coNP\_1) \cup (NP\_1)$

Thus if language is in $BH\_3$ iff: Its first language (namely $NP\_0$) is satisfiable, second language (namely $coNP\_0$) is unsatisfiable, and third language (namely $NP\_1$) is satisfiable.

Alternatively, can we define the complexity levels in $BH$ as follows:

$BH\_i$: A language is in $BH\_i$ iff it requires $i$ oracle calls to an $NP$-oracle to solve the problem in polynomial time. Thus, for any $BH\_i$ there seems to be no algorithm that solves the problem in polynomial time with $j$ oracle calls, where $(j\<i)$ to an $NP$-oracle ((in the worst case).

Is this alternate definition equivalent to the formal definition or there is some flaw in the understanding?

# Answer
> 3 votes
The Boolean hierarchy is *cumulative*: $\mathrm{BH}\_n \subseteq \mathsf{BH}\_{n+1}$. In particular, all levels of the Boolean hierarchy contain $\mathrm{P}$.

The introduction to Pitassi, Shirley and Watson's Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity contains some equivalent definitions of the Boolean hierarchy, and relevant pointers to the literature. The simplest definition that they give is: $\mathrm{BH}\_n$ is the set of decision problems computable by making $n$ many $\mathrm{NP}$ oracle calls, and outputting the parity of the result.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Design a DFA that accepts numbers whose sum of digits is $2 \mod 3$
> Design a DFA that accepts language $$L = \left\\{ x \in \\{ 0, 1, 2 \\} : \text{ sum of digits in } x \text{ is } 2 \mod 3 \right\\}$$

---

How to make a DFA for this? I have no idea how to solve this dfa problem. I have a solution by someone but I am not getting concept to start this solution.

# Answer
A good first step for designing automata is to think about what states you will need. Here, you would need to remember the sum – which is not possible with a DFA – but thankfully, we only need to remember the sum in mod3 arithmetic, which means it can only have three distinct values: 0, 1 or 2. Therefore, we can keep track of the sum mod 3 with a finite number of states.

Then you need to devise the state transitions between the states representing these values. A convenient fact of modular arithmetic to remember is that $a + b \equiv a - (n-b) \mod n$.
> 1 votes

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


# Question
Title: The recognizability of $\overline{A}_{TM}$
In undergrad theory classes, the idea of decidability and recognizability is introduced. It's well known that $A\_{TM}$, the set of words accepted by a TM $M$, is recognizable but not decidable. We also know that the complement problem $\overline{A}\_{TM}$ is co-recognizable but not recognizable.

I have a doubt about the co-recognizability part. If $\overline{A}\_{TM}$ is co-recognizable, then we have a TM that recognizes the set of words not accepted by some TM $M$. Doesn't that mean $\overline{A}\_{TM}$ is recognizable, since we have a machine that recognizes the language?

I know this can't be the case, but I'm not able to find out where I'm going wrong with my logic.

# Answer
> 1 votes
This statement is incorrect.

> If $\overline{A\_{TM}}$ is co-recognizable, then we have a TM that recognizes the set of words not accepted by some TM $M$.

The fact that $\overline{A\_{TM}}$ is co-recognizable means that there is a TM $T$ that recognizes all words not in $\overline{A\_{TM}}$. Equivalently, $T$ recognizes all words in $\overline{\overline{A\_{TM}}}=A\_{TM}$, i.e., $T$ recognizes all words accepted by $M$.

---
Tags: turing-machines, undecidability, semi-decidability
---


# Question
Title: Constructing PDA for $L = \{w\in\{a,b\}^{\ast}\;|\; |w|_a > 2|w|_b\}$
> Construct a PDA, which recognizes the following language $L$: $L = \\{w\\;|\\; |w|\_a \> 2|w|\_b\\}$, so it is the language that consists of words which have more than twice as many $a$'s as $b$'s.

I have constructed a PDA, which I believe to recognize $L$, however it is too complicated to prove its correctness. Is there an easy way to construct such an automata? I need a hint.

# Answer
> 1 votes
While reading prefixes $u$ of a word $w$, you need to count $|u|\_a - 2|u|\_b$ and check whether this value is greater or equal to $1$ when $u = w$.

Counting only the value of $|u|\_a$ is easy: when you read a $a$, push a $A$ in the stack. The number of $A$ in the stack will be the same as $|w|\_a$ at the end.

Counting only the value of $-2|u|\_b$ can be done with the same idea: when you read a $b$, push two $B$'s in the stack.

However, if you need to do both, it could be a bit trickier than that. You could still combine the ideas:

* if there is nothing or a $A$ at the top of the stack while reading a $a$, then push one more $A$ in the stack;
* if there is nothing or a $B$ at the top of the stack while reading a $b$, then push two more $B$'s in the stack;

Can you find what to do if there is a $A$ at the top while reading a $b$, or a $B$ while reading a $a$? I will edit my answer if you need more details.

---
Tags: automata, pushdown-automata
---


# Question
Title: How to prove Big-O when $f(n)$ is defined sectionwise
I'm given a function which is defined based on a condition, for example

$$ f(n) = \begin{cases} 4n+1, \ \text{n is even}\\ 3n^2+2, \ \text{n is odd} \end{cases}. $$

I have to prove or disprove that $f(n)$ is $\mathcal{O} (n^2)$. Do I have to show $f(n) \< c n^2$ for all $n \> n\_0$ for both expressions or do I just select the $3n^2+2$ expression?

# Answer
> 2 votes
Your intuition tells you correctly that it should suffice to check the bound for the term $3n^2+2$, since $3n^2+2$ dominates the function $4n+1$. nir shahar has pointed that out in their answer. However, for a formal proof that $f(n) = \mathcal{O}(n)$, you will need to formalize your intuition that $3n^2+2$ dominates $4n+1$ and you will also have to argue why this reduces your problem to showing $3n^2+2 \< cn^2$.

I advise you not to prove $3n^2+2 \ge 4n+1$ and then use this statement. I think it will be easier to instead prove both $3n^2+2 \le cn^2$ and $4n+1 \le c'n^2$ for $n \> n\_0$, with suitable constants $c, c' \> 0$, and $n\_0$. Then, with $C = \max(c, c')$, you will have $f(n) \le Cn^2$ for all $n\>n\_0$.

Maybe this way will cost you two more lines of a proof, but you will be rewarded with a more straight-forward proof.

# Answer
> 1 votes
you have to do for both expressions. But in this case, one expression is strictly smaller than the other one, so you can do it just for the $3n^2+2$ and say $4n+1\<3n^2+2$ and therefore also $4n+1\<cn^2$.

---
Tags: algorithms, efficiency, big-o-notation
---


# Question
Title: Design a DFA that accepts language L={ x in (0,1)* | the third bit from x from its right end is 1}
this is very confusing question. I am having no idea to solve it, can you please guide me here?

# Answer
> 1 votes
Here is the answer. We are basically tracking the last 3 bits. eg in 001 we get 0 then last 3 bits will be 010. That's all.

---
Tags: finite-automata
---


# Question
Title: Is there some kind of expected error margin for my Monte Carlo algorithm?
My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the other circles, through iteratively testing random points of the larger circle.

On this site it is stated that Monte Carlo algorithms' error decreases with the square root of the number of trials. Would it thus be correct to state that, since my expected error is upper bounded in the beginning by 100%, after 100 iterations, the error would be upper bounded by 10%, and after 10000 iterations, this would be only 1% and so on?

# Answer
> 6 votes
Suppose that you are trying to estimate some quantity $\mu$ by performing some random experiment $X$ with mean $\mu$ and variance $\sigma^2$. In order to obtain a better estimate, you can repeat the experiment $n$ times and take the average $\bar{X} = \frac{X\_1+\cdots+X\_n}{n}$, which also has mean $\mu$ but its variance is only $\sigma^2/n$. This means that $$ \mathbb{E}\[(\bar{X} - \mu)^2\] = \frac{\sigma^2}{n}. $$ Moreover, under mild assumptions, the distribution of $\bar{X}$ will be "close" to a normal distribution with mean $\mu$ and variance $\sigma^2/n$.

The standard deviation is the square root of the variance, which is $\sigma/\sqrt{n}$; this decreases like square root of $n$. The standard deviation is a standard measure for error. If you approximate the distribution of $\bar{X}$ by a Gaussian, then the width of the Gaussian scales like the standard deviation, and so it has inverse square root behavior (as a function of the number of experiments).

---

In your case, the experiment $X$ has two possible answers, $0$ and $1$, and so its variance is $\mu(1-\mu) \leq 1/4$, and its standard deviation is at most $1/2$. Taking the average of $n$ experiments gives us a standard deviation of at most $1/(2\sqrt{n})$.

Therefore if you average over 100 iterations, your standard deviation will be at most $1/20$. This doesn't mean that you will be $1/20$ away from the true value. No such guarantee is possible — if you're unlucky then all $X\_i$'s will be equal to $0$ or all of them to $1$, one of which will result in an error of at least $1/2$. It means that the distribution of the output will look roughly like a standard Gaussian scaled down a factor or 20, and centered around the true answer $\mu$.

---
Tags: algorithm-analysis, randomized-algorithms, monte-carlo, error-estimation
---


# Question
Title: What kind of words does this PDA accepts
I have a PDA A = ({q0, q1}, Σ = {a, b}, Γ = {a}, δ, F = {q1}), with these transition functions δ:

((q0,a,ε),(q0,a));

((q0,b,ε),(q0,a));

((q0,a,ε),(q1,ε));

((q1,a,a),(q1,ε));

((q1,b,a),(q1,ε)).

The exercise asks me to explain the structure of the words accepted. I have designed the PDA but i'm having problems understanding what kind of words the PDA accepts. Any kind of help is really appreciated.

# Answer
I suppose that your acceptance mode is by final state and empty stack.

The loops around $q\_0$ add one stack symbol for each input letter that is read. After this, the third transition reads an $a$ without touching the stack. Finally, all transitions around $q\_1$ remove one stack symbol for each input letter that is read.

To reach an empty stack in $q\_1$, the number of loops around it has to be the same as around $q\_0$. Exactly in the middle there is one $a$ that takes you from $q\_0$ to $q\_1$. Thus the language would be $$\\{w\_1\cdot a \cdot w\_2: |w\_1| = |w\_2|\\}.$$
> 0 votes

---
Tags: pushdown-automata
---


# Question
Title: How to verify-: A language over Σ is also a language over any alphabet that is a superset of Σ?
Context-:

A language over Σ need not include strings with all symbols of Σ Thus, a language over Σ is also a language over any alphabet that is a superset of Σ.

https://www.univ-orleans.fr/lifo/Members/Mirian.Halfeld/Cours/TLComp/TLComp-introTL.pdf

Page number 10

**I am trying to understand what it is trying to say-:**

Σ={a,b}

1. Language need not include both a,b. Which makes sense to me.
2. L is language over Σ={a,b} say L={aa,aaaa,aaaaaa}
3. L is language over Σ then L is language over any alphabet which is superset of Σ.

My confusion is they say L is language over Σ and L is language over any alphabet which is superset of Σ. But isn't superset of Σ=Σ itself? So is there any sense in this logic? This seems to be written in every books I have followed. So curious if it has some deep meaning or just is theory.

As well as another confusion is how we reached this conclusion? Can you show step by step procedure that lead us to believe that if L is language over Σ, then L is language over any alphabet which is superset of Σ.(I don't need mathematical proofs, any verification techniques using examples will work good for me).

# Answer
> 4 votes
$\Sigma$ is a (not proper) superset of itself but there are other supersets of $\Sigma$. For example if $\Sigma = \\{a,b\\}$ and $\Sigma'=\\{a,b,c\\}$ then $\Sigma'$ is a (proper) superset of $\Sigma$.

To show that the claim is true you just need to show that, for every finite set $\Sigma' \supseteq \Sigma$, you have $(\Sigma')^\* \supseteq \Sigma^\*$. Then, for any language $L$ over $\Sigma$ you have: $$ L \subseteq \Sigma^\* \subseteq (\Sigma')^\*, $$ and hence $L$ is also a language over $\Sigma'$.

---
Tags: automata, finite-automata, proof-techniques
---


title: What does ({a,b}*)² mean?

text:
# Question
Title: What does ({a,b}*)² mean?
Pretty much just the title. Is it all possible combinations of a and b that have 2 letters ?

# Answer
It’s not a standard way to specify a regular or any other language, so any answer would be a guess. Most likely candidates:

```
A string in (a, b)*, followed by another string in (a, b)*

A string in (a, b)*, followed by the same string again.

```

Ask whoever gave this specification for a language.
> 0 votes

---
Tags: formal-languages, notation
---