# Question
Title: algorithms and the sequencing of numbers given a value
The numbers in the table below are the result of executing an algorithm that has one parameter $n$, a non-negative integer, and produces sequences of integers as outputs. For values of $n$ from 0 to 5, the algorithm produces the following sequences of numbers as outputs:

* $n = 0$: 0, 2.
* $n = 1$: 3, 5, 7, 9.
* $n = 2$: 6, 8, 10, 12, 14, 16.
* $n = 3$: 9, 11, 13, 15, 17, 19, 21, 23.
* $n = 4$: 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
* $n = 5$: 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37.
* $n = 6$: ?

I just started a course and I don't understand. I get the pattern differences and I understand all the patterns that are formed such as each outputs first number is a multiple of three and then the lists rise by two for each output given. When I put this down off of what I was given as a reference in the class it tells us to create an algorithm for this, but we have not been given but a few ways to do this so I tried:

* $n^2-2\cdot0$ which would be $36-0=36$.
* $n^2-2\cdot1$ which would be $36-2=34$.
* $n^2-2\cdot2$ which would be $36-4=32$.
* $n^2-2\cdot3$ which would be $36-6=30$.
* $n^2-2\cdot4$ which would be $36-8=28$.
* $n^2-2\cdot5$ which would be $36-10=26$.

So my outputs come out as 36, 34, 32, 30, 28, 26.

Is this correct? If not, where am I going wrong?

# Answer
I don't see an algorithm in your answer. Also, I doubt that if you convert your sequence of steps into an algorithm, then it will produce the correct answer for $n=0,\ldots,5$.

From the given examples, you can see that the first number in the sequence is always $3n$, and from then on the numbers increase by $2$ each time (as you mention; but then in your "algorithm" they decrease by $2$ each time), and in total there are $2(n+1)$ of them (you can see this since the length of the sequence increases by $2$ each time).

How do we convert this into an algorithm? An algorithm is a recipe that prints the sequence for *every* value of $n$, not for the particular value $n=6$. Also, it should reproduce the given sequences for $n = 0,\ldots,5$.

Your question makes me doubt that the lecturer has explained the concept of "algorithm", so instead, try to write a function in your favorite programming languages that given $n$, prints the sequence corresponding to $n$. Code is just a formal way of presenting an algorithm.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Determining the number of iterations needed to find the number of bits in an integer
I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer.

```
4 = 100  =  3 bits
3 = 011  =  2 bits
8 = 1000 =  4 bits

```

I skimmed through this article and it says: `A positive integer n has b bits when 2^b-1 ≤ n ≤ 2^b – 1`

But when you do the math for an integer 4, you get `2.32 ~= 2`. What am I doing wrong?

# Answer
> 2 votes
The number of bits is always an integer, so you have to solve for that equation over the integers. Thus, use $\lceil \lg (n+1) \rceil$.

# Answer
> 1 votes
Some answers suggest using the logarithm of n.

Now guess what is the first thing your computer does if you try to calculate log n: It converts n from an integer to a floating point number, and from the exponent of the floating point number you get the number of bits immediately. So whatever time complexity there is, you have spent it already before even trying to calculate the logarithm. Just be converting the integer n to a floating point number.

You also don't need to calculate the logarithm, which is very time consuming, just look at the exponent field in the floating point representation.

Assuming you are given a 64 bit integer:

```
count = 1
if any bit in (n & 0xffff ffff 0000 0000) is set then count = 32 and n = (n >> 32), count = count + 32.
if any bit in (n & 0xffff 0000) is set then count = count + 16 and n = (n >> 16).
if any bit in (n & 0xff00) is set then count = count + 8 and n = (n >> 8).
if any bit in (n & 0xf0) is set then count = count + 4 and n = (n >> 4).
if any bit in (n & 0x0c) is set then count = count + 2 and n = (n >> 2).
if any bit in (n & 0x02) is set then count = count + 1.

```

For a number that is stored in 2^k bits, this takes O(k).

# Answer
> 0 votes
N is 4 and b is 3. The formula holds perfectly fine. Nothing is wrong.

The reason to "round up" in the context of the numbers you have is because of the inequality. 2 would not satisfy `x ≥ ~2.32`. But 3 would.

---
Tags: time-complexity, bit-manipulation
---


# Question
Title: How to convert a decision tree to an automaton?
From what I know,

* a problem can be transformed to a yes/no answer, which can be described by a decision tree.
* Solution to a problem also can be represented by a set of strings (a language), which means the problem can be regarded as a membership problem.
* This set of strings can also be represented by an automaton, although how it is done is still vague in my mind.

My questions are:

1. What is the relationship between a decision tree and an automaton?
2. How to convert a decision tree to an automaton?

I have tried to read some articles related to this, and somehow 'know' these concepts are related with each other, but still feel that I don't quite understand the relation and how to convert them to each other.

# Answer
> 4 votes
A decision tree is a model of computation which makes sense for instance of *constant* size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context) is a model of computation which describes a language.

The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision tree to an automaton.

Here are some examples:

* Determining whether a person is overweight given their age, gender, height, and weight. This can be solved by a decision tree, or by a table.
* Deciding whether a 64x64 image describes a dog or a cat. This can also be solved by a decision tree, though that's not recommended.
* Deciding whether a given integer is a prime. This decision problem defines a language, the language of primes. Agrawal, Kayal and Saxena gave an efficient procedure for solving this problem in 2002, which however cannot be implemented by the kind of automata usually considered in theory of computation classes (DFA, NFA, PDA).
* Deciding whether a given string is a palindrome. This decision problem defines a language, and can be solved by a pushdown automaton, but not by a DFA/NFA.

---
Tags: automata, decision-problem, decision-tree
---


# Question
Title: Master theorem: what to do with constant in parenthesis?
In analysis of algorithms, we sometimes use the (unsimplified) Master Theorem for recurrence relations.

What should be done in the case that there is a constant factor in the numerator following T?

$$ T(n) = 2T\left(\frac{5n}{8}\right) + 1 $$

Does b simply equal $\frac{5}{8}$? This seems a contradiction to the Theorem.

# Answer
> 2 votes
Usually the general form of the recurrences solved by the Master theorem is stated as: $$ T(n) = aT\left(\frac{n}{b}\right) + f(n). $$

In your recurrence you have $a=2$, $b=\frac{8}{5}$, and $f(n)=1$.

# Answer
> 1 votes
Your confusion stems from the fact that the MT is often stated in the form $$T(n) = aT(n/b) + f(n),$$ so $b$ is expected to be some constant larger than 1. The recurrence relation you give is not in this form, so to rewrite it to fit the form you know, write $T(n) = 2T(n / (8 / 5)) + 1$ and take it from there.

---
Tags: master-theorem
---


title: proof non-empty AVL tree

text:
# Question
Title: proof non-empty AVL tree
The vertex of a binary tree is called an single child if it has a father's vertex but does not have a neighbor.

The root is not considered an single child.

let mark in numOnly a number of vertices in T that hold the attribute "single son ", and ‘with n we mark the total number of vertices in the T tree.

i need to prove that every non-empty AVL tree has inequality $\frac{numOnly}{n}\leq \frac{1}{2}$

# Answer
If the tree hasn't any single-children the hypothesis trivially holds.

Given a single-child vertex $v$, we can show that the parent of this vertex $v$ cannot be a single-child. Let $p(v)$ be the parent of $v$.

If $p(v)$ is the root then $p(v)$ isn't a single-child per definition.

If $p(v)$ is not the root: Assume that $p(v)$ is a single-child then $p(p(v))$ has only one child. This implies that the difference in height of the subtrees of $p(p(v))$ must be at least $2$ which conflicts with the AVL-criterium and therefore implies that $p(v)$ is not a single-child.

Using this and the fact that for every single-child there is a unique parent, we can conclude that $2\cdot numOnly \leq n$.
> 1 votes

---
Tags: algorithms, avl-trees
---


# Question
Title: What is the complexity of k-clique problem with a predetermined vertex in the solution?
Clique (from WikiPedia):

> Clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.

K-Clique problem: Finding a clique of size K. This is NP-complete according to Wiki,

> Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

Let us consider a "constrained k-clique problem" - which is a k-clique problem with a constraint of having a predetermined vertex included in the solution. What would be the complexity of this problem? Is it a known problem in the literature?

# Answer
> 3 votes
It is still $\mathsf{NP}$-complete. Consider the following reduction from the normal $\mathrm{Clique}$ problem: Given a graph $G$ and some desired clique size $k$, add a new vertex $v^\ast$ which is connected to all vertices of $G$ to obtain a new graph $G^\ast$. Then $(G^\ast, k + 1, v^\ast)$ is a yes-instance of your modified $\mathrm{Clique}$ problem if and only if $(G, k)$ is a yes-instance of $\mathrm{Clique}$.

---
Tags: np-complete, clique
---


# Question
Title: Maximize area of light with 4 light sources on a diagram of a room
Given a diagram of a room with obstacles in it (like walls or furniture), find the 4 best places to put omnidirectional light sources in it so the area that is lighted is maximized.

Here is a simple example diagram so the problem can be better understood:

The solution I thought was to find the spot with most light and from there find the second one and so on. But something makes me think that it may exist a configuration which is better that doesn't need to be the best from the beginning, kinda feels like a special case of the knapsack problem, if so I'd think of implementing a greedy algorithm or using genetic algorithms to give an approximation of the best places.

The problem could be viewed as a particular case of "the Art gallery problem" but instead of finding the least amount of guards, you have 4 guards and you have to put them in certain places so they can observe the most area of the gallery possible.

I'd be grateful if at least someone points me in the right direction so I can do a better research, thank you very much!

# Answer
This is an optimization problem, where a function $f: \Bbb R^8 \rightarrow \Bbb R$ is defined as an area of the visibility polygon, corresponding to four points, situated inside a polygon with holes. So, your research should go in two directions:

1. Global optimization \- a branch of numerical analysis, that deals with various iterative algorithms, able to find an argument of the optimized function, giving its minimum or maximum value over all the function domain. Sometimes the global optimization problem is solved as a sequence of local optimizations (with random starting points), however in general case there are no guarantee that the optimal solution will be found by this method. Please see this paper, where authors apply the Gradient descent method to maximize the area of the region, visible to the observer in a simple polygon (without holes).
2. Visibility polygon for a point $p$ in the plane configuration with possible boundary and obstacles is the polygonal region $V(p)$ of all points of the plane *visible* from the p. You'll need to compute visibility polygons many times for different points, so it makes sense to pre-process the original polygon (together with its holes) to make this computation faster. Please see this paper, where authors do exactly that - their approach needs $O(n^3log(n))$ pre-processing time, and it allows to compute the visibility polygon with $k$ vertices in $O((1+min(h,k))log(n)+k)$ time, where $h$ is the number of holes. The visibility polygon for four points will be a **union** of four visibility polygons (and this union can have holes) - so you'll need to compute this union. Please see Boolean operation on polygons as a starting point for your research as well.

