# Question
Title: What is a good heuristic for multi-point A* on a directed graph?
I am conducting a stateful search of a large graph in an effort to find some solutions of minimal cost. With an admissible heuristic for estimated time to completion from a given state (as in A\*), I would be able to drop states out of the search queue to improve runtime, otherwise I need a good heuristic that can advance better states with some variety (or even a better search function altogether). What would be a good heuristic to use, when there are multiple target points to reach, in any order?

Some of my thoughts on generating a heuristic (of estimated time to goal):

Since we want to underestimate in all cases, I can drop most of the stateful details and just express the graph like so:

* A strongly connected directed graph $G$ on $V$ vertices and $E$ edges with positive integer costs, with $L$ leaf nodes not counted in $V$. The problem is to visit a subset $S \subseteq L$ of the leaf nodes in minimum time.

(Also, the search space includes "wormholes" that also have time costs, but I'd rather not represent them as edges, since the search space can traverse a wormhole from anywhere to: a) specific previously visited vertices, or b) a previously visited vertex with a certain action performed. If I generate a **minimum directed spanning tree**, the total cost of the tree essentially implicitly assumes wormholes can be used at any time to a previously visited vertex for 0 cost... which I'm fine with, as it underestimates by ignoring the costs and limitations.)

* The **MDST** can be generated using some variety of the Chu-Liu/Edmonds/etc algorithm, and I've found some decent notes on generating one from every vertex. However, I only need to visit a subset $S$ of the leaf nodes (I can easily remove the rest), and I don't care how many other vertices are included, which turns the problem into an NP-hard **Directed Steiner Tree** problem. It seems overkill to solve for this, but at least there are usable approximations.
* I can generate the all-pairs shortest path table using Floyd-Warshall in $O(V^3)$ or learn one of the faster solutions. Presumably, I could make a graph $G'$ by taking all the shortest paths from the root to $S$, add all the nodes included in those paths, take the shortest paths from those nodes to $S$, etc., and generate an MDST on that, in something like $O(EV + V^2log\ log\ V + V^2 S^2 + E\ log\ V)$, but that might just not be worth the effort.

So the options I'm thinking of at the moment are:

1. Use an approximation algorithm for the Steiner Tree. These come with proofs of being within $2 - 2/|S|$ of the cost of the true optimum, so I could just divide the total cost of the generated tree by 2 to guarantee an underestimate.
2. Use the full MDST but only count the edges used to reach the remaining nodes of $S$. This potentially overestimates but might be a good heuristic to pick states to search from.
3. Do something with the shortest pairs? While I could divide the shortest paths by $|S|$ and sort of guarantee that it underestimates that way, I think it would tend to encourage moving towards clumps of leaves, rather than toward the nearest leaf.

Do any of these sound reasonable, or are there other options I'm overlooking that could be better?

# Answer
Just use an exact algorithm for the directed Steiner tree problem. Being NP-hard does not matter, in practice you will get optimal solutions to huge problems. See the following software:

https://scipjack.zib.de/
> 0 votes

---
Tags: optimization, minimum-spanning-tree, heuristics, directed-graphs
---


# Question
Title: is this lanuage or it' complement not Turing-recognisable
K = {\<J, a, b, c\> : J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a never has the same value as b and a never has the same value as c}.

I'm aware the problem is not actually decidable as I performed a reduction from ATM (or halting problem), which proves it is not decidable, but my question is it Turing-recognizable or not Turing-recognizable? if not is it co-Turing recognizable and what would be the complement? I would assume it would be:

K' = {\<J, a, b, c\>: J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a always has the same value as b and a never has the same value as c}.

# Answer
The complement of your language $K$ is easily seen to be recognizable: If $J$ isn't a valid Java programme, or it is lacking the specified integer variables, we can easily tell. Otherwise, we run the Java programme and monitor the values of $a$, $b$ and $c$. If we see $a$ to have the same value as $b$, or if we see $a$ to have the same value as $c$, we are also in the complement of $K$. This process will identify all inputs not belonging to $K$, so we have what we want.
> 1 votes

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


# Question
Title: Determine page number and offsets for address references
I'm working on learning operating systems and I've come across a strange question that I don't know how to answer.

The question is:

> Assuming a 1-KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers)?
>
> 21205

The notes and slides I have are very confusing and I can't find anything quite like this from my searches. I understand that a 1KB page size means that it's 2^10 but what do I do after that exactly? Most descriptions I see involve splitting that in half and using the first half as your offset and the other half as the page number but then I see others saying not to do this and my notes, as I mentioned, are useless. I'm sure this is extremely easy but I feel like I've been given only 1/3 of the knowledge needed.

Any help would be greatly appreciated!

---

**Addendum**

I took a step back for a little while and I think I realized where my confusion was coming from.

I determined that 21,205 is within the range of 2^15, so it's a fifteen bit number. If I subtract the size of the page (10) from the size of the number (15) then that should, in theory, give me a page number of 10 and an offset of 5.

The next bit is pure speculation on my part but I'm assuming that I then take the decimal form of 21,205, which is 101001011010101, and segment it accordingly. The first ten bits (1010010110) equals 662 and the last five bits (10101) equals 21. So my tentative answer is

Page Number = 662 & Offset = 21.

Is this at all reasonable or do I do it completely wrong?

# Answer
You got it a little mix up and wrong
Page number = logical address / page size in this case is $\frac{21205}{1024} = 20$

Offset = logical address mod page size in this case is $21205 \mod 1024 = 725$

Sources:
http://www.yorku.ca/pkashiya/cse1520/Paged%20memory%20technique.htm http://www2.cs.uregina.ca/~hamilton/courses/330/notes/memory/paging.html
> 2 votes

# Answer
You are correct in thinking that you are completely wrong. What you need to do is forget all your notes and work everything out from first principles. That is the delight of maths (for example): there are no facts.

First, try an easier problem. Suppose you have a civilised computer with a 1000-byte page size. Then the address 21205 will be at page 21 (the first page is page 0) and the offset is 205.

Next, try to explain what you have just done in an unnecessarily complicated way. You got “21” not because it was obvious but because you laboriously calculated 21205÷1000. You got “205” not because it was obvious but because you took 21205 and worked out the remainder on dividing by 1000.

Next, take what you did in the last paragraph but instead of 1000 use 1024. You will get a page number and an offset and the answer to your question.

Finally, have an attack of laziness. Realise that you never needed to divide by 1000: you only needed to write down 21205 in decimal and cut off the last three digits. Realise that you never needed to take the remainder after division by 1000: you only needed to take the last three digits on their own.

So the finally final step is to replace “1000” by “1024”, “decimal” by “binary”, and “three” by “ten”.

And *then*, at last, you can look at your half remembered notes and see what you got wrong. It was a simple transposition - but there’s no point in correcting them because now you know *why* it all works, you can reinvent the formula yourself any time you want to.

The great thing about maths is that there are no facts.
> 1 votes

# Answer
I think Page numbers will be given by first 5 bits and last 10 bits will give the offset. With the first 5 bit first you locate which page no. you want to go and then remaining 10 bits will tell you the offset at that page taking you at the exact location
> 0 votes

# Answer
215201 is logical address space provided to us which means it is a process size. 1 KB is page size which is equivalent to 2^10 or 1024 Bytes. Process divided by page size gives a quotient and remainder, 215201/1024 = 210 quotient which is number of pages and 161 as a remainder which is offset.
> -1 votes

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


# Question
Title: Real world example of complex foregin key references
Give a real world, normalized example where table T1 has primary key (A, B), T2 has primary key (B, C) and T3 has primary key (A, C) and table 4 has a primary key (A, B, C) where (A,B) is a foregin key on T1, (B, C) is a foregin key on T2, and (A, C) is a foregin key on T3?

The motivation is this form is allowed in a relational database, but I cannot think of a usage of it.

# Answer
> 0 votes
Here is an example: Assume a database that is maintained in a school. Here, T1 is a course enrollment table, where the (roll\_number, course\_number) is a primary key. It says which student has enrolled in which course.

Then, T2 is a course\_details table where the primary key is (course\_number, instructor\_code). This is because a course could be delivered by multiple instructors.

Next, T3 has a primary key (roll\_number, instructor\_code) signifying the instructors to which a student is reporting to through some course.

Now, I think you will be able to carry forward and conclude it logically.

All the best.

PS. - Thanks for the bounty. I am in deep need of it. Thanks.

---
Tags: database-theory, databases
---


title: But why *is* $FPT$ a subset of $W[1]$?

text:
# Question
Title: But why *is* $FPT$ a subset of $W[1]$?
$FPT$ is the set of parameterized problems that are fixed-parameter tractable. If $L\_{w,h}$ is the language associated to boolean circuits of weft $w$ and depth $h$, then $W\[t\]$ is the set of parameterized problems that can be fixed-parameter reduced to $L\_{t,h}$ for some constant $h$. (I know that there are multiple equivalent definitions.) It is folklore that

$$ FPT \subseteq W\[1\] \subseteq W\[2\] \subseteq \dots $$

but I do not *really* understand the first inclusion, and I could not find a satisfying explanation.

Niedermeier writes in "Invitation to Fixed-Parameter Algorithms" that "The inclusion $FPT \subseteq W\[1\]$ directly follows from the fact that $W\[1\]$ allows '$FPT$-computations' through the use of parameterized reductions". What is meant by that?

# Answer
> 1 votes
A problem $P$ in FPT has a parametrized reduction to *any* parametrized decision problem that has at least one "true" and "false" instance. The reduction algorithm has enough time to compute whether an instance of $P$ is true or false (because $P$ is in FPT), and can then simply map it to one of the true or false instances of the other language.

So, the problem $P$ has a parametrized reduction to $L\_{1,1}$ in particular, and therefore is in $W\[1\]$.

---
Tags: parameterized-complexity
---


# Question
Title: Pathfinding in a known maze with step limitations, points of interest and more
*I hope this is the correct subpage of SE, if not please direct me to the more appropriate place.*

Imagine the following scenario:

You are put into a random but known position inside a given maze. The maze contains, in addition to walls (█) and pathways (.), the following things:

* R - A **refresh point** which is single use but when used refreshes the amount of steps you can take.
* S - A **save point** which is multi use and gives you a known position you can start from (instead of a random position) but does not refresh your steps while inside the maze. If used to re-enter it grants you a full set of steps. Only relevant if algorithm can account for multiple re-entries (see *optional optimizations* below).
* T - A **treasure** chest, which gives you some form of reward (the reward itself is irrelevant for the pathing algorithm)
* M - A **monster** which you will need to fight if you encounter it. It will drop some treasure if defeated, but any damage it does to you will need to be regenerated (so a time penalty) or, if it defeats you, you get kicked out of the maze and need to re-enter it (either randomly or through a previously passed save point).

