# Question
Title: Possibility of using loops instead of traps
Draw DFA for the language of all strings starting with $a$ and ending with $b$.
Now what I have done is

Here I used q3 as a trap.
But could I do this instead?

I have not used trap in the 2nd solution and used a self loop instead.

# Answer
> 1 votes
Your first DFA is minimal. To see this, for each pair of states $q\_i \neq q\_j$ we need to come up with a word $w$ such that $\delta(q\_i,w) \in F$ and $\delta(q\_j,w) \notin F$, or vice versa, where $F$ is the set of accepting states.

Here is such a list of words:

* $q\_0,q\_1$: $\delta(q\_0,b) \notin F$ and $\delta(q\_1,b) \in F$.
* $q\_0,q\_2$: $\delta(q\_0,\epsilon) \notin F$ and $\delta(q\_2,\epsilon) \in F$.
* $q\_0,q\_3$: $\delta(q\_0,ab) \in F$ and $\delta(q\_3,ab) \notin F$.
* $q\_1,q\_2$: $\delta(q\_1,\epsilon) \notin F$ and $\delta(q\_2,\epsilon) \in F$.
* $q\_1,q\_3$: $\delta(q\_1,b) \in F$ and $\delta(q\_3,b) \notin F$.
* $q\_2,q\_3$: $\delta(q\_2,\epsilon) \in F$ and $\delta(q\_3,\epsilon) \notin F$.

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


# Question
Title: Measuring the length of a "loop" in a linked list in $O(n)$ Time?
I have been given a linked list in Python. At some point, one of the nodes is linked to a previous node creating a "tail" and a "loop":

Node1 -\> Node2 -\> Node3 -\> Node4 -\> Node5 -\> Node6 -\> Node3

Node1 and Node2 are considered elements of the "tail", while Node3, 4, 5 and 6 are considered elements of the "loop". My task is to measure the length/number of elements in the "loop".

My approach was to go through the linked list and catch, when a node points towards a node, I have already passed.

However, to check if a node has been already passed, I have chosen to store all passed nodes into a list/array. Whenever I approach the next node, I check, whether the next node is already stored in the list/array.

This approach does work, however I was hinted, that there is a way to solve this in linear complexity.

If the linked list consists of n nodes I am adding 1 element to a list with each node and I am also checking every element in this list with each node

I assume the complexity is something like : $\frac{n^2 + n}{2}$ which is clearly not ideal.

However I struggle to find a way to check whether I have already passed a node, without checking all previous nodes with every step. Which again would make it necessary to

1. Keep a list of all previous nodes and
2. Loop over this list in each step

which then again would increase the complexity.

Is there a way to check, whether I have already passed a node, without checking on all previous nodes?

# Answer
There is a surprisingly simpler solution! Are you familiar with the tortoise and hare algorithm?

Start thinking from there: Understand this algorithm and *why* it works, and then you might get an idea or two for the problem
> 4 votes

---
Tags: algorithms, linked-lists
---


title: CVRP and removing edges from a graph

text:
# Question
Title: CVRP and removing edges from a graph
I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances. I know that, in general, the complexity of the problem in terms of the number of variables (and computational time) increases with the number of edges in the graph. I also know that for particular graphs where node degree is fixed (for example 3 or 4), polynomial-time algorithms exist that return the optimal solution. Therefore, I am playing around with removing the edges with the highest weight from the graph, while ensuring each node retains at least a minimum degree, and seeing how this impacts solution time. As expected, reducing the number of edges in the graph does impact the solution time significantly.

Are there any theoretical results that tie this idea of removing edges from the graph before solving the problem to the optimality of the solution? Is it in some cases possible to conclude, a-priori, that some specific edge will necessarily NOT be part of the optimal solution?

# Answer
I don't know anything about routing, so take this with a grain of salt.

What you have is a metric graph, in that your graph satisfies the triangle inequality. If you start removing edges, then *heuristic algorithms* might have less to work with, which isn't obviously better.

Take for example a look at these questions:

---

Taking *removing edges to the extreme* is actually how Christofides algorithm works for approximating Travelling Salesman; Namely by finding a Minimum Spanning Tree and deleting all the remaining edges.
> 1 votes

---
Tags: graphs, heuristics, traveling-salesman
---


# Question
Title: Does Ford-Fulkerson always produce the left-most min-cut
When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.

However, if you then use the left-over residual graph to produce a min-cut (by flood-filling outward from s along any edges or reverse edges with left-over capacity), it seems the same cut is obtained regardless of which flow-graph you use.

Is this true?

Is there a way to iterate over all cuts such that each iterator-step requires only polynomial time?

# Answer
> 6 votes
Yes, Ford-Fulkerson always finds the cut that is "closest" to the source. See this question for a formalization of what is meant by "closest".

A graph can contain exponentially many min-cuts, so beware that any procedure to enumerate all min-cuts must take exponential time in total in the worst case.

Based on what I've read, there are output-sensitive algorithms to enumerate all min $(s,t)$-cuts. After a single maximum flow computation, the running time is $O(n)$ per min-cut that is output. Details can be found in the following paper:

Jean-Claude Picard, Maurice Queyranne. On the structure of all minimum cuts in a network and applications. Combinatorial Optimization II: Mathematical Programming Studies, volume 13, 1980, pp.8--16.
Unfortunately, there does not seem to be a non-paywalled online version of the paper.

(See also here for a related question.)

---

In contrast, if you want to find all min-cuts of an undirected graph, rather than all min $(s,t)$-cuts, you can use Karger's algorithm to do that efficiently (in polynomial time).

# Answer
> 1 votes
Just adding to the answer of D.W.. Following is a simple example of a graph network that contains an exponential number of $(s,t)$ min cuts.

Let the vertex set be $V = \\{s\\} \cup \\{u\_{1},\dotsc,u\_{n}\\} \cup \\{v\_1,\dotsc,v\_n\\} \cup \\{t\\}$. Let the edges set contains the directed edges $(s,u\_{i})$, $(u\_{i},v\_{i})$, and $(v\_{i},t)$ for each $i \in \\{1,\dotsc,n\\}$. Therefore, there are total $3 n$ edges. Each edge has capacity $1$.

The max-flow on this network is $n$.

The min-cut cut obtained using Ford-Fulkerson algorithm is $\left(\\{s\\}, V \setminus \\{s\\}\right)$.

There are other $(s,t)$ min cuts in the graph as follows. Let $C = (S,T)$ be a cut such that $S$ contains the vertex $s$ and all the vertices in the set $\\{u\_1,\dotsc,u\_n\\}$. It is optional to include a vertex $v\_{i}$ in the set $S$. The remaining vertices, i.e., $V \setminus S$ belongs to $T$. Any such cut has a capacity $n$. Therefore, it is a min-cut. Since there are $2^n$ choices of including $v\_{i}'s$, the total number of min-cuts are $2^n \in 2^{O|V|}$. Hence, we get an exponential number of min-cuts.

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


# Question
Title: Set theory pertaining to category theory and functional programming
I'm reading an unfinished Introduction to Category Theory/Products and Coproducts of Sets and have come across the following:

> A power set of a set is the set of all its subsets. A script 'P' is used for the power set. Note that the empty set and the set itself are members of the power set. \begin{equation}\mathcal{P}\\{1,2,3\\} = \\{\varnothing,\\{1\\},\\{2\\},\\{3\\},\\{1,2\\},\\{1,3\\},\\{2,3\\},\\{1,2,3\\}\\}\end{equation} Set operations are functions from the product of a power set to a power set. \begin{equation}\text{Union}:\mathcal{P}(X) \times \mathcal{P} \to \mathcal{P}(X), \text{Union}(A,B) = A \cup B\end{equation}

I don't understand the last part.

To me a product of a power set should equate to a set of tuples where the first of the ordered pair is a subset from first power set and the second is a subset from the second power set. Whereas a power set is just a set of subsets.

How can this mismatch be explained or is it a mistake?

---

Taking on board the advice below:

If the set $X$ is a singleton value $1$, then: \begin{equation}X = \\{1\\}\end{equation} The power set of $X$ is then: \begin{equation}\mathcal{P}(X) = \\{\varnothing,\\{1\\}\\}\end{equation} The product of $\mathcal{P}(X)$ is then: \begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \\{(\varnothing,\varnothing),(\varnothing,\\{1\\}),(\\{1\\},\varnothing),(\\{1\\},\\{1\\})\\}\end{equation} Applying $\text{Union}$ to the $\mathcal{P}(X)\times\mathcal{P}(X)$ is: \begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) = \\{(\varnothing,\varnothing)\mapsto\varnothing,(\varnothing,\\{1\\})\mapsto\\{1\\},(\\{1\\},\varnothing)\mapsto\\{1\\},(\\{1\\},\\{1\\})\mapsto\\{1\\}\\}\end{equation} As the result is a set, duplicates can be removed: \begin{equation}\\{\varnothing,\\{1\\},\\{1\\},\\{1\\}\\} = \\{\varnothing,\\{1\\}\\}\end{equation} Thus: \begin{equation}\mathcal{P}(X)\times\mathcal{P}(X) \to\mathcal{P}(X)\end{equation} And so the set operation of $\text{Union}$, which is one of a family of set operations (a set of functions) is a function from the product of a power set to a power set

# Answer
> 7 votes
The notation $f:E\times F \to G$ means that $f$ is a function that needs two arguments, one from $E$, one from $F$, and the image is in $G$.

This is how the function $\text{Union}$ is defined: the two arguments $A$, $B$ are in $\mathcal{P}(X)$ and the image $\text{Union}(A, B) = A\cup B$ is in $\mathcal{P}(X)$.

# Answer
> 4 votes
As you have said, $X\times Y = \\{(x,y) \mid x\in X, y\in Y\\}$.

Thus, a function $f:X\times Y\rightarrow Z$ would get two arguments: one from $X$ and the other from $Y$, and output a value from $Z$. Formally, this is written as $f((x,y))=z$, and to reduce the number of brackets, its usually written as just $f(x,y)=z$.

In your case, $f$ is a function that computes the union: It takes two elements from $A,B\in P(X)$ and outputs $A\cup B\in P(X)$.

---

For clarity, the formal definition of $P(X)$ is given by:

\begin{equation}P(X):=\\{A\mid A\subseteq X\\}\end{equation}

Is the set of all subsets of $X$.

# Answer
> 3 votes
The product of a power set to a power set is, indeed, "a set of tuples where the first of the ordered pair is a subset from first power set and the second is a subset from the second power set", to use your own words.

What you reported, though, is the definition of the Union operation. You can think of it as a function that associates an element of the set "tuples..." to an element of the set P(x). In particular, the Union operator, when applied to a pair of subsets, returns a single subset that is the union of the two subsets in the tuple.

---
Tags: sets, functional-programming, category-theory
---


# Question
Title: Has it been shown or can we show that if $SAT \in P$ then SAT can't be in any complexity class C so that $C \subsetneq P$?
I'm already guessing that the answer is no because we cannot know whether there is a class "in between" already known classes? Or can we?

I am very new to complexity theory.

Thanks for any answer in advance!

EDIT: Now that I think about it again, what I am asking is if SAT was in P, could we show that SAT could not be in any class less complex than P? Or could not be in any class that requires as much time complexity as P?

# Answer
SAT is NP-hard with respect to NC$^0$ reductions, and in particular, it is P-hard with respect to NC$^0$ reductions.