Optimization problems on real numbers are intrinsically inexact and their solutions are approximations - the question is how close your solution should be to the optimal one. The gradient descent method might be enough in your case, where the bounding polygon is simply a rectangle, and holes also have simple shape.
> 1 votes

---
Tags: time-complexity, optimization, computational-geometry, approximation, applied-theory
---


title: Natural Languages

text:
# Question
Title: Natural Languages
Can one imply that natural languages can be described by regular grammar? Is that what happens through NPL? Trying to understand the subject of how spoken language can be converted to data and how.

# Answer
> 1 votes
See this paper for an extended discussion which includes the old Chomskyan center-embedding arguments that English, for example, is not regular. See this answer for an argument that natural languages are not context-free and therefore not regular. Moreover, there is no agreement as to what a syntactic theory of natural languages would look like. The situation for semantic theories of language is even worse. So we have a long way to go.

---
Tags: regular-languages, natural-language-processing
---


# Question
Title: Find list of tickets with best price sum
I have an optimization problem, where i need to find set of tickets for certain period, such that sum of prices for these tickets is minimal.

Algo should accepts list of trips and list of tickets as input. And output list of tickets with min possible sum price with conditions that this list of tickets covers all trips.

Trip has following fields:

```
OriginZone
DestinationZone
EndOfTripTimestamp

```

Ticket object consists of these fields:

```
OriginZone
DestinationZone
MaxNumberOfTransfers  // 0 if limited by duration
MaxDuration           // 0 if limited by transfers
Price

```

It's considered that ticket covers trip if `Ticket.OriginZone` =\< `Trip.OriginZone` and `Ticket.DestinationZone` \>= `Trip.DestinationZone`. Example:

Ticket `{OriginZone: 1, DestinationZone: 4, MaxNumberOfTransfers: 1, MaxDuration: 0}` covers trip `{OriginZone: 2, DestinationZone: 3}`

`MaxNumberOfTransfers` specifies how much times this ticket can be used. If value it's value is 2, this ticket can cover 2 trips that happen between `OriginZone` and `DestinationZone`. `MaxDuration` specifies period in seconds, in which this ticket can be used from time of purchase(for example if ticket is valid for 24 hours, this field will be set to 24 * 3600). It should be considered that ticket was bought right before first trip that it's used for.

This fields are exclusive. So if `MaxDuration` field is set, than `MaxNumberOfTransfers` is not used.

Here is example, of how this algo should work:

```
> trips = [
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T15:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-16T16:00:00},
{OriginZone: 1, DestinationZone: 2, EndOfTripTimestamp: 2020-09-16T17:00:00},
{OriginZone: 3, DestinationZone: 4, EndOfTripTimestamp: 2020-09-17T18:00:00}
]
> tickets = [
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 1, MaxDuration: 0, Price: 10},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},
{OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13},
{OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
]
> algo(trips, tickets)
OUTPUT:
  {OriginZone: 1, DestinationZone: 2, MaxNumberOfTransfers 0, MaxDuration: 24 * 3600, Price: 13}
  {OriginZone: 3, DestinationZone: 4, MaxNumberOfTransfers 2, MaxDuration: 0, Price: 15},

```

To clarify this example, here you see 4 trips that happened in period of 2 days. In first day there's 3 trips overall, 2 from zone 1 to 2, and one from zone 3 to 4. And on second day there's one trip from zone 3 to 4. So algorithm picks 2 tickets to cover these trips -- 24 hour ticket for zones 1 to 2 and ticket with 2 transfers for zones 3 to 4.

Overall this looks like combinatorial optimization problem, but i wasn't able to find any non trivial algorithm for solving it. So, currently i'm using brute force algo that looks like:

```
recursive_function(trips, tickets):
    trip = trips[0]
    find best price iterating over tickets:
        price, tickets_list = recursive_function(trips[1:], tickets)

   return tickets_list with best price sum

```

So, my question is, is there any common problem that's similar to my and have non-trivial solution? Or maybe someone can recommend me some topics to look closely into.

# Answer
If you wanted to solve it in practice, I would recommend that you try using an ILP solver. You can express this as an instance of integer linear programming, then use an off-the-shelf ILP solver.

Introduce zero-or-one variables $x\_i$ (indicates whether the $i$th ticket is bought or not) and $y\_{ij}$ (indicates whether the $i$th ticket is used to cover the $j$th trip). Then you can write linear inequalities to express the requirements; e.g., $\sum\_j y\_{ij} \le d\_i x\_i$ where $d\_i$ is the max duration of ticket $i$, and so on. The total price is a linear function of the variables, so you can minimize that objective function, subject to these inequalities.

I don't know whether there is a more efficient algorithm.
> 1 votes

---
Tags: algorithms
---


# Question
Title: What roadblocks are there to HSA becoming standard, similar to floating point units becoming standard?
I remember when my dad explained to me for the first time how a certain model of computer he had came with a "math coprocessor" which made certain math operations much faster than if they were done on the main CPU without it. That feels a lot like the situation we are in with GPUs today.

If I understand correctly, when Intel introduced the x87 architecture they added instructions to x86 that would shunt the floating point operation to the x87 coprocessor if present, or run some software version of the floating operation if it wasn't. Why isn't GPU compute programming like that? As I understand it, GPU compute is explicit, you have to program for it **or** for the CPU. You decide as a programmer, it isn't up to the compiler and runtime like Float used to be.

Now that most consumers processors (Ryzen aside) across the board (including smartphone Arm chips and even consoles) are SoCs that include CPUs and GPUs on the same die with shared main memory, what is holding back the industry from adopting some standard form of addressing the GPU compute units built in to their SoCs, much like floating point operation support is now standard in every modern language/compiler?

**In short, why can't I write something like the code below and expect a *standard* compiler to decide if it should compile it linearly for a CPU, with SIMD operations like AVX or NEON, or on the GPU if it is available?** (Please forgive the terrible example, I'm no expert on what sort of code would normally go on a GPU matter, hence the question. Feel free to edit the example to be more obvious if you have an idea for better syntax.)

```
for (int i = 0; i < size; i += PLATFORM_WIDTH)
{
    // + and = are aware of PLATFORM_WIDTH and adds operand2 to PLATFORM_WIDTH
    // number of elements of operand_arr starting at index i.
    // PLATFORM_WIDTH is a number determined by the compiler or maybe
    // at runtime after determining where the code will run.
    result_arr[a] = operand_arr[i] + operand2;
}

```

I am aware of several ways to program for a GPU, including CUDA and OpenCL, that are aimed at working with dedicated GPUs that use memory separate from the CPU's memory. I'm not talking about that. I can imagine a few challenges with doing what I'm describing there due to the disconnected nature of that sort of GPU that require explicit programming. I'm referring solely to the SoCs with an integrated GPU like I described above.

I also understand that GPU compute is very different than your standard CPU compute (being massively parallel), but floating point calculations are also very different from integer calculations and they were integrated in to the CPU (and GPU...). It just feels natural for certain operations to be pushed to the GPU where possible, like Floats were pushed to the 'Math coprocessor' of yore.

So why hasn't it happened? Lack of standardization? Lack of wide industry interest? Or are SoCs with both CPUs and GPUs still too new and is it just a matter of time? (I am aware of the HSA foundation and their efforts. Are they just too new and haven't caught on yet?)

(To be fair, even SIMD doesn't seem to have reached the level of standard support in languages that Float has, so maybe a better question may be why SIMD in general hasn't reached that level of support yet, GPUs included.)

# Answer
> 1 votes
A couple issues come to mind:

### Synchronization/Communication overhead

In order to seamlessly transition from CPU to GPU code you need to communicate with the GPU. The GPU additionally has to be available(aka not rendering the screen), and all instructions on the CPU side of things need to retire/finish executing. Additionally you need to make sure that any pending writes have reached L3 cache/main memory, so that the GPU sees writes. As a result a transition to GPU code is quiet expensive, especially if the GPU is doing something latency sensitive(like rendering the next frame of something), and you need to wait for that process/task/thread/whatever to finish. Similarly returning back to the CPU is also expensive.

In addition you have to handle what happens if multiple CPU cores start fighting over the GPU.

### Differing Memory Performance Needs

GPUs typically require high bandwith memory, but low latency is not as important, while CPUs are typically more sensitive to low latency. Low performance GPUs can and do use main memory, but if you wanted a high performance GPU built into the CPU you would potentially need two different types of memory. At which point there isn't much advantage to having everything on one chip, since all that does is make cooling harder.

### Inertia/Dev Infrastructure

SIMD has compiler support right now and lots of work put into it. Simple GPU style workloads like dot products are already memory bound anyway on a CPU, so existing CPU+GPU combos would not benefit.

### Could just have lots of SIMD

Not much more to say beyond heading. SIMD+Many cores+lots of execution units would give you a more GPU like CPU. Add better SMT for a bonus. See Xeon Phi for a real world implementation of this concept. Though one thing worth mentioning is silicon spent on more GPU style features is silicon not spent on branch prediction etc.

Edit:

Another thing that comes to mind is there are broadly speaking three reasons to have a GPU.

1. Just want to browse the web, display Netflix etc. For this use case existing CPU and GPU performance/architecture is more than sufficient.
2. Want to play high end videogames etc. Existing architecture has a lot of momentum behind it, and I'm not convinced gaming CPU workloads really need better SIMD performance, and instead need better cache/branch etc, though I don't really know. However the GPU is likely already busy so it might not be the best idea to shift even more work to the CPU
3. HPC applications. Custom hardware like Xeon Phi is available for people who need a more GPU like CPU.

# Answer
> 1 votes
Floating-point units are not standardised. Your typical Intel processor has at least two very very different ones built in. The results of floating-point operations are *mostly* standardised, but not completely.

But designing a floating-point unit is absolutely trivial compared to designing a GPU. GPUs are similar in complexity to CPUs, and CPUs are in no way standardized.

---
Tags: computer-architecture, cpu
---


# Question
Title: Decidability of halting problem for DPDAs with $\epsilon$-transitions?
For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space.

But what about PDAs with $\epsilon$-transitions? Is the halting problem decidable for deterministic PDA's with $\epsilon$-transitions? Given such a DPDA $P$ and an input $x$, can we decide whether $P$ will halt on input $x$?

The stack may be infinitely large, so it seems like it might be much harder here to see if the PDA is in an infinite loop or not.