Used / looted / defeated status of a tile preserve between runs.

You have a maximum of 30 steps you can take before you get kicked out of the maze from exhaustion, unless refreshed at a refresh point.

Mazes are always square, with a side length of 160 tiles.

Example part of a maze:

```
█ █ █ . █ █ █ █ █
. . . . █ . . M █
█ █ █ █ █ . █ . █
M . █ . . R █ . █
█ R █ . █ █ █ . █
█ M . . █ . █ . █
█ █ █ M █ S █ . █
█ . █ . T . . . █
█ . █ . █ █ █ R █

```

Example visualization of a full maze. Blue drops are refresh points, fires are save points, ghosts are monsters and gifts are treasures. Everything else is irrelevant

## What is a good way, given the mentioned restrictions, to find the path, starting from your current position, that passes by the most treasures (and monsters) before you're kicked out of the maze of exhaustion?

***What I tried***

I tried creating a graph of nodes based on the refresh points as the nodes and the paths between them as the connections, giving a higher value to more points of interest between nodes. I then used a modified Dijkstra algorithm to find the path with the highest value.
Unfortunately, while it works somewhat, it doesn't take into account what treasures/monsters have already been visited, often leading to high density areas of the map being covered many times over, requiring human intervention for improvement of said path (which more often than not has caused user error and a miscount, leading to a failed run).

I'm thankful for any ideas and suggestions as to how to tackle this.

***Optional optimizations / extensions:***

* allow backtracking where it makes sense
* use save points strategically to come back to and cover more area, spanning multiple runs.
* allow the use of different weights to prioritize/avoid treasures/monsters by user preference
* there is a single boss inside this maze, which is the ultimate "goal" of it. Make the path end there, while still picking up as many treasures on the way as possible.
* whatever else you can think of

# Answer
# Basic approach

I suggest you reduce this to a longest path problem in a directed graph. In particular, conceptually we imagine the entire state space, and build a graph with one vertex per possible state in the state space, with edges representing moves you can make in a single step.

More specifically, we have one vertex in the graph for each pair $\langle \ell,s\rangle$, corresponding to starting at location $\ell$ with $s$ steps remaining. Add edges $\langle \ell,s \rangle \to \langle \ell',s-1 \rangle$ if you can go from location $\ell$ to location $\ell'$ in a single step. The weight on this edge is the value incurred in taking that step (e.g., if you visited a treasure, add the value of that treasure; if you defeated a monster, add the value of that monster).

Now find the longest path in this graph. You can find a longest path by negating all edge weights, and then finding a shortest path using the Bellman-Ford algorithm.

I am assuming you can assign a value to any particular path (e.g., that each treasure has a value and defeating each monster has a value, and the total value is the sum of those values acquiring along the way, and you can collect a treasure multiple times).

# Save points

When we have save points, we need to keep track of the most recent save point, so let's revise our approach. Create one vertex per triple $\langle \ell,s,p \rangle$, corresponding to starting at location $\ell$ with $s$ steps remaining, and where the most recent save point is $p$. Now we can create edges corresponding to the different ways we can take a single step from this location.

Then, find a longest path in this graph, as before.

# Single-use locations

This assumes you can collect a treasure multiple times, defeat a monster multiple times, and use a refresh point multiple times. I suspect in practice you can't. To take this into account, the state needs to keep track of which treasures have already been collected and which monsters have already been defeated and which refresh points have already been used. Taking this into account, each vertex of the graph might correspond to a tuple $\langle \ell, s, p, T \rangle$, where $\ell,s,p$ are as before and $T$ denotes the set of treasures collected and monsters defeated and refresh points used.

This blows up the size of the state space by a factor that is exponential in the number of treasures/monsters/refreshes, so applying Bellman-Ford naively might become intractable. Instead, you could try using heuristics, like A\* search or some other method.
> 1 votes

---
Tags: algorithms, graphs, path, maze
---


# Question
Title: If X is poly-time reducible to Y and X is in P, then Y is in P
The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y that gives an answer to X and I am getting the answer in polynomial time (since X is in P), then the blackbox of Y must be giving an answer in polynomial time also.

# Answer
When we say that X is polytime reducible to Y, it means that Y is at least as hard as X or that X is no harder than Y. The hardness of X does not affect the hardness of Y since Y is at least as hard as X; it can be even harder (may be NP or NP-complete) than X. Therefore, if X is in P, then it is not necessary that Y is also in P.
> 1 votes

# Answer
Your argument is wrong. There is no guarantee that there exists a blackbox that runs in polynomial time.

If I had \\$10, I could buy you a coffee. But that doesn't imply that I have \\$10.
> 0 votes

# Answer
The only time guarantee you get from "$X$ is polytime reducible to $Y$" is that the time required to form $X$ into an input for the $Y$-subroutine is polynomially-bounded in $|X|$.

If $Y$ were also in $\mathbf{P}$ then, complete-problems from complexity classes $\mathcal{C} \supsetneq \mathbf{P}$ would lie in $\mathbf{P}$, i.e., $\mathcal{C} = \mathbf{P}$. For instance, $\mathbf{P} = \mathbf{NP}$, $\mathbf{P} = \mathbf{EXP}$, and even $\mathbf{P} = \mathbf{R}$, clearly contradicting several hierarchical theorems.
> 0 votes

---
Tags: complexity-theory, np, p-vs-np
---


# Question
Title: Constructing equivalent (to a polynomial-time degree) decision problems from function problems
Let's say we're some function problem, $R \subseteq \Sigma^\* \times \Sigma^\*$, where $\Sigma = \\{0, 1\\}$ and some oracle $O\_R$ that solves $R$.

Now, we're given some language, $L \subseteq \Sigma^\*$ and an associated oracle $O\_L$ that solves $L$.

We say $R =\_{poly} L$ if a machine equipped with $O\_L$ can solve $R$ AND a machine equipped with $O\_R$ can solve $L$.

Is there some function that maps $f \colon \mathcal{P}(\Sigma^\* \times \Sigma^\*) \mapsto \mathcal{P}(\Sigma^\*)$ such that $R =\_{poly} f(R) \\: \forall R$?

My requirement for $f$ is that it must computable. As a bonus, and this isn't really quantifiable, but I would like for it to be "neat;" i.e. it should be able to be written as a "short" human-readable algorithm in the English language.

My question basically boils down to converting function problems to decision problems, such that they are polynomial-time equivalent problems.

# Answer
# Special case: computing a (single-valued) function

In the special case where the relation $R$ corresponds to a (single-valued) function, call it $g$, then yes, there is an equivalence. Suppose the function problem is to compute the function $g$. Define the language $L$ by

$$L=\\{\langle x,i,b \rangle \mid x \in \\{0,1\\}^\*, g(x)\_i=b\\},$$

i.e., $L$ consists of all triples $\langle x,i,b \rangle$ such that the $i$th bit of the output is $b$ when the input is $x$. Assume that we consider $g(x)\_i$ to be $\bot$ if $i$ is past the end of $g(x)$.

Then given an algorithm or oracle to decide $L$, you can immediately compute $g$ (by computing it a bit at a time, trying all three possibilities for $b$ for each $i$), and given an algorithm or oracle to compute $g$, you can immediately decide $L$. Moreover this a polynomial-time reduction in both directions, assuming the length of $g(x)$ is polynomial in the length of $x$.

# General case

I don't know. I am not aware of any way to define such an equivalence, for a general relation $R$ (which might be "multi-valued").
> 4 votes

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


# Question
Title: Understanding recursion tree for withdrawal formula
$$ T(n) = T(n-a) + T(a) + cn $$

Now the solution says that the height of the tree $(h)$ is: $$ h = \left \lfloor n/a \right \rfloor $$

And I don't understand why. Maybe I didn't understand the withdrawal formula as needed.

# Answer
> 0 votes
Your recurrence expands into a recurrence tree in the following way. Each node has a label. If the label $n$ is $a$ or smaller, then the node is a leaf. Otherwise, the node has two children, one labeled $n-a$, the other one labeled $a$.

Suppose that you create this tree starting with a root labeled $n$. The root has two children: one is labeled $n-a$, and the other one, labeled $a$, is a leaf. The node labeled $n-a$ has two children, one labeled $n-2a$, and the other one is a leaf. And so on.

It takes roughly $n/a$ steps until this process terminates (since we start with $n$, have to get to $a$ or less, and drop by $a$ each time). Therefore the height of the tree is roughly $n/a$.

# Answer
> 0 votes
$$\begin{align}T(n)&=T(n-a)+T(a)+cn \\\&=T(n-2a)+T(a)+c(n-a)+T(a)+cn \\\&=T(n-3a)+T(a)+c(n-2a)+T(a)+c(n-a)+T(a)+cn \\\&\cdots \end{align}$$

The recursion stops after $k$ substitutions, in such a way that $n-ka$ is no more a function of $n$. In other words, when

$$0\le n-ka\<a.$$

---

The solution of the recurrence is

$$T(n)=T(n-ka)+kT(a)+cnk-c((k-1)+(k-2)+\cdots0).$$

The final summation is a triangular number, $\dfrac{(k-1)k}2$.

---

Technically, the solution $\left\lfloor\dfrac na\right\rfloor$ is not necessarily correct, as no base case of the recurrence is given. All we could say is that the height of the tree is the $k$ such that we know the value of $T(n-ka)$, and our assumption $0\lt n-ka\<a$ is somewhat arbitrary.

---
Tags: algorithms, trees, recursion, efficiency
---


title: Integrality gap and complexity classes

text:
# Question
Title: Integrality gap and complexity classes
I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems?

In particular, is there a class of problems for which their integrality gap is unbounded?

Where by unbounded integrality gap, I mean an integrality gap that is equal to infinite, where the value of the relaxation is 0. For example, the min-diff Partition problem has an unbounded integrality gap.

# Answer
The question is incorrect. The integrality gap is defined for a linear programming formulation of the problem and not fundamentally for the problem.

It is possible that a problem has more than one integer programming formulations, with some having unbounded integrality gap and the others having bounded integrality gap.

For example, see this paper on the capacitated k-median problem or see this statement from the book The Design of Approximation Algorithms (Page 167, last paragraph).
> 1 votes

---
Tags: complexity-theory, optimization, complexity-classes, integer-programming
---


# Question
Title: Is the number of NP-complete problems finite?
It should be straight forward to show that there are infinitely many NP-hard problems:

**Proof:** Take the problem *Remove 1 Vertex 3-COL* ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and yields a yes answer iff a vertex $x \in V$ exists which, when removed from $V$ yields a new graph $G'=(V\backslash\\{x\\}, \\{(u,v) \in E\\,|\\, u \neq x \land v\neq x\\}$ which is a positive instance of $3COL$.

