title: NX Bit in x86 vs x86_64

text:
# Question
Title: NX Bit in x86 vs x86_64
I've been reading about how the kernel manages memory in x86 from this popular blog post(https://manybutfinite.com/post/how-the-kernel-manages-your-memory/) and had a few questions.

There is a part where the author describes page table entries and their associated fields. To quote "This lack of a PTE no-execute flag illustrates a broader fact: permission flags in a VMA may or may not translate cleanly into hardware protection. The kernel does what it can, but ultimately the architecture limits what is possible.".

I looked into the kernel source and found that the NX bit in modern systems is actually the most significant bit. Is this because modern hardware now supports NX?

If I tried to execute code on the stack with NX enabled, I crash, but what actually happens? Does the kernel check the page permissions on every execute? That seems really slow. Is it the hardware that knows if I can/cannot execute? If so, how does the hardware know. Does this have anything to do with the CS segment selector?

# Answer
No, the kernel does not check the page permissions on every execute. If the CPU supports the NX bit, it checks that bit.

Exactly what the CPU does with it and when probably varies between CPU manufacturers and vendors.

Modern CPUs implement a split TLB, one for instructions and one for data. The Core i7, for example, has (ignoring 2MB and 1GB pages for the moment):

* L1 data TLB: 4-way set associative, 64 entries
* L1 instruction TLB: 8-way set associative, 64 entries
* L2 unified TLB: 6-way associative, 1536 entries

I'm not a CPU designer, so this could be wrong, but if it were me, I would check the NX bit when inserting the page table entry into the L1 instruction TLB.

There are a few things you need to consider; for example, the TLB load might be caused by speculative execution, so an exception shouldn't be raised unless instructions on that page are *actually* executed. But this is nothing special; it's exactly the same behaviour as you would expect if the instruction execution would cause a page fault.

There are architectures which manage TLBs in software or which allow for that possibility, most notably MIPS, Itanium, and some variants of SPARC V9. On such a platform, it is perfectly feasible for the kernel to perform the equivalent of the NX check on every instruction TLB miss.
> 1 votes

---
Tags: computer-architecture, operating-systems, security
---


title: Why it is not $O(m)$ but $O(\log m)$?

text:
# Question
Title: Why it is not $O(m)$ but $O(\log m)$?
I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2.

Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.

Naive solution: $O(\log m)$ bits, exact solution.

I don't understand why it is not $O(m)$ bits but $O(\log m)$ bits. Any help would be greatly appreciated.

# Answer
> 1 votes
Here $O(\log m)$ denotes the space complexity of the algorithm. We can represent a natural number $m$ in $O(\log m)$ space trivially.

For example, when we express numbers in base-2 system (binary number), $m$ is expressed in $\lceil \log\_2 m \rceil$ bits. (e.g., 5 is `101` in binary notation. $\lceil\log\_2 5\rceil$ digits.)

As a side note, $m$ is expressed in $O(m)$ space if we use base-1 system. (e.g., 5 is `11111` in unary notation. 5 digits.)

# Answer
> 1 votes
As a definition, the input size of a problem is the minimum number of *bits* $(\\{0,1\\})$ needed to encode the input of the problem. Since it is given that input length $|\sigma|=m$ , you should have $Ceil ( {\log\_2 m}) $ bits to encode $\sigma$.

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


# Question
Title: Problem A is polynomially reducible to problem B... what can we say about A and B?
This is a question on a practice final.

> Problem A is polynomially reducible to problem B. Which of the following statements is correct?
>
> I. *If problem A is solvable in a polynomial time then problem B is solvable in polynomial time*.
>
> II. *If problem A is NP-complete then problem B is NP-complete*.
>
> III. *If problem A is NP-hard then problem B is NP-hard*
>
> a) I
>
> b) II
>
> c) III
>
> d) I and II
>
> e) I, II and III

We are told that the solution is (c), but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:

(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A. (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)

---

This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why II is incorrect, and why III is correct would be appreciated.

Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.

# Answer
Your intuition about "relative hardness" is correct, the underlying mathematics is why III. is true. However your justification about I. is a little off (not wrong, but the reasoning is possibly not accurate).

It might help to think about reductions in these terms (everything I'll talk about here will be polynomial time, so I will leave that out just so I don't have to type it over and over); a reduction (from A to B) is just an algorithm that turns an instance of A into an instance of B, with the special property that if we know/can figure out/can use magic to find out the answer to the instance of B, we know the answer to the original instance of A. This gives us a way of solving problem A if we already know how to solve B.

This is why we say things like "B is at least as hard as A", because any algorithm for B immediately gives an algorithm for A. To flip it around, if we knew B was "easy", then A must also be "easy" (for some notion of "easy").

Notice that this relationship is not symmetric - knowing how to solve A doesn't tell us anything about how to solve B (given that all we have is the single reduction). If we had more information, maybe it would, maybe it wouldn't, but from the reduction alone we get nothing in that direction.

So then for I., we know we can turn an A into a B, and that we can solve an A, but this tells us nothing about B.

For III., we already know that A is hard (NP-hard!), and the reduction tells us that B is at least as hard as A, so B must also be NP-hard. The formal truth behind this intuition comes from the definition of NP-hardness. Remember that A being NP-hard means every single problem in NP has a reduction *to* A. We also know that A reduces to B, so how does this show B is NP-hard? We can compose the reductions. For every C in NP, we can reduce every instance of it to an instance of A, then take that instance of A and use our new reduction to turn it into an instance of B (as an exercise you might want to think about why we still know this is all polynomial time etc.). So this gives us a way of turning every problem C in NP into problem B, which is the definition of NP-hardness.

Coming back to II., this one again relies on definitions. NP-completeness is NP-hardness, plus the additional property that the problem is in NP. So saying problem A is NP-complete means problem A is NP-hard and A is in NP. We've just seen that the reduction to B tells us that B is NP-hard, so we have that part, but just like part I., where A being in P didn't tell us whether B was in P or not, A being in NP doesn't tell us whether B is in NP or not. It might be, but the reduction doesn't give us this information.
> 14 votes

# Answer
If Problem A is polynomially reducible to problem B then B is at least as hard as A. So only (III) is true. For NPC, NP property is needed so (II) is not true.
> 0 votes

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


# Question
Title: Determine the worst-case complexity that allow you to conclude that a given array with n elements is not sorted
Determine the worst-case complexity (in number of comparisons of two array elements) that allow you to conclude that a given array with n elements is not sorted.

I sort of have a general idea of what is going on. Suppose I have two element array, then make one comparison between these two elements.

If I have three elements, then i compare the 0th index element with 1st index element, sort it, and then compare 2nd index element with whatever is now the 1st element after sorting. Hence, I obtain 2 total comparisons.

Going on this pattern, I believe I will make n-1 comparisons which becomes my worst-case complexity. But of course, this is not a proof. How can I make this mathematically rigorous? Am I on right track?

# Answer
> 0 votes
The minimum number of comparisons to tell whether an $n$-element array is sorted is indeed $n - 1$. However, we don't have to sort the array to arrive to a conclusion.

Here is how to check an array $a$ in $n - 1$ comparisons. Compare $a\_0$ to $a\_1$, compare $a\_1$ to $a\_2$, ..., compare $a\_{n-2}$ to $a\_{n-1}$. If all comparisons result in "less or equal" outcome, the array is sorted. If any comparison results in "greater" outcome, the array is not sorted. Here, "sorted" means "the elements follow in non-decreasing order from left to right".

The harder thing is to prove that less comparisons won't be enough. Sure, if we just followed the above checks but dropped the last one, we won't know whether $a\_{n-2} \le a\_{n-1}$ holds, so the array is sorted if it does but is not sorted if it doesn't. But what if we compared some other $n - 2$ pairs?

One way to prove it is to establish and maintain some global characteristic of our knowledge about comparison results. Namely, consider a graph where vertices are array indices: $0$, $1$, $2$, $\ldots$, $n-1$. The edges of the graph will be the comparisons we make.

As we add our edges, let us track such global characteristic: the number of connected components in the graph. Initially, it is $n$, same as the number of vertices. Each edge either lies inside some component, or connects two different components, so the number of components drops by at most $1$ with each edge added.

In the end, after $n - 2$ edges, we will have at least $2$ connected components. Let all comparisons for vertices $i \< j$ so far result in $a\_i \le a\_j$, so that the result is still unknown. Consider any vertex $u$ from one of them and any vertex $v$ from another, such that $u \< v$. If $a\_u \< a\_v$, our array may still be sorted. If $a\_u \> a\_v$, it is not sorted.

Either of the above does not contradict any prior information about the array, so both are possible, which concludes our proof. If that's unconvincing, we can construct the example arrays. For the first case, simply let $a\_i = i$, which is clearly a sorted array. For the second case, let $a\_i = i$ for all elements of the $v$'s connected component, and let $a\_i = i + n$ for all other indices. We can check that both arrays are consistent with our $n - 2$ comparisons, and for two vertices $u \< v$, $a\_u \< a\_v$ in the first case and $a\_u \> a\_v$ in the second case.

---
Tags: algorithms
---


# Question
Title: Obtaining a computational history of a Turing Machine
I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In this proof, a contradiction is derived via a reduction from the problem of checking whether a Turing machine, $M$ accepts a given input, $w$. The proof seems to use the fact that from an input in the form $\langle M,w \rangle$, it is always possible to get a computational history, $C$, of $w$ when run on $M$. Then, $C$ is fed into some LBA, $B$, which checks if its input is an accepting configuration of $M$.

It seems to me that in order to obtain $C$ in the first place, we must simulate $M$ on $w$. However, if $M$ does not halt (and since $M$ is not an LBA, it is not guaranteed that there are a finite number of configurations), then we will never obtain $C$ (and $C$ would not be finite). It seems that the problem of obtaining a computational history of a Turing machine is equivalent to checking whether a Turing machine accepts its input. So what is the method used to always obtain $C$ from $M$ and $w$? Don't we need to prove the existence of such a method if we are going to use it to derive a contradiction?

# Answer
> 1 votes
It is correct that you cannot compute $C$ in case $M$ does not halt on $w$.

What can be done is to query $C$, that is for a given time $t$ to compute the $t$-th configuration of $M$ on input $w$. Also, you can compute finite prefixes of $C$ of given length. Possibly, these operations are already sufficient for the proof in the book that you read (which I did not read).

Also, from the outline you give it seems that it is not necessary to compute $C$ at all. If $M$ accepts $w$, there is a finite $C$ which will be recognized by $B$. The reduction has to compute $B$ from $M$ and $w$, not $C$ itself. $C$ is just the input that would witness non-emptyness of $L(B)$.

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


title: Heap Data Structures

text:
# Question
Title: Heap Data Structures
What is the difference between min heap and max heap? is it possible to shuffle the elements during insertion time? If so then how come the complexity is logn

# Answer
> 2 votes
The difference between min and max heap is in the invariant holding before and after any insertion or deletion. Namely in a max heap the keys of the son's of a node are always smaller then the node itself (i.e. biggest key is root). In a min-heap the son's keys are always bigger (i.e. smallest key is root).

When inserting a new node with key x you insert it in the first empty leaf of the structure (usually the leftmost leaf). this will probably invalidate the invariant, therefore we need now to adjust the heap. just compare the newly inserted node's key with its parent recursively and swap them if the heap invariant doesn't hold. Repeat the adjusting step until the father is smaller/bigger than it's son \[minheap/maxheap\]. The complexity of an insertion is log(n) because the heap always has a height of log(n) and the adjusting part of the insertion (which is also the most expensive) starts from a leaf (the node we just inserted) and brings it (in the worst case) to the root.

for more material see: https://en.wikipedia.org/wiki/Min-max\_heap

---
Tags: data-structures
---


# Question
Title: Connecting strings in a graph is a PSPACE problem
We define the following problem as:

Let $M$ be a TM with alphabet $\Gamma$, with $\\{a,b,$ #$\\} \subset \Gamma$.

We define, for every natural number $n$ the graph $G\_{M,n}$ by:

$V\_{M,n} = \\{a,b\\}^n$, the vertices

$E\_{M,n} = \\{(x,y) : x,y \in V\_{M,n} $ and $M$ accepts the string $x$#$y$ with a run that requires at most $n^{73}$space$\\}$

Now define the following language $L$:

$L = \\{(\<M\>, x, y) : x,y \in \\{a,b\\}^\*, |x| = |y|$ and $x,y$ are connected by a path in the above graph$\\}$

I want to show $L \in PSPACE$, without using Savitch's theorem.

My attempt:

Define the following algorithm $M\_0$

On input $(\<M\>, x, y)$ with $M$ with the above requirements:

1. Check if $M$ accepts the string $x$#$y$ in space $|x|^{73}$ or less; if so accept, else go to step 2.
2. Keep track of the set $Strings = \\{x,y\\}$ as a second tape.
3. For every string $z \in \\{a,b\\}^{|x|} - Strings$, add $z$ so $Strings$ and run $M\_0$ on

a. $(\<M\>, x, z)$

b. $(\<M\>, z, y)$

If both accept, accept. If all strings in $\\{a,b\\}^{|x|}$ have not yielded accept, reject.

Now I think it's rather obvious that $L(M\_0) = L$ but I'm unsure it solves it in poly. space:

Step 1. requires computing $|x|^{73}$ in unary, which takes poly. space in $|x|$. From here it is known that testing whether a machine accepts a string in some specific space, given in unary, is possible in poly. space when that unary representation is given in the input, using a universal machine. So step 1. requires poly. space in $|x|$.

Each step of the recursion in 2. requires keeping track of the strings tried which is fine. But the depth of the recursion seems to be $2^{|x|}$ which is problematic.

Can you suggest if this solution may still work, or a hint for another?

# Answer
> 1 votes
You say that you need to solve this "without Savitch", but what you're doing is (almost) implementing Savitch's proof within your algorithm.

That's perfectly fine, of course, as long as you're aware of that.

As for the space analysis of your algorithm - indeed, you present an exponential-space algorithm, in particular because you keep track of an exponential number of strings.

Consider the following change: in your subroutines (in the recursion), instead of limiting the set of vertices you're allowed to visit, how about limiting the *number of steps* you're allowed to take?

That is, define the subroutine that takes $\<M\>,x,z,t$ and checks whether $z$ is reachable from $x$ within $t$ steps, with $t$ encoded in binary.

Then, in the recursion, you can divide $t$ by $2$ at each step, thus obtaining a polynomial recursion depth.

This is, in fact, exactly how we prove Savitch's theorem, so it's no surprise that it works...

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


# Question
Title: Does graph G with all vertices of degree 3 have a cut vertex?
I'm asked to draw a simple connected graph, if possible, in which every vertex has degree 3 and has a cut vertex. I tried drawing a cycle graph, in which all the degrees are 2, and it seems there is no cut vertex there. I know, so far, that, by the handshaking theorem, the number of vertices have to be even and they have to be greater than or equal to 4. So, I kept drawing such graphs but couldn't find one with a cut vertex. I have a feeling that there must be at least one vertex of degree one but I don't know how to formally prove this, if its true. I'd appreciate if someone can help with that.

# Answer
Not necessarily true, for example complete graph of 4 vertices have no cut vertex. But there exists a graph G with all vertices of degree 3 and there is a cut vertex. See the picture. Red vertex is the cut vertex.
> 2 votes

# Answer
when dealing with questions such as this, it's most helpful to think about *how* you could go about solving it.

An easy way to make a graph with a cutvertex is to take several disjoint connected graphs, add a new vertex and add an edge from it to each component: the new vertex is the cutvertex. We just need to do this in a way that results in a 3-regular graph.

You've been able to construct plenty of 3-regular graphs that we can start with. If we take three of them, then the "new vertex" above will have degree 3, which is good, but its neighbours will have degree 4, which isn't. However, if we can manufacture a degree-2 vertex in each component, we can join that vertex to the new vertex, and our graph will be 3-regular. It's easy to make degree-2 vertices without changing the degree of any other vertex: just take an existing edge and put a new vertex in the middle of it. (This is known as "subdividing".)

So, the recipe is this:

1. Take three disjoint 3-regular graphs (e.g., three copies of $K\_4$) plus one new central vertex.
2. For each of the graphs, pick an edge and add a new vertex in the middle of it.
3. Add edges from each of these three vertices to the central vertex.
> 0 votes

---
Tags: graphs, discrete-mathematics, max-cut
---


title: Shor's algorithm and offset elimination

text:
# Question
Title: Shor's algorithm and offset elimination
I am wondering if the second Quantum Fourier Transform (QFT) in Shor's algorithm is necessary. I am probably missing a point but it seems that an offset elimination function would suffice to determine the period?

QFT eliminates the offset value and it changes the period from r to M/r, where M is a sufficiently large value \>\> r^2. What we do normally is to take a measurement and get a multiple of M/r. Doing this a couple of times we take the GCD of those measured values and obtain M/r, and then it is easy to obtain r from it.

But is changing the period necessary if there is no offset? Suppose that the period we are looking for is, say 5. Given a superposition with non-zero values only on the multiples of 5, we have a periodic sequence with period 5. Make a measurement and obtain a random multiple of 5. Do this constant number of times. Since all measured values will be multiples of 5, can't I determine r from it by finding their common divisor? So why do we need QFT? Isn't just an offset elimination function sufficient to find the period?

# Answer
> 1 votes
Yes, if you could consistently eliminate the offset then that would be enough. But how are you going to do that?

The state's offset is the discrete logarithm of the value in the ancilla register. But you don't know how to compute the discrete logarithm efficiently classically. And the offset changes from sample to sample. And there are so many possible offsets (assuming you picked a big number to factor) that you won't see the same one twice.

---
Tags: quantum-computing
---


# Question
Title: Reinforcement learning without self-play
Self-play seems to be very important for reinforcement learning algorithms. Can we train reinforcement learning algorithms without self-play (or learn mostly from past experiences)?

For example, let's say that I want to build a TRPG AI, which involves natural language and physical interaction between heterogeneous players. I can't do self-play this game so many times. But I happen to have a lot of match log of past human games.

Can I achieve higher score than humans using reinforcement learning using these logs (maybe like Experience Replay)?

# Answer
If you have a sane reward function and sufficient examples you can train a neural network on predicting your next state/value given a state/action and then use this neural network as a model to generate many more training examples on which to train a policy by selecting new action combinations. This may result in unexpected behaviour if you do not have sufficient examples which is quite likely to occur unless you have a very large training set.

Reading up on Actor-Critic reinforcement learning may help you here.
> 3 votes

# Answer
You might want to look at Least squares policy iteration. These algorithms can incorporate data sets of the form and is an offline method. These may help you incorporate your past experiences in a fruitful manner.
> 1 votes

---
Tags: reinforcement-learning
---


# Question
Title: Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?
I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays for front-of and end-of operations make sense intuitively, but for operations in the middle, not so much.

I see why the middle insert is O(n) for a dynamic array - half the elements need to be shifted one by one.

But, when it comes to linked lists, don't half the elements need to be traversed one by one starting from the head to find the insertion point? And if so, why doesn't that also make linked lists O(n) for middle insertion? And if it does, why is it not represented that way in the Wikipedia article?

# Answer
> 2 votes
You are right: if we have to find a particular place and then insert a value there (for example, insert an element in a sorted list), it is $O(n)$ for a linked list.

However, the Wikipedia article you seem to mention considers another operation named `insertAfter`: given a node, insert an element after that node. When the particular node after which to insert is given to us, we spend only $O(1)$ time to do so, as we don't have to search for it.

An example usage is "duplicate each value $x$ we find in the list". An example solution is to traverse a list, and whenever we find an $x$, add a duplicate right after it, and immediately step over it. Each such insertion takes $O(1)$, and the whole solution is $O(n)$. Note that, without any preallocation strategy, solving such a problem with a dynamic array is $O(n^2)$ worst case.

---
Tags: arrays, linked-lists
---


title: Verifier - Complexity Theory

text:
# Question
Title: Verifier - Complexity Theory
> A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\\{ w \space | V \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\right\\}.$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?

# Answer
> 2 votes
A verifier for a language $L$ is an algorithm that accepts as input an instance $x$ of $A$ and a witness $w$, and has the following properties:

1. The algorithm always halts.
2. If $x \in A$ then there is a witness $w$ such that the algorithm accepts $\langle x,w \rangle$.
3. If $x \notin A$ then for all witnesses $w$, the algorithm rejects $\langle x,w \rangle$.

We are often interested in polynomial time verifiers. Such a verifier exists for the clique problem, which is: given a graph $G$ and a parameter $k$, decide whether $G$ contains a $k$-clique. Here is one polynomial time verifier for this problem: it accepts as witness a list $S$ of vertices, and on input $G,k,S$ it accepts if $S$ is a set of $k$ vertices which form a clique in $G$. I'll let you check that this satisfies all the required properties.

---
Tags: complexity-theory, turing-machines
---


# Question
Title: minimum and maximum nodes of MultiWay tree of height h
I know that it doesn’t have to be balanced so in theory given that the height of the tree is $h$, the minimal number of nodes is obtained when each node has 1 key and 1 child, and since the first level "doesn’t count" in the height, I should have $h+1$ nodes.

The maximal number of nodes in a $M-way- tree$ should be $\Sigma^h\_{i=0} M^i$, when $i$ is the tree level.

Is this correct ? Thank you!

# Answer
> 1 votes
This looks correct.

Note that the sum of the geometric series can be expressed more concisely:

$$\sum\limits\_{i = 0}^{h} M^{i} = \frac{M^{h + 1} - 1}{M - 1}$$

---
Tags: data-structures, trees
---


# Question
Title: Program Counter Incrementation When instruction Is More Than One Word
How is program counter(PC) incremented when instruction takes more than one word? How does PC know when to increment by one word or by more than one word since incrementation is done before decoding the instruction(if I am correct)?

# Answer
> 1 votes
Who says incrementing the program counter would have to happen before decoding the instruction? Modern decoders will actually decode several instructions simultaneously (if the first instructions are simple enough so that the decoder can find the start of the next instructions with negligible delay).

That's what Intel processors with their fabulously complex instruction set do. The decoder is given a large range of bytes. For some instructions it's easy to determine the length, for some it's difficult.

So the decoder tries to find the length of the instruction starting at the first byte, and *very* quickly finds that it is a simple instruction say of 3 bytes, or something more complicated. The decoder does the same thing *simultaneously* assuming an instruction starting at byte 1, at byte 2, at byte 3 and so on. (Duplicating hardware is cheap when a chip can have billions of transistors).

Once the decoder has these numbers (instruction at #0 is 3 bytes, instruction at #1 is difficult, instruction at #2 is 6 bytes, instruction at #3 is 2 bytes, instruction at #4 is difficult, instruction at #5 is difficult etc. ) it combines these results and knows there is a 3 byte instruction at #0, followed by a 2 byte instruction at #3, followed by a difficult instruction at #5. The information about the instruction starting at #1, #2, #4, #6 etc. is thrown away.

And then the decoder gets really going: It can decode *several* simple and one complex instruction. So the processor decodes the simple instruction at #0, the simple instruction at #3, and the complex instruction at #5. And when it has the length of that complex instruction at #5, *then* it increases to program counter.

---
Tags: computer-architecture
---


# Question
Title: How to convert statement with the existential quantifier to statement with universal quantifier?
How to convert the following statement with the existential quantifier to statement with universal quantifier?

$\exists n. n\>1\rightarrow x(n)\not=1$

Please give me some suggestion?

# Answer
> 3 votes
Let's give names for the atom formulas:

$n\>1$ will be $\phi$ and $x(n) \neq 1$ will be $\psi$ Now what we have is: $$\exists{n} (\phi\rightarrow\psi)$$ $$\exists{n} (\neg\phi \lor\psi)$$ $$\neg\neg \exists{n} (\neg\phi \lor\psi)$$ $$\neg\forall{n} \neg(\neg\phi \lor\psi)$$ $$\neg\forall{n} (\phi \land \neg\psi)$$ $$\neg\forall{n}((n\>1) \land \neg(x(n)\neq 1))$$ $$\neg\forall{n}((n\>1) \land (x(n) = 1))$$

---
Tags: first-order-logic
---


# Question
Title: About the turing machine's non-deterministic branches
I have three different cases of non-deterministic turing machine. The first machine has: Branch "accept" and branch "loop". The second has: Branch "rejecte" & branch "loop". Third has: Three branchs "rejecte" "loop" "accept". The question is which machines will rejecte and which ones will accept and which ones will enter a loop? Thank you so much

# Answer
> 2 votes
I guess, with branches you mean the computation branches (the sequence of the konfigurations M has in its computation) of $M$. Then in general a NTM $M$ will accept an input x, if there exists one computation branch in the computation tree, which leads to accept x, no matter, where other branches may lead to (even if there infinite long). So, Machine 1 and 3 will accept.

I am definitely not sure about the following: I guess, the question, what Machine 2 will do is not decidable (please correct me, if I am wrong)

---
Tags: complexity-theory
---


# Question
Title: Which algorithm can calculate an optimal allocation of students to projects?
I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects are predetermined and of fixed number and each student needs to be allocated to exactly one project. Each project needs at least one student, but can hold up to a maximum of $y$ students.

For my purposes, there will be on average between 8 to 15 projects available and 80 to 250 students to assign to these projects, resulting in average group sizes of 8 to 15 students per project. A reasonable value for $y$ is usually $\frac{n}{m}+2$.

The definition of optimal and stable as put by @Gassa:

(1) There is no student $S$ assigned to project $P$ such that $S$ likes $Q$ more and $Q$ has an empty slot; (2) there is no pair of students $(S,T)$ such that the current assignments are $S→P$ and $T→Q$, but $S→Q$ and $T→P$ would both be more preferred.

All sort relevant sources I could find so far (listed below) either require an equal number of students and projects (stable marriage) or allocate only one student to each project (exchange-stable matching \[1\] / the matching problem) and I find it non-trivial to adapt these algorithms for the described purpose.

Sources

# Answer
> 3 votes
This sounds much like a problem for minimum-cost maximum flow.

Construct a network. The nodes will be the students, the projects, and the added source and sink.

Add an edge with capacity $1$ and cost $0$ from the source to each student.

Add an edge with capacity $y$ and cost $0$ from each project to the sink.

Add an edge with capacity $1$ and cost $r\_{i,j}$ from each student $i$ to each project $j$, where $r\_{i,j}$ is the rank given by student $i$ to project $j$, the most preferred being ranked $1$. (Alternatively, we can give negative scores, $-m$ up to $-1$, or even $-(2^m)$ up to $-(2^1)$, and more negative is more preferred. I believe the exact scheme is not significant.)

Now find the minimum-cost maximum flow. The maximum-ness of the flow means that each student is assigned to some project, because the maximum flow is obviously equal to the number of students.

The condition which can break is that each project gets at least one student. (Before proceeding to remedy this, first, check if the values $n$, $m$, and $y$ make failing this condition at all possible.) We can force it by splitting the edges from projects to the sink: instead of one edge of capacity $y$ and cost $0$, we can have an edge of capacity $1$ and cost $-L$, and another of capacity $y - 1$ and cost $0$. The value $L$ is a large constant, effectively infinite compared to all other costs: if we just use the ranks from $1$ to $n$, perhaps something like $m \cdot n$ will suffice. This way, a minimum-cost flow will have to add at least one student to every project in order to use all of the available edges of cost $-L$.

The thing left to prove is that the resulting arrangement is stable. Indeed, if the stable condition was not satisfied, we could just make a local change, like switching a student to their more preferred project, or swapping the projects for two students. These would result in strictly lower cost with the same flow, which would in turn contradict the fact that we found the minimum cost flow.

I'm not going into details here (we should start with a formal definition of stableness when only one side has preferences), but hope that they turn out trivially right. In the unfortunate case they don't, the first I'd do is revisit the cost assignments for $r\_{x,y}$.

---
Tags: algorithms, optimization, combinatorics, matching
---


# Question
Title: Turing machine Representation for string of 3 letters
Can someone explain to me what this statement implies? I am assuming that it means that a string consisting of three characters repeated. What I don't understand is if the repeated string is all 0s or all 1s or both?

Give the state diagram of a machine (any Turing-Complete model) that decides the following languages over {0,1}:

{w : w = xxx, x ∈ Σ\*}

# Answer
> 1 votes
The language you are trying to decide here is `xxx`: that is, three copies of `x`. What is `x`? Well, it can be anything in $\Sigma \*$: any string in your alphabet. (Usually this means "any binary string", but you can also use a different alphabet, the principle will be the same.)

So you're looking for any string which consists of something repeated three times. So strings in the language include `111`, and `000`, and `ε` (the empty string), and `100100100`, and `101011010110101`.

As for the machine that recognizes this, recognizing the language `xx` : $x \in \Sigma \*$ is a classic demonstration of the power of Turing machines (since this language is neither regular nor context-free). Try starting from that machine and seeing what changes you'd need to make for `xxx`.

---
Tags: turing-machines
---


# Question
Title: Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?
According to the wiki page of TSP as a graph problem,

> *It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once*

Then what if a triangle is given, with two edges weighed $1$ and the third weighed $100$,obviously, the shortest path to visit all three vertices are passing the two $1$-weighed edges twice.

So what's the meaning of such a restriction?

# Answer
> 6 votes
This mostly comes down to what makes an interesting problem, and what can be easily analyzed.

The restriction of visiting each vertex once is common in these sorts of problems. A traversal that visits each vertex no more than once is called a "path", and these are well-studied in graph theory, so there are quite a few existing theorems based on them.

The version where you can visit vertices more than once can be readily reduced to the version where you can't (and in poly-time): for every pair of nodes, calculate the shortest distance between them, remove the edge directly between them (if any), and add an edge between them with weight equal to that shortest distance. (In your example graph, this would replace the 100 edge with a 2.)

So your modified version both doesn't play into existing graph theory problems, and can be easily reduced to the standard one. It's easier just to analyze the standard one instead.

TL;DR: It's because of precedent in graph analysis. See also the Hamiltonian cycle problem, which is very closely related, and the longest path, which is a bit more distantly related.

---
Tags: traveling-salesman
---


# Question
Title: What does "higher order address bits" and "lower order address bits" mean?
"Assume a system with 4 GB virtual memory and 1 GB physical memory with 32 bit addresses. if the page size is 4 KB, How many bits will be allocated as the Higher Order Address bits and Lower Order Address bits to identify page numbers and corresponding words respectively?" My question is, What does "higher order address bits" and "lower order address bits" mean in the above question?

# Answer
> 1 votes
According to the problem, the address itself is 32 bits long. Some of those bits (the higher order ones, i.e. closer to the msb) are used to identify a page, and some of those bits (the lower order ones, i.e. farther from the msb) are used to identify a word within that page. The question here is, how many bits should be allocated for each part, to ensure you can address as much of your memory as possible.

(The msb is the "most significant bit": the one that has the highest place value. We can't just talk about the "first bit" or the "last bit" because nobody can agree on whether the msb comes first or last. It's a headache for anyone doing network programming.)

---
Tags: memory-management, paging
---


# Question
Title: Topics from theoretical computer science suitable for a bachelor (undergrate) thesis?
Is the field of theoretical computer science so complex, that it is just "too much" for a bachelor thesis? Unfortunately I haven't found any old thesises because the relevant chair of the university hasn't been occupied for years.

Because of theoretical computer science is the only topic that really interests me, I thought of writing my bachelor thesis in this field. What would be suitable topics or at least fields that can be arranged in the limited focus of a bachelor thesis? I thought of topics like parametrized complexity or formal software verfication (which is actually a bit of the target)

# Answer
> 1 votes
As a bachelor student that is writing his thesis in that field I can guarantee you there are a lot of topics suitable for a bachelors degree. Personally, I am working on graphs and some specific algorithmic problems over those. I suggest you ask your professors if they have some topics for you. At my university usually professors have a list of "problems" and we can either choose between one of those or propose our own topic. Obviously because it is "just" a bachelor thesis you'll have to be specific and concentrate on some smaller problems e.g.

* Formal verifiation of smaller programs in some specific language (like haskel)
* Finding some polynomial algorithm to a specific problem that hasn't been researched too much. (Also, if you can't find anything new, explaining why the problem is "complex" can also be a good plan b)
* Testing of specific cryptographic protocols under specific assumptions (allowing the attacker to have some specific information etc..)

---
Tags: formal-methods, parameterized-complexity, research
---


title: Question about Morris' algorithm

text:
# Question
Title: Question about Morris' algorithm
I am reading the lecture notes. I am trying to understand Morris' algorithm on page 2. The Morris' algorithm is as follows.

Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.

1. Initial: $X=0$
2. For each item in the stream, increment $X$ with probability $\frac{1}{2^X}$.
3. Output: $2^X-1$.

It is said that $\mathbb{E}\[2^X-1\]=m$, where $X\_m$ is the value of $X$ after seeing $m$ items.

How to show that $\mathbb{E}\[2^X-1\]=m$? Any help would be greatly appreciated.

# Answer
Let us denote by $X\_n$ the value of $X$ after reading $n$ elements, and let $Y\_n = 2^{X\_n}$. We have $Y\_0 = 1$ and $Y\_{n+1}$ equals $2Y\_n$ with probability $1/Y\_n$, and $Y\_n$ otherwise. Therefore $$ \mathbb{E}\[Y\_{n+1}|Y\_n\] = Y\_n + \frac{Y\_n}{Y\_n} = Y\_n + 1, $$ which together with $Y\_0 = 1$ implies that $\mathbb{E}\[Y\_n\] = n + 1$.

More generally, we can estimate all moments of $Y\_n$ in this way. We have $$ \mathbb{E}\[Y\_{n+1}^k|Y\_n^k\] = Y\_n^k + \frac{(2^k-1)Y\_n^k}{Y\_n} = Y\_n^k + (2^k-1) Y\_n^{k-1}, $$ and so $Y\_0^k = 1$ implies that $$ \mathbb{E}\[Y\_n^k\] = 1 + (2^k-1) \sum\_{m=0}^{n-1} \mathbb{E}\[Y\_n^{k-1}\]. $$ As an example, $$ \mathbb{E}\[Y\_n^2\] = 1 + 3 \sum\_{m=0}^{n-1} (m+1) = 1 + 3 \frac{n(n+1)}{2}. $$ Therefore the variance of the estimator $Y\_n-1$ is $$ \mathbb{V}\[Y\_n-1\] = \mathbb{V}\[Y\_n\] = \mathbb{E}\[Y\_n^2\] - \mathbb{E}\[Y\_n\]^2 = 1 + 3 \frac{n(n+1)}{2} - (n+1)^2 = \frac{n(n-1)}{2}. $$ More generally, induction shows that $\mathbb{E}\[Y\_n^k\] = \Theta(n^k)$, and with some effort we can even calculate the leading constant: $$ \mathbb{E}\[Y\_n^k\] = \prod\_{\ell=1}^k \frac{2^\ell-1}{\ell} n^k + O(n^{k-1}). $$ In particular, if we denote $Z\_n = (Y\_n-1)/n$ then $Z\_n \to Z$, where $$ \mathbb{E}\[Z^k\] = \prod\_{\ell=1}^k \frac{2^\ell-1}{\ell}. $$ For more on $Z$, see Theorem 7 in Ph. Robert, On the asymptotic behavior of some algorithms.
> 1 votes

# Answer
We can use induction to prove the theorem. Let $X\_n$ be the value of $X$ after $n$ events. If $n=0$, then $X\_0=0$ and $2^{X\_0}=1=0+1=n+1$. The result is true.

Suppose that $\mathbb{E}\[2^{X\_{n-1}}\]=(n-1)+1=n$. We will prove that $\mathbb{E}\[2^{X\_n}\]=n+1$.

We have \begin{align} \mathbb{E}\[2^{X\_n}\] & = \sum\_i 2^i Pr\[X\_n=i\] \\ & = \sum\_i 2^i( Pr\[X\_n=X\_{n-1}+1 \text{ and } X\_{n-1} = i-1 \] + Pr\[X\_n=X\_{n-1} \text{ and } X\_{n-1}=i\] ) \\ & = \sum\_i 2^i( \frac{1}{2^{i-1}} Pr\[ X\_{n-1} = i-1 \] + (1-\frac{1}{2^i}) Pr\[ X\_{n-1}=i\] ) \\ & = \sum\_i 2 Pr\[ X\_{n-1} = i-1 \] + \sum\_i 2^i Pr\[ X\_{n-1} = i \] - \sum\_i Pr\[ X\_{n-1} = i \] \\ & = \sum\_i 2^i Pr\[ X\_{n-1} = i \] + \sum\_i Pr\[ X\_{n-1} = i \] \\ & = \sum\_i 2^i Pr\[ X\_{n-1} = i \] + 1 \\ & = n+1. \end{align}
> 1 votes

---
Tags: randomized-algorithms
---


# Question
Title: Obtain all possible Turing Machines from a Universal Turing Machine
Knowing how a **Universal Turing Machines** works and its capabilities, is it possible to obtain the collection *M* = {M0 , M1 , M2 , M3, … } of all possible Turing Machines?

If so, can we prove that a language *L* = {*wj* |*wj* not accepted by *Mj* } is not accepted by the Universal Turing Machine?

# Answer
> 1 votes
Enumerating all the possible TMs is a boring programming exercise. We do not need to use the UTM at all here -- we only have to generate the representation of all TMs and output it, using the chosen encoding of TMs as words.

The UTM does not accept your language $L$ since it accepts another language, namely $\\{\langle M,w\rangle \ |\ \mbox{$M$ accepts $w$}\\}$.

---
Tags: turing-machines, turing-completeness
---


# Question
Title: Formal definition of loss surface of multi-layered networks
Let $\mathcal{L}$ be a loss function associated with a multi-layered neural network. So it seems almost everyone in AI/ML community is interested in the Hessian $H=\partial^2 \mathcal{L}$ of $\mathcal{L}$. So if you read \[1\] on page 193 the left colum you find the following text

"An important question concerns the distribution of critical points (maxima, minima, and saddle points) of such functions. Results from random matrix the- ory applied to spherical spin glasses have shown that these functions have a combinatorially large number of saddle points. Loss surfaces for large neural nets have many local minima that are essentially equivalent from the point of view of the test error, and these minima tend to be highly degenerate, with many eigenvalues of the Hessian near zero. " Could anyone in the community shed some light on how formally the authors define (perhaps assuming some accepted definition in the community) the loss surface associated with either neural network or the loss function of the neural network?

My guess is that it is the level set of the loss function attaining one of its critical values (of the loss function). I would appreciate if someone would share any knowledge on the nature of the formal definition of the loss surface or any accepted common knowledge definition. Many thanks.

\[1\] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, pages 192–204, 2015.

# Answer
In the empirical risk minimization framework, we let $w$ denote the weights of the neural network (which we are trying to learn) and define $L(w)$ to be the total loss (across the entire training set) if you use weights $w$. Then, the optimization problem is to find $w$ that minimizes $L(w)$.

This is the function that the quote is talking about.

"Loss surface" refers to the graph of this function. $L$ is multidimensional so we obtain a graph in some high-dimensional space.
> 0 votes

---
Tags: computational-geometry, artificial-intelligence, neural-networks
---


title: binary max and binary min

text:
# Question
Title: binary max and binary min
I'm reading a paper about constraint satisfaction problem and found a term "binary Max and binary Min" operations but I dont know the meaning. If someone know could you please explain for me? I googled it but didn't find nothing.

# Answer
> 2 votes
In theoretical computer science, in the context of operators or functions, "binary" usually means "taking two arguments", whereas "Boolean" means "taking one of two values", especially if those values are true and false or $0$ and $1$.

So, for example, the ordinary addition operator on the natural numbers is binary (it adds two things) but not Boolean (the arguments can take infinitely many different values). Conversely, the function $f(x,y,z)=(x\lor y)\land z$ is Boolean (its arguments are true/false) but not binary (it takes three arguments, not two; it's ternary).

"Binary" is also used to denote the base-$2$ number system but that doesn't seem relevant, here: min and max operate on numbers as abstract quantities, and the representation of those numbers (binary, decimal, Egyptian hieroglyphs, ...) is irrelevant.

---
Tags: terminology, logic
---


# Question
Title: Connection between probabilistic algorithm and distributional algorithm
A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for every $x \in L$, it holds that $\Pr(A(x) = 1) \geq 1 - \epsilon$, and for every $x \notin L, \Pr (A(x) = 0) \leq \delta$.
Second definition:
Given a language $L$ and a distribution $D$ on the instances of $L$, the algorithm $A$ decides $L$ with respect to $D$, if it holds that for every $x$ which is drawn from $D$, the above requirements hold ($\Pr(A(x) = 1)\geq ...$).
Clearly, the first notion is "stronger" in some sense: in the second definition, I may force the algorithm make as many mistakes as I want, by creating a different distribution on which he cannot handle.
My main question is the following:
If for a problem there exists an algorithm $A$ such that $A$ decides $L$ with respect to the uniform distribution, does it mean that $A$ decides $L$ for every input (with high probability)? I somewhat "feel" that uniform solving for a uniform distribution is harder, does this feeling correct?

# Answer
The first notion (probabilistic algorithms who are correct with high probability for *all* inputs) is indeed stronger. Distributional complexity relates to randomized (worst case) complexity via Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

You can find an exact formulation in this cstheory question, where both the Las Vegas (the randomized algorithm should always output the correct answer) and the Monte Carlo case (similar to your formulation) are mentioned.

As for your question, it is not true that an algorithm which outputs the correct answer with high probability when the input is drawn according to the uniform distribution, returns the correct answer with high probability for all inputs. Consider an algorithm which answers correctly for all inputs not of the form $0^n$. For an input drawn from the uniform distribution, the probability of getting a correct answer is $1-2^{-n}$, however for inputs of the form $0^n$ you never get the correct answer.
> 2 votes

---
Tags: complexity-theory, probability-theory, probabilistic-algorithms
---


title: Inverting a band matrix

text:
# Question
Title: Inverting a band matrix
I have a band matrix -- a sparse, square, symmetric $N \times N$ matrix whose structure looks like the following:

Here, the area under the blue stripes is the non-zero elements; everything else is zero

Is there an algorithm to invert this kind of matrix that is simple yet more efficient than Gaussian elimination and LU decomposition?

# Answer
> 12 votes
Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did).

Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-band-limited) matrix in general, so just filling out the entries of the inverse matrix would take $\Omega\left(n^2\right)$. So I'll assume you just want to solve a linear system $A x = b$.

Using the algorithm in this paper, a general band-limited matrix $A$ of size $n \times n$ with bandwidth $k$ can be decomposed into triangular $k$-bandwidth matrices $L$ and $U$ in $O \left( k^2 n \right)$ time. From there, $L U x = b$ can be solved quickly in $O(k n)$ time. So overall, the runtime will be $O\left(k^2 n\right)$. As a followup, if $k$ is constant, that means that the system can be solved in linear time (highly useful).

---
Tags: algorithms, linear-algebra, sparse-matrices
---


# Question
Title: Is the derivative of a graph related to adjacency lists?
Some of Conor McBride's works, Diff, Dissect, relate the derivative of data types to their "type of one-hole contexts". That is, if you take the derivative of the type you are left with a data type which shows you how the data type looks from the inside at any given point.

So, for instance, if you have a list (in Haskell)

```
data List a = [] | a : List a

```

this corresponds to

```
data List a = 1 + a * List a

```

and through a little mathematical magic, the derivative is

```
data ListDeriv a = List a * List a

```

which is interpreted to mean that at any point in the list there will be a list to the left and a list to the right. We can zip through the original list by using the derivative data structure.

Now, I'm interested in doing something similar with graphs. A common representation of graphs is a set of vertices and edges, which might be naively implemented with a data type such as:

```
data Gr a b i = Gr [(i,a)] [(i,i,b)]

```

If I understand it correctly, a derivative of this data type, with respect to the graph index, `i`, should be something like.

```
data GrDeriv a b i = d/di (Gr a b i)
     = d\di ( [a*i] * [b*i^2] )
     = (d\di [a*i]) * [b*i^2] ) + [a*i]*(d/di [b*i^2])
     = (a* [a*i] * [a*i]) * [b*i^2] )
       + [a*i] * (2*b*i) *[b*i^2]*[b*i^2])
     = InNodes { nodesLeft :: [(a,i)]
               , nodeLbl :: a
               , nodesRight :: [(a,i)]
               , edges :: [(b,i,i)] }
     | InEdges { nodes :: [(a,i)]
               , adjNode :: Either (b,i) (b,i)
               , edgesLeft :: [(b,i,i)]
               , edgesRight :: [(b,i,i)] }

```

I got this through the use of the product rule and chain rules for derivatives, and although possibly there are some errors, it seems to follow the general scheme. In this structure you will either be focused on Nodes (InNodes constructor) or Edges (In edges) and given the place you will see the relevant data.

But this isn't what I was hoping for. I was hoping for a construct more closely related to the interface of Martin Erwigs Functional Graph Library. Specifically, I want to see at a node a context representing the label of the node and two adjacency lists, one for outgoing, one for incoming.

```
Node a b = ([(i,b)],a,[(i,b)])

```

I do see hope, however, as the adjacency representation has some terms in common with the derivative, the lone lable, `a`, at each hole location, the adjacency representation/dissection of each edge.

Since a derivative isn't the same function as the original, but an integration of the derivative is (kindof), is there some sort of integration analogue which will serve to transform the derivative into a collection of node contexts? Not a direct integration to recover the original structure, mind you, but a structure equivalent to the original but in a more algorithm friendly representation.

If there is, I hope that relationship type structures can be specified by some easy "set of vertices and edges" language and I can derive an efficient library for working with that structure. Such an implemenation could be used to study structures "beyond graph theory": hyper graphs, simplicial complexes...

So. Does this idea seem feasible? Useful? Has there been any study into this type of thing which I could read more about?

### Addendum

As commented upon by Curtis F, a set of nodes and edges is not exactly a graph. However, all graphs can be represented by such, and I find it common enough presentation. I've seen (the very coarse specification) $G=(V,E)$ used in research that applies graph theory to optimizations of wireless networks in various ways. Here's an open-access example, DRAND\*. This raises the question, what is the link between the presentation and how some software might be implemented based upon the research.

That said, I'm not entirely opposed to changing the input spec from $G=(V,E)$ to something else. For instance, given an index type $I$, node labels, $V$, and edge labels, $E$. Then the graph is (approximately) a function from indexes to a label and edge list.

$$ G = I \to (V * I \to E) $$

This, I'm pretty sure can be expressed (Category theory?) as

$$ G = (V * E^{I})^{I} \tag{1} $$

or

$$ G = V^I * E^{I\*I} $$

which can be seen as a set of vertices and edges--given enough caveats. However, its not clear if the derivative of $(1)$ is meaningful:

$$ G' = \ln(V * E^{I}) * (V * E^{I})^{I} * (\ln(E) * V * E^{I}) $$

I for one do think it shows some promise, but I lack the sophistication to go further. I know there must be some work out there exploring the connection further.

* In case the link ever breaks, citation: Rhee, Injong, et al. "DRAND: Distributed randomized TDMA scheduling for wireless ad hoc networks." IEEE Transactions on Mobile Computing 8.10 (2009): 1384-1396.

# Answer
> 7 votes
Your type `Gr` does not really correspond to graphs, because it includes many instances that are clearly not graphs, because the edge indices need not be actual vertex indices.

For example,

$$ V = \\{A, B\\} \\;\\;\\;\\; E = \\{(C, D, e)\\} $$

is not a graph, but is allowed in your type as

```
Gr [(1, A), (2, B)] [(3, 4, e)]

```

Rather, your `Gr` corresponds literally to a list of labeled indexes and a separate, unrelated, list of labeled pairs of indices. This is why you get such a "literal" derivative of `Gr` that doesn't correspond to "holes" in graphs.

There's also the unfortunate problem of caring about the order of vertices/edges (visible in the `nodesLeft/Right` and `edgesLeft/Right` distinctions) but this can be fixed by using a `Set` instead of a list.

---

Here is a type expressed in Haskell that I think more closely corresponds to (non-empty) graphs:

```
data Graph v e = Lone v | Joined v (Graph (v, ([e], [e])) e)

```

For simplicity, I'll instead consider complete, simple, undirected graphs:

```
data Graph v e = Lone v | Joined v (Graph (v, e) e)

```

(To relax complete-ness, let `e = Bool` mark edge presence)

Note that `Graph` is recursive (and in fact, parametrically recursive). This is what allows us to restrict ourselves the type to just graphs and not just adjacency lists combined with vertex lists.

Written more algebraically,

$$ G(v, e) = v + v * G(v * e, e) $$

Since $e$ doesn't vary with $v$, I'm going to eliminate the second argument to $G$:

$$ G(v) = v + v * G(v * e) $$

By repeatedly expanding, we get the fixed point

$$G(v) = v^1 e^{\binom 1 2} + v^2 e^{\binom 2 2} + v^3 e^{\binom 3 2} + v^4 e^{\binom 4 2} + \dots$$

This makes sense, since a (complete) graph is either

* One vertices and no edges
* Two vertices and one edge
* Three vertices and three edges
* Four vertices and four choose 2 = 6 edges
* ....

Call the type of size $k$ graphs $G\_k(v) = v^k e^{\binom k 2} $. Then $G(v) = G\_1(v) + G\_2(v) + \dots$

which has derivative

$$ \frac d {dv} G(v) = \sum\_{i=1} G\_i'(v) $$

The derivative $$ G\_k'(v) = \frac d {dv} \left\[ v^k e^{\frac {k(k-1)} 2} \right\] = k v^{k-1} e^{\frac {k(k-1)} 2} $$

Note that $G\_{k-1}(v) = v^{k-1} e^{\frac {(k-1)(k-2)} 2}$, so that $G\_k'(v) = G\_{k-1}(v) * k * e^{k-1} $

That is, the derivative of a $k$-node graph is a $k-1$ node graph, combined with the $k-1$ edges from the removed node to the $k-1$ remaining nodes, and the index $k$ that the node occupied in the list of vertices.

```
data SimpleGraph v e = Lone v | Joined v (SimpleGraph (v, e) e)

data SimpleGraphHole v e = Empty
                         | InsertLater v (SimpleGraphHole (v, e) e)
                         | InsertHere (SimpleGraph (v, e) e)

```

### Fixing Order in this graph

This version of the Graph data structure is fundamentally a linked-list, and so it encodes the order of vertices. While that could be fixed in your adjacency-list version by using a Set, it's not so direct here.

I think you can modify a tree data-structure to do the same kind of parametric recursion, with the root playing the role the "head" does in `SimpleGraph`. By the interface of the resulting tree-sets, the order/underlying structure becomes invisible (or even canonical, if you aren't interested in fast updates).

# Your Proposed Derivative

You proposed a derivative type; I'll change it to conflate the labels and indices as I did: `([(v,e)], [(v,e)])`

This can be integrated as $ \int \frac 1 {(1 - ve)^2}$ which is $ C + \frac v {1 - ve} $, or just `(v, [(v, e)])`. This doesn't have enough information to reconstruct an entire *graph*, because the "edge" information only identifies a single vertex.

---
Tags: graphs, type-theory
---


# Question
Title: Count of distinct substrings in string inside range
Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ containing indexing $(i,j)$ where $0 \le i \le j \< n$ is asking for count of distinct substring inside given query range for string $S\[i..j\]$.

My approach is just applying linear time construction of LCP array to each query. It gives complexity $O(|q|n)$. Number of queries could raise to order of $n$ so answering all queries makes it $O(n^2)$.

Can it be done better, than linear time for every query?

In general, if one process substring of string for which we already have suffix array, suffix tree, lcp array, are those structures not relevant anymore, and must be build from scratch again?

# Answer
> 1 votes
There is $O(n \sqrt{n} + |Q| \sqrt{n})$ offline solution.

1. Sort elements $(i,j)$ of $Q$ in ascending order of $j$.
2. Distribute them into $\sqrt{n}$ buckets so, that $(i,j)$ goes into bucket number $\lfloor \frac{i}{\sqrt{n}} \rfloor$.
3. For each bucket starting at $b$ and each query $(i,j)$ in it, build a suffix tree for $S\[b,j\]$.
4. For each query in a bucket, remove redundant characters from the left and report the answer.

Step 3 takes $O(n)$ for each bucket, because we use Ukkonen's algorithm and $j$ goes in ascending order.

Step 4 takes $O(\sqrt{n})$ for each query, because removing $\sqrt{n}$ longest suffixes from the tree takes $O(\sqrt{n})$. Note that you can use an indirection layer to avoid modifications to the original suffix tree.

# Answer
> 0 votes
The question does not motivate the number of queries being $O(n)$, which seems an arbitrary worst case since the number of unique possible queries is the number of ordered pairs and thus $O(n^2)$.

Here are two different solutions with better time complexity for the $O(n^2)$ case based on (implicit) suffix trees constructed incrementally with Ukkonen's algorithm. Both solutions are based on preprocessing and have complexity $O(n^2 + |Q|)$ where $Q$ is the set of queries. The second solution runs in $O(n + |Q|)$ if all queries have the same width.

# Solution 1 - Preprocess all unique queries

Iterate over the suffixes of $S$. For each suffix $S\_i=S\[i..n\]$, build the suffix tree of $S\_i$ with Ukkonen's algorithm. After update $j$ to the current suffix tree, store the tree size in a matrix at position $(i,i+j-1)$. A query for the range $\[x,y\]$ is answered by the matrix element at $(x,y)$.

Suffix tree size can be stored along with the suffix tree and updated in constant time at each step by modifying the update procedure in Ukkonen's algorithm. For each update the size increases by the current number of leaves.

# Solution 2 - Preprocess unique query widths

This solution is harder to implement but requires less preprocessing work if there are few query widths. Preprocessing takes $O(n)$ time if there is only one query width.

For each query width $w$, use a sliding window of width $w$ and incrementally build a suffix tree. Remove the suffix starting one character to the left of the window by remove the longest suffix from the tree. At each step, the current number of substrings within the sliding window is the tree size.

All queries can then be answered in linear time by using the results of the precomputation.

Note: removing the longest suffix can be done by removing the oldest leaf of the suffix tree. It is not easy to implement correctly.

---
Tags: algorithms, strings, counting, subsequences
---


# Question
Title: Are there any computer science encyclopedias?
Consider the volume "The Princeton Companion to Mathematics" which has the broadest range of topics attempted by any book in the field.

Does a Computer Science counterpart exist?

# Answer
There are two that I've seen:

Also, Wikipedia could be considered containing a CS encyclopedia.
> 0 votes

---
Tags: reference-request, books
---


# Question
Title: textbook on the human brain for computer scientists/machine learning professionals?
The human brain as studied by neuroscientists, or neurobiologists, generally focus on what I would call

* implementation details (how specifically does information transport between synaptic channels, i.e. what are the chemical processes)
* vague generalities (e.g. about "memory" as a psychological concept and in very vague terms what types of memory there are without studying them mathematically)

There is nothing intrinsically wrong with this.

But I am interested in the brain as a computational system. Of course we don't yet understand the brain very well, but **is there a book on the brain that a computer scientist or machine learning professional could read to get a computational/systematic understanding of what we know about the brain?** e.g. what is the computational role of various neurotransmitters (without going into chemistry), etc.

# Answer
There is no "textbook" on this. However, there is a book! It is How to Create a Mind by Raymond Kurzweil, the director of engineering at Google. Excellent book that explains the brain from a computer-science perspective. It goes into a lot of detail.

Check out the intro sound bytes on Audible.

For a closer to the metal (i.e. actual implementations of models of the brain), check out Cognitive Architectures, such as ACT-R, Soar, CLARION, ICARUS, EPIC, LIDA, etc. Here is a survey.
> 1 votes

---
Tags: reference-request, neural-networks
---


title: Labeling half of a bipartite graph

text:
# Question
Title: Labeling half of a bipartite graph
Consider the following problem: let $(U \cup V, E)$ be a bipartite graph. Is it possible to label the vertices of $U$ with either $\`\`+"$ or $\`\`-"$ such that every vertex of $V$ is adjacent to a vertex labeled $+$ and a vertex labeled $-$?

This seems like a pretty natural problem, and I would be surprised if it hasn't been considered before. I'm not asking for someone to come up with an algorithm for this (although that would be great). Does this problem have a name?

Obvious it can be reduced to an integer linear program, which might be efficient in practice.

# Answer
> 1 votes
Your problem is known as *hypergraph 2-colorability*; the hypergraph has $U$ as vertices and the neighborhoods of vertices of $V$ as edges. Determining whether a hypergraph is 2-colorable is NP-complete.

---
Tags: algorithms, reference-request
---


# Question
Title: How will the value, A(2) be available in, line 2, if A(2) is being calculated in, line 3?
How will the value, A(2) be available in, line 2, if A(2) is being calculated in, line 3?

# Answer
The point is that it *doesn't* use the new value, it uses the old value. You want to take the current value of `A[i+1]` and use it to calculate a new value for `A[i]`. If you do each operation in order, you'll always do the operation which uses the old value, before overwriting it with a new value.

The problem is, when you vectorize this, you might end up changing `A[i+1]` at the same time as you're trying to read its old value. But ideally vectorization shouldn't change the result of a process, only how fast it runs. This is why you need the `TEMP` array, to keep the result the same.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: complexity of outputting the union of a collection of subsets of a set
This question concerns the time complexity of outputting the unions of subsets of a given set.

Given $m$ subsets of an $k$-element set, can the union of those sets be computed in linear time with respect to $m+k$? Or $(m+k)p(\log (m+k))$, where $p(x)$ is some polynomial? Or at least known is there a subquadratic algorithm (with respect to $m+k$)?

Any direction on this would be much appreciated.

# Answer
That's not possible. Any correct algorithm will have to read all of the input. The input size is $\Theta(mk)$, so that means any correct algorithm will have to have running time at least $\Omega(mk)$. $O(m+k)$ and $O(m+k) p(\log(m+k)))$ are not achievable.
> 1 votes

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


# Question
Title: Find the kth smallest element in an unsorted array of non-negative integers
I need to find the kth smallest element in an unsorted array of non-negative integer.

kth smallest element is the minimum possible n such that there are at least kth elements \<= n.

The rub here is that the array is read only so it can't be modified. Also i have to do it in constant space.

Can anybody help come up with the most optimal solution ?

# Answer
There is a simple randomized algorithm running in expected $O(n\log n)$ time. The algorithm is a variant of the better known algorithm QuickSelect.

The algorithm maintains a pair of values $a \leq b$, initially $-\infty$ and $+\infty$ (or, the minimum and maximum values of the array). At each round, it chooses a uniformly random element $c$ in the range $\[a,b\]$ from the array, and computes its order statistics, i.e., the value $\ell$ such that $c$ is the $\ell$th smallest element in the array.

* If $\ell = k$, then we return $c$.
* If $\ell \> k$, we replace $b$ with $c$.
* If $\ell \< k$, we replace $a$ with $c$.

If $a = b$ then we return $a$. Otherwise, we continue for one more iteration.

Each iteration takes time $O(n)$, so in order to estimate the running time of the algorithm, we need to estimate the number of rounds. We will keep track of the number of "live" elements, initially $n$. The algorithm ends when the number of live elements gets down to 1 (or even sooner, if there are repeated elements).

Let us denote by $n\_t$ the number of elements after $t$ rounds, so that $n\_0 = n$. The exact distribution of $n\_{t+1}$ given $n\_t$ depends on the location of the $k$th order statistics among the live elements. Let us suppose that the $k$th order statistics is the $\ell$th live element. Without loss of generality, $\ell \leq (n\_t+1)/2$. Suppose that we choose the $r$th order statistic, so $r$ is uniform over $1,\ldots,n\_t$. Then:

* If $r = 1,\ldots,\ell-1$ then $n\_{t+1} = n\_t - (r-1)$.
* If $r = \ell$ then $n\_{t+1} = 0$.
* If $r = \ell+1,\ldots,n\_t$ then $n\_{t+1} = r$.

In total, the expected value of $n\_{t+1}$ is $$ \frac{1}{n\_t} \[(n\_t + \cdots + n\_t-\ell+2) + (\ell+1 + \cdots + n\_t)\]. $$ The number of summands is constant, and the worst case is when $\ell = (n\_t+1)/2$, in which case the expected value of $n\_{t+1}$ is $$ \frac{(\frac{n\_t+1}{2}+n\_t)\frac{n\_t-1}{2}}{n\_t} \leq \frac{3}{4}n\_t. $$ Induction shows that $\mathbb{E}\[n\_t\] \leq (3/4)^t n$, and so the expectation drops below 1 for $t = O(\log n)$.

While this doesn't quite show that the expected number of iterations is $O(\log n)$, more refined arguments do, and they moreover show that the number of iterations is $O(\log n)$ with high probability.

---

Here are some hints on how to implement the algorithm. The crucial step is to choose a uniformly random element $c$ in the range $\[a,b\]$ from the array. There are at least two ways to go about it, both taking $O(n)$:

**Reservoir sampling**

1. Initialize $N = 0$ and $X = \bot$.
2. Go over all elements of the array. For each element $x$, if $a \leq x \leq b$:

* Increment $N$.
    * Replace $X$ with $x$ with probability $1/N$.
3. Return $X$.

**Linear scan**

1. Count the number of elements in the array between $a$ and $b$ — say the answer is $N$.
2. Draw a random integer $i$ between 1 and $N$.
3. Go over the array again, and return the $i$th element between $a$ and $b$.
> 4 votes

# Answer
Maybe you're looking for an obvious answer that satisfies the requirements.

You can loop through the array and find the smallest element ($x$) and how many times it occurs ($y$).

In the next loop you find the next smallest element ($x'\_{\>x}$) and add how many times it occurs to the count $y$.

Continue until $y$ reaches $k$. It takes $O(nk)$ time and constant space.
> 1 votes

---
Tags: algorithms, time-complexity, arrays
---


title: Complexity of polynomial interpolation

text:
# Question
Title: Complexity of polynomial interpolation
Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of unity, it can be interpolated in $O(n\log n)$ time with the Fast Fourier Transform. Or at least, that's the only situation that I am aware of that can be done better than $O(n^2)$.

Are there any other forms of input that can be interpolated in better than $O(n^2)$ time?

I am particularly interested in knowing whether or not there is an algorithm that interpolates a polynomial from evenly spaced points (in the x-coordinate that is) that beats $O(n^2)$, because I think I've come up with something that does it in $O(n\log n)$ time.

# Answer
> 3 votes
Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field has 2N (?) roots of unity. Both are based on Fast polynomial division. All three are $O(n\log^2 n)$ time.

Currently they are taught at university courses and I downloaded a lot of lecture notes some time ago. Unfortunately, most links are now dead. So you can download my archive from https://mega.nz/#!ugYRXIYB!T\_0cKabvJpZmBNN7ym98nofPIOksqTN5XFxToSKj9Zg

Or read the only course still available at the old address: http://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf http://people.csail.mit.edu/madhu/ST12/scribe/lect07.pdf

Or just look for up-to-date notes among google search results of ,  and . Or, yeah, try to understand the original paper.

---
Tags: reference-request, runtime-analysis, polynomial-time, polynomials, fourier-transform
---


title: Boolean expression to a truth table

text:
# Question
Title: Boolean expression to a truth table
How do I fill a truth table from the following expression? I can't decide whether it is SOP or POS.

```
Y=(A+B)C+AB`+(A+C)C`+(`AB)

```

# Answer
SoP or PoS doesn't matter when building a truth table, you just list out the 8 possible inputs and then derive the possible outputs.

If A B and C are all false what is the value of Y?

If only C is true what is the value of Y?

And so on.
> 1 votes

---
Tags: logic, boolean-algebra
---


# Question
Title: Recognize end of Input in a Turing Machine
If I have a turing machime TM, can I recognize end of input on the tape?

I know that the "end of input" in a turing machine is signaled with a special character, $\sqcup$.

Can I do this -

> Let $TM$ be a turing machine.
>
> Until we reach the first $\sqcup$, continue. If we reached $\sqcup$, replace it with a special character - #.

Is it "legal" to that this?

# Answer
> 2 votes
There are many possible input conventions for Turing machines. The one I know has the tape initialized by the input word (in case of a single input) surrounded by *blanks*, where a *blank* is a symbol of the tape alphabet that isn't in the input alphabet. The Turing machine treats all tape symbols in the same way, so you can do with them whatever you want.

Other conventions are also possible. For example, we might want to forbid writing *blank* for some reason. Only you know which convention is used in your class. The various input conventions are mostly equivalent, so in practice it usually doesn't matter which one is used.

---
Tags: complexity-theory, turing-machines
---


# Question
Title: Find the shortest sub-tree with node deletion
Let $T=(V,E)$ be a tree rooted in $r$ and let $L$ denotes the set of leaves of $T$. For a given $v \in V$, let $C(v)$ be the out-neighors of $v$ *i.e.* its children in $T$ and $p(v)$ be its in-neighbor *i.e.* its predecessor in $T$. We have a metric $d : V \times V \rightarrow \mathbb{R}^+$ (respecting the triangular inequality). The *length* of the tree is then $\sum\_{u \in V} d(u,p(u))$.

For a subset of internal non-root nodes $V' \in V \setminus (L \cup \\{r\\})$, the rooted *"sub-tree"* $T'$ corresponds to the tree we get after removing each $v\in V'$ and connecting its parent $p(v)$ to all $C(v)$. An example:

My problem is to **find the subset of internal $V'$ to remove such that the sub-tree $T'$ has the minimum length**. Below are some observations I made (maybe the problem is well-known but if it's not then they may provide some insight). Any remark/reference is most welcome!

## Steiner tree related problem?

My first thought was that this problem is a special case of the Steiner tree problem. We can construct a graph $G=(V,A,d)$ with $A = \\{(u,v) \in V \times V : u \text{ is an ancestor of } v \text{ in } T\\}$, edge length $d$ and $L$ as the set of terminal nodes. However a Steiner tree of $G$ may correspond to solutions that are impossible to get via node removal on $T$. Indeed, node removal preserves the siblings relations existing in $T$. This may not the the case for Steiner trees in G.

That being said I would be interested to know the complexity of the Steiner tree problem for graphs constructed like G. I suspect the problem to still be NP-hard. Note that the approximate solution obtained by taking a minimum spanning tree according to shortest-paths distances would be the star graph connecting the terminal nodes to $r$ (since $d$ respects the triangular inequality).

## Iterative/Recursive solution or approximation?

Assuming $T$ is of height $2$, we only need to check if each internal node $u$ respects the inequality

\begin{equation} \sum\_{l \in C(u)} d(l,r) \> d(u,r) + \sum\_{l \in C(u)} d(l,u) \text{ (Ineq. 1)} \end{equation}

and add it to $V'$ if it does not. In the general case, a possible approach is therefore to iteratively remove the nodes that do not respect the Ineq. 1. However, such "local" approach may lead to the best solution. For example assume the distances $d$ for the example in Figure 1 are (sorry for the formatting):

```
   d(.,.) | r | a | b | l_(1,2,3) | l_4 | l_5 |
   ____________________________________________
   r      | 0 | 2 | 2 | 1         | 3   |   1 |
   a      |   | 0 | 1 | 2         | 1   |     |
   b      |   |   | 0 | 1         |     |     |

```

Here Ineq. 1 is respected for both internal node $a$ and $b$. However, the shortest tree is the one obtained after the removal of both nodes.

I therefore tried to apply Ineq. 1 in a recursive fashion. I check it not only for the direct parent but for all the ancestors. The procedure is as follow:

**Procedure** ShortestSubTree$(T,u,d)$:

1. For $v \in C(u) \setminus L$ do
    * ShortestSubTree$(T,v,d)$
2. $a \leftarrow p(u)$
3. While $a$ is defined do
    1. If $\sum\_{v \in C(u)} d(a,v) \leq d(u,a) + \sum\_{v \in C(u)} d(u,v)$ then
        * remove $u$ from $T$
        * **stop**
    2. $a \leftarrow p(a)$

However it seems that ShortestSubTree removes too many nodes. In some experiment, the "iterative" approach can produce shorter sub-trees.

# Answer
> 1 votes
This can be solved with dynamic programming.

Define $A\[u,v\]$ as follows. Consider all trees obtainable by starting with the subtree rooted at $v$, removing some of the nodes, and making $u$ be the parent of all of the nodes with no parent. (Or, to put it another way: all of these trees are a subset of the subtree rooted at $u$; they contain $u$ as their root; and every node in them other than $u$ is either $v$ or a descendant of $v$.) Then $A\[u,v\]$ is defined to be the length of the minimal-length tree of this sort.

Notice that we have a recursive relationship for $A\[u,v\]$. In particular, if $w\_1,\dots,w\_k$ denote the children of $v$, then we have

$$A\[u,v\] = \min(d(u,v) + A\[v,w\_1\] + \dots + A\[v,w\_k\], A\[u,w\_1\] + \dots + A\[u,w\_k\]).$$

(Here the first term in the $\min$ corresponds to the case where $v$ is included in the tree, and the second term where $v$ is not included.)

As a result, we can compute all of the $A\[u,v\]$ values using dynamic programming. There are at most $O(|V|^2)$ many values to compute, and each one can be computed in $O(k)$ time where $k$ is the maximum degree of the tree, so the total running time is $O(|V|^2 k)$.

---
Tags: algorithms, graphs, optimization, trees
---


# Question
Title: Comparing turing based programming languages
According to Turing thesis, Can we say all programming languages that support turing machine like C have same power for solving problems and performing algorithms? In other words is there any algorithm or problem that one of them can solve it and the other can't?

# Answer
> 2 votes
The notion you are looking for is probably Turing completeness. All languages that are Turing complete are essentially equivalent in what problems they can solve (at least in principle). Most general-purpose programming languages are Turing complete.

---
Tags: programming-languages, church-turing-thesis
---


# Question
Title: Finding a non-boundary, local optimum of a non-convex function over a convex feasible region
I have a reasonably smooth non-convex non-monotone function in high(ish) dimensional space, that I wish to find a local minimizer for, over a convex feasible region (the intersection of a ball with a set of halfspaces, so a "wedge" of the ball or a polytope), with the caveat that I want the minimizer to be *away* from the boundary of the feasible region.

Are there any sound ways, or even just good heuristics, for doing that?

Edit: If all minimizers (or regions looking like minimizers) are around the boundary, then is there a way to detect that?

One idea I had is to use barrier functions near the boundary and then just use gradient descent, but the barrier functions might create false local minima...

Thanks!

# Answer
> 1 votes
Your question is not well-defined yet. You have described *two* criteria you want to optimize over: minimize the function, and be away from the boundary. You often can't simultaneously optimize both; the way to minimize the function might be near the boundary, and points away from the boundary might not minimize the function.

So, before you can solve this problem, you first must figure out how to formulate it in a well-posed way. Basically, you will have to decide how to trade off between your two goals. One way would be to define an objective function $\Psi(x)$ that is a sum of your function and some penalty term, where the penalty is larger the closer to the boundary you are. e.g.,

$$\Psi(x) = f(x) + 1/d(x),$$

where $f$ is your function and $d(x)$ is the distance from $x$ to the nearest point on the boundary of the feasible region. Then, you could try to minimize $\Psi(x)$. That's one possibility, but there are of course others. (This particular approach is sometimes known as a barrier method.)

Once you have formulated the problem, then you can select an optimization algorithm. Gradient descent would be a good starting point if the problem is high-dimensional and you can compute gradients. If the number of dimensions is not too large, you can also consider second-order methods, like Newton's method, trust region methods, and many others. The choice of method will depend on the properties of the function, and might also require some experimentation.

Alternatively, rather than treating both goals as soft goals to be balanced, you might decide that the "away from the boundary" is a hard requirement that absolutely must not be violated. Then you would define the region $\mathcal{R}$ of points that are away from the boundary (e.g., distance at least $D$ from the boundary, for some constant $D$ of your choice), and then your problem becomes to minimize $f$ over the region $\mathcal{R}$. There are a number of methods for doing that; you might start by trying projected gradient descent.

If you want to detect whether all minimizers are near the boundary, you can first find the absolute minimum within the feasible region (e.g., using gradient descent or projected gradient descent), then find the minimum within the region $\mathcal{R}$ of points that are away from the boundary (e.g., using projected gradient descent); if the latter is larger than the former, you know that all the minima are near the boundary (at least, up to the optimality of your optimization routine).

We can't tell you how to formulate your problem, because that depends on what you want to achieve, and only you know that. You will have to decide what your goals and requirements are, and then choose a formulation that matches your needs and goals.

---
Tags: optimization, machine-learning
---


# Question
Title: What is the complexity of this algorithm for sparse matrices?
I am reading a paper on sparse matrices and there is an algorithm for sparse lower triangular systems. In the below pseudo-code $l$ is a sparse matrix and $x,b$ are sparse vectors.

```
x=b
for j=0 to n-1 do
    if x[j] != 0
        for i=j+1 to n-1 do
            if l[i][j] != 0
                ~5 operations.

```

The paper claims that this algorithm is $\mathcal{O}(n+|b|+f)$, where $|b|$ is the number of non-zero entries in $b$ and $f$ is the number of floating point operations carried out.

I do not understand why this algorithm is not $\mathcal{O}(n|b|f)$.

Reference: Chapter 3 - Section 2 of https://epubs.siam.org/doi/book/10.1137/1.9780898718881

Some context on sparse matrices: Sparse matrices usually appear when solving problems using numerical schemes such as the finite element method. These matrices usually have a very small number of non-zero entries per row. For instance, a $n$-by-$n$ matrix might only have $\mathcal{O}(1)$ entries per row. The situation might not be as good as this in the algorithm above (there is no mention of a definition of sparse matrices in the book, as far as I can see.)

# Answer
They say the running time is $O(n+|b|+f)$, where $f$ is the number of floating point operations taken during the entire computation. This takes some careful reading to understand what they mean.

They mean, if you take the total number of floating-point operations that are performed inside the innermost loop, and call that $f$, then the running time is not too much more than $f$. In other words, they are saying we do $O(n+|b|)$ operations for updating the loop indices, plus the time taken by the body of the innermost loop (summed over all the iterations).

The body of the innermost loop might indeed take $5 n|b|$ operations in total (say), in which case the total running time would be $O(n + |b| + 5n|b|) = O(n|b|)$, as you had expected.

Note that $f$ is not the number of floating point operations in a single iteration of the innermost loop; it is the total across all iterations of the loop. So $f$ is not 5.

Why do they count it this way? Presumably, the floating point operations are ones that we'll have to do no matter what, because they are essential to the operation you're doing; they instead want to focus on the extra book-keeping needed to update loop indices etc. and make sure that doesn't add too much extra cost.

Finally, I'll note that you changed the pseudocode. The pseudocode they show is not the same as what you listed in the question. In the book the pseudocode of the innermost loop is not "for $i=j+1$ to...", but rather "for each $i\>j$ for which $l\_{ij}$". That's not the same. Since $l$ is a sparse matrix/vector, there are more efficient ways to iterate over the non-zero entries of $l$ than iterating over all possible values of $j$ and testing whether that element is non-zero. This also affects the running time.
> 1 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: What is shell expansion in programming language theory?
From Bash Reference Manual

> Expansion is performed on the command line after it has been split into tokens. There are seven kinds of expansion performed:
>
> * brace expansion
> * tilde expansion
> * parameter and variable expansion
> * command substitution
> * arithmetic expansion
> * word splitting
> * filename expansion

From the programming languages perspective, are shell expansions of the same kind of pre-defined compiler macros in C?

What is the concept for shell expansions called in programming languages?

# Answer
Shell languages and scripting languages have specific features adapted to the context of their use. Such features may not exists in that form in more classical programming languages as they would not be inappropriate for their context of use.

A shell language has to assist the user and make him productive in an interactive context, often for commands that are executed only once and then forgotten. Syntactic preprocessing of commands for common needs, use of abbreviation, and such, is part of the interactice help provided.

Programming languages must be often more explicit, more verbose and less context dependent, as they live long and have to be maintained, which requires them to be very readable by a variety of people. Hence, in the context of a programming language, these fonctionalities may be used, but have to be explicitly called as subprograms applied to the concerned data, rather than be implicit in the shell preprocessing of a command to be executed on the spot.
> 1 votes

# Answer
# Compiler directives or macros.

To give a full idea of how complex this gets, consider that in 9 characters I can write:

```
$ echo {,*}.{,*}
. . .. .git .gitignore *. file.md package.json package-lock.json README.md report.ts
tsconfig.json

```

This is first being expanded to `echo . .* *. *.*` by the `{,*}` expansions, which is then being expanded based on directory globbing rules, so `.` is just a literal string while `.*` is globbing to `. .. .git .gitignore` while `*.` is not matching anything so it is again a literal string (though I think this depends on whether a bash globbing setting is flipped or not) and `*.*` is matching the other files in the directory that have at least one period in the middle of their filename, `file.md package.json package-lock.json README.md report.ts tsconfig.json`.

Or even worse,

```
$ {ec,}{ho,}
ec ho

```

So we are performing what in Haskell would look like `[a ++ b | a <- ["ec", ""], b <- ["ho", ""]]` before any sort of evaluation is taking place, this yields `["echo", "ec", "ho", ""]`, and only after that is this used to produce the string `ec ho\n`, six characters all told including the newline. In Haskell we would call this composition "in the List Monad", it is I believe distinct from what Lisp macros can do, that being "unquote splicing".

The obvious mental model to appeal to is **a multi-pass compiler**. You have some lexical analysis which is tokenizing the string into "words", then a bunch of passes are going through through those "words" to get to the final command that will be executed. So for example in `echo ~{crdrost,$HOME}` we see first a tokenization to `echo` and `~{crdrost,$HOME}`, there are then three rules being applied in sequence:

1. A brace expansion of the latter to two words, `~crdrost` and `~$HOME`,
2. A tilde expansion which checks whether `crdrost` is a valid user (I am!) and replaces with `/home/crdrost`, versus whether `$HOME` is a valid user (it is not!) and therefore doesn't replace.
3. Then there is the variable substitution in `~$HOME` to `~/home/crdrost`.

After these "compiler passes" are done we have something which can be evaluated; we look up the `echo` builtin function and apply it to the argument strings to produce the string `/home/crdrost ~/home/crdrost\n`, the words are emitted separated by single spaces followed by a newline character.
> 1 votes

---
Tags: programming-languages
---


title: Circular queue problem

text:
# Question
Title: Circular queue problem
In ciruclar queue the following command statement is very useful to use the determine the unused location. What is its importance? I know that without this line it won't be a circular queue. But how to say it in theoretical way?

### rear=(rear+1)%max

# Answer
> 6 votes
Suppose that we arrange the numbers $0,\ldots,n-1$ in an oriented cycle. The number which follows $i$ is $i+1$ for $i \neq n-1$, and $0$ for $i=n-1$. We can combine both cases by saying that the number following $i$ is $i+1 \bmod{n}$.

---
Tags: data-structures, programming-languages, queues
---


# Question
Title: Why do we discard the constant 1 in proving that $2^{n+1} = O(2^n)$
In this post someone said:

> $n + 1$ is approximately equal to 1 for $2^{n+1} = O(2^n)$.

I don't understand this point. For example, in this example:

$$ n + 1 \leq c \cdot n $$

for some $c$ and some $n \geq n\_0$, the right-hand side will always be at least the left-hand side.

But here: $$ 2^{n+1} =O(2^n)$$

the left-hand side will always exceed the right-hand side.

# Answer
No, there exists such a constant. Indeed take $c=2$, then $$\forall n \in \mathbb{N}\quad 2^{n+1}=2^1 \cdot 2^n \le c \cdot 2^n.$$ So $2^{n+1}=O(2^n)$.
> 3 votes

---
Tags: algorithm-analysis
---


# Question
Title: Does the space complexity of a recursive algorithm depend on the total no of recursive calls?
I am confused whether space complexity of a recursive algorithm depends on the total number of recursive calls or not.

Say I have an algorithm which has exponential function calls, but stack size is linear, so in that case we can say that space complexity is not proportional to number of recursive calls but if we say that does it depend on the total number of recursive calls or not, then does it make sense to make such a statement because after all stack is made because of the recursive calls only?

So is it better to say that "stack size depends on the recursive calls but not on the total number of recursive calls"? Is this statement valid?

# Answer
Yes, that's right.

The statement "space complexity is $f(n)$" means that, if we had only $f(n)$ memory and no more, it would still be possible to run the algorithm.

As an example, say we are generating all permutations of length $n$ recursively. Then we make $c\_1 \cdot n!$ recursive calls but, at every moment, use at most $c\_2 \cdot n$ memory. A hypothetical machine with $c\_2 \cdot n$ memory, and no more, would still run the algorithm correctly.

The space complexity depends on the structure of recursive calls, not simply on their number.
> 3 votes

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


# Question
Title: Why do we consider the order of growth when analyzing algorithms?
Seriously why do we consider how the computation time time increase with the number of inputs as a measure of performance when we can easily measure such as program execution time,power consumption,memory usage etc?Because all of these facts are depends on the hardware and programming language we use in that moment and order growth is only depends on inputs?

# Answer
I think the key point in time complexity analysis is it can give us a metric to measure the time independent of any hardware or software dependency directly.

Hence, we can talk about the time complexity based on inputs and outputs of the problem without considering more sophisticated or even complex cases by mentioning that we are talking about the hardware or software specifications.

However, hardware usage is mentioned in some real applications too, somewhere the time complexity can't distinguish the solutions in its abstract asymptotic definition. These kind of analysis are common in AI algorithms which have the same time complexity but have some real differences in real applications and hardware usage. For example, in real applications "Quick Sort" is better than "Merge Sort" because we have a large constant factor in "Merge Sort" time complexity, however, on the paper, in time complexity, "Merge Sort" is better than "Quick Sort" in worst cases.

In sum, time complexity base on the growth can be proper to compare algorithms independent of any hardware or software specifications, although hardware usage in real applications makes sense more!
> 2 votes

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


# Question
Title: Difference between regular language and context free language
What is nature of difference of regular language and context free language?

My guess is

```
RL - CFL = RL
CFL - RL = CFL

```

Am I correct with this?

# Answer
> 3 votes
No, those are not quite correct.

For any alphabet $\Sigma$, the language $\Sigma^\*$ is regular. The set difference between that and any CFG with the same alphabet is the complement of the CFG, and CFGs are not closed with respect to complement. So your first claim is incorrect.

However, CFGs are closed with repect to intersection with a regular language and regular languages are closed with respect to complement. Thus, your second claim is correct.

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


# Question
Title: DFA that accepts two more $1$'s than $0$'s
What is the state diagram of a DFA that follows

$L = \\{w \in \\{0,1\\}^\*\mid w\text{ has at least two or more 1's than of 0's}\\}$.

Examples: $110$ doesn't work, $1110$ works.

# Answer
As mentioned this is not a regular language.

To prove this, recall that a language, $L$, is regular iff some DFA recognizes it.

We will show that no DFA recognizes $L$. Consider the infinite set of strings $S=\\{0^n : n \ge 0\\}$. Then any two strings in $S$ are of the form $\alpha=0^x$ and $\beta=0^y$, $x,y\ge0$, we may assume wlog that $x\>y$.

Let $\lambda=1^{y+2}$.

Then $\alpha\lambda=0^x1^{y+2} \notin L$ (since $x\>y \implies y+2 -x \< 2$), but $\beta\lambda=0^y1^{y+2} \in L$.

Thus we have an infinite set of strings (prefixes), $S$, such that for every pair of distinct strings $\alpha,\beta \in S$ there exists another string (suffix) $\lambda$ where exactly one of $\alpha\lambda$ or $\beta\lambda$ is in $L$. Thinking about this, this means that if a DFA, $D$, recognizes $L$, then every string in $S$ must take $D$ to a different state (if $\alpha,\beta \in S$ both took $D$ to the same state then so would $\alpha\lambda$ and $\beta\lambda$ for any $\lambda$, but we know that only one of these strings is in $L$). So $D$ must have at least $|S|$ states, but $|S|=\infty$, thus $D$ cannot exist.
> 3 votes

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


# Question
Title: "Semantic Web", "Semantic Network", "Semantic Search", "Knowledge graph"(not Google's Knowledge Graph) and "knowledge base"
who can help me explain the concepts of "Semantic Web", "Semantic Network", "Semantic Search", "Knowledge graph"(not Google's Knowledge Graph) and "knowledge base" and the relations among them?

# Answer
Semantic Web is a set of technologies that want to make the data on the web readable and understood by machines. The domain that semantic web is the web. Therefore the URI is in the bottom of the technologies stack.

Semantic Network is a graph model to store the information. If you can model your data as a graph with node and edge, you can think it as a semantic network.

Knowledge graph is also a kind of graph model. However, it emphasis the store of all data on the level of both schema and individual. Therefore, it has no essential difference with Semantic network. Knowledge base is an instantiated storage of a domain knowledge. You can think it as a database. It has not to be a graph model, if you can store the knowledge in some way, you can call it as knowledge base.
> 7 votes

---
Tags: knowledge-representation
---