I don't think it's as easy as answered here for non-$\epsilon$ PDAs:

> \[For\] DFAs or PDAs, the halting problem is decidable: the machine always halts because it halts when it reaches the end of its input, the input is finite and the machine consumes one character of input at every step.
>
> Is the halting problem specific to Turing machines?)

The answer to my earlier question (Is a PDA's stack size linear bounded in input size?) also seems to point in a direction of a higher difficulty of proving this.

# Answer
> 2 votes
Let $L\_1$ be the language of all $(M, p, y)$ such that if we start $M$ (a DPDA with $\epsilon$ transitions) in state $p$ with a stack consisting of only $y$ (which is either a single symbol or nothing), then reading an empty string as input would cause $M$ to eventually return to state $p$, with a $y$ on top of its stack if $y$ was a symbol rather than nothing (if $y$ was originally nothing, we don't care about what's on the top of stack after $M$ returns to $p$; anything is fine).

claim: $L\_1$ is decidable.

proof: modify $M$ as follows: make a copy $p\_0$ of $p$ with the same outgoing transitions but no incoming transitions, and start the DPDA in $p\_0$ with a symbol $y$ (or empty) in its stack. If $y$ is empty, then make $p$ the only accept state. Otherwise if $y$ is a symbol, then after creating $p\_0$, modify the outgoing transition of $p$ with $y$ on the top of its stack to instantly go to a state $w$ that is now the only accept state (see note 1). Now use the standard CFL emptiness decider on this modified DPDA and we are done.

Note 1: If there is no such transition to modify due to determinism of $M$, i.e. $p$ only has one outgoing $\epsilon$ transition that either does nothing or pushes some symbol onto the stack, then do the following instead: delete the transition, add one that pops $y$ and goes to $w$ and also add trivial no-op transition that pops then immediately pushes back all other symbols that are not $y$.

Next, let $L\_2$ be the language of all $(N, q, x)$ such that if we start the DPDA $N$ in state $q$ with a stack having only a single symbol $x$ (or empty), then with an empty input string, it will run forever without ever attempting to pop an empty stack. Note Sipser calls $(q, x)$ a "looping situation".

claim: $L\_2$ is decidable (Sipser third edition problem 4.32 asks to prove this)

proof: take $N$ and delete all its input-reading transitions (leaving only $\epsilon$ transitions). Then, start $N$ in state $q$ with an $x$ on its stack, and for every state $p$ it enters, take its stack top $y$ and run the decider for $L\_1$ on $(N, p, y)$. This procedure is guaranteed to terminate in either an accept for $L\_1$ for some $p$ and $y$, or $N$ itself will terminate (either by attempting to pop an empty stack or by running out of $\epsilon$ transitions to follow). (Why? Suppose $N$ runs forever. Consider all of the pairs $(p,y)$ that it encounters at each step during execution. Since there are only finitely many states and symbols, by the pigeonhole principle, there must be some pair $(p,y)$ that is encountered infinitely often during execution; consider all the time points where we encounter $(p,y)$. Since the size of the stack cannot decrease forever, there must be some adjacent pair of such time points where the stack is larger at the second than at the first. Now consider the execution between between those two times, and find the time in that range when the stack is smallest. Let $p'$ be the state of the DPDA and $y'$ the value on the top of its stack. Then starting the DPDA at state $p'$ and just $y'$ on the stack and running forward will eventually return to state $p'$ with $y'$ on the top of the stack. Why? Well, we start $(p',y')$, then reach a point with state $p$ and $y$ on the top of the stack, then continues on to a point with state $p'$ and $y'$ on the top of the stack, and we never pop off the initial $y'$. Basically, we've decomposed the trajectory $(p,y) \leadsto (p',y') \leadsto (p,y)$ into its second part $(p',y') \leadsto (p,y)$ followed by its first part $(p,y) \leadsto (p',y')$, but with things chosen so that we can start with just the symbol $y'$ on the stack and nothing more, and it will never get popped off. It follows that $(N,p',y')$ is accepted by $L\_1$, i.e., if $N$ runs forever, it will visit a pair that is accepted by $L\_1$.)

Finally, we get to the problem in the main question: define $L\_3$ as the language of $(M, x)$ where $x$ is some input string such that the DPDA $M$ halts on input $x$.

claim: $L\_3$ is decidable.

proof: run $M$ on input $x$, and after every input symbol read, run the decider for $L\_2$ on the current state and stack top: either $M$ itself will halt or the $L\_2$ decider will return an acceptance. (Why? Suppose $M$ never halts normally. Then consider the configuration $(q,s)$ where $s$ is the shortest stack among all configurations, resolving ties arbitrarily. Since $s$ is among the shortest stacks, it will never pop below the element on top of $s$. Consequently, $(q,y)$ is accepted by the decider for $L\_2$, where $y$ is the top of $s$.)

Note 2: it's probably not necessary to run $L\_2$ decider to prove decidability of $L\_3$: we can just run the $L\_1$ decider instead.

# Answer
> 0 votes
Suppose we have a DPDA with $\epsilon$ transitions, $M$. Define a configuration of $M$ to be a pair $\langle p,s \rangle$ where $p$ is a state and $s$ is a stack; and define the silhouette of $\langle p,s \rangle$ to be the pair $(p,y)$ where $y=\textrm{top}(s)$ is the symbol at the top of the stack $s$.

Define a subroutine called SimpleLoop as follows: when provided a silhouette $(p,y)$, it checks whether, if you start in configuration $\langle p,y \rangle$ (i.e., in state $p$ and with a stack containing only $y$), running $M$ on an empty input will return to the same silhouette and in this way enter an infinite loop. This can be tested using the decider for $L\_1$ from xdavidliu's answer. Note that if SimpleLoop returns yes on a silhouette $(p,y)$, then any configuration with that silhouette will lead to an infinite loop (if we process the empty input), but the reverse does not hold.

Now to test whether $M$ halts on input $x$, we'll use the following algorithm. Simulate running $M$ on input $x$. At each configuration reached, we invoke the SimpleLoops subroutine on the current silhouette $(p,y)$; if SimpleLoops returns yes, then we terminate and output that $M$ never halts. If $M$ halts, we terminate and output that $M$ halts.

---

Now we need to prove that the above algorithm is correct. Clearly, if the algorithm terminates, its output is correct. We need to show that the algorithm will always terminate. If $M$ halts on input $x$, then the algorithm terminates, so now assume $M$ never halts on input $x$.

In this case, it must enter a non-terminating computation after consuming some prefix of $x$, say $x\_{1..k}$; the non-termination happens among the $\epsilon$-transitions after reading $x\_{1..k}$. We'll ignore everything before those $\epsilon$-transitions. Consider the sequence of silhouettes that are traversed during these $\epsilon$-transitions.

You can classify each silhouette according to whether it is traversed finitely many times (bad) or infinitely many times (call this a good silhouette). Since this is an infinite sequence, by the pigeonhole principle, there must be some point in time after which all silhouettes visited are good. So, discard the part of the sequence before that, and focus only on the sequence of silhouettes/configurations after that point in time.

Now of all configurations reached after that point that have a good silhouette, take the configuration $\langle p,s \rangle$ whose stack is shortest. Let $y$ be the symbol on the top of $s$, so its silhouette is $(p,y)$. Since the silhouette $(p,y)$ is good, i.e., is visited infinitely many times, there must be a subsequent configuration $\langle p,s' \rangle$ with the same silhouette. Moreover, the part of the execution $\langle p,s \rangle \leadsto \langle p,s' \rangle$ never pops off any element under the top of $s$ (since $s$ was one of the configurations with the shortest stack), so $s$ must have the form $y:t$ and $s'$ must have the form $y:t':t$, where $y$ is the symbol on the top of $s$ and $t$ is the rest of $s$. Consequently it follows that $\langle p,y \rangle \leadsto \langle p,y:t' \rangle$ on an empty input, and thus the SimpleLoop subroutine will return yes on the silhouette $(p,y)$.

So we have shown that if $M$ never halts on input $x$, the algorithm will eventually reach a silhouette where SimpleLoop returns yes, and the algorithm will terminate in finitely many steps. Alternatively, if $M$ halts on input $x$, the algorithm will also terminate after finitely many steps. So the algorithm always terminates, and always yields the correct answer.

---
Tags: decision-problem, pushdown-automata, halting-problem
---


# Question
Title: Paging: Does the page table of a process also gets swapped out when the process gets swapped out from main memory?
Does a process's page table too gets swapped out to secondary storage from main memory when the process gets swapped out to secondary storage from main memory? And gets swapped back in when the process is swapped in?

I tried to find the answer in text books and online, but none is clear.

Also, it would be helpful if you can tell me if the PCB (process control block) of a process also gets swapped out when the process is swapped out.

# Answer
There are two different methods: Method 1 is that the page table maps a logical address to a physical address. Since two processes use the same logical addresses (for totally different things), process B using the page table set up for process A would be fatal, so that page table needs to be swapped out. That's time consuming and painful.

Method 2 is that the page table maps a combination of logical address + an identifier for the process to a physical address. So having entries for other processes in your page table is not a problem, they will not be used, they may be swapped out at some point if the new process needs more page table address, but the transition is smooth, and there is only *one* method for changing page table entries.

With Method 2, in the not uncommon case that two processes don't actually need the whole page table, it's quite possible that the CPU can switch forth and back between these two processes without touching the page table at all.

No idea why this question has come back, but since it's here, a little addition. There are two things that you never, ever, ever swap out. One is your hard disk driver, because it's no good to you if it is somewhere on your hard disk and you can't read it because you need a hard disk driver in real accessible RAM. The other is the part of the page table that tells you were your page table is stored. If that is swapped out, then you can't read your page table.
> 0 votes

# Answer
The below article include the answer of your questions, apparently this is possible using multi level page table.

https://www.8bitavenue.com/page-table-vs-inverted-page-table/
> -1 votes

---
Tags: operating-systems, virtual-memory, process-scheduling, paging
---


title: Matrix rank only adding single row

text:
# Question
Title: Matrix rank only adding single row
I have a dense matrix and a set of rows. I would like to check if adding any single row from the set to the original matrix would make the new matrix rank deficient. Right now I am doing a full LU decomposition each time. This feels wasteful, and I have a hunch that I should be able to keep some information between iterations. Does anyone know of a way to speed this up?

# Answer
> 0 votes
I will assume the original matrix has $n-1$ rows, $n$ columns, and the rows are linearly independent (this is easy to check; and if it is not the case, then the problem is trivial).

Adding a new row $r$ will leave the matrix rank-deficient if and only if $r$ can be expressed as a linear combination of the existing $n-1$ rows. So, in a precomputation stage, use Gaussian elimination on the existing matrix. Then, it is easy to test whether any new row can be expressed as a linear combination of the existing rows. This will be much faster than doing one LR decomposition per row.

# Answer
> 1 votes
It's unnecessary to perform an LU factorization each time. Instead, you can compute a projection matrix $P$ from your dense matrix. Then, for any vector $x$ in your set, just check if $Px = x$.

In particular, suppose your original dense matrix $A^T$ has all of its rows independent (if it doesn't just delete rows until it does) and you wanted to know if adding any $x$ to the columns of $A$ would increase its rank. Then compute $P = A(A^T A)^{-1} A^T$ once. Here, $P$ projects any vector $x$ onto the column space of $A$, which is the row space of your original dense matrix $A^T$.

Alternatively, you can factor $A = QR$ using either Gram-Schmidt or Householder, in which case you would have $P = QQ^T$.

Then, for every $x$, concatenating it onto the columns of $A$ would increase its rank if and only if $Px \neq x$.

---
Tags: matrices
---


title: SGD statistical guarantee

text:
# Question
Title: SGD statistical guarantee
I have a question regard online learning with SGD. Is there a way to give a statistical guarantee that the value obtained after $n$ samples deviates at most $\epsilon$ from the real value?

Thank you guys.

# Answer
> 1 votes
No, there are no guarantees. SGD finds a local optimum but not a global optimum, and the solution it finds can be arbitrarily bad, if you have an unfriendly objective function.

The only results I've seen that provide guarantees start from strong assumptions about the objective function (e.g., convexity).

---
Tags: machine-learning, statistics, gradient-descent
---


# Question
Title: Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?
What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages?

I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and also that all the language that do have Turing machines are in $\mathsf{RE}$, so is it true that for any language that is in $\mathsf{coRE} \setminus \mathsf{R}$ there's isn't a Turing machine? I wonder why is that so, can someone elaborate?

# Answer
We can associate a language to a Turing machine in several ways.

If the Turing machine halts on all inputs, then the language *accepted* by the Turing machine consists of all words which cause the Turing machine to halt in an accepting state. The class $\mathsf{R}$ consists of all languages which are accepted by some Turing machine.

For an arbitrary Turing machine, the language *recognized* by the Turing machine consists of all words that cause the Turing machine to halt (in any state). The class $\mathsf{RE}$ consists of all languages which are recognized by some Turing machine.

If $L \in \mathsf{coRE} \setminus \mathsf{R}$, then in particular $L \notin \mathsf{R}$, and so no Turing machine accepts $L$. If $L$ were recognized by some Turing machine then $L \in \mathsf{RE}$. However, this is impossible, since then $L \in \mathsf{RE} \cap \mathsf{coRE} = \mathsf{R}$.
> 1 votes

# Answer
Let me expand on the first sentence of Yuval Filmus' answer:

> We can associate a language to a Turing machine in several ways.

Yuval mentions two: *acceptance* (which characterizes $\mathsf{R}$) and *recognition* (which characterizes $\mathsf{RE}$). There are others, however. Most obviously, we could consider "co-recognition" - say that a Turing machine $M$ "co-recognizes" a language $L$ if the strings in $L$ are exactly the strings on which $M$ does *not* halt. Then of course co-recognition characterizes $\mathsf{coRE}$.

However, that's a bit unnatural. Much more natural in my opinion is the notion of **limit computability**. Phrased in terms of natural numbers for simplicity, this is the following:

> A function $f:\mathbb{N}\rightarrow\mathbb{N}$ is **limit computable** iff there is a computable function $h:\mathbb{N}^2\rightarrow\mathbb{N}$ such that $$f(x)=\lim\_{s\rightarrow\infty} h(x,s),$$ or more precisely such that for all $x$ there is some $n$ such that for all $s\>n$ we have $h(x,s)=f(x)$.

A *set* $X$ is limit computable, meanwhile, iff there is some limit computable function $f$ such that $X=\\{i: f(i)=1\\}$. (There are many other equivalent formulations of this.)

It turns out that limit computability has a very nice alternate characterization:

> **(Shoenfield)** A function $f$ is limit computable iff it is computable relative to the halting problem $\emptyset'$.

(And via Post we get another characterization in terms of "definitional complexity.")

Of course this includes both $\mathsf{RE}$ and $\mathsf{coRE}$, and much more besides: there are sets computable relative to the halting problem which are not Turing equivalent to any set in $\mathsf{RE}$. (This is hard to prove!)

And there are even more ways to assign languages to sets; for example, we can talk about "limit recognizability" (which is to limit computability as recognizability is to acceptance), which gives us the $\Sigma^0\_2$ languages.
> 1 votes

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


title: Count subset divisible by 3

text:
# Question
Title: Count subset divisible by 3
I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is anyone kind enough to give me the right approach to solve this ?

> ***Problem:*** You are given $N$ boxes indexed from 1 to $N$. The number of boxes with 0, 1, or 2 coins is $n\_0$, $n\_1$, and $n\_2$, respectively. You take a random subset of the boxes where each subset has the same same probability to be selected. The empty set and the set itself are considered a subset.

> What is the probability that the total number of coins in a random subset is divisible by 3?

# Answer
You can use generating functions. Let me switch notations to $a = n\_1$ and $b = n\_2$, noticing that empty boxes make no difference. The generating function for the *total* number of coins is $$ \left(\frac{1+x}{2}\right)^a \left(\frac{1+x^2}{2}\right)^b, $$ that is, the coefficient of $x^m$ is the probability that the boxes contain a total of $m$ coins. The trick is now to substitute cubic roots of $3$ for $x$, using the following observation, where $\omega = e^{2\pi i/3}$: $$ \frac{1^m + \omega^m + (\omega^2)^m}{3} = \begin{cases} 1 & \text{if } 3 \mid m, \\ 0 & \text{otherwise}. \end{cases} $$ Using this, we find that the probability that you're after is $$ \frac{1}{3} + \frac{1}{3} \left(\frac{1+\omega}{2}\right)^a \left(\frac{1+\omega^2}{2}\right)^b + \frac{1}{3} \left(\frac{1+\omega^2}{2}\right)^a \left(\frac{1+\omega}{2}\right)^b. $$

---

This formula is not necessarily so helpful. Instead, we can use dynamic programming, which can be succinctly expressed using matrices. Suppose that we open the boxes one by one (each one with probability $1/2$), and keep track of the vector of probabilities of the various residues modulo $3$, a column vectors whose entries correspond to the residues $0,1,2$. An opened box with one coin affects the vector according to the matrix (multiplying the vector on the left) $$ \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}. $$ If instead we open the box with probability $1/2$, we get the average of this matrix with the identity matrix: $$ \begin{pmatrix} \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \end{pmatrix}. $$ We can analyze boxes with two coins similarly, and over all the vector of probabilities is $$ \begin{pmatrix} \tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \end{pmatrix}^a \begin{pmatrix} \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & \tfrac{1}{2} \end{pmatrix}^b \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} $$ You can get your probability by taking the first entry. The matrix expression above can be evaluated in many ways – by multiplying the vector matrix-by-matrix, using repeated squaring to compute the matrix powers, or by diagonalizing the matrices to obtain an even more rapid algorithm (which is identical to the formula obtained above using generating functions).

---

Finally, let me spell out the dynamic programming algorithm, which just implements the matrix-by-matrix approach hinted to above:

* Initially, $(p\_0,p\_1,p\_2) \gets (1,0,0)$.
* Repeat $n\_1$ times: $(p\_0,p\_1,p\_2) \gets (\frac{p\_0+p\_2}{2},\frac{p\_0+p\_1}{2},\frac{p\_1+p\_2}{2})$.
* Repeat $n\_2$ times: $(p\_0,p\_1,p\_2) \gets (\frac{p\_0+p\_1}{2},\frac{p\_1+p\_2}{2},\frac{p\_0+p\_2}{2})$.
> 2 votes

---
Tags: dynamic-programming, probability-theory
---


# Question
Title: What's the difference between Row Polymorphism and Structural Typing?
The definitions I've stumbled across seem to indicate they express the same idea. That's that the relationship between record types is determined by their fields (or properties) rather than their names. Their Wikipedia pages also seem to indicate the same idea:

> A structural type system (or property-based type system) is a major class of type system in which type compatibility and equivalence are determined by the type's actual structure or definition and not by other characteristics such as its name or place of declaration.

> In programming language type theory, row polymorphism is a kind of polymorphism that allows one to write programs that are polymorphic on record field types (also known as rows, hence row polymorphism).

Are there any differences between them?

# Answer
> 4 votes
Structural type systems don't necessarily have anything to do with records. For instance, you could have a system where:

```
data Bool = False | True
data Two = Zero | One

```

are actually the same type, because they are both types with two nullary constructors. It also doesn't necessarily tell you much about records, because even though types are determined by their structure, the two records:

```
{s : S ; t : T}
{s : S ; t : T ; u : U}

```

are not the same structure, so you could have structural typing without there being anything convenient about these two types.

Similarly, row polymorphism in isolation doesn't tell you much---just that you can quantify over rows, and probably use them with e.g. a record type parameterized by a row. But there are all sorts of variations on what you can do with rows that really specify the capabilities of the system.

Usually with structural records people at least want subtyping. That allows you to say that my second record type above is a subtype of the first, so that you can pass the latter to anything expecting the former. A typical way to do this with row polymorphism is to instead quantify over the extra fields that may be present, and use some kind of row concatenation.

So perhaps a more targeted question is what is the difference between subtyping and quantifiers. The answer to that is generally that subtyping cannot express quantified types unless the quantified variable only occurs exclusively covariantly or contravariantly. So we could say:

```
(forall a. a -> T) ~= Top -> T
(forall a. T -> a) ~= T -> Bot

```

But for a type like `forall a. a -> a`, there is no one type to pick for `a` without losing information.

This extends to systems with *just* record subtyping vs. (appropriate) row polymorphism. However, if you have a system with subtyping and quantifiers, and subtyping can apply to quantified types, then the differences might be a lot more subtle. Having both quantifiers and subtyping can get quite tricky, though (not that row polymorphism is easy to get right, either).

---
Tags: type-theory, polymorphisms
---


# Question
Title: Algorithm for maximizing the number of same-sized groups
Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the goal is that you want to maximize the number of same-sized groups.

There can be multiple correct answers, and you can add to different groups (i.e. you can add 2 to one group, 3 to another, etc.)

Examples: group sizes:\[1,1,1\], able to add 7 objects Answer: 3, every group already has the same amount

\[3,0,2,2,1\], able to add 3 objects Answer: 4, you can add 2 objs to the group with 0, and 1 obj to the last group that has 1. So you maximize the 2's.

\[5,4,1,3,4\], able to add 2 objs Answer: 3, you can either add 1 obj to the group with 3, creating 3 4's, or you can add 1 to each of the groups of 4, creating 3 5's.

I can easily solve this using brute-force (for each number 1...n, where n is the max amount able to be added, try all possible combinations of adding to current groups and adding the number of newly created ones to the original total) but I am confused as to where the algorithmic optimization is. Have a nice day, thanks!

edit: put some example code of what I've tried.

```
#include <iostream>
#include <vector>
#include <map>

int maxCountOfEqualGroupSize(const std::vector<int>& groups, int objsToAdd) {

int maxGroupCount = 0;
std::map<int,int> groupSizeToGroupCount;
for (const auto& i : groups) {
  groupSizeToGroupCount[i]++;
}

//edge case - all groups already have the same size
auto iter = groupSizeToGroupCount.begin();
int firstVal = iter->second;
bool foundDiff = false;
for (; iter != groupSizeToGroupCount.end(); ++iter) {
  if (iter->second != firstVal) {
    foundDiff = true;
    break;
  }
}

if (!foundDiff) {
  return groups.size();
}
//end edge case

//find biggest value and get that key
//Then advance that key one by one to the right
//for each iteration: start at that key, and start moving left
//filling groups in, once you run out of objs to fill with,
//terminate.
int maxKey;
for (const auto& p : groupSizeToGroupCount) {
  if (p.second > maxGroupCount) {
    maxGroupCount = p.second;
    maxKey = p.first;
  }
}

auto startIter = groupSizeToGroupCount.find(maxKey);
auto lastIter = groupSizeToGroupCount.rbegin();
auto firstIter = groupSizeToGroupCount.begin();

for (; startIter->first != lastIter->first; ++startIter) {
  int objCounter = objsToAdd;
  int runningGroupCount = startIter->second;

  auto startPoint = --startIter;
  ++startIter;
  for(auto goingLeft = startPoint;
     objCounter >= 0;
     --goingLeft) {

    int diff = startIter->first - goingLeft->first;
    int groupsToFill = goingLeft->second;
    int amountToAdd = groupsToFill * diff;
    if (amountToAdd > objCounter) {
      //add up to what we can, since we can't fill all the groups
      while (objCounter >= diff) {
        ++runningGroupCount;
        objCounter -= diff;
      }
    } else {
      objCounter -= amountToAdd;
      runningGroupCount += groupsToFill;
    }

    if (goingLeft == firstIter) {
        break;
    }
  }
  maxGroupCount = std::max(maxGroupCount, runningGroupCount);
}
return maxGroupCount;
}

int main() {
  std::vector<int> ttt = {1,1,1};
  std::vector<int> tt = {3,0,2,2,1};
  std::vector<int> t = {5,4,1,3,4};
  std::cout << maxCountOfEqualGroupSize(t, 2) << std::endl;
  std::cout << maxCountOfEqualGroupSize(tt, 3) << std::endl;
  std::cout << maxCountOfEqualGroupSize(ttt, 2) << std::endl;

}

```

# Answer
> 1 votes
Hint:

> Try working through some examples. Can you narrow down the set of possible values that might appear in the largest group in the best solution? (For instance, your second example has 2's as the value, and your third example has 4's or 5's.) Can you see how to use that to help you do better than brute force?

---
Tags: optimization
---


# Question
Title: Deadlock and cycle in a resource allocation graph
Here is a resource allocation graph asked in my Operating Systems Theory midterm. The question is, "Is there a deadlock here? Explain your answer in detail"

Ra and Rb are resource sets and every dot inside of them are resources. Circles are processes. An arrow from process to a resource set means that process is requesting a resource from that set. An arrow from resource set to process means that process owns a resource from that resource set.

I want to have your opinions on this, because the lecturer's answer is conflicting with mine. Lecturer says there is a deadlock here. But my answer was, since Py and Pz are not requesting a resource, they will simply continue their execution and terminate, releasing their resources. Then Px and Pw can obtain their requested resources and keep executing. It is obvious there is a cycle in this graph as Px-Pw but this doesn't conclude us to a deadlock. Thus I can't see a way to make "there is a deadlock here"conclusion.

So is there a deadlock here?

# Answer
> 3 votes
I did some thinking and then searching and all RAG conditions of this example leads to conclusion that there is no deadlock (altho there is a cycle here).

Beside after searching I found this where you can find this:

Which clearly stands **Graph With A Cycle But No Deadlock**

Are you sure that you have your graph correct here?

# Answer
> 0 votes
By all means, your answer is correct: judging by the RAG, Py and Pz have all resources they need to complete; so, once they finish, there will be resources available to Px and Pw finish their own tasks. Therefore, there is no deadlock. Simple like that.

Please, check this answer, provided by Neelesh Shukla.

The only possibility for your answer become wrong: the graph the lecturer referred to is NOT the one depicted here!!

# Answer
> 0 votes
there is no deadlock because there are more than one instance per resource type even though there is cycle in the graph.

# Answer
> 0 votes
Here no deadlock occurs because p2 and p4 are holding a resource. So they can release it so that p1 or p3 can acquire it to avoid deadlock

# Answer
> 0 votes
Your analysis makes sense, and there is no deadlock.

**Some basic facts about RAG:**

If the graph contains no cycles, then no deadlock

If the graph contains a cycle:

* If only one instance per resource type, then deadlock
* If several instances per resource type, there is the possibility of deadlock

Hence it is inappropriate to conclude a deadlock simply because of cycle, when resources hold mutiple instances.

---
Tags: operating-systems, concurrency, resource-allocation, deadlocks
---


# Question
Title: Sort half-edges around common vertex in 3d
I'm trying to figure out this problem for very long time and am no getting nowhere. I'm working on a simple 3d modeler that uses half-edge data structure.

Say I have non-manifold geometry where two triangles share a common vertex, as shown in the image below. And I want to add another triangle such that now three triangles share a common vertex. Once we add the new triangle we need to reorder the half-edges around the common vertex. In 2d this ordering is done by sorting the half-edges from the common vertex clockwise, as explained in this post.

However in 3d this becomes a nightmare. If the same three triangles share the common vertex but have an arbitrary orientation in 3d space and are not coplanar. How can one possibly sort the half-edges?

I experimented with using the common vertex normal to construct a plane, and project all the half-edges around the vertex to that plane. After which we could sort them clockwise relative to the plane. But I've found this approach to have a lot of issues. And now I'm all out of ideas.

# Answer
> 1 votes
It seems that the problem here is that you try to determine something similar to a rotation system from a skeleton1 embedded in $\mathbb{R}^3$. The problem here is that such a skeleton is not enough to uniquely define a rotation system, because rotation systems encode embeddings of a graph onto a surface. Without having access to a given surface as a reference, almost any rotation along a vertex is possible, and you will not be able to find the "right" one.

So what can you do? This likely depends a bit on what it is you are actually modelling. Since the rotation around a vertex is a concept that depends on a surface, to determine it you will have to decide what your surface looks like, at least locally around the vertex you're inserting a triangle in. Likely, the edges that are part of a triangle should always be consecutive in the ordering, but that doesn't give all the information.

One possible approach on how to decide where a new triangle fits into the ordering, is to look at all consecutive pairs of triangles in the existing ordering, and insert the new triangle in between the pair with smallest distance to the new triangle. (Note that you have to store the ordering around the vertex explicitly, you cannot compute this on the fly)

More precisely, to determine where to place a new triangle incident to vertex $v$ in the ordering around $v$, consider all pairs of consecutive edges $(e\_i,e\_{i+1})$ that do *not* form a triangle with vertices $(a,b)$ being their endpoints not equal to $v$. Let $(x,y)$ be the new vertices of the triangle. Place the edges of the new triangle in between the pair of edges $(e\_i,e\_{i+1})$ such that $\min(\\|a-x\\|+\\|b-y\\|, \\|a-y\\|+\\|b-x\\|)$ (or another similarity measure of the pairs $(x,y)$ and $(a,b)$) is minimized.

For example, in the figure below, vertices with the same colors are the pairs we'd compare with our new vertices $x,y$.

---

1: I will assume that you just have a graph for now, but perhaps a simplicial complex might be a better description? I don't think it matters much for the discussion here, though.

---
Tags: computational-geometry, doubly-connected-edge-list
---


# Question
Title: "what does the 1 to 10 mean?" FOR number ← 1 TO 10
"what does the to 10 mean?" FOR number ← 1 TO 10

# Answer
> 0 votes
In Python, this is typically written

```
for number in range(1, 10):  # or range(1, 11) depending on interpretation
    pass  # do stuff here

```

where `pass` is replaced with the block you want to execute.

Note that I wrote `range(1,10)` which gives

```
number = 1, 2, 3, 4, 5, 6, 7, 8, 9

```

in turn, i.e. the endpoint (10) is *exclusive*. It could mean that the `1 TO 10` should be interpreted *inclusive*, i.e.

```
number = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

```

but out of context, this is difficult to say.

In C-like languages, this often looks like

```
for (int i = 0; i < 10; i++) {
    // do stuff here
}

```

Again, maybe the `i < 10` should be `i <= 10`.

The syntax in the exercise looks a lot like Pascal, which uses

```
begin
   for number := 1 to 10 do
   begin
      // do stuff here
   end;
end.

```

which I believe is *inclusive*.

---
Tags: algorithms, loops
---


title: Is a file a string of zeros and ones?

text:
# Question
Title: Is a file a string of zeros and ones?
Is a computer file just a string of zeroes and ones? If so, can it start with zeroes?

I have not been able to find an answer, surprisingly.

# Answer
> 1 votes
Yes the File has a binary representation and it can start with a leading zero.

To verify this open any file from your computer with an hex editor and modify the leading hex to 00.

You would most likely be unable to open the file, because you damage the signature but it still can be considered a valid file.

# Answer
> 0 votes
The most common type of file is a *binary file*, which is composed of:

* A stream of bytes, which can be completely arbitrary.
* Metadata: name, length, owners, permissions, relevant dates, and so on.

This is the "view" of the file from the outside. From the inside, the file will also be associated with locations on disk. Furthermore, if the filesystem is journaled, recent changes to the file will also be stored.

---
Tags: binary, filesystems, philosophy
---


# Question
Title: Minimize range of distances between two sets of points
I have two sets of `n` points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets `A` and `B` such that the *range of distances* between the points is the smallest.

For example, consider $n=3$, $A\_1 = (0,0)$, $A\_2 = (1,0)$, $A\_3 = (3,0)$, $B\_1 = (1,1)$, $B\_2 = (3,2)$, $B\_3 = (-1,0)$. The best pairing will is $A\_1 \text{ and } B\_1$, $A\_2 \text{ and } B\_3$, $A\_3 \text{ and } B\_2$, because the distances are $(\sqrt{2}, 2, 2)$, giving the smallest range of $2 - \sqrt2$.

Ideally, I am looking for a solution which is able to solve the problem quickly (\<5 seconds) for $n=300$.

The naive solution of trying all `n!` permutations is clearly too slow. I also thought about finding all `n^2` combinations of distances, sorting them, and then removing the extremes until no possible pairing exists, but I don't know how to determine whether removing one possible connection will make it so no pairing exists.

# Answer
> 4 votes
Here is a simple algorithm to get you started.

Compute all $\binom{n}{2}$ pairwise distances, and put them in an array $A$. For each pair $a\<b$ in $A$, use a bipartite matching algorithm to determine whether there is a matching that uses only distances in the range $\[a,b\]$. Choose the pair minimizing $b-a$. In total, there are $O(n^4)$ invocations of the matching algorithm.

It is easy to improve upon this. For example, for each $a$ we can find the best $b$ using binary search (this is essentially bottleneck matching), dropping the number of invocations down to $O(n^2\log n)$. You can improve this further (in practice) as follows:

* Let $a$ be the minimal element in $A$.
* Find the minimal $b$ such that an $\[a,b\]$-matching exists.
* Decrement $b$, and find the maximal $a$ such that an $\[a,b\]$-matching exists.
* Increment $a$, and find the minimal $b$ such that an $\[a,b\]$-matching exists.
* And so on, until no more matchings are possible.

Here an $\[a,b\]$-matching is one only using weights in $\[a,b\]$, and "increment/decrement" are relative to $A$.

You can probably improve this even further, even in this oblivious setting where we do not use the fact that the distances originate from a planar embedding of the points.

---
Tags: algorithms, bipartite-matching
---


# Question
Title: Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states
In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It is then stated that using the pumping lemma, it can be shown that if 01(001)^n01 is accepted for n=0,1,2,3,4,5 then all strings of the form 01(001)\*01 must also be accepted.

I know of the pumping lemma but do not see how the next leap has been made. Why is it sufficient to only test n up (number of states) - 1?

# Answer
Let the automaton have states $Q$, initial state $q\_0$, accepting states $F$, and transition function $\delta$, and suppose that $|Q| = n$. Denote the language that it accepts by $L$.

Suppose that $xy^iz \in L$ for $i = 0,\ldots,n-1$. Denote $p\_i = \delta(q\_0,xy^i)$. We consider two cases:

* The states $p\_0,\ldots,p\_{n-1}$ are all different. In this case, $Q = \\{p\_0,\ldots,p\_{n-1}\\}$, and so $\delta(q,z) \in F$ for all $q \in Q$, implying that $\delta(q\_0,xy^iz) \in F$ for all $i$, and so $xy^iz \in L$ for all $i$.
* For some $j \< k$, we have $p\_j = p\_k$. It follows that the sequence $p\_i$ is eventually periodic, and so again $xy^iz \in L$ for all $i$.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Converting Decimal Numbers between 0 and 1 to Binary
I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater than or equal to 1), to convert a decimal to binary, the results turn strange likely due to floating point imprecision.

For example, the following is a result you might find when applying the algorithm:

The number 0.531904 multiplied by 2 and then subtracted by 1 should result in 0.063708 instead of what is highlighted. Successive instances of this cause the error to eventually propagate to a much greater margin after more iterations.

**Thus, I have made 3 observations:**

1. For a decimal between 0 and 1 with "N" places after the point, multiplying it by 2 should never make it more than "N" places. (e.g. multiplying 0.022, where N=3, by any power of 2 should never give it a fourth place etc.)
2. For a decimal number between 0 and 1 with "N" decimal places beyond the dot. (e.g. 0.022 has N=3 and 0.0101 has N=4) if the binary representation is repeating, then the repeating portion should be no longer than 10^N digits.
3. For a decimal number between 0 and 1 with the last (rightmost) digit being {1,2,3,4, ,6,7,8,9} it will always have a repeating representation in binary. It will only not have a repeating representation if the last digit is 5.

**My Questions are as follows:**

1. Are these observations true?
2. If so, is rounding the number to "N" decimal places at every iteration step an appropriate way to fix the problem of precision?
3. Can someone confirm the result I obtained that 0.002992 has a repeating portion that is 12500 digits long?

# Answer
> 1 votes
You are not doing arithmetic on arbitrary infinitely precise numbers. You are doing arithmetic on the subset of number representable in your computer's native floating point format. Moreover, the values you see printed out are not infinitely precise representations of the actual values encoded in the computer. They are decimal numbers (of a maximum precision) which approximate the internal value. This makes it a little difficult to see what's really going on. At the very least, it is confusing.

Although some programming languages (and even some computers) natively support decimal arithmetic, most of the time the internal representations you will be working with are fixed-precision binary representation. By fixed precision, I mean that the number represented is a fraction $n/2^i$ where $i$ is an integer in a limited range and $n \< 2^p$ for some fixed $p$, the precision. Typical CPUs have settled on a precision of 53 bits, so $n \< 2^{53}$.

When you supply $.002992$ -- that is, $2992/10^6$ -- the programming language needs to find an internally representable number that is as close as possible to that value in order to minimise calculation errors. At least on my machine, the value selected is $1724770570891843/2^{59}$. That number is extremely close to $2992/10^6$ -- so close that if you round it off at the 18th decimal point you will still see $0.002992$ -- but it's not equal. So your calculation starts with a small inaccuracy.

However, if you just run your algorithm (multiply by 2; subtract 1 if the result is not less than 1), you will not increase the inaccuracy. Multiplying by 2 is exact (unless you exceed the exponent limits), since it only requires changing the exponent to the next integer. And 1 can be represented exactly. In fact, every integer up to $2^{53}$ can be represented exactly, as well as quite a few other integers (but not $2^{53}+1$). So your algorithm will reveal the binary representation of the number actually being used by your computer instead of $0.002992$. That number has no more than 53 binary digits of precision, but it is slightly longer than 53 binary digits because of the 9 leading 0s (in binary). There is no repeating part at all.

Trying to "correct" this computation by introducing additional round-off errors at each step is not going to help.

If you want to find the exact binary representation of $0.002992$, you can use integer arithmetic to work with successive rational numbers. Start with $2992/1000000$ and repeatedly double the numerator and, if necessary, subtract the denominator \[Note 1\]. (You don't need any extended precision for that. If you start with $0 \le n \lt d$, then $n$ will never exceed $2d$. In the case of $2992/1000000$, that's well within the range of a normal 32-bit integer.)

That will indeed show that the repeating fraction has a period of 12500. It's straightforward to show that the period of the repeating fraction of $n/d$ is less than $d$ in any base. The above algorithm only depends on the value of $n$ and never changes the value of $d$, so the second time you hit a particular value for $n$, your output will start repeating. The period must be less than $d$ because if $n$ is 0, you have an exact fraction, and there are only $d-1$ other possible values of $n$, so it must repeat before $d$ steps.

---

### Notes:

1. Base 2 makes this particularly easy. If you want to do the computation for a base other than 2, you'll need to do the following

```
 n = n * b          # Note: n < d
 f = floor(n / d)   # Thus: f < b
 Output f as the next digit
 n = n - d * f      # Or: n = n mod d

```

The simpler base 2 case is just what happens if you plug $b=2$ into the above calculation.

---
Tags: algorithms, floating-point, binary, rounding
---


# Question
Title: Bipartite maximum matching with added constraints
Suppose you have two lists as follows

List $A$ = $(a\_1, a\_2, ..., a\_m)$

List $B$ = $(b\_1, b\_2, ..., b\_n)$

Each element in list $A$ can be paired with many or no elements in list $B$. I have a function $f(a\_i, b\_j)$ that returns true or false depending on whether the match is valid or not. However, if you pair element $i$ in list $A$ then you also have to pair the $i$-th element in list $B$. So, for example, the pair can be $(a\_i, b\_2)$ and $(a\_1, b\_i)$ or even $(a\_i, b\_i)$.

I want to find the maximum number of pairings between the two lists with the added constraint of if the $i$-th element of list $A$ is paired, then the $i$-th element of list $B$ must also be paired.

---

My intuition says that modifying the maximal matching bipartite algorithm might be useful for this. However, I am stuck in actually figuring out how to do this. Any help would be appreciated.

# Answer
> 1 votes
Let me start by modifying the problem statement to use standard graph theory terminology, according to my interpretation of the original post:

> Let $G=(V, E)$ be a bipartite graph, with $V= A \cup B$, with $A=\\{a\_i\\}\_{1\leq i \leq m}$, with $B=\\{b\_j\\}\_{1 \leq j \leq n}$, and with $E \subseteq A \times B$. For an edge set $S \subseteq E$, let $f(A, S)$ denote the set of integers $i$ such that $(a\_i, b\_k) \in S$ for some $k$, and let $g(B, S)$ denote the set of integers $j$ such that $(a\_k, b\_j)\in S$ for some $k$. Find a maximal edge set $S^\*\subseteq E$ with the property that $f(A, S^\*)\subseteq g(A, S^\*)$.

Assuming that this interpretation is correct, this algorithm should work:

Initialize $S = E$. Construct $m$ lists $A\_1, A\_2, \ldots A\_m$, where $A\_i = \\{j \ |\ (a\_i, b\_j) \in S\\}$, and construct $n$ lists $B\_1, B\_2, \ldots B\_n$, where $B\_j = \\{i \ |\ (a\_i, b\_j) \in S\\}$. Compute $f(A, S)$ and $g(B, S)$, and take some $c \in f(A, S) - g(B, S)$. Remove all edges of $S$ of the form $(a\_c, b\_k)$, and update $\\{A\_i\\}, \\{B\_j\\}, f(A,S)$, and $g(B, S)$ accordingly. Repeat until $f(A, S) - g(B, S)$ is empty.

It is easy to see that the resultant $S$ is maximal, as every edge removed was necessary. It is also easy to see that the running time is $O(\lvert V \rvert+\lvert E \rvert)$, as each edge is processed $O(1)$ times.

---
Tags: algorithms, graphs, bipartite-matching, vertex-cover
---


# Question
Title: Why can't we say that a Neural Network is a NP problem solver?
From this video lecture from MIT https://youtu.be/moPtwq\_cVH8?t=1229 there is mention how NP complexity works with finding a "lucky" algorithm and luck can never be accounted for. The example he draws on is just seeking the next yes till you find some final output. For those reasons, I had assumed that even SGD is NP complex, and by extension Neural Networks. And my logic was that, through readings it seems like a Back Prop algorithm is always looking for a way to reach towards the global minima by taking the most negative step.

However, from my reading, it seems like Neural Networks have a computational Complexity of P. And as a result of the fact that most people believe $P\neq NP$ then a NN can only take a guess/approximation at a solution.

From what I follow, the belief is that since a Neural Network can't promise an ideal result, it isn't an NP solver. But that confuses me since from what I have seen, a Neural Network just never gives that ideal solution. Does that mean all these problems are just more complex than P and so they can only make a different guess every time? While an NP solution is supposed to consistently give back the correct answer.

From linear Algebra, we know that a solution needs to be a repeatable, deterministic mapping from $X\to Y$ Or else it is a mere approximation function and $X$ is not in the domain of the transformation.

To me that means either my understanding of what a Neural Network does in its backpropagation is wrong. Or that my understanding of NP complexity is wrong.

# Answer
> 29 votes
SGD is an algorithm, not a problem. It is not NP-complete or NP-hard. SGD is one approach to an optimization problem. Some optimization problems are NP-hard; some are not.

All of your deductions start from that one incorrect assumption, so they don't actually follow.

"Neural Networks" don't have a computational complexity; they aren't a problem.

# Answer
> 11 votes
Let me start by briefly reviewing the kind of problems under discussion:

* Problems in P: These are decision problems (where the answer is Yes or No), optimization problems (where the answer is an optimal solution to a problem such as minimum spanning tree), or function problems (compute some function of the input) which can be solved efficiently (in a certain exact sense) on *all* instances.
* Problems in NP: You should not be troubled with the definition of these. Let me just suggest that you ignore the remarks on the MIT video. If you want to know what NP problems are, pick up a textbook on complexity theory.
* NP-complete problems: The hardest problems in NP. For example, deciding whether a graph is Hamiltonian (contains a cycle visiting each vertex exactly once). Another example, finding a TSP tour of minimum cost. Most researchers conjecture that NP-complete problems cannot be solved efficiently on all instances, and so do not belong to P. There is a vast collection of NP-complete problems, and it is known that if one of them can be solved efficiently, then all of them can.
* Learning problems: Let me describe the simplest setting, two class supervised learning, with an example. An algorithm is given a collection of pictures of cats and dogs, each one annotated by one of these two classes. The goal is to construct a "learner" algorithm, which will later on be able to classify new cats and dogs with a small probability of failure.

Neural networks are a certain kind of learner that can be constructed by a learning algorithm. Nowadays, most of these learning algorithms employ stochastic gradient descent, which involves backpropagation. Some neural networks accept inputs of a fixed size, others (for example, RNNs) accept an input stream.

As you can see, neural networks do not really fit into the P vs NP framework. They solve a "learning problem" rather than a decision problem or an optimization problem. People have tried solving NP-complete problems using neural networks, with some success, but this has no bearing on the P vs NP issue, for several reasons:

* The neural networks involved have a fixed input size. Perhaps it all breaks down for larger input sizes.
* The neural networks make mistakes, whereas P vs NP is about efficient algorithms that solve *all* instances of NP-complete problems.

In fact, it is already known that some NP-complete problems are feasible on real-world instances (check, for example, the areas of SAT solving and Integer programming).

---

If you want to understand these issues more (and to avoid stating claims such as "SGD is NP-complete", which do not make much sense), you would have to roll up your sleeves and get more technical. The MIT lecturer is painting a nice picture when they are discussing "luck", and people who are already familiar with NP might be able to understand how this corresponds to the actual definition of NP, but for anybody else, such descriptions are at best misleading.

Stochastic gradient descent (which is implemented efficiently via backpropagation) is a variant of gradient descent, which is a standard algorithm in continuous optimization. The corresponding algorithmic technique in combinatorial optimization is the *greedy heuristic*, which demonstrably fails on many NP-complete problems (though in some cases, results in the best worst-case approximation ratios).

Despite the mental picture suggested by the MIT video, stochastic gradient descent is not a universal solver for NP problems. In order to understand why, I will have to explain a bit more about NP problems, using examples:

* NP decision problems: Consider the problem of deciding whether a graph contains a Hamiltonian cycle. Given just a graph, it might be hard to find such a cycle. But given a graph and a Hamiltonian cycle, it is easy to verify that the graph is indeed Hamiltonian (by checking that it contains the given cycle). It is conjectured that no such "witness" exists for non-Hamiltonicity.
* NP optimization problems: Consider TSP, which is the analog of Hamiltonicity for weighted graphs: the goal now is to find a Hamiltonian cycle with smallest total weight. We can verify that the optimal cost is at most $W$ given a Hamiltonian cycle of total weight at most $W$. This is what it means for this optimization problem to be in NP.

Stochastic gradient descent is a continuous optimization algorithm which attempts (in this case) to find weights for the neural networks which minimize the number of errors that the network makes on the test instances. In many cases, there is also a regularization factor which pushes the weights down. Minimizing this cost function is NP-complete in general, but much of machine learning involves avoiding this worst case by "changing the problem" until it becomes feasible.

From the perspective of learning theory, more is happening here. We are interested not only in the *training error* (the error on training instances), but also in the *generalization error* (the error on new instances). Stochastic gradient descent continues minimizing the generalization error even after it has minimized the empirical error – it is not completely understood why (though many researchers have come up with partial explanations, often rejected by other researchers).

Getting back to the issue of stochastic gradient descent as a universal algorithm, one can view stochastic gradient descent as solving an NP-complete optimization problem. But there are several issues with this:

* The optimization angle is only part of the picture. Generalization is as important.
* Stochastic gradient descent doesn't always succeed. It doesn't solve all instances of the optimization problem it sets out to solve (minimize the training error).

There are other "universal algorithms" which appear to solve many NP-complete problems en masse, namely the ones used for SAT solving (and now, QBF solving) and integer programming. In these cases, it is easy to come up with explicit instances which are *provably* hard for all such algorithms. The case of stochastic gradient descent is more complicated due to the issues mentioned above, but it is also no panacea.

---

Finally, you mention that neural networks have a complexity of P. This is certainly true in some senses. For example:

* Evaluating a neural network is in P. However, finding good weights seems to be hard. Similarly, finding a Hamiltonian cycle is difficult, but verifying that a given cycle is Hamiltonian is easy.
* Running one step of stochastic gradient descent is in P (modulo the stochastic part!). However, we might have to run many steps of stochastic gradient descent, making the entire training process inefficient.

As you can see, this has no bearing on the capabilities of neural networks.

# Answer
> 5 votes
Non-linear optimization in general is not in NP, it isn't solvable at all. You cannot check in polynomial time whether a solution is the global optimum or just a local one. There is, in fact, no way to tell if your optimum is global, other than finding all of them (How would that work, how do you know how many optimums there should be, and what do you do if no global optimum exists, just infinitely many local ones?)

Backpropagation, SGD and any other optimization algorithm can't promise that they **actually** have found the global optimum. They can only promise a local optimum.

By the way: What problems a NN can solve (after it is trained) is independent on how its parameters were learned. If we look at a specific NN, we could say computing the output from the input is in O(1) because there are a fixed set of calculations that is done for any input. But that only makes moderate sense because the input size is also fixed for a specific NN.

# Answer
> 4 votes
Neural networks work reasonably well solving some kinds of problems. They are also awfully bad at solving other problems that they are used for.

Neural networks are totally incapable of solving NP complete problems beyond cases that can be solved by brute force, and not very good at this. There are optimisation problems where finding a good solution is possible even though finding an optimal solution is NP-complete, that’s the only area where neural networks *might* help.

The strength of neural networks is to detect patterns, especially small patterns. Now take a problem like “divide a set of integers into two subsets whose sums are equal or as close together as possible”. There are no patterns. If you change one number in a set, the other numbers change completely. There’s no pattern.

# Answer
> 4 votes
I think it is worthwhile to expand upon the “lucky guess” in reference to NP problems. That is a reference to the fact that NP problems are easy to verify. Instead of the typical factoring primes, let’s go with with a more down to earth problem. Say the year is 1970 and you want to know if there is a company that has 2 employees, one named Bob, one named Alice, who do not work in the same department, but both work primarily with numbers and they do know each other’s work phone number’s. How do you solve this problem quickly and easily? Today, you might be able to solve this problem through scanning online profiles, but in 1970 it would be different. It might be impossible to solve if the answer is no, but if the answer is yes, and you know the answer, it is trivial to verify, especially if the answer includes their numbers (simply pick up the phone, make two phone calls, done).

Now, if you were the “lucky guesser”, you could solve that problem nearly as quickly as you could verify it, you’d pick up the phone and call a company, and ask to speak to the operator, you’d ask for the number of Alice, they say they are a big company and have 150 Alice’s, which one do you want, and you’d say you’d like the number of Alice N, and they give you a number, you then ask for Bob, get told there are 163 Bob’s, you ask for and get Bob P’s number. One conference call later and you’re done.

A neural net may be able to solve your NP problem through brute force, it might be able to identify factors that dramatically reduce the search space so that the problem is smaller than you first thought. **But it’s not going to be a lucky guesser**, and it is unlikely to come up with step by step instructions that would allow you to solve the problem as quickly as the lucky guesser.

Neural nets frequently come up with precise answers, but they don’t do so by developing new algorithms. Which is what you’d need to do for P=NP.

# Answer
> 2 votes
It seems like the OP is asking "what class of problems can be solved by a neural network"? It turns out that we have an answer.

First, realize that neural networks are "function approximators". In other words, a neural network is itself a function $\hat{f}$, which has been "trained" to mimic some function $f$ that we have sampled. The set of samples is the "training set", and an optimizer like SGD is used to minimize the "distance" between $f$ and $\hat{f}$ over the training set. The hope is that the learned function $\hat{f}$ will **generalize**. I.e. we hope that $f\approx \hat{f}$ outside of the training set as well.

Thus, when we ask about the "kinds of problems" which can be solved by neural networks, we really mean "which functions can they approximate?" Can neural networks be used to approximate any function? If not, what class of functions can neural networks approximate?

The answer to this question is given in the paper Multilayer Feedforward Neural Networks are Universal Approximators. The paper

> rigorously establishes that standard multilayer feedforward networks with as few as one hidden layer using arbitrary squashing functions are capable of approximating **any Borel measurable function from one finite dimensional space to another** to any desired degree of accuracy, provided sufficiently many hidden units are available.

A precise definition of a "Borel measurable function" is given here. A more thorough discussion will be given in any text on Measure Theory.

This type of result is an known as a Universal Approximation Theorem. For another example, see here.

# Answer
> 0 votes
The other answers are correct, but to maybe add an intuitive perspective, you could imagine a neural network like a human brain, in terms of NP problem solving capabilities.

Both humans and neural networks are capable of "solving" hard problems "efficiently". One distinction I want to make to what has been previously discussed here is what constitutes "solving" with a neural network. I would say that optimizing the network parameters (backprop, SGD) is more similar to coming up with an algorithm to solve a problem, and the actual solving happens at inference time, not during training.

Humans have the advantage of using heuristics to come up with solutions, as do neural networks. For instance if we take some modern multiplayer game (many games are NP hard), we could observe that neural networks and humans are better at playing the game than a computer with a classical algorithm is. You can see that bots (computer controlled players), following a classical handcrafted algorithm, are worse than any decent player. For some of these games, such as DotA 2 or StarCraft II, we even have neural networks that easily beat any bot as well. In other words, a neural network algorithm is superior to a classical algorithm. Perhaps so much so that it is in a lower class than NP?

The answer has to be no, to maintain $P\neq NP$, but why? If we vaguely equivalate "solving" an NP hard problem as winning such a game, then the network is indeed very "fast", even in terms of computational complexity. However, in this view, winning a game is perhaps more similar to making a lucky guess, but not actually solving the problem. Solving the problem would mean you could theoretically make statements such as: *Given the starting parameters of both teams in the game (e.g. heroes, items, skills), who wins, if everyone plays perfectly?* Or even for any particular state of the game, you could tell who will win with perfect play. Having such knowledge by the way would trivially make you an extremely good player (only being limited by things like dexterity).

A neural network may be a fast NP solver in the sense that it is a fast algorithm, but within its complexity class, that is larger than polynomial. Even for problems that are NP hard, we sometimes do have to come up with fast algorithms to solve them, even when we know there is no polynomial complexity algorithm for that. I would say neural networks have a place in this area, however it would be really hard to prove that they actually solve the problem, even when we have a lot of experimental evidence that they understand/capture the problem well. So in that sense, you could call them "solvers", for which we cannot actually prove (yet) that they do solve the problems. But that might be an acceptable trade-off to make, in face of a problem where computation time does not allow for traditional algorithms to succeed.

---
Tags: complexity-theory, np-complete, neural-networks
---


# Question
Title: Is automaton not practical in real coding?
This question relates with this question and answer.

May I know why "Writing a structured program for any tangle of an automaton is possible in principle, but probably not worth the hassle (translating arbitrary transfers of control into a nice structure -- for some non-trivial value of "nice" -- is a lot of work, and making sure both check out even more so)" and why "it's rarely done in practice"?

Does that mean automaton is not useful in practice (real coding)? In terms of translating the automaton into a code. If not useful, then what is used in practice? Is automaton still useful in problem solving though?

# Answer
> 1 votes
While solving common programming tasks it's usually not helpful to think of an automaton. But there are still many cases where they are applied:

* writing small parsers (e.g. parse an integer/float); in order to not forget edge cases drawing an automaton is really helpful; for more complicated parsers grammars are usually a better tool
* state machines are often encountered in game programming (e.g. to manage which animation is currently executing; e.g. press the UP key switches the animation state machine in walking up mode; or to manage game states like if are you currently in-game or in the main menu)
* important (string) algos such as the KMP string matching algorithm use an automaton in the background but it's usually represented as a table and quite hard to wrap your mind around

Automatons are models that are theoretically useful to prove properties of language classes. To make proves as simple as possible their definition is also kept simple. In day to day code you usually stitch together powerful high level data structures to solve your problems and don't think on the low level of e.g. a Turing Machine that would manipulate input on the bit level but rather in terms of higher data types such as ints and lists.

P.S. Automatons are very useful for designing circuits, since circuits work on the bit level and you usually try to minimize the components used it's useful to note down which states your circuit needs and how it should transition between them given some small binary input.

---
Tags: automata
---


# Question
Title: Knapsack Problem with Constraints on Item Values
Given $n$ items with weights $w\_1,...,w\_n$ and values $v\_1,...,v\_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight limit). Now, a new constraint is, once an item with value $v\_i$ is taken, all items whose value is greater than $v\_i$ must also be taken. (It is okay to assume that all $v\_i$'s are different)

My purpose is to achieve this in $O(n)$ time, and here is my attempt (suppose the input is an array $A$ of tuples $(w\_i, v\_i)$):

> 1. Calculate total weight of the items: $W\_{\mathrm{total}}\gets \sum\_{i=1}^n w\_i$;
> 2. while $(W\_{\mathrm{total}} \> W)$ do:
>
> 2.1 $p\gets$ median of values in $A$;
>
> 2.2 $R\gets$ items whose value is greater than $p$;
>
> 2.3 $L\gets A\setminus R$; (items whose value is smaller than $p$)
>
> 2.4 $W\_R\gets$ $\sum\_{A\[i\]\in R}w\_i$;
>
> 2.5 $W\_{\mathrm{total}}\gets W\_R$;
>
> 2.6 $A\gets R$;
> 3. $W\gets W- W\_{\mathrm{total}}$; (the remaining capacity)
> 4. Repeat step 2 for the array $L$, generating the array $L'$;
> 5. Return $L'\cup A$;

Notice that the algorithm for finding the median costs linear time.

I presume that my algorithm costs $O(n)$ time since, for every iteration in each while loop, the input size halves--but I am not 100% confident of that. So does this algorithm really cost linear time? If not, what amendments can be made, or is there a general idea for designing such an algorithm that costs linear time? Any help will be much appreciated! :)