$R1V3COL$ can indeed be reduced to 3-colorability problem (which is proven to be NP-complete) by (as an example reduction) simply removing a vertex from $G$ and testing if $G$ is 3-colorable. If $G$ is not 3-colorable remove another vertex from $G$ and test it. Repeat until there are no vertices left for testing.

Therefore we know $R1V3COL$ is an NP-hard problem.

We can now reduce $R2V3COL$ to a $R1V3COL$ problem (by a similar concept as shown above for $R1V3COL$ to $3COL$ to show that $R2V3COL$ is in NP-hard and so on for every *Remove n Vertices 3-COL* problem. In other words we can always reduce $R(n)V3COL$ to $R(n-1)V3COL$. Therefore we know that there have to be infinitely many NP-hard problems and we are done.

**Now to my Lemma:** I cannot think of a simple proof to show that a certain problem with infinitely many variations (like $R(n)V3COL$) is also in NP to prove NP-completeness and therefore prove that infinitely many problems are in the subclass NP-complete.

# Answer
> 2 votes
As in the comment, consider the collection of problems $N$-SAT (Is $\phi$, a logical formula in $N$-CNF, satisfiable?). Or $N$-coloring of graphs, for $N \ge 3$ (Can the graph be colored with $N$ colors?). Many NP-complete problems have some parameter (Is there a clique of size $k$ in the graph? Has the digraph a feedback vertex set of size $k$?).

# Answer
> 3 votes
Take any NP-complete problem, for instance $\text{SAT}$. Note that there are infinitely many unsatisfiable formulas. So let $\phi\_1, \phi\_2, \phi\_3 \ldots$ be an infinite enumeration of (distinct) unsatisfiable formulas.

For each $i$, we can consider the problem $\text{SAT}\_i = \text{SAT} \cup \\{\phi\_i\\}$ i.e. the problem of deciding whether a given formula is either satisfiable, or equal to $\phi\_i$.

This problem is clearly in NP and there is a straightforward reduction from $\text{SAT}$ to $\text{SAT}\_i$: Given any formula $\phi$, we have $\phi \in \text{SAT}$ iff $(\phi \neq \phi\_i) \land (\phi \in \text{SAT}\_i)$.

# Answer
> 1 votes
For every integer k, take the travelling salesman problem with n \> 1 cities where n is a power of k. (Picked the problem that way because all the instances are distinct, so we can say with good conscience that these are distinct problems).

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


# Question
Title: How to show that an algorithm is not fair?
Algorithm fairness is the field of research aimed at understanding and correcting biases like these. It is at the intersection of machine learning and ethics. Specifically, the field includes: Researching the causes of bias in data and algorithms.

There are several ways to define fairness. I am interested in the individual fairness (see in the figure below).At an individual level, fairness can be defined as similar individuals being treated similarly. At a group level, a fair outcome demands the existence of parity between different protected groups, such as those defined by gender or race.

I am currently working on similarity of multimedia objects. I want to measure the individual fairness of the algorithm $A$ I am using on a dataset $D$. How to show that algorithm $A$ is fair or not on the dataset $D$?

# Answer
> 0 votes
Hash codes are computed using the same formula on all keys and are designed to yield dissimilar values even from similar data. The semantic interpretation of the data is irrelevant and will be "erased" by hashing. No unfairness is possible.

In addition, hash codes are used in hash tables, that have collision arbitration mechanisms, so that all data are stored and none is lost. Speaking of unfairness would be perfectly irrelevant.

---
Tags: machine-learning
---


# Question
Title: Reducing the min weight perfect matching problem to a T-join
My lecture notes for $T$-joins states:

> If $T = V$ then $T$ -joins of cardinality $V/2$ are exactly the perfect matchings of $G$ = $(V ,E)$. So, the minimum weight perfect matching problem can be reduced to the minimum weight $T$ -join problem by adding a large constant to each edge weight (to get a degree of 1 for each vertex in a $T$-join.)

I agree with this but I don't see how adding a large constant to each edge weight restricts the degree of each vertex to 1 in the $T$-join.

# Answer
> 1 votes
Since the algorithm is adding a large positive weight to each edge, the minimum weight $T$-join will have the minimum number of edges in it. Note that the least number of edges in a $T$-join for $T = V$ could be $|V|/2$. That is, each vertex has degree exactly $1$.

---
Tags: algorithms, graphs, matching
---


# Question
Title: What would be an efficient algorithm that finds the maximum number of party people?
You want to organize a party and invite as many of your N friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be familiar with at least three other guests. The input to the problem is number N and the list of pairs (i, j) where i and j know each other. What would be an efficient algorithm that implements the above mentioned and what's the complexity? Could I use some greedy approach?

# Answer
> 2 votes
Hint: It's actually quite simple.

(Yes, that's all the hint you need).

---
Tags: algorithms, graphs, greedy-algorithms
---


# Question
Title: How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford
I want to find how many shortest paths are there from Node A to node B. For example, let's say we have a graph with 3 nodes and 3 connections: from 1 to 2 weight 5 from 1 to 3 weight 11 from 2 to 3 weight 6 The answer is 2. Also I should keep track what vertices were visited for every path. In the example above, I would have 1 -\> 3 and 1 -\> 2 -\> 3 How can I do it? Both ideas and pseudocodes are welcomed. Thanks in advance.

# Answer
> 0 votes
As you cannot decide which are the interesting paths until you know the shortest length, a two-pass method is possible: 1) find a shortest path using your favorite algorithm, 2) enumerate all paths from source to destination and report those of that length, for example using DFS. As a micro-optimization, you can leave the partial paths that are longer than the shortest length.

---
Tags: graphs, graph-traversal, weighted-graphs, dijkstras-algorithm
---


# Question
Title: On proving the uncomputability of Kolmogorov complexity by contradiction
I have seen a proof by contradiction for the uncomputability of Kolmogorov complexity. The idea the basically the same as in the proof for halting problem (i.e., there are cases that lead to Berry paradox example). However, I would argue that since there are infinitely possible ways to interpret a given string, this fact already shows that in the worst case, you can't even iterate through any string, let alone finding the equivalent shortest string for a given string. Is there anything wrong to my reasoning?

# Answer
Kolmogorov complexity doesn't say anything about "interpret"ing a string or finding the equivalent shortest string for a given string, so your argument is not relevant. I don't know what it means to say that one can or cannot iterate through any string.

Kolmogorov complexity has a precise mathematical definition, as does the notion of computability. Arguments in informal English language can often lead one astray, as they might not correspond to the actual mathematical concepts.

---

Your comment clarifies that you're concerned that there could be an infinite number of programming languages that could be used. That's not correct. With Kolmogorov complexity, we first fix a programming language -- typically, Turing machines.

I suggest finding a textbook or lecture notes that covers this. Wikipedia is probably not sufficient as a resource, as there are important details that aren't listed there.
> 1 votes

---
Tags: complexity-theory, kolmogorov-complexity
---


# Question
Title: Bucket sort for gaussian / standard distribution
I know this post. But I still have no idea to adapt the bucket sort algorithm to handle input with a gaussian / normal distribution. Can someone provide me a Pseudocode / Python code for that? So far I tried the following, but sadly it does not work, and I don't understand why.

```
def bucket_sort(numbers):
    mean = sum(numbers) / len(numbers)
    variance = sum((x - mean) ** 2 for x in numbers) / len(numbers)
    std_deviation = math.sqrt(variance)

    num_buckets = int( math.sqrt(len(numbers)) )
    buckets = [[] for _ in range(num_buckets)]

    for num in numbers:
        index = int( ( (num - mean) / std_deviation) * num_buckets)
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_numbers = [num for bucket in buckets for num in bucket]

    return sorted_numbers

```

# Answer
> 1 votes
Let $F$ denote the cumulative distribution function for your distribution. Suppose you want $N$ buckets. Then use the following buckets:

$$(F^{-1}(0),F^{-1}(1/N)\],(F^{-1}(1/N),F^{-1}(2/N)\],\dots,(F^{-1}((N-1)/N),F^{-1}(1)\].$$

This ensures that about $1/N$ of the samples fall into each bucket. Then, use bucket sort with these buckets.

To compute which bucket a value $x$ falls into, it suffices to compute the cdf for $x$. In particular, $x$ goes into bin number $\lfloor F(x) N \rfloor$.

This works for any distribution, assuming the distribution is known and you can compute the cdf.

# Answer
> 1 votes
So I finally understand, what is happening. The input is distributed with a normal distribution. This leads us to a normal probability distribution function PDF for the probability of the elements. We can describe the distribution using the mean µ and derivative $\sigma$:

$$ µ = \frac{\sum\_{n \in N} n}{| N |} \quad \sigma = \sqrt{\frac{ \sum\_{n \in N} (n - µ )^2 }{| N |}} $$

The cumulative distribution function CDF is the integral over the PDF and creates a uniform random distributed output for the elements in the initial distribution. The reason for the uniformity is based on a phenomena called probability integral transform. In the case of normal distribution the CDF is closely related to the errorfunction, BUT NOT exactly the error function. A mistake that took me way too long to realise. The CDF is as follows:

$$ f(x) = \frac{1}{2} * (1 + erf(\frac{x - µ}{\sigma \sqrt 2})) $$

where $erf$ refers to the error function. Last but not least we want buckets and because we have an integral over probability, we only have values between 0 and 1. We can simply rescale using the number of buckets and we are done. This way, we can build a bucket sort for normal/gaussian distribution which is still in $O(n)$. My result:

```
import math
import scipy.stats

def bucket_sort(numbers, mean, deviation):
    # Just recompute here to see what happens
    mean = sum(numbers) / len(numbers)
    variance = sum((x - mean) ** 2 for x in numbers) / len(numbers)
    deviation = math.sqrt(variance)

    num_buckets = int( math.sqrt(len(numbers)) )
    buckets = [[] for _ in range(num_buckets)]

    for num in numbers:
        # index = scipy.stats.norm.cdf(num, mean, deviation)
        tmp = (num - mean)/(deviation*math.sqrt(2))
        index = 0.5 *(1+math.erf(tmp))
        index = int(index * num_buckets)

        # Append rescaled value to bucket
        buckets[index].append(num)

    for bucket in buckets:
        bucket.sort()

    sorted_numbers = [num for bucket in buckets for num in bucket]

    return sorted_numbers

# example call
mean = 50
std = 20
input = scipy.stats.norm.rvs(50,20,100)
input = [int(i) for i in input]
print(bucket_sort(input,mean, std))

```

I am not quite sure whether I should thank Yves Daoust or not :D At least he tried to help me, which I appreciate a lot, but I am sorry, your input wasn't quite helpful. What helped me a lot, was this post.