Now let $C$ be a complexity class which is closed under NC$^0$ reductions. If SAT is in $C$ then every problem in P can be reduced to $C$ using NC$^0$ reductions, and so belongs to $C$, implying that $C$ contains P.
> 4 votes

---
Tags: complexity-theory, satisfiability
---


# Question
Title: proving that if graph has perfect elimination order than the graph is perfect
I need help with this problem: Let say that G has a perfect elimination order, than I have to prove that G is perfect. Can someone help me with that? I've tried to solve it with induction but I did not succeed..

# Answer
Here's a route you can take.

Prove (or use the fact) that a graph is chordal iff it has a perfect elimination order. Now, it will suffice to show that a chordal graph is perfect. For that, you can take the strong perfect graph theorem stating that a graph is perfect iff it contains no odd hole and no odd antihole. Proceed by contradiction.
> 1 votes

---
Tags: graphs
---


# Question
Title: Dynamic programming and probability - list of problems
Does anyone have a list of problems where you have to combine dynamic programming with probability?

# Answer
> 1 votes
You can use search on this site to find some examples: https://cs.stackexchange.com/search?q=%5Bdynamic-programming%5D+probability

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


# Question
Title: Is the kernel loaded into memory for every user simultaneously using a Multi-User O.S. system?
I have a doubt about loading kernel for every user using a Multi-User system. Every user's processes and programs are scheduled to CPU in a time-sharing fashion. But, do every user on the multi-user system have their individual kernel loaded in the main memory, or is there only one kernel loaded which is sort of distributed amongst the users?

# Answer
> 3 votes
The shell (or window manager) which provides a visual interface is *not* part of the kernel. It's a simple user process and it runs in userspace without elevated privileges. In order for the user to "log in", which involves associating their terminal with the shell (or window manager), a login manager is needed. This program does run with elevated privileges, but it is also not part of the kernel. And there is only one instance of it.

Almost all user processes interact at some point with the kernel, usually by triggering a software interrupt which is caught by the kernel and triggers some kind of kernel request handler. There is only one copy of the executable image which contains kernel functions, but each handler needs to run independently and normally requires some transient storage. This would most naturally be stored on a stack, as with the transient storage for any ordinary procedure. However the "kernel stack" for a process is provided, it will by unique to the process. But it's usually not very big at all.

# Answer
> 1 votes
The multi-user operating system is also a single machine which is desiged to allow multiple users to connect to it at the same time. so you can imagine it as a unix server and users have access to it. so at the end there is just the kernel of the server(or multi-user OS in this case)

---
Tags: operating-systems, multi-tasking
---


# Question
Title: Is there any practical trick to mentally count in Gray code?
*When I was fairly young, I taught myself to count in binary. I thought it would be a fun party trick to impress people. I soon found out that it was not.*

Over the years I've come to appreciate Gray code/reflected binary code for its property of only flipping one bit for each increment/decrement of the underlying count. But I've always been bothered by the fact that, if I wanted to mentally take any arbitrary Gray code and add or subtract 1 from it, I'd have to either convert it to and then back from its numeric value, or construct a table to work out what the next code should be.

It seems to me that there should be some trick that a person with "average" short term memory and addition skills should be able to do to take any arbitrary value in Gray code and figure out which bit to flip to get the next value... But I've never found it.

Does such a thing exist?

# Answer
> 5 votes
I have a solution that I just found looking at the patterns, and I checked the pattern up to decimal 31 or binary 11111 or Gray 10000, and it worked quite fine, and I am confident enough the answer will carry through larger values too.

Take a Gray code, and count the number of 1's:

Case I:
Odd number of 1's: flip the bit one position before the last '1'.
Case II:
Even number of 1's: flip the last bit.

Examples:

> Even case: After 10100101, the next one is 10100100.

Explanation: there are 4 1's so we apply the even case, i.e., flip the last bit.

> After 111011010, the next one is 111011011.

Explanation: there are 6 1's so we again flip the last bit.

> Odd case: After 110111, the next one is 110101.

Explanation: there are 5 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.

> After 1100100, the next one is 1101100.

Explanation: there are 3 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.

I hope this helps!

# Answer
> 2 votes
The title of my masters thesis was *Efficient Hardware Implementations of Gray Code Arithmetic*. The goal was to find a way to, at the digital hardware level, perform arithmetic on Gray code directly without first converting to binary. Spoiler alert: I never did find a way to do that. What I **did** find was a way to convert from Gray code to binary more quickly (in logarithmic rather than linear time). If I'm remembering correctly, converting from binary back to Gray code is already fast.

Now I **did** come up with a fast Gray code numeric comparitor, i.e. a circuit that could compare the value of two numbers expressed in Gray code, that did not require initial conversion to binary.

# Answer
> 1 votes
Wikipedia describes a very simple algorithm for this task:

> To construct the binary-reflected Gray code iteratively, at step 0 start with the $\text{code}\_0 = 0$, and at step $i \> 0 $ find the bit position of the least significant 1 in the binary representation of $i$ and flip the bit at that position in the previous code $\text{code}\_{i-1}$ to get the next code $\text{code}\_i$.

Source: https://en.wikipedia.org/wiki/Gray\_code#Constructing\_an\_n-bit\_Gray\_code

This is certainly simple enough to do in your head.