# Answer
> 0 votes
Yes your algorithm runs in $O(n)$ time if you use the median of medians algorithm. You can prove that to yourself by looking at your algorithm and noting that in every loop the size of the array we are considering is cut in halve. And the runtime of the loop body is $O(n)$ (if we use median of medians and array copying/filtering is $O(n)$ anyway). Now we get the following sum:

$$\sum\_{i=0}^{\log(n)} \frac{n}{2^i} \leq \sum\_{i=0}^{\infty} \frac{n}{2^i} = n\cdot\sum\_{i=0}^{\infty} \frac{1}{2^i} = 2n \in O(n)$$

The $\log(n)$ comes from the fact that you can only divide the array size $log(n)$ times in halves until you arrive at $1$ (because $2^{\log(n)} = n$). Every term of the sum expresses the cost of one execution of the loop body.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, knapsack-problems
---


# Question
Title: If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$?
Suppose the following is true for some f(n) and g(n): $f(n) = \Theta(g(n))$

Does that mean $f(n/k) = \Theta(g(n))$ for any value of $k\>0$?

I know that for the above to be true, there must exist positive constants $c\_1$, $c\_2$, $n\_0$ such that for all $n \geq n\_0, $ $c\_1(g(n)) \leq f(n) \leq c\_2(g(n))$. Thus if $f(n) = \Theta(g(n))$, then can I assume:

$\frac{1}{k}c\_1(g(n)) \leq f(n/k) \leq \frac{1}{k}c\_2(g(n))$ to satisfy big Theta?

My apologies if this is totally obvious or if I'm completely on the wrong track, my math background isn't the strongest. Are there any relevant properties that might describe this relationship?

# Answer
Take $f(n) = n^4$. For this function, if you double the argument, the result is multiplied by 16, that is by a constant factor. Now take $g(n) = 2^n$. For this function, if you double the argument, the result is squared, and since $2^n$ can grow arbitrarily large, there is no limit to the growth factor achieved by squaring g(n).

That’s the difference. If the growth from doubling the argument has an upper limit then $\Theta$ stays the some, otherwise it doesn’t.
> 1 votes

# Answer
Suppose $f(n) = 2^n$. Then $f(n / 2) = 2^{n / 2} = \sqrt{2^n}$ and setting e.g. $g(n) = 2^n$ as well shows $f(n) \in \Theta(g(n))$ but $f(n / 2) \notin \Theta(g(n))$, so this does not hold in general.
> 1 votes

# Answer
For given $f(n)$, well defined, for $\forall n\in \mathbb{N}$, the function $f(n/x)$ can be even undefined: for example $f(n)=\frac{1}{n-\frac{1}{2}}$ and $x=2$.