---
Tags: sorting, statistics
---


# Question
Title: Random paths from one point to another going through all the cells of a square grid
I am looking for a very specific algorithm, so I think it doesn't exist yet. I would be satisfied if anyone was able to give me some hints to develop it.

My problem is about a square grid of size `n x n`, where `n` is an odd natural number ≥3. For instance, it can be a 5 by 5 grid:

```
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.

```

The middle cell of the first column and the middle cell of the last column must be found:

```
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
| ● |   |   |   | ● |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.

```

Then, and this is the hardest part of the algorithm, I want to get a path from the left-most point to the right-most one, that goes through every cell of the grid.

For example, this is one possibility:

```
  > > v   > > > > v
  ^   v   ^       v
  ^   v   ^   v < <
  ^   v   ^   v
  ●   v   ^   v   ●
      v   ^   v   ^
  v < <   ^   v   ^
  v       ^   v   ^
  > > > > ^   > > ^

```

and this is another:

```
  > > > > v   > > v
  ^       v   ^   v
  < < <   v   ^   v
      ^   v   ^   v
  ● > ^   v   ^   ●
          v   ^
  v < < < <   ^ < <
  v               ^
  > > > > > > > > ^

```

This implies directly some obviousnesses. Let `a` be the number of up displacements, `b` down, `c` left and `d` right, we can know that:

* `a + b + c + d = n^2 - 1`
* `a = b`
* `d - c = n - 1`

I also want to randomize the creation of this path, and the best would be a uniform distribution amongst all the possibilities (I don't know their number but I am almost sure it increases as `n` increases).

I think it can be solved thanks to graph theory since my grid can be considered as an unoriented graph where the vertices are the cells and where two adjacent cells are linked with an edge. The problem is now equivalent to making a non-redundant graph traversal, but I have no idea where to begin.

I hope my question was clear enough, thanks in advance.

# Answer
> 1 votes
A depth-first search with backtracking algorithm would work. This algorithm tries all 4 directions and is capable of finding all possible paths.

In order to find a random path, you could traverse the 4 directions in a random order at each step, and stop the first time the path fills all the cells AND ends in the target cell.

Start with a grid filled with 0. The algorithm would set cells to a value greater than 0, counting the steps, beginning with 1 at the starting cell.

The algorithm stops and backtracks any time it walls itself in, like the Snake game. In this case, it resets the cell to 0.

But eventually it will find a solution, if one exists. Otherwise, all possible paths are traversed.

The number of paths grows very quickly, so in practice, this algorithm would take an enormous amount of time to complete, even for smaller grids of say size 9 or 11. Optimizations would be important, for example detecting loops that cut off empty cells and make them unreachable. This is considerably more complex to implement, but is essential for a decent runtime in practice.

Here's an example implementation in C#:

```
void Main()
{
    // define a 5x5 grid and start and end squares
    int Rows = 5, Cols = 5, StartRow = 2, StartCol = 0, EndRow = 2, EndCol = 4;

    // Grid starts with all zeros
    var Grid = new int[Rows,Cols]();

    bool CreatePath(int r, int c, int number)
    {
        // if out of bounds or a collision, don't move this way
        if (r < 0 || r >= Rows || c < 0 || c >= Cols || Grid[r, c] > 0)
            return false;

        // take the next step
        Grid[r, c] = number;

        // if all cells are filled, check whether path ends at the correct place
        if (number == Rows * Cols)
            return (r == EndRow && c == EndCol);

        number++;

        // recursively search in all 4 directions in a random order
        // note that the "return true" after each is an indicator
        // that a path has been found, and leaves the path in Grid.

        foreach (int direction in RandomPermutation([UP, LEFT, RIGHT, DOWN]))
        {
            switch (direction)
            {
                case UP:
                    if (CreatePath(r - 1, c, number)) return true;
                    break;
                case LEFT:
                    if (CreatePath(r, c - 1, number)) return true;
                    break;
                case RIGHT:
                    if (CreatePath(r, c + 1, number)) return true;
                    break;
                case DOWN:
                    if (CreatePath(r + 1, c, number)) return true;
                    break;
            }
        }

        // all searches have returned: backtrack out of this cell
        Grid[r, c] = 0;
        return false;
    }

    // start the search
    if (CreatePath(StartRow, StartCol, 1))
    {
        // print Grid
    }
    else
    {
        // No path exists
    }
}

```

This will find just one path meeting your requirements, but it can easily be modified so that instead of stopping it continues the traversal, so that it enumerates all possible unique paths.

---
Tags: graphs, randomized-algorithms
---


# Question
Title: Given an array of size $n$, return a sorted array of floor($n^k$) elements for some $k<1$
> We are given an array of size $n$ (it is not specified if we have an integer array, a specific range or any other assumptions), which might be unsorted, and a real number as a constant $k\<1$. We need to prove or disprove that it is possible to output the $\lfloor n^k \rfloor$ smallest elements of a sorted order, in $O(n)$ worst case time complexity.
>
> example: let $A$ be an array of size 4, and let $k=0.6$. The algorithm should output the smallest $\lfloor 4^{0.6}\rfloor \approx \lfloor2.29\rfloor = 2$ items in A in a sorted order.

I have two ideas here, one to prove the statement and one to disprove it, but not sure how can both be possible:

Disprove: Given that we are able to choose a $k\<1$ as we wish, choose a $k=0.9999...$ so $\lfloor n^k \rfloor = n-1$. Assuming by contradiction that this algorithm is possible, we can sort the $n-1$ smallest elements of $A$, and then append the largest element in $O(n)$. This leads to a contradiction resulting from the lower bound for comparison based sorting in $\Omega(n\log n)$.

Prove: use the following algorithm:

1. Find $\lfloor n^k \rfloor$'s rank in the array using median of medians and partition the array using it as a pivot.
2. Preform a Heapsort on a min heap created (in $O(n)$) from the elements smaller than $\lfloor n^k \rfloor$ following the partition.

for the sorting part, calculating the time complexity might generally look like this: As $\lfloor n^k \rfloor \le n^k$ , $\lfloor n^k \rfloor * \log(\lfloor n^k \rfloor) \le k\*n^k\*\log(n)$. As $k\<1$ $\lim\_{n\to \infty} \frac{k\*n^k\*\log(n)}{n} = \dots =0 $, so the sorting is in $o(n)$, and the entire algorithm is in $O(n).$

I think my main issue in both is understanding the asymptotic calculation vs the practical matter of sorting an array (or that my math is entirely wrong, which is an option).

What should be the correct idea/solution?

# Answer
> a constant $k\<1$

The answer depends on the understanding of the word "constant".

### The meaning of "a constant $k$"

Here is the expected interpretation.

You are asked to answer infinitely many questions. One of them is the following.

> We are given an array of size $n$. Is it possible to output the $\lfloor n^{0.6} \rfloor$ smallest elements in $O(n)$ worst case time complexity?

The answer to the question above is, as you have proved, yes.

Another such question is the following.

> We are given an array of size $n$. Is it possible to output the $\lfloor n^{0.999} \rfloor$ smallest elements in $O(n)$ worst case time complexity?

The answer to the question above is, as you have proved, yes. As you must have noticed, I am repeating myself, except that $0.6$ has been replaced with $0.999$.

Still another such question is the following.

> We are given an array of size $n$. Is it possible to output the $\lfloor n^{\frac1{10}} \rfloor$ smallest elements in $O(n)$ worst case time complexity?

The answer is, as you have proved, yes. As you must have noticed, I am repeating myself, except that $0.6$ has been replaced with $\frac1{10}$.

It turns out that whatever number is used to substitute for $0.6$, as long as it is between $0$ and $1$ exclusive, the answer is yes. This is the expected answer.

### Nitpicking on your proof

A vital piece is missing from the following statement.

> As $k\<1$ $\lim\_{n\to \infty} \frac{k\*n^k\*\log(n)}{n} = \dots =0 $, …

It should have been the following.

> As $k\<1$ **is a constant with respect to $n$**, $\lim\_{n\to \infty} \frac{k\*n^k\*\log(n)}{n} = \dots =0 $, …

If $k$ is not a constant with respect to $n$, for example $k=\frac{\log(n-1)}{\log n}$, that limit is no longer $0$.

On the other hand, you will probably not see the phrase "is a constant" in the official solution to this problem nor solutions to similar problems, since people will assume that phrase on that spot given the condition "a constant $k$" in the problem statement. In other words, your proof is pretty good.
> -1 votes

# Answer
The "disproof" is wrong, and the answer is positive.

Because there is no $k$ such that

$$\lfloor n^k\rfloor=n-1$$ for all $n$. You may *not* assume that $k$ is a function of $n$, this would amount to saying "sort *any number* of smallest elements".

On the opposite, with $m=\lfloor n^k\rfloor$, getting the $m$ smallest elements with Heapsort will take time $O(n+m\log n)$ and for *any constant* $k\<1$,

$$\lfloor n^k\rfloor\log n\le n^k\log n=o(n).$$

This is because

$$\log n=o(n^\epsilon)$$ for any $\epsilon\>0$.
> 1 votes

---
Tags: asymptotics, sorting, big-o-notation
---


# Question
Title: Why do simple Logical Gates have an Irrational amount of Bits?
Suppose $2$ bits are used to encode a message, A and B.

* If you know $A$ is $1$, you have one bit of information.
* If you know $A\land B$ is $1$, you have two bits of information.
* If you know $A\land B$ is $0$, you have $0.415$ bits of information.

**When is this number ever useful?**

P.S: The formula for calculating the information content is $-\log\_2\left(\text{probability}\right)$, and since the probability that $A\land B=0$ is $\frac{3}{4}$, we have $–\log\_2\left(\frac{3}{4}\right) = 0.415$ bits.

# Answer
> 2 votes
An amount of information does not need to be an integer, just like the weight of an object does not need to be an integer number of grams.

One might see as a source of confusion to give the same name to the unit of information and to a digit in the binary base. Of course this comes from the fact that a single equiprobable binary digit (Boolean value) conveys an amount of information equal to one.

When the distribution of a bit value is skewed, one of the amounts of information *must be* a fractional number because not two integer powers of $\frac12$ sum to $1$, except $\frac12+\frac12$.

In your example, the expectation of the amount of information of an *and* bit is

$$\frac14\text{colg}\frac14+\frac34\text{colg}\frac34=0.811\cdots$$

which shows the loss of information from the initial $2$ bits.

---
Tags: complexity-theory, logic, information-theory, boolean-algebra, entropy
---


# Question
Title: Quick and space-efficient way to find whether two sets intersect
I hope you can help me -

Given a lot of sets containing integers, **I'd like for any two sets, to quickly (i.e. `O(1)`) ask whether they intersect**. Note that I don't need the exact intersection, rather just a yes/no answer. Also, I am fine with some false-positives. Also, the representation of the sets should be space-efficient (i.e. less than the set-size).

Ideally, I'd also like to (infrequently) update the sets.

My requirements make me think of Bloom Filters, which 1)represent sets efficiently, 2)allow `O(1)` containment-test and 3) have some false-positives. Unfortunately it they don't apply to two-set-intersection.