This works if you are willing to start at 0 and increment one at a time (since then you can remember how many times you've incremented), but if someone else is going to give you an arbitrary bitstring and ask you to find the next Gray code, this isn't of any use (it would require converting the Gray code back to an ordinary integer, which might be harder).

# Answer
> 1 votes
Gray codes are hamilton cycles in hypercube graphs $Q\_n$, which can be recursively constructed using Hamilton cycles in $Q\_{n-1}$. Perhaps you can do these computations by hand for small n and see if that helps.

---
Tags: arithmetic, encoding-scheme, number-formats
---


# Question
Title: Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma
I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof. The language is

$$L = \\{ a^n b^m \mid n \leq m^2 \\}$$

Assume Demon picks $p$ and I choose $s = a^{p^2}b^p$ and $s = uvwxy$ such that $p \geq |vwx|$.

The first case is $vwx = b^j$. If we choose $i = 0$ everything is ok and the relationship isn't right.

The second case is $vwx = a^j$. If we choose $i = 2$ every thing is ok.

I get stuck when $vwx = a^j b^k$. How can I finish the proof in this case?

Did I choose the right string? I repeated them for $s = a^{p}b^p$ but it didn't work.

# Answer
When $vwx = a^j b^k$, there are two possibilities:

* $v$ contains both $a$s and $b$s, or $x$ contains both $a$s and $b$s. In this case $uv^2wx^2y \notin a^\*b^\*$, and in particular $uv^2wx^2y \notin L$.
* $v = a^s$ and $x = b^t$, where $s,t\>0$ and $s+t \leq p$ (since $|vwx| \leq p$). In this case, $uv^0wx^0y = a^{p^2-s}b^{p-t}$, and so $p^2 - s \leq (p-t)^2 \leq (p-1)^2$, which translates to $s \geq 2p-1$, which is impossible, since $s \leq p-1$.
> 3 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: Find minimal spanning tree of graph with edge values from 1 to 5 integers
How can I find the minimal spanning tree of graph with edge values from 1 to 5 integers (no need to be unique) most effectively? I know I can use Kruskal algorithm, but how can I modify the algorithm to find it faster when I know there are edges with values only 1, 2, 3, 4 or 5? I cant figure it out how it could be faster when I know this limitation on edges.

# Answer
Take a look at the complexity of Kruskal's algorithm. Since the edges are with integer weights, you can sort them in linear time. The entire algorithm will take a total of $O(|V|\alpha(|E|)+|E|)$. We need $O(|E|)$ to sort, and an additional $O(|V|\alpha(|E|))$ for Kruskal's algorithm.
> 1 votes

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


# Question
Title: How to prove that the reduction relation is not symmetric
I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show two languages $L\_{1},L\_{2}$ so $L\_{1}\leq L\_{2}$ and $L\_{2}\not\leq L\_{1}$. My textbook suggests to use $L\_{1}\triangleq\Sigma^{\*}$ and $L\_{2}\triangleq HP$ and show that $L\_{1}\leq L\_{2}$ and $L\_{2}\not\leq L\_{1}$. So I need to split the proof into two sections:

* Prove $L\_{1}\leq L\_{2}$ \- Stuck. Not sure how to prove it formally.
* Prove $L\_{2}\not\leq L\_{1}$. I want to use that $HP\not \in R$. So lets assume by contradiction that $HP\leq\Sigma^{\*}$. This means there such function $f\\,:\\,\Sigma^{\*}\to\Sigma^{\*}$ between $HP$ and $\Sigma^\*$. How to continue?

The definition of reduction: Given two languages $L\_1$ and $L\_2$, we say that there is reduction from $L\_1$ to $L\_2$ (and mark $L\_1\leq L\_2$) if there is a function $f\\,:\\,\Sigma^{\*}\to\Sigma^{\*}$ so:

* $f$ is full - for each $x\in \Sigma^\*$ there is one $y\in \Sigma^\*$ so $f(x)=y$.
* $f$ can be computed - there is a Turing machine that can compute $f$.
* fulfils: $x\in L\_1$ iff $f(x)\in L\_2$.

As formality is important, how do I fill the blank spaces up to the full proof?

# Answer
In order to show that $L\_1 \leq L\_2$, we need to come up with a computable function $f$ such that $x \in L\_1$ iff $f(x) \in L\_2$. Since $L\_1 = \Sigma^\*$, every $x$ satisfies $x \in L$, and so we need to find a computable function $f$ such that $f(x) \in L\_2$ for all $x$. The easiest way to satisfy this is to choose $f$ to be a constant function.

In order to show that $L\_2 \not\leq L\_1$, we need to show that $f$ is a computable function that it is *not* the case that $x \in L\_2$ iff $f(x) \in L\_1$. That is, we need to show that for every computable $f$ there exists $x$ such that it is *not* the case that $x \in L\_2$ iff $f(x) \in L\_1$. Since $L\_1 = \Sigma^\*$, we always have $f(x) \in L\_1$, so the only way in which "$x \in L\_2$ iff $f(x) \in L\_1$" can fail is if $x \notin L\_2$. That is, we need to show that for every computable $f$ there exists $x$ such that $x \notin L\_2$. The goal doesn't involve $f$, so it suffices to show that there exists $x$ such that $x \notin L\_2$.

You take it from here.
> 1 votes

---
Tags: complexity-theory, computability, reductions
---


# Question
Title: An algorithm that finds ord(a) in $O(\log n)$
Let $p$ be a Fermat prime ($p=2^m+1$) and $n=p2^k$ and $a∈Z^\*\_n$, I should suggest an algorithm that will find $\operatorname{ord}(a)$ in polynomial time (that is, in time polynomial in $\log n$).

I showed that if $n$ is the above then $φ(n)$ is power of 2.

For example: let $m=k=2$ so $n=5\cdot4=20$ and $φ(20) = |{1, 3, 7, 9, 11, 13, 17, 19}| = 8 = 2^3$

Let $a=7$:

$7^1 \bmod 20 = 7$, $7^2 \bmod 20 = 9$, $7^3 \bmod 20 = 3$, $7^4 \bmod 20 = 1$

so $\operatorname{ord}(7) = 4$

But I don't get how can I use that to find such algorithm.

# Answer
> 2 votes
Suppose that $\phi(n) = 2^m$; note $m \leq \log n$. The order of $a$ is thus $2^k$ for some $k \leq m$; in fact, it is the minimal $k$ such that $a^{2^k} \equiv 1 \pmod{n}$. You find find this $k$ by repeatedly squaring $a$.

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


# Question
Title: NFA designing for strings starting with $01$
The question was asked

> Construct an NFA with set of all strings that start with $10$.

The solution provided to me is

But my question is what if the automaton receives an input $0$ at the starting? Also there is no option for $q\_1$ to transit after receiving $1$. So I think the solution should be

Please correct me if I am wrong.

# Answer
> 1 votes
Since this is an NFA, the solutions are equivalent. When you are in a state without any transition for the current input you receive, you terminate (equivalent to getting stuck in a non-accepting state without going out of it).

---
Tags: finite-automata, transition-systems
---


title: Is RAM always volatile?

text:
# Question
Title: Is RAM always volatile?
I understand that computer memory in typical modern computing systems (such as the laptop I am asking this question from) is generally involatile but in some exceptions, such as RAM, the memory is indeed volatile.

Is RAM always volatile? Isn't there any "exceptional" kind of involatile RAM by humans somewhere?

# Answer
Go 45 to 65 years back in time when RAM was “core memory” - tiny magnetic rings with wires threaded between them. Core memory was not volatile.
> 0 votes

---
Tags: memory-hardware
---


# Question
Title: Find the element $x$ that maximizes $f(x)$ for $x \in \sum A_i$
I have a collection of sets $A\_i \subset \mathbb{Z}$ where I want to find the global maximum after combining the sets using sumset.

The sumset is $$ A + B = \\{ a + b : a \in A , b \in B \\} $$ and $R$ is the combination of each set $A\_i$ $$ R = \sum A\_i $$ Then with some function $f : \mathbb{Z} \rightarrow \mathbb R$, I want to select the element $x \in R$ such that $f(x)$ is maximized.

Practically, each element in a set is a 64 bit unsigned integer, so each set is bounded by $M = 2^{64}-1$ and the output of a sumset operation never produces an element exceeding that bound. Also each set is sparse.

I have a solution for this but I am looking for optimizations or different approaches. I currently use sparse polynomial convolution based on Johnson's *Sparse Polynomial Arithmetic* (1974) \[\]. In summary, I am implementing sparse polynomial convolution first, and then iterating over terms of that result to select the element such that $f$ is maximized.

My current method is to represent each set by its characteristic function. Then the sumset operation becomes the convolution of two of polynomials. Normally, FFT would be used next but since the set is sparse, using a dense array to hold the polynomial produces many zeros, so I instead resort to using a sparse polynomial where each is a sorted array of integers representing the exponents with non-zero coefficient. This step is computed by distributing the terms of one polynomial over the other to create a set of polynomials multiplied by one term. Since each term is represented solely by the exponent, this is just adding to each value in an array, which maintains the sorted property. Then I combine them using a $k$-way merge using a heap. Then, after each convolution is performed ending with the resulting polynomial $r$, the function $f$ is mapped over the exponents of $r$, and the exponent that maximizes the value of $f$ is the solution.

I've implemented this approach and it works well on small cases, but as each $|A\_i|$ increases, $|R|$ increases exponentially and won't fit in machine memory. The issue is that I am generating the entire set $R$ whereas I only need a single element of $R$. A followup would be finding the elements $x\_k$ that result in the top $k$ values of $f(x\_k)$, in which case generating the entire set $R$ allows it to be ranked for any value $k$.

The most recent research I found on sparse polynomial multiplication is Roche's *What Can (and Can’t) we Do with Sparse Polynomials?* (2018) \[\], which continues from Johnson's work and notes that there hasn't been any significant change in this problem since the idea of using a heap.

\[1\]: http://www.cecm.sfu.ca/~mmonagan/teaching/TopicsinCA11/johnson.pdf

\[2\]: https://arxiv.org/pdf/1807.08289.pdf

# Answer
> 1 votes
Unless you have some further structure to the problem (i.e., the function) you can't do better than checking all.

---
Tags: optimization, sets
---


# Question
Title: Computer Architecture-3 level RAM hierarchy
In all computer architecture books we study that Cache memory could be divided into 3 levels (L1,L2 and L3) and its very beneficial to do so. Why don't we use the same approach in case of main memory (RAM). Is there any particular reason that we avoid this?

# Answer
Cache memory levels are inherently a "subdivision" of main memory (RAM). To speed up the access of RAM, the cache was created using the notion of "The Principle of Locality". Frequently in programs, memory is accessed in locations that are close (local) to previously accessed locations, so it benefits to keep sections of data stored in nearby cache instead of going all the way to the hard drive. Also, cost has historically been a factor. Cache memory is more expensive than memory space on a hard drive, etc. Keep in mind, the landscape of computer memory models is always changing, and it is likely that other methods will be used in the future to speed up memory access. I think the current trend is to move away from mechanical storage devices with moving parts, hence the SSD's.
> 4 votes

# Answer
What do you need for a cache? You need two things: One kind of memory that is faster and more expensive, and another kind of memory that is slower and cheaper. Why do we need this? If you had no faster memory then you would just use the cheaper one. And if faster memory wasn't more expensive, you would just use the faster one.

And the problem is that right now there is no RAM that would be significantly cheaper and slower than the RAM that you would put into a computer. Therefore no two levels of RAM.

The M1 processors seem to use technology that can access a moderate (16 GB) amount of RAM at very high speed. There is a chance that future versions would use these 16 GB of RAM like a cache for larger amounts of RAM at usual speeds.
> 1 votes

---
Tags: computer-architecture, memory-hardware
---


title: Hamming Code help

text:
# Question
Title: Hamming Code help
I'm stuck on the following question that I am trying to use for revision purposes. The question states that the data transmitted is 1001101, however, during transmission the second bit has an error and is received as 1 instead of 0, thus the data is 1101101. I need to use the hamming code to detect this error, however, when doing so, my p1, p2 and p4 values are all equal to 1, giving me 111 and indicating an error with bit 7.

Can anyone please help point me in the right direction? I am new to this so apologies if the error is staring me right in the face.

Thanks in advance for any help.

# Answer
If you are using the Hamming(7,4) code as described in here, then there is already a bit error in $1001101$. Indeed, we have parity bits $p\_1 = 1$, $p\_2 = 0$ and $p\_3 = 1$ and message bits $d\_1 = 0$, $d\_2 = 1$, $d\_3 = 0$ and $d\_4 = 1$. Since (for example) $p\_2 + d\_1 + d\_3 + d\_4 = 1 \mod 2$, that means that there is a bit error (and it's among $p\_2$, $d\_1$, $d\_3$ and $d\_4$).

Now to find which bit was switched, it does not suffice to see the value of $(p\_1p\_2p\_3)\_2$, because here it would be $(101)\_2 = 5$, since it would indicate an error on the fifth bit, which is $d\_2$, but $d\_2$ was not in the above list of error candidates.

To find the right (or more exactly the wrong) bit, you need to calculate 3 check values:

* $c\_1 = p\_1 + d\_1 + d\_2 + d\_4 \mod 2$
* $c\_2 = p\_2 + d\_1 + d\_3 + d\_4 \mod 2$
* $c\_3 = p\_3 + d\_2 + d\_3 + d\_4 \mod 2$

And the position of the bit will be given by $(c\_1c\_2c\_3)\_2$. In our example, we get $(111)\_2 = 7$, so the wrong bit is $d\_4$ and the original transmission was $1001100$.

Now there is also a bit error in $1101101$. Can you find it applying this method?
> 1 votes

---
Tags: hamming-code
---


# Question
Title: In Operating Systems, I can't understand why deadlock happens, why does a process not let go of a resource when it is done using it?
I know deadlock occurs when Process A has resource R1 and is waiting for resource R2, while process B has resource R2 and is waiting for resource R1, however why don't both processes just let go of the resource they are currently owning before/while waiting for the other resource? How does A keep holding on to R1 even though it is waiting for R2.

# Answer
To answer part of your question: Processes are not smart. Processes just execute the code of their program, so if the program of P1 has not been written to release R1 when it's done with it, it won't be released.

Besides, the classical setting in which a deadlock happens does not have to do with processes not releasing resources **after** they are done with them, but rather with competing processes trying to acquire the needed resources.

Process A needs **both** R1 and R2 to perform some task, so it starts acquiring them. It acquires R1, and tries to acquire R2.

Just before P1 gets to acquire R1, some process P2 that also needs **both** R1 and R2 tries to acquire them. This time P2 starts with acquiring R2, and succeeds.

At this point the following two things happen:

* P1 tries to acquire R2 which is unavailable, so it waits for R2 be released.
* P2 tries to acquire R1 which is unavailable, so it waits for R1 be released.

From this point on both P1 and P2 are stuck waiting for another resource that will never be released, i.e., they are in a deadlock.

Notice that no process ever held a lock on a resource that didn't intend to use. The problem was that P1 and P2 tried to lock the resources in a different order.

Finally, you might think that when P1 tries to acquire R2, and finds that it is unavailable it could just temporarily release R1 and try to acquire both R1 and R2 at a later time. However, without additional synchronization, this also doesn't ensure that P1 and P2 will manage to acquire the needed resources. The following could happen:

* P1 acquires R1, P2 acquires R2.
* P1 tries to acquire R2, and finds that R2 is unavailable.
* P2 tries to acquire R1, and finds that R1 is unavailable.
* P1 releases R1.
* P2 releases R2.
* P1 acquires R1 and is about to acquire R2.
* P2 acquires R2 and is about to acquire R1.
* P1 tries to acquire R2, and finds that R2 is unavailable.
* P2 tries to acquire R1, and finds that R1 is unavailable.
* ....
> 3 votes

# Answer
You run into a problem when thread A has aquired lock 1, and then decides that it needs *both* lock 1 and lock 2, and tries to aquire lock 2, while thread B has aquired lock 2, and then decides that it needs *both* lock 2 and lock 1.

Once a thread starts aquiring a lock, that operation can't be stopped - it hangs until the lock is available.
> 0 votes

# Answer
There are four necessary conditions for deadlock , and these are

`1. Mutual Exclusion`

`2. Hold and Wait`

`3. No preemption`

`4. Circular wait`

And to prevent deadlock we need to disable one of these four necessary conditions.Now the solution to no preemption is taking resources away ( which requires hardware support ). But this will cause inconsistency e.g., if a process P is using printer and now another process Q demands for it. And now if printer is given to Q , then for P we need to start the task again.
> 0 votes

---
Tags: operating-systems, deadlocks
---


# Question
Title: why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?
I'm trying to understand a poly-time reduction proof from dominating set to vertex cover. If I'm understanding correctly, it goes something like this: suppose we have a vertex cover of size $k$ in graph $G$. Then we construct a new graph $G^\prime$ with the same vertices and edges, except for every edge $(u,v)$ we add a new vertex $w\_{uv}$, which has an edge to both $u$ and $v$.

Then, here's the oddest part: it says that if there's some dominating set in $G^\prime$ that includes any of the $w\_{uv}$, then we can construct another dominating set, that's at least as good, by replacing that $w\_{uv}$ with either $u$ or $v$. That is, we end up not including any of the $w\_{uv}$ at all, and thus the dominating set in $G^\prime$ is the vertex cover in $G$ plus any remaining isolated vertices not in the cover.

This raises the obvious question: what's the point of $w\_{uv}$ if we're gonna include them and then argue that the original $u$ and $v$ can render them obsolete anyway? The proof in the link above conspicuously does not explain this. If the dominating set of $G^\prime$ doesn't even include $w\_{uv}$, and the vertex cover dominates just fine (except for the isolated vertices, which are trivial and have nothing to do with $w\_{uv}$), why even add the $w\_{uv}$? Why does the proof fail if we never introduce the $w\_{uv}$ at all?

# Answer
The key reason we need $w\_{uv}$ is because not every dominating set is necessarily a vertex cover, but $w\_{uv}$ "patches" that up.

In particular, assume isolated vertices can be ignored. Then every vertex cover is a dominating set, but *not* every dominating set is a vertex cover. Hence, if we tried to do the reduction without adding $w\_{uv}$, then only one direction would work: we can show that if $G$ has a vertex cover of size $k$, then $G$ also has a dominating set of the same size. However, the converse is *not* true; only by adding the $w\_{uv}$ does every dominating set of $G^\prime$ necessarily dominate the $w\_{uv}$ as well, and thus cover all edges in $G$.
> 1 votes

---
Tags: np-complete, polynomial-time-reductions, vertex-cover
---


# Question
Title: Is process address space part of Process Control Block(PCB)?
I recently read about the process address space and PCB and trying to link them together. I don't find much literature on their relation.

Is the process address space a part of the PCB data structure?

# Answer
Let me start off like this.

---

The process state includes all the registers that the process may be using, especially the Program counter, plus any other operating system-specific data that may be necessary. This is usually stored in a data structure called a process control block (PCB) or switch frame.

This is what happens in context switching. *The PCB is stored on a per-process stack in kernel memory (as opposed to the user-mode call stack)*, or there may be some specific operating system-defined data structure for this information.

When a process is ready to run again, its PCB is restored. The program counter from the PCB is loaded, and thus execution can continue in the chosen process.

So, the process's address space is not a part of the PCB data structure.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: Context-free grammar for $a^ib^ic^id^{3i}$
I'm trying to make a context-free grammar for $L=\\{a^ib^ic^id^{3i}\mid i\>0\\}$.

I could make a grammar for $a^ib^jc^jd^{3i}$. But I can't make the grammar for the special case that $i=j$ as it is in $L$.

# Answer
> 3 votes
You can use the pumping lemma to show that this language is not context-free.

Suppose it is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = a^nb^nc^nd^{3n}$. $u$ can be written $u = vwxyz$ with:

* $|wxy| \leq n$
* $|wy| \> 0$
* $\forall k \in \mathbb{N}, vw^kxy^kz\in L$.

Now using the first condition, $wxy$ can be written with at most two letters from the initial four. You can take it from here to find a contradiction.

---
Tags: context-free
---


# Question
Title: How can we solve halting problem efficiently?
I was doing exercises regarding the halting problem and there is this question where I am stuck

Ques: it goes like suppose if you can decide the halting problem with a query "Is \<tm,s\> belongs to HALT?" (tm = turning machine and s = string) so it can solve i number of instances \<tm1,s1\> \<tm2,s2\> \<tm(i),s3(i)\> now it says show how can we solve 3 instances with 2 queries only?

I am not sure how to start thinking about this one.. like should we have to simulate one instance with another one? Can anyone provide a proof?

# Answer
> 1 votes
The idea is to determine how many of the Turing machines halt. We will show more generally that given $N = 2^n-1$ many Turing machines $T\_1,\ldots,T\_N$, we can determine which of them halt (on the empty input) using only $n$ calls to an oracle that solves the halting problem.

First, let us see how to determine, using a single oracle call, whether at least $\ell$ of the Turing machines halt. The idea is to construct a Turing machine $S\_\ell$ which runs all of $T\_1,\ldots,T\_N$ in parallel, and halts once $\ell$ of the machines have halted.

Given this, we can determine how many of $T\_1,\ldots,T\_N$ using binary search. In your case, $N = 3$, this proceeds as follows:

* Determine whether at least two of $T\_1,T\_2,T\_3$ halt.
* If so, determine whether at least three of $T\_1,T\_2,T\_3$ halt.
* Otherwise, determine if at least one of $T\_1,T\_2,T\_3$ halts.

Having found out that exactly $\ell$ of the machines halt, we simply simulate all the machines in parallel until $\ell$ of them halt. The remaining machines will not halt.

It would be interesting to figure out whether this is optimal, that is, whether we can determine the halting of more than $2^n-1$ machines using only $n$ oracle calls.

---
Tags: turing-machines, automata, halting-problem, efficiency
---


title: Turing machine that accepts $a^{n^2}$

text:
# Question
Title: Turing machine that accepts $a^{n^2}$
How do you make a TM that accepts the following language?

$$ \\{ a^{n^2} \mid n \ge 0 \\} $$

# Answer
> 0 votes
Here is one way to go about it.

The idea is to use $n^2 = 1 + 3 + \cdots + (2n-1)$.

Accordingly, we construct a Turing machine which will transform the input in the following way:

$$ a^n \to b a^{n-1} \to cb^3 a^{n-4} \to c^4 b^5 a^{n-9} \to \cdots $$

To move from $c^{m^2} b^{2m+1}$ to $c^{(m+1)^2} b^{2m+3}$, repeatedly change the leftmost $b$ to a $c$, and then the leftmost $a$ to a $d$; when running out of $b$s, change all $d$s to $b$s.

If, in the middle of the process, you run out of $a$s, then the answer is negative. If you run out of $a$s right at the beginning of a stage, the answer is positive.

---
Tags: turing-machines
---


title: Sort an array in specific bounds

text:
# Question
Title: Sort an array in specific bounds
Given an array with size of $n$ and except from $\sqrt{n}$ ( **lower value** ) elements in the array, all of the other elements are integers between the bounds of \[$\sqrt{n}$, $n$$\sqrt{n}$\]

I will need to write an algorithm that sorts that array in $\Theta$($n$)

Furthermore, will the same mission could be performed if, now it is given that except from $n/2$ ( **lower value** ) elements in the array, all of the other elements are integers between the bounds of \[$\sqrt{n}$, $n$$\sqrt{n}$\]

And how about $n/log(n)$ ( **lower value** )? ( In this time thare are ( $n$ \- $n/log(n)$ ) ( **lower value** ) integers in the given bounds )

**Note -* We can not know where are the the integers located in the array*

> **MY METHOD:** For the first question I tried to seperate the array to 2 arrays, and then for the array with the numbers inside the bounds of \[$\sqrt{n}$, $n$$\sqrt{n}$\] - I have converted the elements to $n$ based and sorted it with counting-sort. For the second array - sort it with any other sorting method and then merge the 2 arrays

My questions are:

1. Does my approach is correct to the first question ( in terms of run-time, algorithm )?
2. What would be the best solution for the other question asked

# Answer
1. I am not sure counting sort would work, since it does not depend on the base, but on the range of the sorted values. In this case, you would need to create an array of size $(n-1)\sqrt{n}$ to count, so you would be in $\Omega(n^{3/2})$. As suggested in the comment, radix sort may do the trick here.
2. It is not possible to sort in $O(n)$ for one of the other bounds. Indeed, the problematic part would be sorting values not in the bounds $\[\sqrt{n}, n\sqrt{n}\]$: sorting $\frac{n}{2}$ values requires $\Omega(n\log n)$ time.

On the other hand, sorting $\frac{n}{\log n}$ values can be done in $O\left(\frac{n}{\log n}\log\left(\frac{n}{\log n}\right)\right) = O(n)$ time.
> 1 votes

---
Tags: algorithms, data-structures, runtime-analysis, sorting
---


# Question
Title: How to design a turing machine for a context-free grammar? what are the steps?
How to design a Turing machine for a context-free grammar? what are the steps? for example, What are the steps to design a Turing machine for the following grammar with alphabet $\\{a,b\\}$.

> $S\rightarrow aX\mid b$
>
> $X\rightarrow bS\mid aX\mid \varepsilon$

This is what I come so far for the above example, in the link, any help appreciated.

# Answer
> 2 votes
You should first construct a PDA for your grammar. You can then use the tape in stead of the stack. When pushing something in the stack, write it on the tape of the TM from left to right. When poping the stack, read the tape then move the head left if necessary.

There is no other change (states and transitions can be the same).

---
Tags: turing-machines, context-free
---


# Question
Title: Possible partitions, for k-means problem(k=2)
I have this brute-force algorithm to solve the problem:

1. Generate all possible partitions of P into two subsets of P1 and P2
2. For each partition P1, P2 generated in Step 1, compute the cost of the partition
3. Report the partition with the lowest cost found in Step 2.

How can I analyze the number of possible partitions and use that to determine the running time?

# Answer
If $(P\_1, P\_2)$ is a partition of $P$, that means that $P\_2 = P\setminus P\_1$.

That means that is suffices to count the number of possible choices of $P\_1$, which is the cardinal of the powerset of $P$, $|\mathcal{P}(P)| = 2^{|P|}$.

If $P\_1$ and $P\_2$ have symmetrical roles, you can divide the result by $2$ (but it does not change the asymptotical complexity).
> 2 votes

---
Tags: time-complexity, clustering
---


# Question
Title: PDA accepting of a specific symmetric language
Assume we have PDA that accepts a specific symmetric language on $\\{a,b\\}^\*$.

if we have $a$ This side of the string, on the other side of the string we have $aa$. and if we have $b$ This side of the string, on the other side of the string we have $bb$.

Examples of words in this language (middle point emphasized):

$ab\\, bbaa$

$aaa\\, aaaaaa$

$bab\\, bbaabb$

What is a PDA accepting this language?

I can find a grammar for this language but I can't find a PDA.

The grammar: $S \to aSaa \mid bSbb \mid aaa\mid bbb$

# Answer
There are general constructions that give a PDA given a CFG.

In this case, start with the PDA for $\\{a^n b^n \colon n \> 0\\}$, instead of storing one $A$ on the stack for each input $a$, store two, and the same for $b$. When reaching the middle, start discounting and accept by empty stack.
> 1 votes

---
Tags: regular-languages, pushdown-automata
---


title: Solving a CSP using AC-3

text:
# Question
Title: Solving a CSP using AC-3
> Peter (P), Mary (M), Otto (O) and Dicky (D) would like to rent an apartment house. The house has three floors: G/F, 1/F, 2/F. Every floor has only one apartment. P, M, O and D must be assigned to exactly one floor. Note that more than one person can live in the same apartment. Consider the following constraints.
>
> * P and M cannot live in the same apartment.
> * D must live on a higher floor than O.
> * D must live alone.
> * If P and O live together, they must be on 1/F.
> * If P and O live separately, one of them must live on the 2/F.

How do I use AC-3 to solve this question?

I found two possible solutions: P,M,O,D = 2,0,0,1 or 1,0,1,2

# Answer
AC-3 is an algorithm for solving CSPs. In order to use it solve a question, you need to present the question as solving a CSP.

In your case, the CSP is on four variables $P,M,O,D$ ranging over $\\{0,1,2\\}$. The constraints are:

* $P \neq M$.
* $D \> O$.
* $D \neq P$.
* $D \neq M$.
* $(P = O) \Rightarrow P = 1$.
* $(P \neq O) \Rightarrow (P = 2 \lor O = 2)$.

We can convert them into the following explicit constraints:

* $(P,M),(D,P),(D,M) \in \\{(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)\\}$.
* $(D,O) \in \\{(1,0),(2,0),(2,1)\\}$.
* $(P,O) \in \\{(0,2),(1,1),(1,2),(2,0),(2,1)\\}$.

You can now take any implementation of AC-3 and simply run it on these constraints.
> 0 votes

---
Tags: algorithms, constraint-satisfaction
---


# Question
Title: Meaning of "number of keys in the range $a$ to $b$"
Regarding this question:

> You are given an unsorted array $A$ of $n$ integers in the range $2^n −10n \leq A\[i\] \leq 2^n$. Suggest a data structure that allows to answer in $O(1)$ steps the number of keys in the range $a$ to $b$ (note that $a, b$ are not necessarily integers). The construction of data structure should cost at most $O(n)$ steps.
>
> 1. Describe in few sentences the data structure.
> 2. Write a pseudocode for constructing the data structure.
> 3. Write a pseudocode for the `numberKeys(NewDataStructure,a,b)`.
> 4. Give a short explanation of the time and space complexity of (2) and (3).

Can someone please explain me what "the number of keys in the range $a$ to $b$" means?

# Answer
It probably means "the number of array elements whose value is between $a$ and $b$".

For the solution, it is crucial that the number of possible values of array elements is $O(1)$.
> 1 votes

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


# Question
Title: How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect
To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem instances, including a few simple "corner cases". This is a great heuristic: it's a great way to quickly weed out many incorrect attempts at an algorithm, and to gain understanding about why the algorithm doesn't work.

However, when learning algorithms, some students are tempted to stop there: if their algorithm works correctly on a handful of examples, including all of the corner cases they can think to try, then they conclude that the algorithm must be correct. There's always a student who asks: "Why do I need to prove my algorithm correct, if I can just try it on a few test cases?"

So, how do you fool the "try a bunch of test cases" heuristic? I'm looking for some good examples to show that this heuristic is not enough. In other words, I am looking for one or more examples of an algorithm that superficially looks like it might be correct, and that outputs the right answer on all of the small inputs that anyone is likely to come up with, but where the algorithm actually doesn't work. Maybe the algorithm just happens to work correctly on all small inputs and only fails for large inputs, or only fails for inputs with an unusual pattern.

Specifically, I am looking for:

1. An algorithm. The flaw has to be at the algorithmic level. I am not looking for implementation bugs. (For instance, at a bare minimum, the example should be language-agnostic, and the flaw should relate to algorithmic concerns rather than software engineering or implementation issues.)
2. An algorithm that someone might plausibly come up with. The pseudocode should look at least plausibly correct (e.g., code that is obfuscated or obviously dubious is not a good example). Bonus points if it is an algorithm that some student actually came up with when trying to solve a homework or exam problem.
3. An algorithm that would pass a reasonable manual test strategy with high probability. Someone who tries a few small test cases by hand should be unlikely to discover the flaw. For instance, "simulate QuickCheck by hand on a dozen small test cases" should be unlikely to reveal that the algorithm is incorrect.
4. Preferably, a deterministic algorithm. I've seen many students think that "try some test cases by hand" is a reasonable way to check whether a deterministic algorithm is correct, but I suspect most students would not assume that trying a few test cases is a good way to verify probabilistic algorithms. For probabilistic algorithms, there's often no way to tell whether any particular output is correct; and you can't hand-crank enough examples to do any useful statistical test on the output distribution. So, I'd prefer to focus on deterministic algorithms, as they get more cleanly to the heart of student misconceptions.

I'd like to teach the importance of proving your algorithm correct, and I'm hoping to use a few examples like this to help motivate proofs of correctness. I would prefer examples that are relatively simple and accessible to undergraduates; examples that require heavy machinery or a ton of mathematical/algorithmic background are less useful. Also, I don't want algorithms that are "unnatural"; while it might be easy to construct some weird artificial algorithm to fool the heuristic, if it looks highly unnatural or has an obvious backdoor constructed just to fool this heuristic, it probably won't be convincing to students. Any good examples?

# Answer
A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases.

**Example:** Coin denominations, $d\_1,\dots,d\_k$ and a number $n$, express $n$ as a sum of $d\_i$:s with as few coins as possible.

A naive approach is to use the largest possible coin first, and greedily produce such a sum.

For instance, the coins with value $6$, $5$ and $1$ will give correct answers with greedy for all numbers between $1$ and $14$ except for the number $10 = 6+1+1+1+1 = 5+5$.
> 94 votes

# Answer
I immediately recalled an example from R. Backhouse (this might have been in one of his books). Apparently, he had assigned a programming assignment where the students had to write a Pascal program to test equality of two strings. One of the programs turned in by a student was the following:

```
issame := (string1.length = string2.length);

if issame then
  for i := 1 to string1.length do
    issame := string1.char[i] = string2.char[i];

write(issame);

```

We can now test the program with the following inputs:

"university" "university" $\Rightarrow$ True; OK

"course" "course" $\Rightarrow$ True; OK

"" "" $\Rightarrow$ True; OK

"university" "course" $\Rightarrow$ False; OK

"lecture" "course" $\Rightarrow$ False; OK

"precision" "exactness" $\Rightarrow$ False, OK

All of this seems very promising: maybe the program does indeed work. But a more careful testing with say "pure" and "true" reveals faulty output. In fact, the program says "True" if the strings have the same length and the same last character!

However, testing had been pretty thorough: we had strings with different length, strings with equal length but different content, and even equal strings. Furthermore, the student had even tested and executed every branch. You can't really argue testing had been careless here -- given that the program is indeed very simple, it might be hard to find the motivation and energy to test it thoroughly enough.

---

Another cute example is binary search. In TAOCP, Knuth says that "although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky". Apparently, a bug in the binary search implementation of Java went unnoticed for a decade. It was an integer overflow bug, and only manifested with large enough input. Tricky details of binary search implementations are also covered by Bentley in the book *Programming Pearls*.

Bottom line: it can be surprisingly hard to be certain a binary search algorithm is correct by just testing it.
> 75 votes

# Answer
The best example I ever came across is primality testing:

```
input: natural number p, p != 2
output: is p a prime or not?
algorithm: compute 2**(p-1) mod p. If result = 1 then p is prime else p is not.

```

This works for (almost) every number, except for a very few counter examples, and one actually needs a machine to find a counterexample in a realistic period of time. The first counterexample is 341, and the density of counterexamples actually decreases with increasing p, although just about logarithmically.

Instead of just using 2 as the basis of the power, one may improve the algorithm by also using additional, increasing small primes as basis in case the previous prime returned 1. And still, there are counterexample to this scheme, namely the Carmichael numbers, pretty rare though
> 37 votes

# Answer
Here's one that was thrown at me by google reps at a convention I went to. It was coded in C, but it works in other languages that use references. Sorry for having to code on \[cs.se\], but it's the only to illustrate it.

```
swap(int& X, int& Y){
    X := X ^ Y
    Y := X ^ Y
    X := X ^ Y
}

```

This algorithm will work for any values given to x and y, even if they the same value. It will not work however if it's called as swap(x,x). In that situation, x ends up as 0. Now, this might not satisfy you, since you can somehow prove this operation to be correct mathematically, but still forget about this edge case.
> 27 votes

# Answer
There is a whole class of algorithms that is inherently hard to test: pseudo-random number generators. You can not test a single output but have to investigate (many) series of outputs with means of statistics. Depending on what and how you test you may well miss non-random characteristics.

One famous case where things went horribly wrong is RANDU. It passed the scrutiny available at the time -- which failed to consider the behaviour of *tuples* of subsequent outputs. Already triples show lots of structure:

Basically, the tests did not cover all use cases: while single-dimensional use of RANDU was (probably mostly) fine, it did not support using it to sample three-dimensional points (in this way).

Proper pseudo-random sampling is a tricky business. Luckily, there are powerful test suites there days, e.g. dieharder that specialise in throwing all the statistics we know at a proposed generator. Is it enough?

To be fair, I have no idea what you can feasibly prove for PRNGs.
> 21 votes

# Answer
**2D local maximum**

**input:** 2-dimensional $n \times n$ array $A$

**output:** a local maximum -- a pair $(i,j)$ such that $A\[i,j\]$ has no neighboring cell in the array that contains a strictly larger value.

(The neighboring cells are those among $A\[i, j+1\], A\[i, j-1\], A\[i-1, j\], A\[i+1, j\]$ that are present in the array.) So, for example, if $A$ is

$$\begin{array}{cccc} 0&1&3&\mathbf{4}\\ \mathbf{3}&2&\mathbf{3}&1\\ 2&\mathbf{5}&0&1\\ \mathbf{4}&0&1&\mathbf{3}\end{array}$$

then each bolded cell is a local maximum. Every non-empty array has at least one local maximum.

**Algorithm.** There is an $O(n^2)$-time algorithm: just check each cell. Here's an idea for a faster, recursive algorithm.

Given $A$, define cross $X$ to consist of the cells in the middle column, and the cells in the middle row. First check each cell in $X$ to see if the cell is a local maximum in $A$. If so, return such a cell. Otherwise, let $(i, j)$ be a cell in $X$ with maximum value. Since $(i, j)$ is not a local maximum, it must have a neighboring cell $(i', j')$ with larger value.

Partition $A \setminus X$ (the array $A$, minus the cells in $X$) into four quadrants -- the upper left, upper right, lower left, and lower right quadrants -- in the natural way. The neighboring cell $(i', j')$ with larger value must be in one of those quadrants. Call that quadrant $A'$.

**Lemma.** *Quadrant $A'$ contains a local maximum of $A$.*

*Proof.* Consider starting at the cell $(i', j')$. If it is not a local maximum, move to a neighbor with a larger value. This can be repeated until arriving at a cell that is a local maximum. That final cell has to be in $A'$, because $A'$ is bounded on all sides by cells whose values are smaller than the value of cell $(i', j')$. This proves the lemma. $\diamond$

The algorithm calls itself recursively on the $\frac{n}{2}\times\frac{n}{2}$ sub-array $A'$ to find a local maximum $(i, j)$ there, then returns that cell.

The running time $T(n)$ for an $n\times n$ matrix satisfies $T(n) = T(n/2) + O(n)$, so $T(n) = O(n)$.

Thus, we have proven the following theorem:

**Theorem.** *There is an $O(n)$-time algorithm for finding a local-maximum in an $n\times n$ array.*

Or have we?
> 17 votes

# Answer
Fisher-Yates-Knuth shuffling algorithm is an (practical) example and one on which one of the the authors of this site has commented about.

The algorithm generates a random permutation of a given array as:

```
 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

```

One sees that in the loop the elements are swapped between $i$ and $j$, $0 \le j \le i$. This produces **unbiased sampling of the permutations** (no permutations are over-represented and others under-represented).

A "naive" algorithm could be:

```
 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ n-1
       exchange a[j] and a[i]

```

Where in the loop the element to be swapped is chosen from all available elements. However this produces **biased sampling of the permutations** (some are over-represented etc..)

Actually one can come-up with the fisher-yates-knuth shuffling using a **simple (or naive) counting analysis**.

The number of permutations of $n$ elements is $n! = n \times n-1 \times n-2 ..$, meaning 1st element can be placed in any of $n$ positions, 2nd element in remaining $n-1$ positions and so on.This is exactly what Fisher-Yates shuffle does and is why it produces un-biased (random) permutations (unlike the "naive" algorithm)

The main problem with verifying whether the shuffling algorithm is correct or not (*biased or not*) is that due to the statistics, a large number of samples is needed. The codinghorror article I link above explains exactly that (and with actual tests).
> 12 votes

# Answer
These are primality examples, because they're common.

(1) Primality in SymPy. Issue 1789. There was an incorrect test put on a well-known web site that didn't fail until after 10^14. While the fix was correct, it was just patching holes rather than rethinking the issue.

(2) Primality in Perl 6. Perl6 has added is-prime which uses a number of M-R tests with fixed bases. There are known counterexamples, but they're quite large since the default number of tests is huge (basically hiding the real problem by degrading performance). This will be addressed soon.

(3) Primality in FLINT. n\_isprime() returning true for composites, since fixed. Basically the same issue as SymPy. Using the Feitsma/Galway database of SPRP-2 pseudoprimes to 2^64 we can now test these.

(4) Perl's Math::Primality. is\_aks\_prime broken. This sequence seems similar to lots of AKS implementations -- lots of code that either worked by accident (e.g. got lost in step 1 and ended up doing the entire thing by trial division) or didn't work for larger examples. Unfortunately AKS is so slow that it is difficult to test.

(5) Pari's pre-2.2 is\_prime. Math::Pari ticket. It used 10 random bases for M-R tests (with fixed seed on startup, rather than GMP's fixed seed every call). It will tell you 9 is prime about 1 out of every 1M calls. If you pick the right number you can get it to fail relatively often, but the numbers become sparser, so it doesn't show up much in practice. They have since changed the algorithm and API.

This isn't *wrong* but it's a classic of probabilistic tests: How many rounds do you give, say, mpz\_probab\_prime\_p? If we give it 5 rounds, it sure looks like it works well -- numbers have to pass a base-210 Fermat test and then 5 pre-selected bases Miller-Rabin tests. You won't find a counterexample until 3892757297131 (with GMP 5.0.1 or 6.0.0a), so you'd have to do a lot of testing to find it. But there are thousands of counterexamples under 2^64. So you keep raising the number. How far? Is there an adversary? How important is a correct answer? Are you confusing random bases with fixed bases? Do you know what input sizes you'll be given?

There is a related point: what is a big number? To students it seems many think 10,000 is a *huge* number. To many programmers, $10^{16}$ is a big number. To programmers working on cryptography, these are small, and big is, say 4096 bits. To programmers working on computational number theory, these are all small, and big might be 10 to 100 thousand decimal digits. To some mathematicians these all may be considered "not big" considering there are many more positive numbers larger than these examples than there are smaller. This is something a lot of people don't think about, but makes a difference when thinking about correctness and performance.

These are quite difficult to test correctly. My strategy includes obvious unit tests, plus edge cases, plus examples of failures seen before or in other packages, test vs. known databases where possible (e.g. if you do a single base-2 M-R test, then you've reduced the computationally infeasible task of testing 2^64 numbers to testing about 32 million numbers), and finally, lots of randomized tests using another package as a standard. The last point works for functions like primality where there is a fairly simple input and a known output, but quite a few tasks are like this. I have used this to find defects in both my own development code as well as occasional problems in the comparison packages. But given the infinite input space, we can't test everything.

As for proving correctness, here is another primality example. The BLS75 methods and ECPP have the concept of a primality certificate. Basically after they churn away doing searches to find values that work for their proofs, they can output them in a known format. One can then write a verifier or have someone else write it. These run very fast compared to the creation, and now either (1) both pieces of code are incorrect (hence why you'd prefer other programmers for the verifiers), or (2) the math behind the proof idea is wrong. #2 is always possible, but these have typically been published and reviewed by multiple people (and in some cases are easy enough for you to walk through yourself).

In comparison, methods like AKS, APR-CL, trial division, or the deterministic Rabin test, all produce no output other than "prime" or "composite." In the latter case we may have a factor hence can verify, but in the former case we're left with nothing other than this one bit of output. Did the program work correctly? Dunno.

It's important to test the software on more than just a few toy examples, and also going through some examples at each step of the algorithm and saying "given this input, does it make sense that I am here with this state?"
> 11 votes

# Answer
The best example (read: thing I am most butt hurt about) I have ever seen has to do with collatz conjecture. I was in a programming competition (with a 500 dollar prize on the line for first place) in which one of the problems was to find the minimum number of steps it takes for two numbers to reach the same number. The solution of course is to alternately step each one until they both reach something that has been seen before. We were given a range of numbers (I think it was between 1 and 1000000) and told that the collatz conjecture had been verified up to 2^64 so all of the numbers we were given would eventually converge at 1. I used 32-bit integers to do the steps with however. It turns out that that there is one obscure number between 1 and 1000000 (170 thousand something) that will cause a 32-bit integer to overflow in due time. In fact these numbers are extremely rare bellow 2^31. We tested our system for HUGE numbers far greater than 1000000 to "ensure" that overflow was not occurring. Turns out a much smaller number that we just didn't test caused overflow. Becuase I used "int" instead of "long" I only got a 300 dollar prize rather than a $500 prize.
> 8 votes

# Answer
The **Knapsack 0/1** problem is one that almost all the students think is solvable by a greedy algorithm. That happens more often if you previously show some greedy solutions as the Knapsack's problem version where a *greedy algorithm works*.

For those problems, in class, I should show the proof for Knapsack 0/1 (*dynamic programming*) for remove any doubt and for the greedy problem version too. Actually, both proofs are not trivial and the students probably find them very helpful. In addition, there's a comment about this in *CLRS 3ed, Chapter 16, Page 425-427*.

*Problem:* *thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and ith item weigh wi and is worth vi dollars. What items should thief take? to maximize his gain*?

**Knapsack 0/1 problem**: The setup is the same, but the *items may not be broken into smaller pieces*, so thief may decide either to *take an item or to leave it* (binary choice), but may not take a fraction of an item.

And you can get from students some ideas or algorithms that follow the same idea as greedy version problem, that's:

* Take the total capacity of the bag, and put as much as possible the most value object, and iterate this method until you can't put more object because bag it's full or there's not object with less o equal weight for put inside the bag.
* Other wrong way is thinking: put lighter items and put these following highest to lowest price.
* ...

Is it helpful for you? actually, we know the *coin problem* is a knapsack problem version. But, there are more examples in the forest of knapsack's problems, by example, what about Knapsack 2D (that's is real helpful when you want cut wood for make furniture, I saw in a local from my city), it's very common think that the greedy works here, too, but not.
> 6 votes

# Answer
Pythons PEP450 that introduced statistics functions into the standard library might be of interest. As part of the justification for having a function that calculates the variance in the standard library of python the author Steven D'Aprano writes:

> ```
> def variance(data):
>         # Use the Computational Formula for Variance.
>         n = len(data)
>         ss = sum(x**2 for x in data) - (sum(data)**2)/n
>         return ss/(n-1)
>
> ```
>
> The above appears to be correct with a casual test:
>
> ```
> >>> data = [1, 2, 4, 5, 8]
> >>> variance(data)
>   7.5
>
> ```
>
> But adding a constant to every data point should not change the variance:
>
> ```
> >>> data = [x+1e12 for x in data]
> >>> variance(data)
>   0.0
>
> ```
>
> And variance should *never* be negative:
>
> ```
> >>> variance(data*100)
>   -1239429440.1282566
>
> ```

The issue is about numerics and how precision gets lost. If you want maximum precision then you have to order your operations in a certain way. A naive implementation leads to incorrect results because the imprecision is too large. That was one of the issue my numerics course at university was about.
> 4 votes

# Answer
A common mistake is to implement shuffling algorithms wrong. See discussion on wikipedia.

Trouble is that the bias is usually not easy to detect, and one needs to prove that there are indeed $n!$ "choices" done by the algorithm, and not $n^n$ or $(n-1)^n$ which are common for wrong implementations.
> 4 votes

# Answer
For almost 40 years it was thought that an intuitive two-pointers based algorithm for finding a maximum-area triangle inside a convex polygon was correct. It was proved incorrect in https://arxiv.org/abs/1705.11035.
> 3 votes

# Answer
While this is likely not quite what you're after, it's certainly easy to understand and testing some small cases without any other thinking will lead to an incorrect algorithm.

**Problem**: Write a function that takes a nonnegative integer $n$ and returns the number of proper divisors of $n^2+n+41$, namely the number of integers $0\<d$ for which $d\text{ divides } n^2+n+41$ and $d \< n^2+n+41$.

**Proposed solution**:

```
int f(int n) {
   return 1;
}

```

This happens to be correct for $n= 0, 1, 2, \dotsc, 39$ but fails when $n=40$.

This "try some small cases and infer an algorithm from the result" approach crops up frequently (though not as extremely as here) in programming competitions where the pressure is to come up with an algorithm that (a) is quick to implement and (b) has a fast run time.
> 2 votes

# Answer
Though this question was asked a long time ago, let me also contribute with two - in my opinion - demonstrative examples (both matching all the criteria you listed) - maybe they will come in handy if you would like to update your slides someday.

1. The famous activity selection problem. An intuitive (greedy) approach many people may come up with is to choose the **shortest** interval/activity first. If you think of an edge case where a short activity conflicts with 2 other longer, non-conflicting activities (at the end of the first one and at the beginning of the other), it can be seen easily that the algorithm is incorrect (we could have picked those 2 instead of this single one). Interestingly, the correct solution is also greedy.
2. This one may be a less popular problem: instead of copying over all the details from Leetcode, please, read them there before proceeding. When I came across this problem first, I had a solid understanding of **backtracking** already, so I thought, let's solve it with a 2-phased (greedy) backtracking approach! I.e.: let's try to collect as many cherries as possible on the way down to the bottom right corner, then let's try to do the exact same thing on the way back to the upper left corner (for the remaining, so far unpicked cherries). I solved correctly 50 test cases out of 56. An edge case that I didn't consider was something like:

My approach would have solved it like:

Note that on the way back (2nd phase), due to the moving rules defined by the problem, you can pick only one of the remaining 2 cherries. However, you can actually pick up all of them, still playing by the rules:

Sorry for not posting pseudo-code snippets here: you can find it to the first one on the Wikipedia site, and the translation of my C++ solution for the 2nd problem would have been just way too long/complex.
> 0 votes

---
Tags: algorithms, algorithm-analysis, education, correctness-proof, didactics
---


# Question
Title: How to sample Bivariate Normal Distribution with Accept reject method
I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods:

1. Prior Sampling
2. Gibbs Sampling
3. Rejection Sampling

I have done the first two samplings and I also have clear understanding of what accept reject method or so-called rejection sampling is. yet I can not find any proposal distribution for it.

---

**Rejection Sampling and proposal distribution**

assume you have a distribution $f(x)$ which is not easy for you to sample. choose another distribution that is easy for you to sample wisely called $g(x)$ so that for some constant $C$ for all $x$ we have $C.g(x) \> f(x)$.

we call this $g(x)$ the proposal distribution.

sample from $g(x)$ and name it $X\_i$ as you chose $g(x)$ because it was easy to sample. accept this sample with a probability of $p = f(X\_i)/C.g(X\_i)$.

As I said before I cant find any $g(x)$ easy enough to sample and yet bigger than bivariate normal distribution for some $C$.

# Answer
> 0 votes
I came up with this answer which can approximately sample a bivariate normal distribution with accept reject method and I thought it might be useful for others in future.

we choose a 2D uniform distribution called $F\_{X,Y}(x,y) = F\_X(x).F\_Y(y)$ where both $X$ and $Y$ are uniform distributions in range of $(0, +a)$ and they are independent of each other.

We choose a constant $C$. Both $C$ and $a$ are chosen based on our bivariate normal distribution so that:

1. for all $x, y$ we have $C.F\_{X,Y}(x,y) \geq BN(x,y)$, Where $BN$ is our bivariate normal distribution.
2. $x, y \in (-a, +a)$ supports most of our $BN$ density.

---

The Accept Reject Method:

1. Now we sample from our $F\_{X,Y}(x,y)$. Suppose it's $X1 = (x1, y1)$.
2. We uniformly choose from: $$X\_{1.1} = (x1, y1),$$ $$X\_{1.2}=(-x1, y1), $$ $$X\_{1.3}=(x1, -y1), $$ $$X\_{1.4} = (-x1, -y1)$$ and name that $\hat{X\_1}$ so that we consider all four quadrants of $xOy$.
3. Now we accept $\hat{X\_1}$ as a sample of $BN$ with a probability of $p=BN(x1,y1)/C.f\_{X,Y}(x,y)$.
4. We come back to step 1 and do this cycle to collect as much sample from the bivariate normal distribution as we want.

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


# Question
Title: Initializations methods for lloyds algorithm (Kmeans++ vs Gonzalez)
I'm learning the initialization methods for Lloyd's algorithm. And I have a hard thing finding examples where Kmeans++ works better than Gonzalez and where the reverse is true so Gonzalez works better than Kmeans++. Does anyone have an example input (Pointset and value k) for these two scenarios?

# Answer
**Partial Answer:**

Let us construct an instance where k-means++ initialization performs better than the Gonzalez initialization.

Consider the real line. Place $n$ points at the origin, i.e., position $0$. Place $n$ points at the position $1$. Lastly, place $1$ point at the position $n^{1/4}$. Let us cluster this pointset with $2$ clusters, i.e., $k = 2$.

In the optimal clustering, one center is placed at each of the two positions $0$ and $1$. The optimal k-means cost would be $\Theta(\sqrt{n})$ since the cost of $2n$ points at positions $0$ and $1$ is exactly $0$ and the cost of point at position $n^{1/4}$ is at most $\sqrt{n}$.

With the **Gonzalez algorithm**, only the following two center sets are possible (you can try this your own):

1. Center set where one center is at position $0$ and the other at $n^{1/4}$
2. Center set where one center is at position $1$ and the other at $n^{1/4}$

Without loss of generality, after this initialization, Lloyd's algorithm will cluster the points at positions $0$ and $1$ within the same cluster. And, the point at position $n^{1/4}$ would be clustered in a different cluster (singelton cluster). The $k$-means cost would be $\Theta(n)$.

With the **k-means++ algorithm**, the first center is chosen uniformly at random. With the high probability, the center would be chosen from positions $0$ or $1$. Without the loss of generality, suppose the first center is chosen from position $0$. Then, the probability that the second center will be chosen from position $1$ is $n/(n+\sqrt{n}) \geq 1/2$. And, the probability that the second center will be chosen from position $n^{1/4}$ is at most $\sqrt{n}/(n+\sqrt{n}) \leq 1/(2\sqrt{n})$. As you can see, the second center would be chosen from position $1$ with a high probability.

Therefore, with high probability, after this initialization, the $k$-means algorithm would open centers at positions $0$ and $1$. And, the $k$-means cost would be $\Theta(\sqrt{n})$. This cost is better than the cost with the Gonsalez algorithm that had cost $\Theta(n)$.
> 2 votes

---
Tags: clustering
---


# Question
Title: Is there a function $t$ fulfilling $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?
$f:\mathbb{N} \to \mathbb{N}$ is in $\mathcal{O}(0)$ only if $f(n) \neq 0$ for a finite number of values of $n$. Therefore, $\mathcal{O}(0) \subset \mathcal{O}(1)$ strictly. Is there something in between, i.e. a function $t:\mathbb{N} \to \mathbb{N}$ with $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?

# Answer
Yes, for example: $f(n)=\cases {0&$n\in\mathbb{N}\_{even}$\\1&$n\in\mathbb{N}\_{odd}$}$

This function is not in $O(0)$, since it has infinitely many $1$'s, but also $1$ is not $O(f)$ since it has infinitely many $0$'s.

To see more clearly why $1$ is not $O(f)$, consider any constant $c\>0$ and any constant $n\_0\in \mathbb{N}$. Then, **if** $1 \le c\cdot f(n)$ for any $n\>n\_0$, we will have that for any $n\_0\<n\in \mathbb{N}\_{even}$, $1 \le c\cdot f(n) = c\cdot 0 = 0$ which is a contradiction. Hecne $1\notin O(f)$.

Therefore $O(0)\subsetneq O(f)\subsetneq O(1)$.

However, for computer science usages, as Pal GD said, we consider only monotonically increasing functions - in which case there is no such $f$.
> 1 votes

---
Tags: big-o-notation
---


# Question
Title: CFG for $\{uvw \mid u,v,w \in\{0,1\}^*,|u|=|v|=|w| \wedge u\neq w\} $
$L=\\{uvw \mid u,v,w \in\\{0,1\\}^\*,|u|=|v|=|w| \wedge u\neq w\\} $

Any help would be appreciated.

# Answer
> 0 votes
The idea is that a word $uvw\in L$ can be written as $x\alpha y\beta z$ with $x, y, z \in \\{0,1\\}^\*$, $\alpha, \beta\in \\{0,1\\}$, verifying the following conditions:

* $\alpha \neq \beta$
* $|x\alpha z| = |u| = |v| = |w|$. This implies $|x| + |z| + 1 = |u|$ and then $|y| = 3|u| - 2 - |x|-|z| = 2|u| - 1 = 2 |x| + 2|z| + 1$.

That means that if we use a grammar symbol $X$ to create $x$ and part of $y$, centered on the position of $\alpha$, informally we will need to push "one symbol on the left and two on the right" of $X$. The converse is done for creating part of $y$ and $z$, centered on $\beta$. And for the ending $+1$, we will add an additional terminal symbol from the starting rule.

Now we only need to do it for $\alpha = 0$ and $\beta = 1$, and the other way around.

In details, we can use the following grammar:

> $S \rightarrow X\_1AZ\_0 \mid X\_0AZ\_1$
> $X\_0 \rightarrow AX\_0AA \mid 0$
> $X\_1 \rightarrow AX\_1AA \mid 1$
> $Z\_0 \rightarrow AAZ\_0A \mid 0$
> $Z\_1 \rightarrow AAZ\_1A \mid 1$
> $A\rightarrow 0\mid 1$

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


# Question
Title: Quicksort: Probability of an element being compared to fewer than $k$ pivot elements
Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S\_{(1)},S\_{(2)},\dots,S\_{(n)}$ be the sorted order of the elements in $S$. Furthermore, let $d(i)$ be the number of elements that $S\_{(i)}$ is compared to. Finally, the pivot element is chosen uniformly at random.

How do I then compute the probability that $d(i) \< k$ for some $k \in \mathbb{N}$?

# Answer
> 1 votes
This is not the answer to your question, but maybe you can use some elements of it.

For $i\<j$, let us denote $X\_{ij}$ the random variable: $$X\_{ij} = \left\\{\begin{array}{rl}1 & \text{if }S\_{(i)}\text{ and }S\_{(j)}\text{ are compared}\\0&\text{otherwise}\end{array}\right.$$ and $A\_{ij} = \\{S\_{(i)}, S\_{(i+1)}, …, S\_{(j)}\\}$.

Since a comparison between two elements only occurs if one of them is a pivot, and since a pivot is never compared to other elements after the end of the partition occurring when it was chosen, we can conclude that:

$$\mathbb{P}(X\_{ij} = 1) = \mathbb{P}(S\_{(i)} \text{ first pivot in }A\_{ij}) + \mathbb{P}(S\_{(j)} \text{ first pivot in }A\_{ij})$$ This is also due to the fact that if another element of $A\_{ij}$ is chosen as first pivot, $S\_{(i)}$ and $S\_{(j)}$ will be put in two different parts of the partition.

Since the choice of the pivot is uniform, we get $\mathbb{P}(S\_{(i)} \text{ first pivot in }A\_{ij}) = \frac{1}{|A\_{ij}|}$ and finaly $\mathbb{P}(X\_{ij} = 1) = \frac{2}{j - i +1}$.

Now, the expected number of comparisons where $S\_{(i)}$ is involved is:

$$\begin{array}{rcl} \displaystyle\mathbb{E}\left(\sum\limits\_{j=1,j\neq i}^nX\_{ij}\right) & = & \displaystyle\sum\limits\_{j=1,j\neq i}^n\mathbb{E}(X\_{ij})\\ & = & \displaystyle\sum\limits\_{j=1,j\neq i}^n\mathbb{P}(X\_{ij} = 1)\\ & = & \displaystyle\sum\limits\_{j=1,j\neq i}^n\frac{2}{|j-i| + 1}\\ & = & \displaystyle\sum\limits\_{j=1}^{i-1}\frac{2}{i - j +1} + \sum\limits\_{j=i+1}^{n}\frac{2}{j - i +1}\\ & = & \displaystyle\sum\limits\_{k=1}^{i-1}\frac{2}{k +1} + \sum\limits\_{k=1}^{n-i}\frac{2}{k +1}\\ \end{array}$$

This analysis is generally sufficient for the analysis of the average time complexity of quicksort, because this value is $O(\log n)$. However, I am not sure as to how use part of it to find the value you want, which is: $$\displaystyle\mathbb{P}\left(\sum\limits\_{j = 1, j\neq i}^n X\_{ij} = k\right)$$

Also it is not so clear that for $j\neq j'$, $X\_{ij}$ and $X\_{ij'}$ are independant (since for example $X\_{ij}$, $X\_{ij'}$ and $X\_{jj'}$ are not independant because at most two of the three could be $1$).

# Answer
> 1 votes
We can describe quicksort with a random pivot as follows. Assume for simplicity that $S\_{(i)} = i$. First, choose a permutation of $\\{1,\ldots,n\\}$. Then, whenever processing some subarray, choose the element that appears first in the permutation as the pivot.

Suppose we are interested in the number of elements compared to $i$. Suppose that $i$ is found at location $j$. Suppose that when $i$ is chosen as a pivot, it is compared to $k\_-$ elements smaller than itself and $k\_+$ elements larger than itself. These elements must be $i-k\_-,\ldots,i-k\_+$, and the elements $i-k\_--1,i+k\_++1$, if they are in range, must appear before $i$. Let $b\_-,b\_+$ be the indicators of these elements being in range (i.e., $b\_- = 1$ if $k\_- \< i-1$, and $b\_+ = 1$ if $k\_+ \< n-i$).

Suppose that $j\_-$ of the elements preceding $i$ are smaller than $i$, forming a set $S\_-$, and so $j\_+ = j - 1 - j\_-$ of the elements preceding $i$ are larger than $i$, forming a set $S\_+$. There are $\binom{i-1-k\_--b\_-}{j\_--b\_-}$ choices for $S\_-$ and $\binom{n-i-k\_+-b\_+}{j\_+-b\_+}$ choices for $S\_+$. There are $\binom{j\_++j\_-}{j\_+}$ ways of putting them together, and $(n-j)!$ ways to choose the order of the remaining elements.

The number of permutations of $S\_-$ with $\ell\_-$ left-to-right maxima is the Stirling number of the first kind $\genfrac{\lbrack}{\rbrack}01{j\_-}{\ell\_-}$. Similarly, the number of permutations of $S\_+$ with $\ell\_+$ left-to-right minima is $\genfrac{\lbrack}{\rbrack}01{j\_+}{\ell\_+}$.

We obtain the following formula for the probability that $i$ is compared to exactly $s$ elements: $$ \frac{1}{n!} \sum\_{j\_++j\_- \leq n-1} \sum\_{\substack{k\_++k\_-+\ell\_++\ell\_-=s \\ k\_- \leq i-1 \\ k\_+ \leq n-i}} \\ \binom{j\_++j\_-}{j\_+} \binom{i-1-k\_--b\_-}{j\_--b\_-} \binom{n-i-k\_+-b\_+}{j\_+-b\_+} \\ (n-j\_+-j\_--1)! \genfrac{\lbrack}{\rbrack}00{j\_-}{\ell\_-} \genfrac{\lbrack}{\rbrack}00{j\_+}{\ell\_+}. $$

---
Tags: algorithms, algorithm-analysis, probability-theory, randomized-algorithms, quicksort
---


title: Karp's reduction strategy

text:
# Question
Title: Karp's reduction strategy
One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq\_p$ is polynomial reduction): $$\begin{array}{rr}X \leq\_p Z & (1)\\W \leq\_p X&(2)\end{array}$$

The usual way to prove NP-Completeness however, is to follow Karp’s strategy which consists in proving that $$\begin{array}{rr}X\in \textsf{NP} & (3)\\W \leq\_p X&(4)\end{array}$$

I am trying to show that $(1)$ and $(3)$ are equivalents, but but I'm not sure where I can start. Can someone help me with how to do this?

# Answer
> 1 votes
$(3)\Rightarrow (1)$ should just be a consequence of the definition of $\textsf{NP}$-completeness.

For $(1)\Rightarrow (3)$, you can use the fact that there exists a function $f$, computable in polynomial time, such that $u\in X \Leftrightarrow f(u) \in Z$. Now to decide if $u\in X$, you can compute $f(u)$, and then decide nondeterministically if $f(u)\in Z$.

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


title: Dijkstra's Algorithm Invariant

text:
# Question
Title: Dijkstra's Algorithm Invariant
I am trying to prove the first assertion in the following code, taken from notes of Damon Wischik:

```
def dijkstra(g, s):
    for v in g.vertices:
        v.distance = ∞
    s.distance = 0
    toexplore =  PriorityQueue([s], sortkey = lambda  v: v.distance)

    while not toexplore.isempty():
        v = toexplore.popmin()
        # Assert: v.distance is the true shortest path distance between s and v
        # Assert: v is never put back into toexplore
        for (w, edgecost) in v.neighbours:
            dist_w = v.distance + edgecost
            if dist_w < w.distance:
                w.distance = dist_w
                if w in toexplore:
                    toexplore.decreasekey(w)
                else:
                    toexplore.push(w)

```

Base case: The estimate of the source node is correct when it is popped.

Inductive step: Consider the shortest path from the source node $s$ to some destination node $d$,

$$ s \to v\_1 \to v\_2 \to \cdots \to v\_k \to d. $$

Assume that the estimates for $s,v\_1,v\_2,\ldots,v\_k$ are correct when they are popped.

When $d$ is popped, we can be sure that $s, v\_1, v\_2, \dots, v\_k$ were popped prior to that as their true shortest distances from the source $s$ are lower than that of $d$. In particular, when $v\_k$ is popped, we are sure that the edge $(v\_k, d)$ will be relaxed since relaxing the edge $(v\_k, d)$ gives us the true shortest distance from the source to the destination, which is definitely an improvement on any prior estimate of D. Hence D's estimate is the true shortest distance from the source when it is popped.

Hence the assertion is true.

Is there a flaw in my proof?

# Answer
I believe your proof is a bit incomplete, since you do not guarantee the shortest path to $d$ is a path which only traverses the popped nodes. You can add this part to make you proof complete :

Assume the shortest path to our vertex $d$ is the path $s \to u\_1 \to u\_ 2 \to \cdots \to u\_l \to x \to \cdots \to d$ Where nodes $s, u\_1, u\_2, \cdots, u\_l$ are popped earlier, therefore their distances are correctly determined, and $x$ as the first vertex which is not popped yet. Since the edges are nonnegative, therefore $dist\_x \le dist\_d$ (let $dist\_v$ be the actual distance of the vertex $v$). Since $x$ is the first vertex which is not popped yet, it's distance should now have been determined by relaxing $(u\_l, x)$. We assumed $d$ has the smallest estimate, let it be $est\_d$, so $est\_d \le est\_x = dist\_x$, and thus $est\_d \le dist\_x \le dist\_d \implies est\_d \le dist\_d$, and since estimate can never be less than actual distance, $est\_d = dist\_d$.

I hope my answer was helpful.
> 1 votes

---
Tags: algorithms, graphs, dijkstras-algorithm
---


# Question
Title: Is it possible to have a zero knowledge proof with a P Prover?
In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP.

Is it necessary for the prover to have higher computational power than the verifier?

If it is, is there any variant that does not need this property?

If any of the answers is yes can you give me references?

# Answer
> 1 votes
If the prover has the same power as the verifier, then the verifier can simulate the entire interaction himself, which makes the interactive proof unnecessary. For example, if we have an interactive proof with a probabilistic polynomial verifier and a polynomial prover for some language $L$, then $L\in BPP$. When dealing with interactive proof systems with a polynomial verifier it suffices to consider PSPACE provers, since a PSPACE prover can find and send the messages that maximize the verifier's acceptance probability.

Note that the above refers to interactive proof systems in general, there's nothing specific to zero knowledge (zero knowledge simply adds the condition that for yes instances, the entire communication of the protocol can be generated by a simulator who only has access to the input).

---
Tags: complexity-theory, cryptography, zero-knowledge-proofs
---


# Question
Title: Prove $\{xy \mid |x|=|y|, x \neq y\}$ is not a linear language
> Show the language
>
> $$L = \\{xy \mid |x| = |y|, x\neq y\\}$$
>
> is not linear.

I've seen and proved a pumping lemma for linear languages, mentioned here:

> If $L$ is linear then there exists a constant $p$ such that for all $w \in L$ with $|w| \ge p$ there is a decomposition $w = uvxyz$ such that:
>
> 1. $|uvyz| \leq p$.
> 2. $|vy| \> 0$.
> 3. $uv^ix^iz \in L$ for all $i \geq 0$.

I'm trying to find a counterexample string.

# Answer
> 4 votes
Consider this string: $w=a^kb^ka^{2k+2k!}b^ka^k$. We will show that we can't write this string in form of $uvxyz$ in a way that the conditions of pumping lemma for linear languages statisfy.

Because $|uvyz|\leq k$ we have : $|uv|\leq k$ and $|yz|\leq k$

So we can write: $uv=a^{f\_1}$ , $yz=a^{f\_2}$ , $y=a^{g\_1}$ , $v=a^{g\_2}$ where $g\_1+g\_2\>0$ (because $yv$ is cannot be empty string) and $g\_1+g\_2\leq k$.

Now we pump $v$ and $y$ $n$-times and we have: $w'=a^{k+ng\_1}b^ka^{2k+2k!}b^ka^{k+ng\_2}$

We want to conclude this string is not in language for some $n$. So if we rewrite $w'$ as $w'=a^{k+ng\_1}b^ka^xa^{2k+2k!-x}b^ka^{k+ng\_2}$,

we should have: $k+ng\_1=2k+2k!-x$ and $x=k+ng\_2$

so $k+ng\_1=2k+2k!-k-ng\_2 \to n(g\_1+g\_2)=2k! \to n=\frac{2k!}{g\_1+g\_2}$.

Notice that $g\_1\leq k , g\_2 \leq k \to g\_1+g\_2 \leq 2k$ $\to$ $g\_1+g\_2| 2k!$

So we only need to set $n=\frac{2k!}{g\_1+g\_2}$ to have $w'=w''w''$ and this is a contradiction. So $L$ is not linear.

# Answer
> 1 votes
Let $p$ be the constant promised by the pumping lemma. Without loss of generality, $p \geq 2$.

Let $w = 0^p 1 0^{2p+p!} 1 0^p$. Since the left half of $w$ is $0^p10^{p+p!/2}$ and the right half of $w$ is $0^{p+p!/2}10^p$, we see that $w \in L$.

Let $w = uvxyz$ be the decomposition promised by the pumping lemma. Since $|uvyz| \leq p$, necessarily $v = 0^j$ and $y = 0^k$ belong to the first and last zero runs, respectively, and $j+k \leq p$. Since $|vy| \> 0$, we have $j+k \> 0$.

Let $i = 1 + p!/(j+k)$. According to the pumping lemma, $uv^ixy^iz \in L$. But $$ uv^ixy^iz = 0^{p + jp!/(j+k)} 1 0^{2p+p!} 1 0^{p + kp!/(j+k)}. $$ The total length of this word is $2(2p+p!+1)$. Therefore its left half and its right half are both equal to $$ 0^{p + jp!/(j+k)} 1 0^{p + kp!/(j+k)}, $$ showing that $uv^ixy^iz \notin L$, in contradiction to the pumping lemma.

---
Tags: pumping-lemma, linear-languages
---


title: What is a forwarded clock?

text:
# Question
Title: What is a forwarded clock?
I'm reading the overview book of the Intel QuickPath Interconnect and it says there:

> The physical connectivity of each interconnect link is made up of twenty differential signal pairs plus a differential forwarded clock.

I can't find what is a forwarded clock, does anyone know what it is and if there is some material for reading about it?

# Answer
> 2 votes
According to lecture notes of Sam Palermo, there are three common I/O clocking architectures:

---
Tags: computer-architecture
---


# Question
Title: Randomly selecting element from data structure, probability based on weight
I have a list of elements, each with an id and a weight.

**A**: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as likely to be selected as an element with weight 5.

**B**: I need to add/remove elements and increase/decrease their weight dynamically.

I have already found a solution, if I exclude B:

```
1. fill array with id and weight
2. compute prefix sum
3. generate random number r between 0 and sum of weights - 1
4. binary search which element in the prefix sum corresponds to r

```

Let n be the number of elements, this solution would be able to retrieve the desired element in O(log(n)), precomputation is O(n). However I cannot add/remove elements or alter their weight without having to precompute the prefix sum again.

Can someone provide me with an approach working for A and B? I have tried using a segement tree but don't find a satisfactory solution.

# Answer
I think it would work with a complete tree with elements stored in leaves, the whole thing being stored in an array (the same way as for heaps). You also need to store in each node the sum of the weights of all its children.

To be able to modify weight, you would also need a corresponding array (or hashtable if ids are not consecutive integers), to know where in the heap is stored an element with given id.

* To know how to select an element, when exploring the tree `t` of weight `t.weight`, you can generate a number `r` between $0$ and `t.weight`, and go left if `r < t.left.weight` and right otherwise.
* To insert, just put it at the last available leaf position and modify the weights of all its ancestors.
* To delete, switch the position with the last leaf, and modify the ancestors of both the deleted node and the switched leaf.
* To modify weight, use the corresponding structure to know the position of the element of given id, and modify the weights of its ancestors.

All operations can be done in $O(\log n)$.
> 5 votes

---
Tags: algorithms, data-structures, randomness
---