More sophisticated example is $$ f(n)=\begin{cases} 2^k, & n=2k+1 \\ k, & n=2k \end{cases} $$ Obviously $f(2n) \in \Theta(n)$, but $f(n)\notin \Theta(n)$.

Case, where your sentence is true is, for example, homogeneous function with homogeneous degree $k=1$ i.e. when $g(Cx)=Cg(x)$ and we consider homogeneous functions subset from $\Theta(g)$.
> 0 votes

---
Tags: complexity-theory, asymptotics
---


title: AEP with a Twist!

text:
# Question
Title: AEP with a Twist!
We know by AEP that if random variables $X\_1,X\_2,...$ are i.i.d. drawn from $P\_X$ then the probability of the vectors in the weak typical set $$A\_{\epsilon}^n = \\{\vec x \in \mathcal{X}^n: |\frac{-1}{n}\log P(\vec x) - H(P\_X)| \leq \epsilon \\}$$ tends to 1.
I am working on a slightly different problem. Random variables $X\_1,X\_2,...$ are independently drawn from $P^1\_X,P^2\_X,..,P^n\_X$ respectively. Let use denote $\tilde P\_X = \frac{1}{n} \sum\_{i=1}^n P^i\_X$ (ie, the average of the distributions). Is it true that the sum of the vectors contained in the set $B\_{\epsilon}^n$ would have a very high probability? $$B\_{\epsilon}^n = \\{\vec x \in \mathcal{X}^n: |\frac{-1}{n}\log P(\vec x) - H(\tilde P\_X)| \leq \epsilon \\}$$

$$ = \\{\vec x \in \mathcal{X}^n: |\frac{-1}{n}\sum\_{i=1}^n\log P^i\_X(x\_i) - H(\tilde P\_X)| \leq \epsilon \\}$$ I have no idea how to prove/disprove this. It seems like I can not use Weak law of large numbers.

# Answer
Suppose that $X\_n = n$ with probability $1$. Then $H(\tilde{P}\_X) = \log n$, but the only vector with non-zero probability has $\frac{1}{n} \log \frac{1}{P(\vec{x})} = 0$.
> 1 votes

---
Tags: probability-theory, information-theory
---


# Question
Title: The same outgoing and incoming degree in graph
I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same outgoing and incoming degree.

# Answer
> 7 votes
If such an orientation is possible, then all degrees are even. Conversely, if all degrees are even then the graph is Eulerian. Orient the edges according to an Eulerian circuit.

---
Tags: algorithms, graphs, network-flow
---