Any ideas? Thanks!

(Just FYI, the sets are subsets of ids of adjacent edges from a huge graph)

# Answer
> 1 votes
Use a partitioned Bloom filter for testing set intersection. It has lower FPR than unpartitioned (standard) Bloom filters.

To intersect two partitioned Bloom filters:

1. AND the bit vectors for all the partitions.
2. Compare the range of bits for each partition to all zeroes in turn.
3. If ANY partition is all zero bits, the sets are likely disjoint.

If the sets ARE disjoint, on average you only have to compare half of the Bloom filter bits.

The comparison is fast, as you can rely on hardware parallelism to compare lots of bits in O(1) time. At worst it is O(log(M)) time.

However, the FPR for testing disjointedness of two sets is higher than the FPR for any given query. To match the desired FPR of a query, you must increase the size of the filter. The factor for the size increase is roughly sqrt(N) for set cardinality N.

The research on this is here:

https://www.eecg.toronto.edu/~steffan/papers/jeffrey\_spaa11.pdf

"Understanding Bloom Filter Intersection for Lazy Address-Set Disambiguation" by Mark C. Jeffrey and J. Gregory Steffan

# Answer
> 2 votes
Build a $k \times k$ table $ans$ of answers, storing in each entry the smallest (according to some total order) element in that intersection or a sentinel value (e.g. -1) if the intersection is empty, and also maintain a mapping from each element to the set of all sets that contains it (e.g. using a hashtable of hashtables).

When you add an element $x$ to a set $i$, you can efficiently find all other sets $j$ for which $ans\[i\]\[j\]$ might need to change, and the change itself is also simple: set $ans\[i\]\[j\] = \min(ans\[i\]\[j\], x)$. Removing an element will also be efficient, except in the rare case when you remove that minimum shared element, which requires fully recomputing (just) $ans\[i\]\[j\]$.

# Answer
> -1 votes
You might want to try Dynamic Partition Bloom Filters.

---
Tags: graphs, time-complexity, space-complexity, graph-traversal, bloom-filters
---


title: What is a procedure?

text:
# Question
Title: What is a procedure?
Non-computer scientist here, trying to understand what SICP (*Structure and Interpretation of Computer Programs*) means by a ***procedure***, whether it matches the dictionary definition, and also how a procedure relates to an algorithm (so maybe I should ask separate questions).

First, SICP defines a *process*:

> We are about to study the idea of a *computational process*. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called *data*. The evolution of a process is directed by a pattern of rules called a *program*. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.

This seems clear to me (although I did struggle with it in the past). It mentions processes run by e.g. a modern operating system, (ultimately) on a computer. They are evolving manipulations of data directed by a pattern of rules which is a computer program inserted in memory and made up by instructions. I've taken my share of the *From Nand To Tetris pt. I* course to understand what this means.

Later on, it goes:

> The most significant of these features is the fact that Lisp descriptions of processes, called *procedures*, can themselves be represented and manipulated as Lisp data.

I'm trying to conciliate this with the dictionary definition of *procedure*. I've bumped into the mention in SICP of a procedure receiving a name and being callable (or something like that; I couldn't find it again when I looked it up), so I suspect that both of them refer to the same concept. Also I'm aware that a process in the OS executes algorithmic instructions (i.e. instructions described by an algorithm), so this seems like a safe assumption to make.

> **Definition of *algorithm***
>
> (...)
>
> : a procedure for solving a mathematical problem (as of finding the greatest common divisor) in a finite number of steps that frequently involves repetition of an operation
>
> *broadly* : a step-by-step procedure for solving a problem or accomplishing some end

> **Definition of *procedure***
>
> (...)
>
> **2a** *(presumably related to 2b below)* : a series of steps followed in a regular definite order
>
> // legal *procedure*
>
> // a surgical *procedure*
>
> **2b** : a set of instructions for a computer that has a name by which it can be called into action

> **Definition of *operation***
>
> (...)
>
> **8** : a single step performed by a computer in the execution of a program (see program entry 1 sense 6a)

> **Definition of *program* *(Entry 1 of 2)***
>
> (...)
>
> **6a** : a sequence of coded instructions that can be inserted into a mechanism (such as a computer)

I must admit that I struggle with definitions sometimes.

So, the **2b** definition of procedure simply says a procedure is a set of instructions for a computer (should it have said a *sequence* of instructions I'd say it refers to the binary machine code in a program) that has a name (or, for that effect, any usable reference) by which it can be called into action. Despite it not being a sequence, it still sounds like it refers to a callable function.

So is the SICP definition the same as a function that can be called from its address (thinking of assembly, following a certain convention for passing arguments and returning a value)?

I've taken a look into the JavaScript edition of SICP and from what I recall it replaces procedures with functions in the text.

I'm aware that the Pascal programming language differentiates a procedure from a function. Based on my suspicion, it seems that all these definitions match (a Pascal procedure is the same as a SICP or dictionary procedure; and also simply a function that returns no value).

**So do both definitions match? Or is a procedure something trickier than it seems?**

**Bonus question, which definition of a procedure can I use to define an algorithm?**

Further dissecting the dictionary definitions, it seems to be that **a)** coded instructions are not the same as instructions (although both can be referred by the same name); **b)** an operation is the execution of a coded instruction by a processor, not the instruction itself; **c)** a procedure is defined as a set of instructions, possibly because a callable function in assembly is made up of multiple parts (i.e. the calling part which sets it up and the callee); **d)** in the definition of algorithm, I don't know what it means by *repetition of an operation* -- repetition of *operations* would make more sense to me.

P.S.: The question tags are a mess, but I'm not sure which ones to add.

# Answer
> 3 votes
A lot of this comes down to specific semantics. There are some core ideas that are switched around depending mostly on the language, I'll share the version that I'm used to and how they're different in different languages.

* A **program** is a complete list of instructions detailing receiving input, processing it, and producing output. It describes a sequence of **operations**, the smallest unit of action that a language can express, such as addition or control flow operations. Sometimes this is called a *computation*.
* A **function** is a named list of instructions that acts on some input, a sort-of shorthand for doing some nontrivial operation.
* An **expression** is anything which returns a value. This includes trivial operations like `a + b`, functions that return values, and other stuff. In essence, you can insert an expression into an equation of some sort. Usually these do not mutate the state of the input, but they may.
* A **procedure** is a function that does not return a value. Or in other words, functions that are not expressions. Usually these involve mutating the given state.
* An **algorithm** is a function that solves a specific provided problem (given as input) and eventually terminates.

These terms shuffle around depending on context, and even within one context. For instance, in Python, sorting can be a procedure `list.sort()` or an expression `sorted(list)`. Python calls both of these *methods*, which in turn means something more specific in Java. In Rust, everything is an expression, and there is basically no such thing as a procedure. in SQL, functions are what I call named expressions, and procedures are what I call procedures. I'm not sure about Lisp specifically as I haven't worked with it much, but it seems to be like SQL with named expressions being their functions, and procedures being their procedures. The main point is that a lot of this is semantics and highly depends on context.

However, as SICP states, in their context understanding procedures is important. In SICP, the significance of a procedure is described in the quote you provide: it can be manipulated as data. This idea is a little tricky to define, but the book itself goes into a lot more detail on this further on (In my copy of 2nd ed. it's in section 2.1.3). In essence, it means you can use conditions on procedures to validate behavior.

> Surprisingly, this idea is very difficult to formulate rigorously. There are two approaches to giving such a formulation... Both methods are surveyed in the paper by Liskov and Zilles (1975).

# Answer
> 3 votes
Almost every programming language has a way to specify sequences of instructions that can be reused (or used once). But programming languages don't agree on what these are called. Sometimes they are called procedures, or functions, or routines, or subroutines. I'm not aware of any languages which call them algorithms.

Apparently, in Lisp they are called "procedures" even though the keyword used to define them is `defun`.

It's best to treat these words as interchangeable, unless there is a specific context in which they have different meanings. You can see from the dictionary definitions you quoted that the words "algorithm", "procedure", "program" have at least one similar meaning - a sequence of steps to accomplish some task.

Visual Basic distinguishes between functions (which return values) and subroutines (which do not). Haskell distinguishes between functions (pure computations) and I/O operations. You wouldn't expect to find these distinctions in an English dictionary, but you would learn them when learning about these respective programming languages.

Dictionaries written for general audiences are not expected to have precise definitions of jargon - don't get caught up in the minutiae, like the fact your dictionary says a procedure has a name and an algorithm doesn't. These dictionary entries could have been written by different people at different times, and one thought of procedure names and one didn't. As you learn programming you will learn what each word means in the context in which you need to use it (such as a specific programming language) and the commonalities across different contexts.

It seems the author of SICP has chosen to use the word "process" to refer to the sequence of instructions, and "procedure" to refer to the way it is written in Lisp. I daresay that most programmers don't even make this distinction.

You might notice something similar in mathematical papers, too - authors will define precisely what they mean by certain words, and each paper may use a slightly different definition, while still conforming to the same general idea. For example, some papers will say that 0 is a natural number, and some will say it's not, but it doesn't matter because the set of integers greater than or equal to 1 by any other name smells just as sweet.

# Answer
> 1 votes
Outside computing, a *procedure* is a way of doing things. It usually has specific steps in a specific order, possibly to be executed by different parties.

In computing, an *algorithm* is a way of performing a certain computational task. For instance, quicksort is an algorithm for inline sorting. In the case of distributed or concurrent algorithms, different parties may be involved. For instance, we may discuss algorithms to solve the dining philosophers problem.

In computing, and more specifically, software development, a *procedure* is an executable piece of code, written in a programming language, usually with a name and, optionally, arguments, that can be called from other code. When executing the procedure, the computer will do whatever the code specifies. For instance, a procedure may specify sorting an array of items using quicksort.

So in computing, a procedure is code; an algorithm is not. A procedure may implement an algorithm; it cannot *be* an algorithm. Algorithms are often described using pieces of code; either pseudo-code or code in an actual programming language. Such code is not the algorithm; it illustrates or implements the algorithm. The algorithm is the method being used by the code.

(As explained in other answers, terms used to describe programming languages tend to be specific to the language; for instance,

* in Algol, we have *procedures*;
* in C, we call them *functions*;
* in Fortran, we call them *functions* or *subroutines*, depending on whether they return a value or not;
* in Pascal, we call them *functions* or *procedures*, depending on whether they return a value or not;

and these are just four of the tens of thousands of languages out there.

So it's a challenge for textbook authors to find and use generic terminology when discussing these things.)

# Answer
> 1 votes
Disregarding the context of programming languages, a procedure is an unambiguous decomposition of a task in elementary operations, such that it can be performed mechanically. It is implicit that the "operator" knows how to perform the elementary operations.

E.g. the procedure to solve the Hanoi Towers problem is a sequence of disk moves from one stick to another.

The procedure can be described by a textual "program", but not necessarily.

An algorithm is a procedure, with the special characteristic that it solves a problem of general interest.

E.g. a sorting algorithm is a generic procedure that applies in a wide variety of situations.

---
Tags: algorithms, computer-architecture, definitions, instruction-set
---


# Question
Title: Is the language of sums of integers regular?
Over the alphabet $\Sigma=\\{0,\ldots,9,/\\}$, is the following language regular:

$$L=\left\\{x/y/z:z=\mathrm{str}\bigl(\mathrm{int}(x)+\mathrm{int}(y)\bigr)\right\\}$$

where $\mathrm{str}$ maps an integer to its decimal representation, and $\mathrm{int}$ does the opposite thing.

It contains $0/0/0$, $10/34/44$, $1/999/1000$ and so on. It is not an homework or something, I am just curious.

# Answer
It is not regular. Consider the strings "$1^n/0/$" which must be followed by exactly n 1's. So with a finite state machine, after processing $1^n/0/$, we must be in a state $S\_n$ which ends up in an accepting state if and only if we process exactly n further 1's. So for n ≠ n', the states $S\_n$ and $S\_{n'}$ are different, which means the finite state machine has an infinite number of states.
> 1 votes

---
Tags: regular-languages
---


title: Vertex Cover on Comparability Graphs

text:
# Question
Title: Vertex Cover on Comparability Graphs
Is there anything known about the hardness of Vertex Cover on the subclass of comparability graphs? In particular, is it known whether the problem is still NP-hard?

Related Results: In "Modular decomposition and transitive orientation, McConnell & Spinrad, 1999" the authors show that the problem lies in P for co-comparability graphs. According to Wikipedia is is also known to lie in P for perfect graphs, but I haven't been able to find any results on comparability graphs.

# Answer
Vertex cover for comparability graphs is solvable in P-time:

1. Comparability graphs are (strongly) perfect ("Strongly Perfect Graphs", Berge & Duchet, 1984)
2. Independent set is P-time on perfect graphs (https://en.wikipedia.org/wiki/Perfect\_graph)
3. The complement of an independent set is a vertex cover, and vice versa

Independent set for comparability graphs is also listed as "Polynomial" at section "Unweighted problems" on the page of comparability graphs at at ISGCI.
> 2 votes

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


# Question
Title: Shortest string which all input strings is its substring
Given a set of input strings, how do I find a shortest string S so that all input strings appear as a substring of S?

for example:

```
foobar + bar -> foobar
foo + bar + rfo -> barfoo

```

I guess it's related to graphs, but don't know how to solve it.

1. first check all the "substrings", for example, "bar" to "foobar". Remove "bar".
2. the more two string share head and tail, the more likely they will be joined together, like nodes in a graph.

---

background:

> GCC seems to do an optimization where it combines string literals that share the same suffix.

https://stackoverflow.com/questions/51551068/

So I want to broaden this problem.

# Answer
This is called the shortest common superstring problem. It is NP-hard. Therefore, you should not expect any efficient algorithm that works for all possible inputs.

Like many NP-hard problems, I imagine you could solve it with a SAT solver or ILP solver, or use an approximation algorithm (see the Wikipedia article for one approximation algorithm).
> 1 votes

---
Tags: strings, substrings, string-matching
---


# Question
Title: How to cover elements with minimum amount of elements
I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem. I have elements from 1 to n and I am trying to cover all of the elements using the minimum amount of elements as possible. Each element can cover an amount of elements to the left (x direction) and an amount of elements to the right direction (y direction) I'm trying to get all of them connected, meaning that if i pick one element z, each pair of adjacent elements i and i+1 should be covered from z.

Let me explain with an example:

I have placed n=7 boxes here (the boxes are i=0,1,2,3,4,5,6)

In each box i have put the range it can cover from the x and y list i provided, for example, in box 0, we can see that it covers element from 0 to 1, box 1 can cover element 0,1,2,3, box 2 can cover from 1-3, etc.

The goal is to find the minimum amount of elements in order to cover the entire 1 to n elements.

```
This is an example:
If n= 7
x= 0 1 1 2 1 1 1 [how many elements you can cover to the left]
y= 1 2 1 2 1 1 0 [how many elements you can cover to the right]

#as you can see you can cover 1 element to the left from element 2, and 2 elements to the right from element 2

```

To clarify, the reason it is 0 in the first x element, is because you can cover 0 elements to the left, and 0 in the last y element because you can cover 0 elements to the right. **So from each element i, you can cover everything from i-xi and i+yi.**

> Answer: we could pick elements 2, 4 and 7 to cover all of the 7 elements (there are many other combinations). So the minimum would be 3 which is the right answer for this input

**The reason why I dont pick element 2 and 6**,(one might think they cover all of them) is because that would leave a gap between element 4 and 5 where they are not connected. So the minimum is not 2, but 3

What algorithm can solve this? I have looked at interval scheduling, as well as vertex cover, but vertex cover would not solve that just because you can cover for example element 6 from element 4, it does not imply vice versa. (if you look at the example) I have looked at dynamic programming and greedy algorithms, but they do not seem to solve the connecting issue, and would give the output of 2 and not 3, so Im a but clueless in how to tackle this so I am hoping that there is someone out there that can help me solve this, any advice, recommendations, youtube clips, pages and such are highly appreciated if you dont know or have the time to help Thank you in advance. If there are any clarifications needed let me know.

A solution i tried: Lets say i merge the two lists x and y to create an upper and lower bound we will get (0,1) (0,3) (1,3) (1,5) (3,5) (4,6) (5,6) meaning that index 0 can cover from 0 to 1, index 1 can cover from 0 to 3 etc. if i start from the left, and pick each square that covers a new element, in this case it would be correct, because it would pick 1,3 and 5. but what if i have the edgecase (0,1) (0,3) (1,3) (1,5) (3,5) (4,6) (0,6) then i would start from the left, and pick 1,3,5, when in fact, the right answer would be to only pick 6 (since it covers all of the elements)

# Answer
Create the set of intervals $\[3i - 3 \\, x\[i\] - 2, 3 \\, 3i + y\[i\] - 4\]$, i.e., the left endpoint of the $i$th interval is $3i - 3 \\, x\[i\]+1$ and the right endpoint is $3i + y\[i\] - 1$. Now look for a minimal cover of all integers $1,2,3,\dots,3n-4$ using these intervals. THe solution to that will be a solution to your problem as well. You can find the minimal cover very efficiently, in particular in $O(n \log n)$ time, using the method in https://stackoverflow.com/q/293168/781723.
> 0 votes

---
Tags: algorithms, algorithm-analysis, dynamic-programming, search-algorithms, greedy-algorithms
---


# Question
Title: What's the Big O runtime of a DFS word search through a matrix?
The problem is to try and find a word in a 2D matrix of characters:

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example:

board =

\['A','B','C','E'\],

\['S','F','C','S'\],

\['A','D','E','E'\]

Given word = "ABCCED", return true.

Given word = "ABCB", return false

Source: https://leetcode.com/problems/word-search/description/*

Solution:

```
static boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
                    return true;
                }
            }
        }

        return false;
    }

    private boolean search(char[][]board, String word, int i, int j, int index){
        if(index == word.length()){
            return true;
        }

        if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
            return false;
        }

        visited[i][j] = true;
        if(search(board, word, i-1, j, index+1) ||
           search(board, word, i+1, j, index+1) ||
           search(board, word, i, j-1, index+1) ||
           search(board, word, i, j+1, index+1)){
            return true;
        }

        visited[i][j] = false;
        return false;
    }

```

Assume we use a DFS to recursively check each character's 4 neighbours. What would be the correct runtime? I've read various thoughts on this but nothing conclusive.

My thoughts:

We have to check every character in the MxN matrix, so that gives us at least M\*N.

Then, for each character, we check in four directions for the length of the input string, so that would give us 4\*len. But then for each neighbour we go to, we potentially check each of its neighbours too, but only if they haven't already been visited. This is where I get slightly confused and I'm not sure how to calculate the correct runtime for this.

(Edited question to add exact problem and solution)

# Answer
The complexity will be $O(m\*n\*4^{s})$ where m is the no. of rows and n is the no. of columns in the 2D matrix and s is the length of the input string.

When we start searching from a character we have 4 choices of neighbors for the first character and subsequent characters have only 3 or less than 3 choices but we can take it as 4 (permissible slopiness in upper bound). This slopiness would be fine in large matrices. So for each character we have 4 choices. Total no. of characters are $s$ where s is the length of the input string. So one invocation of `search` function of your implementation would take $O(4^{s})$ time.

Also in worst case the `search` is invoked for $m\*n$ times. So an upper bound would be $O(m∗n∗4^{s})$.
> 16 votes

# Answer
I think the worst case is bound by O(n * m * 3^s), that's because we can't use a letter which we already used, therefore any node in the DFS would have 3 options and would obviously not consider the parent.
> 2 votes

# Answer
Based on Navjot's answer, I think the complexity should be $(\times 3^s)$, because except the first step, you can only chose from 3 directions. You cannot go back to the previous position.
> 0 votes

# Answer
For people wondering why the above algorithm is not TLE (Time Limit exceeded),

The time complexity is **not O(mn\*4^k)** but **O(mn\*3^k)**.

Assuming m,n = 6 and k=15,

**O(36\*4^15)** = 10^11 and **O(36\*3^15)** = 10^8.

Anything above 10^9 is TLE which above algo doesn't exceed.
> 0 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, recursion
---


# Question
Title: How can I tell if a bit pattern can represent offset gray-code?
I have a very poor understanding of gray code in general and I find it to be a difficult thing to learn. While trying to learn about it I stumbled upon this seemingly looking trivial question that I can't answer.

**Can the bit pattern **01110011** represent offset gray-code?**

What is "gray-code" and how do I construct it and recognize offset gray-code?

# Answer
> 0 votes
Yes. Any bit pattern can represent an offset gray-code number. Gray code is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).To fully understand it you need and example and compare with default binary. In binary:

```
1-> 0001
2-> 0010
3-> 0011

```

You can see that in binary when incrementing from 1 to 2, there are happening two bit operations. One is that the first bit turns off and second the 2'nd bit lights up. So this violates the rule of gray-code - "two successive values differ in only one bit".

In gray code it would look like this:

```
1-> 0001
2-> 0011
3-> 0010

```

Can you see the difference? When we incremented from 1 to 2, the first bit didn't turned off anymore and the second lighted up. So only one bit operation happened.

You can also check out this article which has a C program that generates gray-codes between 1-32 bits. Using-Gray-Codes

# Answer
> 0 votes
The gray codes are designed to cover all possible bit patterns (of a given length). So 01110011 is perforce a gray code.

The purpose is to enumerate all patterns while changing a single bit at a time.

E.g. 000 001 011 010 110 111 101 100

You don't recognize a code in isolation, the sequence matters.

---

The reason these codes were invented is practical: if you change two bits or more at a time, for instance in a mechanical device, you are never sure that the changes are perfectly simultaneous and unwanted patterns can be generated transitorily.

---
Tags: binary
---


# Question
Title: Is there an AI that can play "One of these things is not like the other" (Sesame Street)?
Refers to: https://en.wikipedia.org/wiki/One\_of\_These\_Things\_(Is\_Not\_Like\_the\_Others)

Some of the actual games

The idea is that there are four different objects, but one in particular stands out from the rest. I've always said that I didn't think AI would ever be able to this, that this is something that kids instinctually understand that computers never would. But now I'm thinking maybe it might? Is there an AI that could identify the "different" object and explain why it chose it?

# Answer
One of These Things (Is Not Like the Others): banana, apple, orange, shoe ?

*The item that does not belong in the group is "shoe."*

*The other three items, banana, apple, and orange, are all fruits commonly consumed as food. On the other hand, a shoe is not a fruit; it is a type of footwear typically worn on the feet. So, the shoe stands out as different from the others in terms of category and usage.*

Who do you think wrote this ?

---

Interestingly, the AI that did this has no reasoning capability (as confirmed by the creators), and instead assembles the words in a way that probabilistically matches the input question.

The lesson is that playing this game does not take any understanding, but just having met similar sentences in the past. IMO this strongly questions our own intelligence.

By the way, current AIs are also able to recognize these objects from the pictures.

---

Follow-up:

Is there another difference ?

*Yes, there is another difference between the items. The banana, apple, and orange are all natural objects, whereas a shoe is a man-made object. Fruits like bananas, apples, and oranges are produced by plants and occur naturally in the environment. In contrast, a shoe is a human invention, designed and manufactured for the purpose of protecting and covering the feet. So, in addition to the difference in category and usage, there is a distinction between the natural origin of the fruits and the artificial creation of the shoe.*
> 1 votes

---
Tags: artificial-intelligence
---


title: Empty regular expression

text:
# Question
Title: Empty regular expression
When my professor introduced regular expressions, he said that the empty string is the simplest regular expression, where it matches everything. How can this be true? I would think the empty string matches nothing, but perhaps I have an incorrect Computer Science understanding of what "null" or "empty" means.

# Answer
The empty regular expression matches one string: the empty string. That's not everything (most strings aren't the empty string) but it also isn't nothing (the empty string is a string, and the regular expression does match it).

In many programming languages with "regular expression" (regex) support, the default when you match a regex against a string is to consider it a match if any substring matches. Since every string has the empty string as a substring, the empty regular expression will match any string. But that convention isn't standard in computer science.
> 2 votes

# Answer
I wonder if you might be getting confused about the difference between the regular expression that matches only the empty string (often written $\varepsilon$, or sometimes written $\lambda$; it recognizes the language $\\{\varepsilon\\}$) vs a regular expression that does not match any string (often written $\emptyset$; it recognizes the language $\emptyset$, i.e., the empty set) vs the empty regular expression (which, by convention, matches only the empty string).

See What is the difference between the set containing the empty string and the set containing nothing at all?, What's the difference between phi and lambda in regular expression?, What are Lambda productions.
> 0 votes

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


# Question
Title: Why does Computer Science need so much math?
I'm taking some college courses and they have so much math. Why is that?

I'm very good with computers already software and a little bit of hardware and I fix other laptops/Desktops Linux Boxes, Macs etc..

Is this normal or is it just a requirement to get a good job?

# Answer
The activities you mention are not computer science but *hardware maintenance* and *system administration*. Computer science is about inventing new algorithms and data structures tailored to new unforeseen situations, it is about inventing new concepts that can be built into new programming languages, inventing new communication protocols, etc. These all require a great deal of knowledge, and especially mathematical knowledge, because they are based on mathematics. For example, do you believe you could competently design a 3D graphics library without having a good grasp of geometry and linear algebra? Do you think you can understand "exponential back-off" in network protocols if you don't understand "exponential" and some probability theory? How about understanding RSA encryption without knowing number theory? You will just have to trust your teachers a little bit there with the fact that math is good for computer science.

Of course, if all you want to do is system administration, configuration of software that was designed and written by someone else, and installing new graphics cards into old computers, or be a mid-range manager, then you don't need that much math – but you don't need a college degree either.

If computers were cars, we could describe the difference as one between a good mechanic, and an engineer with the ability to help design new cars – and such a car engineer would need to know, you guessed it, a lot of math.
> 12 votes

# Answer
Computer Science is essentially about *programming* computers, how to do it rigorously, efficiently and using methods that have been proven useful by generations of scientists. (To a lesser extent, it is also about *designing* new hardware at the bit level.)

The skills that you mention have nothing to do with programming, so better make up your mind about your future trade.
> 3 votes

---
Tags: operating-systems
---


# Question
Title: Markov algorithm for words of the form $ww$, $w\in \{a,b\}^*$
I need to construct a Markov algorithm as a set of an ordered rules which will recognize a language $L = \\{ww |w \in \\{a,b\\}\*\\}$ and give $$\begin{cases} Y, \\: \text{if given word is in L} \\ N, \\: otherwise. \end{cases}$$ Is there a solution for this problem?

UPD. Omitting the formalities Markov Algorithm is an ordered set of rules of the form $$ \begin{cases} u\_1 \to v\_1\\ \vdots \\ u\_n \to v\_n, \end{cases} $$ where $u, v \in \Sigma^\*$. Markov algorithm executes the first possible rule in this list, so order is important. For example, next set is a solution of the same problem for a language $L = \\{ww^R |w \in \\{a,b\\}\*\\}$:
$$ \begin{cases} Ca \to aC \\ Cb \to bC \\ CC \to T \\ a \to AC \\ b \to BC \\ CT \to N \[1\]\[2\]\\ AA' \to A'A\\ BA' \to A'B\\ A'A \to e, \text{e is an empty row}\\ A'B \to N \\ AT \to A'\[3\]\\ BB' \to B'B\\ AB' \to B'A\\ B'B \to e, \text{e is an empty row}\\ B'A \to N \\ BT \to B'\[3\]\\ G \to Y\\ e \to G \end{cases} $$ \[1\] if after converting all CC's to T there is a C, then word length is odd
\[2\] In this and similar cases the string we're working with still has some symbols except for the N, then we will need to clear the output but I've omitted it for brevity.
\[3\] check if the string has the same first and last symbols an remove them if yes.

Algorithm implementation for the word abba is: $$abba \to ABbaCC \to ABbaT \to ABBATT \to ABBA'T \to $$ $$ \to A'ABBT \to BBT \to e \to G \to Y.$$

# Answer
This is just some ideas to find the Markov algorithm, I have not tried to write it completely. In particular, I have not determined all priorities.

1. First, it could help to add a left-marker and a right-marker. To do that, just create rule:

> $\varepsilon \to LR$ ($\varepsilon$ is the empty word)

with low priority, and move the right-marker to the right with rules

> $Ra \to aR$
>
> $Rb \to bR$

with high priority.

2. Next, as you said, it is useful to find the middle of the word. You can use the tortoise and hare method to do that. The idea is to combine a tortoise $T$ that moves one letter at a time, and a hare $H$ that moves two letters at a time. When the hare reaches the end, the tortoise is in the middle. The following rule creates the tortoise and the hare.

> $L\to LTH$

Now the problem is that the tortoise and the hare must move at the same time. The idea for that is that after a move, the hare sends a "move signal" to the tortoise: for $x, y\in \\{a,b\\}$, add rules (in this order):

> $xM \to Mx$
>
> $TMx\to xT$
>
> $Hxy \to MxyH$

To check when the hare reach the right side, add rules (with the right priority relatively to the rules above):

> $HxR\to N$ (the length is odd)
>
> $HR \to SR$

3. Now you can reverse the word between the turtle and the right side (to transform $uu$ into $uu^R$). The idea is to **S**witch those letters into variables $A$ or $B$:

> $aS\to AS$
>
> $bS\to BS$

and to reverse the whole thing, for $x\in \\{a,b\\}$ and $Y\in \\{A,B\\}$:

> $xY\to Yx$

4. Now we can check if the word is of the form $uu^R$ (I think there is a simpler method than the one you gave, since we know the middle of the string):

> $aTA \to T$
>
> $bTB \to T$
>
> $aTB \to N$
>
> $bTA\to N$

5. Finally, when there is no more letters, the word is accepted:

> $LTSR\to Y$

Note: one might add rules to delete any other letter when there is a $N$.
> 0 votes

---
Tags: discrete-mathematics
---


# Question
Title: How can I transfer the following language into an context-free grammar?
My problem of understanding is how to create a new a before the b's if you create new c's.

Hopefully someone can help me out.

# Answer
> -1 votes
You can firstly spawn $k$ letter $c$'s providing an $a$ for every $c$ spawned, then start putting $m$ $b$'s between $a$ and $c$ adding $a$ for every $b$. Also letter $a$ can be created any number of times after all $b$ and $c$ letters are created. This approach can be done with the following CFG: $$G = (V, \Sigma, S, R), \\: V = \\{S, A, B, B', C, C'\\} \cup \Sigma,$$ and the rules are $$R = \begin{cases} S \to AC, \\ S \to AB, \\ C \to ACC', \\ C \to AC', \\ C \to ABC', \\ B \to ABB', \\ B \to AB', \\ C' \to c, \\ C' \to e, \\ B' \to b, \\ B' \to e, \\ A \to Aa, \\ A \to a. \end{cases}$$ This grammar is definetely not the most beautiful and short, I have put some safety checks there. However, it demonstrates the idea of my solution.

---
Tags: context-free
---


# Question
Title: Proof techniques and correctness proof of minimum cost to make string equal
I've lately been struggling to write correctness proofs for various algorithms, even when it is "obvious" to me that the algorithm works and is correct. For example, take the following problem:

Given a binary string $s$ of length $n$, you can perform an invert operation on index $i$ (0-indexed) which inverts the prefix of $s$ from index $0$ to index $i$ inclusive for a cost of $i+1$. What is the minimum total cost needed to make all characters of the string identical (i.e. $s$ will either be the string of all $0$s or the string of all $1$s)?

It is clear (to me) that the optimal way to do this is to simply loop through the array and invert the first $i$ characters to match the next character. But I am not sure how to turn this into a proof of optimality. An arbitrary algorithm could do something crazy, and I'm not sure how to argue that anything crazy is not better than the above algorithm. I'm looking for something rigorous, and not just the proof, but for the thought process leading up to the proof, because I want to be able to solve similar problems and convince myself that my solution is indeed definitely optimal.

# Answer
> 0 votes
Your string has k bit changes where bit i and bit i+1 are different. You reduce the number of bit changes by 1 by inverting the first I+1 bits. So that gives you a way to make all bits equal.

Then you need to prove that as long as you don’t invert the first I+1 bits the bit change from but I to I+1 will remain, so the set of inversions that you found is optimal. Each of those inversions is needed, but you can perform them in any order.

Now imagine a very similar problem that might be lot harder: The cost is not the number of bits changed, but the number of bits changed from 0 to 1. So inverting 0100 has a cost of 3, but inverting 0110 has a cost of two only. The same bit inversions are *necessary*. Can you reduce the cost by doing some unnecessary inversion twice? What is the difference in cost between doing inversion a then inversion b vs doing inversion b then inversion a?

---
Tags: algorithms, proof-techniques
---


# Question
Title: Selecting a submatrix of a binary matrix NP hard?
I have the following problem and I am wondering if it is NP Hard or not.

Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$. A rectangle is a set $R=I\times J$ with $I\subseteq\mathcal{I}$, $J\subseteq\mathcal{J}$ and its value is defined by $$f(R) = \left|\left\\{(i,j) : A\_{i,j}=1,i\in I,j\in J\right\\}\right|+\left|\left\\{(i,j) : A\_{i,j}=0,i\in \bar{I}\text{ or }j\in \bar{J}\right\\}\right|. $$ For a given binary matrix $A$, the problem consists in finding the rectangle with the highest value.

Thanks for any advice!

# Answer
Your problem is NP-hard. In particular, it is equivalent to maximum edge weight biclique problem (MWBP), which is known to be NP-hard.

# Maximum edge weight biclique

MWBP is the following problem: given a bipartite graph with weights on the edges, find a biclique that maximizes the sum of weights on the edges in the biclique. It has been shown to be NP-hard in papers in the research literature. There are also inapproximability results. See, e.g.,

I also want to highlight the following thesis, which discusses techniques for approaching this problem:

# Equivalence with your problem

If $R$ is a rectangle, let $n\_1(R)$ denote the number of 1's within $R$, $n\_0$ the number of 0's within $R$, $n\_0(\overline{R})$ the number of 0's within $\overline{R}$ (i.e., the entries that are not within $R$), and $n\_0(A)$ the number of 0's within the entire matrix. Then $n\_0(A) = n\_0(R) + n\_0(\overline{R})$, so $n\_0(\overline{R}) = n\_0(A) - n\_0(R)$. Also your objective function $f$ is defined as

$$f(R) = n\_1(R) + n\_0(\overline{R}).$$

Therefore

$$f(R) = n\_1(R) - n\_0(R) + n\_0(A).$$

Of course, $n\_0(A)$ does not depend on $R$, so maximizing $f(R)$ is equivalent to maximizing

$$g(R) = n\_1(R) - n\_0(R).$$

Now this in turn is equivalent to a MWBP problem: you replace all the 0 entries in $A$ with $-1$; then the goal is to find a rectangle $R$ where the sum of entries in $R$ is maximized; but treating that matrix as the adjacency matrix of a bipartite graph, each rectangle $R$ corresponds to a biclique, and maximizing the sum of entries in $R$ is equivalent to maximizing the sum of edges in a biclique.

It follows that your problem is equivalent to the MWBP problem, and therefore is NP-hard.
> 1 votes

---
Tags: complexity-theory, np-hard, combinatorics, matrices
---


# Question
Title: which formula should i use with this Question
**Here is the Question :**

**The hit ratio is the percentage of times that a page number is found in the Translation look-aside buffer (TLB). An 80% hit ratio means that we find the desired page number in the TLB 80% of the time. Suppose we have a hit ratio of 70% and 40 ns is needed for TLB, where main memory access time is 80 ns. Calculate the EAT (effective access time)**

I found many formula I'm kinda lost with this Question

The first formula

EAT = (Hit ratio * Hit time) + (Miss ratio * Miss penalty)

the second formula EAT = TLB + (2 – hit ratio) * main memory access

the third formula

EAT = Hit Ratio\* TLB Access Time + Miss Ratio\* (TLB Access Time + Main Memory Access Time)

I appreciate the help for guide thought the correct one

# Answer
> 0 votes
Assume that you perform 100 accesses. 70 of them will take 40 ns and 30 of them 40+80 ns. On average 64 ns.

Can you derive the formula from this ? (Or compare to the results with the given formulas.)

---
Tags: operating-systems
---


# Question
Title: Queries to count points lying on arbitrary line
Suppose we have $N$ points on $XY$ plane, ie. $(x, y)$ and $x, y \in Z$ and multiple queries where each query is of the form $y = mx + c$ and $m, c \in Z$.

Is it possible to count number of points that lie on the given line more efficiently than $O(N)$ per query?

I believe some preprocessing might help or some data structure like QuadTree that counts points inside arbitrary rectangle.

The queries are offline so if it's possible using some batch processing technique or even SQRT optimization it would be better than naive brute force.

# Answer
Note that via point-line duality (i.e. mapping each point $(p\_x,p\_y)$ to the line $y=p\_x x - p\_y$ and each line $y=mx +c$ to the point $(m,-c)$), this problem is equivalent to: given a set $L$ of $n$ lines, count the number of lines that contain a query point.

The subdivision of the plane induced by $L$ is known as an arrangement of lines $\mathcal{A}(L)$, and has a complexity of $O(n^2)$. A doubly connected edge-list (DCEL) that represents the faces, edges and vertices of $\mathcal{A}(L)$ can be computed in $O(n^2)$ time. For each vertex of the DCEL, store the number of lines intersecting it. Next, construct a trapezoidal decomposition of the DCEL in $O(n^2\log n)$ expected time.

When given a query point, first find the trapezoid that contains the point, then traverse the boundary edges and vertices of the trapezoid to determine whether the query point coincides with an edge, face, or vertex. Finding the trapezoid takes $O(\log n)$ expected time, the rest takes $O(1)$, as a trapezoid has $O(1)$ vertices and edges.

---

So, with $O(n^2\log n)$ expected preprocessing time and $O(n^2)$ expected storage, queries can be answered in $O(\log n)$ expected time. This is one way to get a smaller query time, although the storage requirement is rather large, so there may be a better way.
> 8 votes

# Answer
Depending on the size of N (the number of points) and M (the number of queries), it may be enough to precompute all the answers: there are no more than N\*N possible lines. :-) You can represent all lines by exact slope and 0-crossing using reduced (i.e. simplified) rationals. Then search. Binary search, hashing, perfect hashing, etc.

With the constraint that slope and 0-crossing are integers in queries you can probably discard some lines, and perhaps use some optimizations such as using an array indexed by m,c. You can run a prepass to compute minimum and maximum m and c.

Update: this idea **fails for** the case where the answer is **exactly one**. See comments. :-(
> 0 votes

---
Tags: data-structures, optimization, computational-geometry, range-query
---


# Question
Title: Compile procedural code to pure stack operations
I asked this question specifically about why the JVM has a separate area for local variables: https://stackoverflow.com/q/76086392/1463507

It was answered satisfactorily within the scope of the question, but it made me realise my real question is actually not what I asked, but rather this:

Is it possible to compile procedural code down to relatively "pure" stack operations, i.e. such that they don't need to reference values arbitrarily deep down in the stack?

My only experience with stack-based languages are not Turing complete ones, but constrained to RPN calculators. With those, I have yet to find a nested arithmetic expression that cannot be evaluated with a very limited stack depth, as long as the subexpression evaluations are sequenced cleverly.

I suspect if I had more experience with Forth I could use that experience to intuit the answer, but I don't, so I turn to you! Is there some easy example or obvious property of procedural languages that prevent them from being compiled to pure stack operations?

# Answer
No. You need a heap, for dynamically sized data structures like linked lists, trees, graphs, etc. You can't simulate that with a stack in the way you're looking for.

(I am assuming that each element stored in the stack is fixed size, e.g., 64 bits, and that each operation can only look at the top 2 elements of the stack, say, and only a finite amount of additional memory, say 16 registers of 64-bit values.)

The justification comes from the separation between pushdown automata and Turing machines: there are things that can be computed with a Turing machine or a RAM model machine that cannot be computed by a pushdown automata.
> 1 votes

# Answer
Conceptually, you can always copy the local variables to the new stack frame upon entering a block, and copy back upon exit. So if you give no other constraint, the answer is yes, you can live with the last stack frame.
> 0 votes

---
Tags: compilers, stacks
---


# Question
Title: Are "computable problem" and "computable function" the same thing?
I'm confused by the use of the expressions "computable problem" and "computable function" in the context of computability theory. Are they refer to the same thing or are there differences?

# Answer
They're basically the same, in informal usage. They're not necessarily exactly 100% identical.

A computable function is often defined to be a function $f:\mathbb{N}^k \to \mathbb{N}$, or a function $f:\mathbb{N} \to \\{0,1\\}$, or a function $f:\\{0,1\\}^\* \to \\{0,1\\}$, that can be computed by some algorithm (e.g., a Turing machine that always halts). These definitions are all basically equivalent, up to encoding of the inputs and outputs.

A decidable language is a set $L \subseteq \\{0,1\\}^\*$ that can be decided ("computed") by some algorithm. It is also sometimes called a recursive language.

These are basically equivalent: for instance, any function $f:\\{0,1\\}^\* \to \\{0,1\\}$ corresponds to a language $L=\\{x \mid f(x)=1\\}$, and $f$ is computable iff $L$ is decidable; and conversely the language $L$ corresponds to the function $f(x) = 1$ if $x \in L$, $f(x) = 0$ otherwise.

A "computable problem" is a slightly more informal term, and probably refers to a problem that can be formulated as either a function or a language, and where that function/language is computable/decidable.

Introductory textbooks may choose one of these formalisms and definitions and then work with it in a precise and rigorous and careful way, carefully distinguishing these concepts. Professionals who are experienced in this field might speak a bit more informally and not bother to distinguish between these concepts, as they are after all basically equivalent.

That is my impression about how those terms are normally used, in the absence of any context. Looking at the specific context might influence the interpretation of those terms.
> 17 votes

---
Tags: computability
---