# Question
Title: Intuitive explanation of Hoare assignment axiom
$\small\textit{''The obvious things are the most difficult to understand''}$

May be the question does not make sense, but let me ask it anyway.

The Hoare assignment axiom is $$ \dfrac{}{\\{Q\[v \mapsto expr\]\\} \\;\\; v:=expr \\;\\; \\{Q\\}} $$

**Is there an *intuitive* explanation of the axiom?**

I "agree" with the Floyd assignment axiom: $$ \dfrac{}{\\{Q\\} \\;\\; v:=expr \\;\\; \\{\exists old: Q(old,..) \land v=expr(old,...)\\}} $$ which can be thought as "if `Q` holds before the assignment, then after the assignment we know that the variables should satisfy: 1) `Q(old)` holds for some old variables (since we assume `Q` holds), 2) variable `v` has the new value`expr(old,...)`".

Is there a similar intuition for the Hoare assignment axiom?

# Answer
> 7 votes
Hoare Logic proceeds backwards. It is a method to compute a *precondition* such that the desired postcondition holds. In fact, the inference rules given in your standard Hoare Logic deductions compute weakest preconditions, or the most "specific" precondition that still guarantees that the post-condition holds at the next program point.

I think this is the salient difference. There's no comparable interpretation (of reasoning about the next program point) for backwards predicate transformers because we have to reason about the "state" before an operation given that we know its "state" after. In comparison, the alternative axiom reasons about the postcondition given a precondition.

Now, the two axioms are duals of each other, in the sense that the backwards axiom computes a weak precondition while the forward axiom computes a strong postcondition (most "general" postcondition such that all possible postconditions are subsumed). Logically, they are equivalent. Therefore, not only do we have a singular backwards intuition of the Hoare axiom, but we should also have some sort of connections between the intuitions behind the backwards axioms and those behind the forward axioms.

* *The intuition behind the backwards axiom*: This is actually relatively easy to see, given that you know what the deduction system is doing. Let's look at the Hoare assignment rule: $$ \frac{}{\\{P : Q \[x \mapsto e\]\\} ~x = e ~\\{Q\\}} $$ which roughly says that the weakest precondition of $Q$ preceding an assignment $x = e$ is just $Q$ with every occurrence of $x$ replaced by the expression $e$. To see this in action, say you have the goal $Q = (x^2 = 4)$ and you want to see if $x = 3$ satisfies this goal. Well, the assignment axiom tells us that we should transform this post-condition into $(x^2 = 4)\[x \mapsto 3\] \to (9 = 4) \equiv \bot$, which says that there is no precondition that can get us to the goal. On the other hand, a goal of $Q = (x^2 = 9)$ allows us to compute a weakest precondition of $(9 = 9) \equiv \top$, so any precondition will satisfy this program.
* *The connection between the forward and backward systems*: Recall that we said that the two deduction systems are duals of each other. In other words, given a deduction (in the form of an inference rule) in the forward system, we can infer a similar deduction (in the backward system) by joining the leaves/exit points of this tree together, and inverting the proof. In other words, there's a (rough) correspondence. Suppose that the forward system is characterized by the rule function $F$, such that $F(\\{\phi\_1, \dots\\}) e$ returns the set of propositions that *might* hold after executing $e$ given that we know $\\{\phi\_1, \dots\\}$ before hand. Similarly, we also have a backwards rule function $B$, such that $B(\\{\psi\_1, \dots\\}) e$ returns the set of propositions that *must* be true before $e$ so that $\\{\psi\_1, \dots\\}$ holds afterwards. We can see that $$ Q = B(F(Q)) $$ (though the other direction $Q = F(B(Q))$ does not necessarily hold, since $B$ can produce $\bot$ and $F(\bot) = \bot$)

# Answer
> 3 votes
The precondition is in fact the *weakest (liberal) precondition* that guarantees a valid Hoare triple for that postcondition and assignment statement. ("liberal" because termination is not considered.) So what does this precondition express? The precise condition that has to hold if we "undo" the assignment but want the postcondition: everything in the state is the same except for the value of the variable we assign to.

So maybe alluding to a common "undo" operation can connect to your students' understanding.

# Answer
> 0 votes
What about just considering a simple case? Let `Q: x != y, v: x, expr: 3`. Then if `3 != y` before executing `x := 3`, then `x != y` afterwards. Can you see why (and an example which would fail if you e.g. exchange pre- and postconditions in the rule)?

---
Tags: hoare-logic
---


# Question
Title: Resulting complexity class for allowing two passes over witness in NL?
I know that when an NL Turing machine is allowed to go back and forth freely, the resulting class of problems solvable on it is NP.

But limit of two passes over the witness tape, does not seem to add much power to the NL machine, if at all.

I am stuck on this problem. What is the resulting complexity class? Is it still NL? How do I prove this?

# Answer
Any finite number of passes will still give you NL. Here is why two passes give you NL — the general case is very similar. You can guess the state of the work tape after the first pass and them simulate the two passes in parallel. In the end you verify that the state of the work tape after the first pass in indeed what you guessed earlier.
> 3 votes

---
Tags: complexity-theory, nondeterminism
---


# Question
Title: Calculating the difference between two dates in different timezones in hours and minutes
I need to calculate the difference between two dates in hours and in minutes which is what the code below does. The only issue I have is that the dates and the location (timezone) has to be input by the user. How do I achieve that? Can be a different language from PHP as I only need a flowchart and the pseudocode.

?php

$departure = new DateTime('8pm March 27, 2016 America/New\_York');

$arrival = new DateTime('7:20am March 28, 2016 Europe/London');

$flighttime = $departure-\>diff($arrival);

echo "$flighttime-\> h hours $flight\_time-\>i minutes";

Output: 7 hours 20 minutes

# Answer
> 1 votes
TimeA -\> ConvertToTimeZoneUtc -\> NormalizeToGreenwichUtcTime -\> ConvertToTicks Same for timeB ( ticksA - tickB) =\> timepsan. GetHours | GetMins

Is that ok?

---
Tags: algorithms, programming-languages
---


# Question
Title: importance of alternate storage in external sort
I'm trying to understand how external sorting works from the book "Data Structures and Algorithm Analysis" by Mark Allen Weiss.

The author illustrates an example where he tries to sort 81,94,11,96,12,35,17,99,28,58,41 with a memory which can hold upto M=3 numbers. He uses two input tapes Ta1,Ta2 and two output tapes Tb1,Tb2.

```
Ta1    81,94,11,96,12,35,17,99,28,58,41
Ta2
Tb1
Tb2

```

In the first step M numbers are read into memory then, sorted and written to Tb1 and Tb2 alternatively.

```
Ta1
Ta2
Tb1    11,81,94   17,28,99   15
Tb2    12,35,96   41,58,75

```

I understand how the algorithm works but, don't understand why it is important to write results alternatively. Couldn't this be achieved without alternating?

# Answer
I believe the alternation is done to ensure that the data is split as closely as possible into equal-sized subsets, which minimizes the time spent on each later pass.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Advice needed. NLP and ML. Where to start?
Hi fellow computer scientists,

I just began my journey to the world of ML and NLP so please bear with me. I'm hoping to find some guidance here. I would be very grateful if anyone could point me in the right direction (reading materials, lectures, specific algorithms, tools, etc.) for solving the following list of problems:

1. Spell checking, grammar checking, proofreading with ML
2. Text generation on a given topic with ML
3. "Artistic Style Transfer" for articles (if it is even possible), i.e. "transfer" Shakespeare's writing style onto a given text.

I've done some learning already but neither of this helps:

1. ML lectures by Andrew Ng
2. Hacker's guide to Machine learning
3. Udacity's Introduction to Deep Learning

# Answer
> 3 votes
As far as I can see, your reading list lacks specific NLP introductions. A really good starting point is Dan Jurafsky and Chris Manning's Coursera course (for example here https://www.youtube.com/watch?v=nfoudtpBV68 ). This specifically covers spell checking in one of the first videos.

In general, spell checking is a rather easy task, while (convincing) text generation is a lot harder. Grammar checking should be easy in theory but I'm not sure about that. Concerning proofreading, I'm not completely sure what you mean by that. Does this extend over spell and grammar checking, in your point of view?

Artistic style transfer is possible although I'm not sure what the current state of the art. You could be more luckily diving into stylometry (https://en.wikipedia.org/wiki/Stylometry) there.

A really good NLP text book to start with is Jurafsky and Martin: Speech and Language Processing (specifically covering generation). 1st edition is publicly available as pdf (just google). But there is also a 2nd edition and they are currently working on a 3rd (the chapters they are done writing are freely available as well).

# Answer
> 3 votes
> 1. Spell checking, grammar checking, proofreading with ML

Norvig: How to Write a Spelling Corrector

> 3. "Artistic Style Transfer" for articles (if it is even possible), i.e. "transfer" Shakespeare's writing style onto a given text.

Yes, it is possible. Recurrent neural networks can do this. See The Unreasonable Effectiveness of Recurrent Neural Networks for a nice explanation how this works and Creativity in Machine Learning for a very high-level introduction.

If you want a general introduction to neural networks, I recommend

> Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” Nature, vol. 521, no. 7553, pp. 436–444, 2015. \[Online\]. Available: http://www.nature.com/nature/journal/v521/n7553/abs/nature14539.html

---
Tags: machine-learning, natural-language-processing, edit-distance
---


# Question
Title: Convex-hull of a star shaped polygon in O(n)
I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows:

> A polygon $P$ is star-shaped if there exists a point $p$ in the interior of $P$ that is in the shadow of every point on the boundary of $P$. The set of all such points $p$ is called the kernel of $P$.
>
> Given an $n$-vertex, star-shaped polygon $P$ specified by its vertices in counterclockwise order, how to compute convex hull of this polygon in linear time.

According to these slides (slide $64$), it's really possible to find such a convex hull in linear time using Graham's Scan. This result is given as a corollary. This means that we probably need only the "*scan*" part of the Graham's Scan algorithm to solve this problem.

---

Imagine we have the following *star-shaped* polygon $P$:

and lets pick the point with the lowest $y$ coordinate of $P$, i.e., $p\_2''$. If I'm not wrong, start from there, the steps applied would be:

1. Pick the next vertex, i.e., $p\_3''$.
2. Lets consider the vertex $a$. We check if $p\_2''p\_3''a$ is a left or right turn, by using the cross product $(p\_3'' - p2'') \times (p\_3''- a)$. Since it's a left turn, we pick $a$.
3. We now consider $p\_3''ab$. It's also a left turn, so we pick $b$.
4. We now consider $abc$. We also have a left turn, so we pick $c$.
5. Consider $bcp\_1'$. It's a left turn, so we alsp pick $p\_1'$.
6. $cp\_1'p2'$ is a right turn. Thus we need to remove from the stack $p\_1'$. Thus, so far we have included the following vertices in the $CH(P) = p\_2'', p\_3'', a, b, c, p\_2'$.
7. We consider $cp\_2'p\_3' = cp\_2'p\_1''$ (just notation). It's a left turn, so we should include $p\_3' = p\_1''$. $CH(P) = p\_2'', p\_3'', a, b, c, p\_2', p\_3'$.
8. We now consider $p\_2'p\_3'p\_2''$. It's a right turn, so we should remove all points which create a right turn with $p\_2''$, i.e. , $p\_3' = p\_1''$, but also $p\_2'$, because of $cp\_2'p\_2''$. So, now our final $$CH(P) = p\_2'', p\_3'', a, b, c, p\_2''$$

The (literally) Graham's scan seemed to work in this instance, but I would not know for sure if it would work in general.

---

I tried to think about other ideas to solve this problem, since I was not sure this Graham's scan is correct, but it was mostly because I was not considering as initial point the one with the lowest $y$ coordinate.

If Graham's scan is enough to solve this problem, then the order given of the vertices, as specified in the problem above, must be related to one of the necessary orderings of the vertices required in a usual Graham's scan. I'm talking about sorting the points by polar angle in counter-clockwise around the initial chosen point $p\_0$ or about sorting the points according to their $x$ value.

---

I would appreciate an explanation of the corollary in the slide I'm mentioning above, provided it's really a corollary.

# Answer
Graham scan for a convex hull works if you have an ordering of points $a\_1,a\_2,...a\_N$ such that you have a sequence $p\_1 \< p\_2 \<...\< p\_k$ where your convex hull is $a\_{p\_1}, a\_{p\_2},...,a\_{p\_k}$ of which it is not possible to have a winding number greater than $1$.

In general for any polygon $P$ this might not work, but for a star shaped polygon, you could observe that from the point $p$ visible to all points, in counter-clockwise order, will be have the aforementioned property.
> 2 votes

---
Tags: computational-geometry, convex-hull, polygons
---


title: Memoization without array

text:
# Question
Title: Memoization without array
In Cormen et al.'s *Introduction to algorithms*, section 15.3 *Elements of dynamic programming* explains memoization as follow:

> A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time that we encounter this subproblem, we simply look up the value stored in the table and return it.

And it adds, as a footnote:

> This approach presupposes that we know the set of all possible subproblem parameters and that we have established the relationship between table positions and subproblems. Another, more general, approach is to memoize by using hashing with the subproblem parameters as keys.

Is there any well-know DP problems that requires (or makes it easier) to store memoized values in a dictionary rather than in a (multi dimensional)array?

---

Background: if this is of any use, the reason for this question is that I'm trying to motivate the notion of (self-balanced) binary search trees to people that has just seen dynamic programming.

# Answer
> 5 votes
There are probably better examples, but here is one, off the top of my head:

Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance. You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place where the edit distance is known to be $\>d$. This means you probably won't need to fill in the entire table; you'll only need to fill in some of the entries. Thus, using a dictionary can give a performance boost.

# Answer
> 3 votes
I would like to provide 2 examples.

## 0-1 Knapsack problem

In case of the 0-1 Knapsack problem (where *W* is a capacity of the knapsack and *N* is an amount of items), sometimes it is better to use the top-down Dynamic Programming with memoization, instead of the systematic bottom-up enumeration of entire 2D array of size *WxN* (especially in a case when the capacity of the knapsack *W* is big, but the cardinality of the set of the *allowed combinations of weights of items* is much smaller than *W*).

In this case, for the sake of economy of a memory, one may choose to make use of the dictionary for memoization instead of the 2D array.

## Earley parsing algorithm

Earley parsing algorithm can be used for the parsing of statements, which belong to a context-free grammar. As opposed to the CYK algorithm (which is based on the bottom-up DP approach, and uses 2D table for memoization) - Earley parser uses the top-down approach in combination with the parsing chart for memoization.

Parsing chart contains the partially parsed grammatical productions (e.g.: given the production *X → A B*, and after successful matching of the *A* part of this production, we store the partially matched production inside the parsing chart: *X → A • B*, where dot points to the already matched part).

The amount of columns inside the parsing chart equal to the amount of tokens. However, in general case it might be very tricky, to estimate the amount of partially parsed grammatic productions per column (it depends on the grammar and the particular sequence of tokens).

Hence, it is more convenient to implement the parsing chart based on the dictionary data structure.

In the Natural Language Processing domain, usually Earley pareser is more convenient choice, because it doesn't require the Chomsky normal form for the grammar (and CYK does have such requirement).

# Answer
> 0 votes
In my experience from competitive programming, using a hash table (Python's `dict` or similar) is often more convenient than using an array, because any hashable data type can be used as key, such as strings, sets (`frozenset` in Python) or tuples like `(string, int)` etc. If using an array you must manually translate all keys into integers (starting at 0), which takes extra work and, as your source notes, may not be possible if you don't know the space of keys in advance. So dictionaries are rather more general than arrays.

Of course, if you can get away with using arrays it is probably faster because it avoids repeatedly computing hashes (on the other hand it requires initialising the whole array first, which takes time and memory), but it may take longer to write the code because you have to do the extra work of translating all keys into integers.

---
Tags: dynamic-programming, search-trees, dictionaries, memoization
---


# Question
Title: Shortest path between 2 vertices using at most K edges using Bellman-Ford
I'm a bit confused about stopping at Kth iteration on the Bellman-Ford algorithm to find the shortest path of at most length k from s to t. Let me show you a graph and explain you what I understand:

At first iteration, I will have:

* Shortest path to get to A is S-\>A (cost 1)
* Shortest path to get to B is S-\>B (cost 4)
* Shortest path to get to T is still unknown

At second iteration I will have:

* Shortest path to get to A is S-\>A (cost 1)
* Shortest path to get to B is A-\>B (cost 2(A-\>B) + cost 1(S-\>A) = 3) **updated!**
* Shortest path to get to T is B-\>T

But now going to B takes 2 edges instead of 1, so going to T is 3 edges away now: S-\>A-\>B-\>T, and this has happened in 2 iterations.

What am I understanding wrong?

# Answer
The bellman ford algorithm presents to us the ***cost*** of all the shortest paths from a source vertex to all the other vertices . For constructing the ***path*** we reconstruct it after the algorithm has terminated and returned to us the cost. We backtrack on our solutions and reconstruct the path so don't get confused if you don't get the correct path at an intermediate step of the algorithm. (Just for some additional information while coding the algorithm you might have notices the use of an two dimensional array which stores solution at each step . the same is used to reconstruct the path.)

The recursive definition of the algorithm is

$\delta^{k+1}(v) = \min \Big(\delta^{k}(v), ~ \min\_{x\in\mathbb{N} - \\{v\\}} (\delta^k(x) + w(x, v) ) \Big) $

For the example which you have presented

* When the edge budget is $0$ :

The shortest path from **S** to **T** is $+\infty$.

* When the edge Budget is $1$ :

we till have the cost to be $+\infty$.

* When the edge budget gets $2$ :

We update the cost of our path to : $7$

* When the edge budget is $3$:

We now get the following : $\min ( 7 , \min (6))$

Hence giving the final cost as $6$.
> 2 votes

# Answer
In every iteration, all values are updated at once and they only use values from previous iteration. Imagine the program first calculating ALL of the new values before updating what is stored in memory (and therefore beginning to use these new values). In reality you probably have two arrays, one containing the previous iteration's result and the second one being filled in with the new values.
> 1 votes

---
Tags: graphs, shortest-path, dynamic-programming
---


# Question
Title: Is there an example of Dinitz's algorithm running with the worst time complexity?
I am trying to find a network, where Dinic's algorithm makes $|V|^2\*|E|$ steps. Clearly it cannot be a network with $3$ or less vertices, but I am not able to come up with a working example for quite a while now.

Any idea?

# Answer
1. Dinic's algorithm runs in $O(|V|^2 \cdot |E|)$ time, so it might never make $|V|^2 \cdot |E|$ steps.
2. Finding a single example is insufficient, as any finite-size counterexample can be "hidden" as a constant in asymptotic notation. You will need an infinite sequence of networks of strictly increasing size with a lower time bound of $\Omega(|V|^2 \cdot |E|)$ to prove that the bound is indeed tight.
> 2 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, network-flow
---


title: Selling blocks of time slots

text:
# Question
Title: Selling blocks of time slots
Given $n$ time slots that $k$ people want to buy. Person $i$ has a value $h(i,j)\geq 0$ for each time slot $j$. Each person can only buy one consecutive block of time slots, which could be empty.

Is there a *polynomial-time algorithm* to compute the maximum value the seller can achieve?

Without the consecutiveness constraint, we can give each time slot to the person who values it most. Also, if we fix the order of the time slots of the $k$ people, then dynamic programming can be used to solve for the maximum value of the first $0\le i \le k$ people buying the first $0\le j \le n$ time slots.

# Answer
Given a 3CNF with clauses $\phi\_1,\ldots,\phi\_k$ on variables $x\_1,\ldots,x\_n$. Suppose both $x\_i$ and $\overline{x\_i}$ appear in the formula for at most $k\_i$ times respectively.

We design a colored DAG $G$ whose vertices consists of three parts:

* "Assignment" vertices $v\_i(j)$ and $\bar{v}\_i(j)$, $1\leq i\leq n$, $1\leq j\leq k\_i$. Color $v\_i(j)$ with the "color" $x\_i(j)$, and $\bar{v}\_i(j)$ with $\overline{x\_i}(j)$.
* "Clause" vertices $w\_{i'}(j')$, $1\leq i'\leq k$, $j'=1,2,3$. Color $w\_{i'}(j')$ with the color $x\_i(j)$ (or $\overline{x\_i}(j)$) if $\overline{x\_i}$ (or $x\_i$, resp.) is the $j'$-th literal of clause $\phi\_{i'}$, and it's the $j$-th clause containing this literal.
* "Cut" vertices $s=s\_0,s\_1,\ldots,s\_n, s\_{n+1},\ldots s\_{n+k}=t$. Color them with distinct colors different from above.

The edges include:

* $s\_{i-1}v\_i(1)$, $v\_i(j)v\_i(j+1)$, $v\_i(k\_i)s\_i$;
* $s\_{i-1}\bar{v}\_i(1)$, $\bar{v}\_i(j)\bar{v}\_i(j+1)$, $\bar{v}\_i(k\_i)s\_i$;
* and $s\_{n+i'-1}w\_{i'}(j')$, $w\_{i'}(j')s\_{n+i'}$.

For instance, from the 3CNF $(x\_1 \vee x\_2 \vee \overline{x\_3})\wedge(x\_1 \vee \overline{x\_2}\vee x\_3)$ the following graph is constructed (The edge directions are from left to right).

Now it is not hard to see that the original 3CNF is satisfiable if and only if there is a $s$-$t$ path with different vertex colors in $G$.

(By the way, it is a by-product that the existsence of $s$-$t$ path with different vertex colors in colored DAG is $\textsf{NP-hard}$. I didn't find many literatures about this problem in computational perspective. If you know, please comment!)

So what is the relation between $G$ and OP's problem? Intuitively what we are going to do is to design a matrix $h$, so that each color is mapped to a row (which is a person), and the edges are mapped to consecutive columns (time slots). Therefore a maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.

Our matrix $h$ have $2n+1+\sum\_i 2k\_i+k$ columns, with indices starting from $0$. In the following constrcution $X$ an $Y$ are two values satisfy $1\ll X\ll Y$. The ratios $X/1, Y/X$ can be large powers of $k$ and $n$. Let $K\_i=2i+2\sum\_{j=1}^i k\_i$.

* For each $s\_i$, $0\leq i\leq n$, let $h(s\_i,K\_i)=h(s\_i,K\_i-k\_i-1)=h(s\_i,K\_i+k\_{i+1}+1)=Y$ (if the coordinate exists, same below).
* For each $x\_i(j)$, let $h(x\_i(j),K\_{i-1}+j)=X$; For each $\overline{x\_i}(j)$, let $h(\overline{x\_i}(j),K\_{i-1}+k\_i+1+j)=X$.
* For each $\phi\_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi\_{i'}$, let $h(x,K\_n+i')=1$.
* All the other entries are 0.

For example, for the above example graph the corresponding matrix is

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+1)Y+\sum\_i k\_iX+k$.

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+1)$ columns in $h$ containing $Y$, they should all be covered. For the column $K\_i+k\_i+1$ which has two choices of $Y$, suppose the scheduling assigns it to $s\_i$. Since column $K\_i$ must be assigned to $s\_i$, by the consecutiveness we have to lose the columns $K\_i+1$ to $K\_i+k\_i$. Same things happen if the scheduling assign the column $K\_i+k\_i+1$ to $s\_{i+1}$.

Therefore, in order to have the value $\sum\_i k\_iX$, we must select all the rest available $X$'s in the matrix, which corresponds to an assignment on variables. So the rest value of $k$ is achievable if and only if the assignment satisfy every clause.

As a conclusion, deciding the maximum value of a legal scheduling is in $\textsf{NP-hard}$. Maybe that's why all our previous attempts to find an algorithm failed.
> 9 votes

# Answer
**This solution has problems and will be deleted soon; see templatetypedef's comment.**

You can solve this in polynomial time using minimum-cost flow. In the following, all edges have unit capacity.

* Create a source vertex $s$, and a target vertex $t$. We will send $k$ units of flow from $s$ to $t$.
* Create $n+1$ vertices $v\_0, \dots, v\_n$ to represent the time points between slots, and a directed edge $v\_jv\_{j+1}$ for each $0 \le j \< n$ with cost 0.
* For each person $i$, create the following:
    + A sub-source vertex $s\_i$ and a sub-sink vertex $t\_i$.
    + For every $0 \le j \< n$, an edge from $s\_i$ to $v\_j$ having cost $\Sigma\_{k=1}^j{h(i,k)}$ (which we take to be 0 if $j=0$).
    + For every $1 \le j \le n$, an edge from $v\_j$ to $t\_i$ having cost $-\Sigma\_{k=1}^j{h(i,k)}$.
    + An edge $ss\_i$ with cost 0.
    + An edge $t\_it$ with cost 0.

A minimum-cost flow in this network will have total cost equal to the negative of the best possible profit. (This cost will be negative, but that's not a problem.) There is an optimal integral solution in which every person $i$ has a single edge leaving $s\_i$ with a flow of 1 and a single edge arriving at $t\_i$ with a flow of 1, and all other edges incident on either $s\_i$ or $t\_i$ have 0 flow. Let these flow-1 edges for person $i$ be $s\_iv\_j$ and $v\_kt\_i$: then $k \ge j$, since the only paths among $v$-vertices are those that increase the subscript. If $k = j$, then person $i$ is allocated no time slots; otherwise, person $i$ is allocated the block of time slots $j+1, \dots, k$.

Intuitively, each person "gets" 1 unit of flow from $s$ and chooses a start time (edge) and end time (edge); these start and end edges are the only edges with nonzero cost in the network, and we can represent the value of a block $j+1, \dots, k$ as the difference of two prefix sums. The unit capacities on the edges between the $v$-vertices act to prevent 2 people from using the same time slot.

Interestingly, this formulation will work even if the values $h(i, j)$ may be negative.
> 3 votes

---
Tags: algorithms, optimization, np-hard, scheduling
---


title: Column Major Order

text:
# Question
Title: Column Major Order
I have a doubt understanding How a 3-Dimensional array is stored in column Major Order. An array in Row Major order is stored like **\[plane\]\[row\]\[column\]** So, for finding address of any element we cross planes first, rows next and then some elements in that column.

But How is a 3-Dimensional array stored in Column Major Order?

It's better if understood from a problem.

> A is an array $\[2.....6,3.....8,4.......10\]$ of elements. The starting location is $500$. The location of an element $A(5,5,5)$ using column major order is \__________.

# Answer
> 1 votes
In the Row-major order the elements of rows are continous, so you have already described the Column-major order.

X-major order means that n-dimensional array when stored in the memory is flat for easy, sequential access if the X entries.

To find address of any element of the Column-major order: the first is plane, than row and *the last is column*.

---
Tags: data-structures, arrays, c
---


# Question
Title: Is it possible to determine if C=A+B faster than adding A+B in logical circuits
With an adder circuit where A+B=C, I am trying to have a method to determine when C will be valid based on a change in A or B. I know that it is possible to just determine the longest the circuit would take, but is it possible to determine if the result (C) is equal to A+B. This would speed up the result of the operation as if A and B had a small change, C could be determined faster than a full adder cycle.

In general: If you know A, B, and C, can you determine if A+B=C faster than adding A+B

# Answer
> 4 votes
Consider computing $\overline{a\_{n-1}\ldots a\_0}+\overline{b\_{n-1}\ldots b\_0}=\overline{c\_{n-1}\ldots c\_0}$. If the last $(k+1)$-bits are correctly computed, then $c\_{k+1}$ is correct if and only if $$\big((a\_k\wedge b\_k)\vee((a\_k\oplus b\_k)\wedge \neg c\_k)\big)\oplus a\_{k+1}\oplus b\_{k+1}=c\_{k+1}.$$ That is because the first part, $(a\_k\wedge b\_k)\vee((a\_k\oplus b\_k)\wedge \neg c\_k)$ indicates whether there is a carry-over. So you can check the correctness for each bit in parallel.

However, in theory both questions require $\Omega(\log n)$-depth bounded fan-in circuits. Good thing is, for the checking problem the $\log n$ part in the circuit depth is only for a $n$-bit $\textsf{AND}$, so I think it is a constant boost in the performance.

# Answer
> 2 votes
In theory, there are other ways to check the result without re-generating it, using modular arithmetic. In practice, these methods probably won't be useful at all, but I'll outline what I'm talking about anyway.

Remember the "cast out 9's" method for checking your arithmetic? From a mathematical perspective, "casting out 9's" amounts to reducing each number modulo 9. Then, we check whether $(A \bmod 9) + (B \bmod 9) = (C \bmod 9)$. If the result was generated correctly (i.e., if $A+B=C$), this check will always succeed. If the result was generated incorrectly (i.e., if $A+B \ne C$), then the check might fail.

We can generalize this, as follows. Pick a random $k$-bit prime, call it $p$. Reduce $A$, $B$, and $C$ modulo $p$. Now, check whether $(A \bmod p) + (B \bmod p) = (C \bmod p)$. If this check fails, then we're sure that $C$ was generated incorrectly. If this check succeeds, then with high probability $C$ was generated correctly. In particular, if we have $A,B,C$ such that $A+B \ne C$, then with high probability (over the choice of $p$) we'll have $(A \bmod p) + (B \bmod p) \ne (C \bmod p)$.

How high is the probability of detecting an error? Basically, it is exponentially small in $k$. The probability can be bounded explicitly using the fact that an error goes undetected iff $A+B-C$ is a multiple of $p$ and using an upper bound on the number of $k$-bit prime divisors that $A+B-C$ can have (at most $2 \log n / \log k$, where $n$ is the number of bits in $A,B,C$) and using the prime number theorem (there are at least $2^k/k$ $k$-bit prime numbers). You end up with a probability that's at most something like $(2 k \log n / \log k)/2^k$, and this is asymptotically exponentially decreasing in $k$.

In particular, if you want the probability of an error going undetected to be at most $1/2^t$, it suffices to choose $k=O(t \log t \log \log n)$. In practice, if $t \ge 64$, the chance of an undetected error is far smaller than the chance of a cosmic ray messing everything up. So, if we think of $t$ as constant, then we need a $k=O(\log \log n)$-bit prime.

Is this faster than just doing the addition? I doubt it.

# Answer
> -2 votes
So basically checking if A+B=C is the decision problem version of the function problem of finding the value of A+B. I guess the decision problem can be solved by subtraction i.e A-C and then comparing the result with B. The circuit for the full subtractor is more complex (having more number of gates) then the full adder. So, finding the addition value is much more easy then checking the addition result.

---
Tags: circuits, digital-circuits
---


title: social network graph problem

text:
# Question
Title: social network graph problem
Here is the problem:

There are connected graph with nodes representing a number of people. Each node/person has an opinion on a topic e.g. trump vs clinton, paper books vs kindle, etc

The goal is make every node in a graph share the same opinion, by selecting a specific subset of nodes, in a particular sequence.

If majority of a person A's friends support trump, but person A supports clinton. if person A is selected, his/her opinion will change to trump.

If person's friends opinions are equally divided, then you can decided the selected person's opinion.

I am running out of ideas as how to proof this is achievable. Maybe some of you can give me some pointers.

# Answer
> 17 votes
This is known as *majority dynamics*. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, this converges either to a fixed point or to a cycle of length 2; see for example pages 5-6 of Ginosar and Holzman's The majority action on in nite graphs: strings and puppets. If you break ties in a biased way, then the dynamic probably always converges.

What you describe is the asynchronous model, in which the majority rule is applied in sequence rather than in parallel. In that case the process always converges. See for example Tamuz and Tesler, though their methods are probably overkill for you, since in your case you get to choose the sequence, whereas in their case the sequence is chosen at random.

# Answer
> 6 votes
This is not generally achievable. Consider a blue and a red triangle connected with a single edge. Whatever node you select will keep its previous colour.

In general, if you have large monochromatic clusters with few connections between them, the graph is stable.

---
Tags: graphs, social-networks
---


# Question
Title: Effect of increasing the capacity of an edge in a flow network with known max flow
I need your help with an exercise on Ford-Fulkerson.

> Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
>
> Now suppose you are given an arc $e$ in $G$ and suppose this arc's capacity is increased by one.
>
> Give an efficent algorithm which returns true iff the increase of the capacity of the arc $e$ will allow an increase in the max flow.

I suppose we shouldn't run Ford-Fulkerson again but somehow use the given $|f|$… Any ideas how?

# Answer
> 4 votes
I am assuming that you are given the flow on each edge which corresponds to the maximum flow for the graph $G$. So $f\_e$ is the flow on edge $e$.

I am also assuming that all the capacities and flows values are integral.

Now given this information, capacity of an edge $e$ is increased by 1. Therefore, the mincut value can increase by at most 1 implying that the maxflow can increase by at most 1.

Thus, find the residual graph and check if there is an augmenting path $P$ from $s$ to $t$. If such a $P$ exists, then increase your maxflow by augmenting this path, otherwise the current flow is still the maximum.

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


# Question
Title: Is this a generic way to convert any recursive procedure to tail-recursion?
It seems that I've found a generic way to convert **any** recursive procedure to tail-recursion:

1. Define a helper sub-procedure with an extra "result" parameter.
2. Apply what would be applied to the procedure's return value to that parameter.
3. Call this helper procedure to get started. The initial value for the "result" parameter is the value for the exit point of the recursive process, so that the resulting iterative process starts from where the recursive process starts to shrink.

For example, here is the original recursive procedure to be converted (SICP exercise 1.17):

```
(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

```

Here is the converted, tail-recursive procedure (SICP exercise 1.18):

```
(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

```

Can someone prove or disprove this?

# Answer
> 13 votes
Your description of your algorithm is really too vague to evaluate it at this point. But, here are some things to consider.

# CPS

In fact, there is a way to transform *any* code into a form that uses only tail-calls. This is the CPS transform. CPS (Continuation-Passing Style) is a form of expressing code by passing each function a continuation. A continuation is an abstract notion representing "the rest of a compuation". In code expressed in CPS form, the natural way to reify a continuation is as a function that accepts a value. In CPS, instead of a function returning a value, it instead applies the function representing the current continuation to the being "returned" by the function.

For example, consider the following function:

```
(lambda (a b c d)
  (+ (- a b) (* c d)))

```

This could be expressed in CPS as follows:

```
(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

```

It's ugly, and often slow, but it does have certain advantages:

* The transform can be completely automated. So there's no need to write (or see) the code in CPS form.
* Combined with thunking and trampolining, it can be used to provide tail-call optimization in languages that do not provide tail-call optimization. (Tail-call optimization of directly tail-recursive functions can be accomplished via other means, such as converting the recursive call into a loop. But indirect recursion is not as trivial to convert in this manner.)
* With CPS, continuations become a first-class objects. Since continuations are the essence of control, this enables virtually any control operator to be implemented as a library without requiring any special support from the language. For example, goto, exceptions, and cooperative threading can all be modeled using continuations.

# TCO

It seems to me that the only reason to be concerned with tail-recursion (or tail-calls in general) is for the purposes of tail-call optimization (TCO). So I think a better question to ask is "does my transform yield code that is tail-call optimizable?".

If we once again consider CPS, one of its characteristics is that code expressed in CPS consists solely of tail-calls. Since everything's a tail-call, we don't need to save a return-point to the stack. So all code in CPS form *must* be tail-call optimized, right?

Well, not quite. You see, while it might appear that we have eliminated the stack, all we have done is merely change the way we represent it. The stack is now part of the closure representing a continuation. So CPS doesn't magically make all our code tail-call optimized.

So if CPS can't make everything TCO, is there a transform specifically for direct recursion that can? No, not in general. Some recursions are linear, but some are not. Non-linear (e.g., tree) recursions simply *must* maintain a variable amount of state somewhere.

---
Tags: algorithms, logic, recursion, lisp
---


# Question
Title: Preparing precedence graph from fork and join code
I was referring to this page which defines `fork`, `join` and precedence graph as follows:

> * When the statement `Fork(label)` is executed by a thread of control, a second thread of control is started from the statement with the specified label. The two threads execute concurrently.
> * When the statement `Join(count)` is executed, where count is an integer variable, the value of count is decremented. If the resulting value is positive the executing thread is terminated.
> * A PRECEDENCE GRAPH is a directed, acyclic graph where nodes represent sequential activities and where arcs, say from node i to node j, require that activity i complete before activity j can start.

Base upon this I have been asked to draw precedence graph for a code containing `fork` and `join` constructs. For simple code, I can do. Also once given both code and precedence graph, I can see how the two correspond to each other. However when the code gets little bit complex, it becomes difficult to prepare precedence graph for me. Also doing reverse, from precedence graph preparing fork-join code is almost always difficult for me.

Can anyone give me intuitive stepwise procedure explaining how to obtain fork-join code from any given precedence graph?

Can we take example of following graph to apply the steps and get the fork and join code:

# Answer
> -1 votes
x=2; y=2; z=2;

**p1;**

Fork L1 ; start p2

Fork L2 ; start p3

goto L3 ; stat P4

L1: **p2;**

```
fork L3 ;start p4;

goto L5

```

L3: join (x)

**P4;**

L4: join(y)

**s6;**

Quit();

L2 : **P3;**

L5: join(y)

```
 P5;

 goto L4

```

---
Tags: parallel-computing, precedence-graph
---


title: Spinlock using cache coherence

text:
# Question
Title: Spinlock using cache coherence
Have been trying to understand the image below which shows status of spinlock using cache coherence. Reference is Computer Architecture A Quantitative Approach------------------
Could anybody explain why there is a cache miss in step no.5 when P2 tries to execute swap.

# Answer
> 1 votes
In step 4 P2 *tests* the lock and sees the value is 0. But testing the lock is just a read operation, so P2 has the cache line in state `shared`. In step 5 P2 executes a swap operation, which is both a read and a write, so requires a coherence action (invalidate P1's shared copy) to acquire the cache line in state `exclusive`. It's a "cache miss" in the sense that the required state in the cache is incorrect, not in the sense that the data is missing.

# Answer
> 0 votes
* In step 2, there is a write invalidate (from P0) of the lock variable.
* In step 3, P1 experiences a cache miss.
* In step 4, P1 is waiting for the bus to become available.
* Finally, in step 5, the bus becomes available and P1's request is satisfied.

---
Tags: cpu-cache
---


# Question
Title: When used as call stack, do garbage-free spaghetti stacks form a DAG?
I'm looking into implementation techniques for programming languages, and recently came across spaghetti stacks, which are supposedly a good fit for a continuation passing style model (given their use in e.g. Scheme and SML/NJ). For sake of simplicitly, let's only consider a single-threaded processes for this question.

However, I'm a bit confused by the diagram on Wikipedia (also found elsewhere). In particular, I don't understand how such a situation can arise. I can only imagine that the grayed-out branches are unreachable and should be garbage-collected. On the other hand, with my vague understanding of how to implement CPS using spaghetti stacks, I can't imagine how you could ever get a loop in that structure. I have to conclude that, rather than a "parent-pointer tree", it's actually a directed acyclic graph, with as many non-garbage sources as there are threads, and as many sinks as there are (potential) "exit points".

But my understanding of this implementation is pretty vague, so I guess I'm probably missing something. I hope someone can enlighten me here on "spaghetti call stacks", by which I mean the data structure as used in Scheme and/or SML/NJ to implement CPS-based processes.

1. Given the following spaghetti call stack:

```
[exit point] <-- ... <-- [frame A] <-- [frame B (active)]
                                ^
                                 `---- [frame C]

```

As far as I understand, any flow control from B either unwinds the stack by jumping to a parent (A becomes active, unreachable B is now garbage), or replacing the active frame by a subgraph, connected only using references held by B or references to the new frames. Execution can't flow to frame C, which must mean that **frame C is garbage.**
2. Rather than the previous situation, I'd think that the following garbage-free situation may arise:

```
[exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)]
                                ^                     |
                                 `---- [frame Y] <---´

```

For example, I can imagine that frame Z belongs to some decision function, which either continues with frame X or frame Y (either of which would return to W). This means that **spaghetti call stacks aren't "parent pointer *trees*".**
3. However, I can't imagine any situation where a loop can be constructed. Take the following situation, for instance:

```
[exit point] <-- ... <-- [frame P] --> [frame Q (active)]
                                ^             |
                                |             v
                                 `---- [frame R]

```

I know that recursive bindings are a thing, but I highly doubt that this is sensible. If Q were to return to R, frame Q is "spent". If R were to return to P, and P can't simply return to Q, since it would need to be reinitialised first. As such, **loops would cause inconsistent states.** (Unless, of course, I misunderstand the purpose of this data structure, and you'd only use the nodes in it as a template for your current frame.)

From these observations, I have to conclude that a spaghetti call stack (without garbage) is actually a DAG. Is this correct? Or am I misunderstanding the purpose of this data structure?

---

*Updates:*

* I've skimmed through a copy of the following paper:

> E. A. Hauck and B. A. Dent. 1968. Burroughs' B6500/B7500 stack mechanism. In *Proceedings of the April 30--May 2, 1968, spring joint computer conference* (AFIPS '68 (Spring)). ACM, New York, NY, USA, 245-251. DOI=http://dx.doi.org/10.1145/1468075.1468111

This paper seems to define the Suguaro Stack System. As it turns out, this Suguaro Stack System is a traditional call stack that allows multiple "jobs" to walk through the frames of a partially shared stack; it is absolutely not related to continuations.
* The following paper (and its 1996 companion paper) apparently explains what's going on in the SML/NJ compiler:

> Zhong Shao and Andrew W. Appel. 2000. Efficient and safe-for-space closure conversion. *ACM Trans. Program. Lang. Syst.* 22, 1 (January 2000), 129-161. DOI=http://dx.doi.org/10.1145/345099.345125

I think I should read this paper (copy on author's website) before doing anything else with this question. The "Safely Linked Closures" concept is very similar to the Suguaro Stack System, in that it's always very shallow and only intended to share free variables:

> Our new closure-conversion algorithm uses *safely linked closures* (the 3rd column in Figure 1) that contain only variables actually needed in the function but avoid closure copying by grouping variables with the same *lifetime* into a sharable record. \[...\] Unlike linked closures, the nesting level of safely linked closures never exceeds more than two (one layer for the closure itself; another for records of different life time) so they still enjoy very fast variable access time.

The paper also explicitly mentions that it doesn't use "any runtime stack":

> Instead, we treat all activation records as closures for continuation functions and allocate them in registers on in the heap.

I'm think I misunderstood and/or misread the Wikipedia article, since spaghetti stacks are not used for flow control. However, after careful reading of the papers by Appel and Shao, I could perhaps restate the question in reference to the dependency graph of closures rather than the "spaghetti call stack" (which apparently isn't a thing).

# Answer
> 3 votes
# Are Spaghetti Stacks Parent-Pointer Trees?

Yes, spaghetti stacks are parent-pointer trees. You can think of a spaghetti stack as having the same structure as a collection of single-linked lists which share structure. When viewed as a whole, the collection of lists form a tree. But when viewed individually, each list forms a stack.

Each process in the system will have one of these lists, which represents its control stack. The head of the list is the top of the stack (i.e., active frame). Its `next` pointer references the parent frame.

What you see in the diagram is the structure for multiple processes. The stack for the "active" process is highlighted. The portions of the tree that are not part of the active stack are grayed out. These represent stacks for other processes.

# Do Spaghetti Stacks Form a DAG?

Since Spaghetti stacks are parent-pointer trees, they are indeed DAGs. But only DAGs that are also trees can be Spaghetti stacks. So no, Spaghetti stacks do not form DAGs that are not trees.

Your example of a decision function conflates the structure of a control stack with the data stored *in* the stack. Certainly, any structure could be formed if we start considering the data. But as a datastructure, each node in a spaghetti stack will have exactly one parent.

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


# Question
Title: Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?
Tomorrow is my presentation and I want to clear my concepts…

I've read that in DFA, "For each state, transition on all possible symbols (alphabet) should be defined."

Is for each state, defining transition on all possible symbols mandatory in DFA? If its not, then please give any examples?

# Answer
> 12 votes
A DFA is specified by the following data:

* An alphabet $\Sigma$.
* A set of states $Q$.
* An initial state $q\_0 \in Q$.
* A set of final states $F \subseteq Q$.
* A transition function $\delta\colon Q \times \Sigma \to Q$.

As you can see from the signature of $\delta$, it specifies a transition at every state for every symbol.

# Answer
> 24 votes
Suppose a DFA was allowed to have missing transitions. What happens if you encounter a symbol which has no transtion defined for it? The result is undefined. That would seem to violate the "deterministic" characteristic of a DFA.

However, it's trivial to transform such an incomplete DFA into a complete DFA. Simply add a new state, `illegal`, and map any undefined transitions to the `illegal` state. Finally, add transitions for every symbol from the `illegal` state back to itself. This `illegal` state is often called a *sink* state, because once data falls into the sink there's no way to get out.

So, from a practical perspective, it's kind of moot, as long as you have a well-defined way to handle missing transitions.

# Answer
> 5 votes
A DFA is often defined as a restricted type of NFA. If $\Sigma$ is the input alphabet and $Q$ is the set of states, the transition structure of an NFA is specified as either a relation $\rho \subseteq Q \times \Sigma \times Q$, or as a function $\delta : (Q \times \Sigma) \to 2^Q$. If we adopt the latter definition, then we can say that an NFA is *deterministic* if $|\delta(q,\sigma)| \leq 1$ for all $q\in Q$ and $\sigma \in \Sigma$, and *complete* if $\delta(q,\sigma) \neq \emptyset$, again, for all $q \in Q$ and $\sigma \in \Sigma$.

A word is accepted by an NFA if it has an accepting run. A deterministic automaton has *at most* one run. A complete automaton has *at least* one run.

Some authors define *trim* automata as those in which each state is on some path from an initial state to a final state. For certain languages, you cannot have automata that are both trim and complete. In those cases, it is convenient to keep the completeness requirement out of the definition of deterministic automaton.

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


# Question
Title: Prove that at least as many edges as vertices implies a cycle
I am EXTREMELY confused on where to start with this problem. We recently just started learning about graph theory and I don't know where to begin.

> Prove that in a connected graph G with $p$ vertices, $q$ edges, and at least one cycle, $q \ge p$

How do I begin with this question? Any help would be greatly appreciated. Thank you so much.

# Answer
Graph has a cycle on $k$ vertices implies that those vertices are connected with $k$ edges. Also, the graph is connected so $p-k$ vertices which left should be connected to the cycle, that means extra $p-k$ edges (distinct end points). Totally the graph has more($\geq$) than $p$ edges.
> 2 votes

---
Tags: graphs, proof-techniques
---


title: Graph with repeated/redundant edges?

text:
# Question
Title: Graph with repeated/redundant edges?
Is a graph with two of the same edges a graph? Specifically, can this graph be considered a directed graph?

# Answer
Graphs, as usually defined, don't have parallel edges. Graphs with parallel edges are known as *multigraphs*.

However, like humpty dumpty, we can give a term whatever meaning we want. In some contexts, all graphs are multigraphs, and so the word *graph* denotes a multigraph. In other contexts, there are *graphs* and *graphs with parallel edges*. In yet other contexts, there are *graphs* and *multigraphs*. Only you know the conventions in your field.
> 1 votes

---
Tags: graphs
---


# Question
Title: Multi modal learning from separate modal datasets
Let's say I'm trying to learn emotion given multi-modal sources. In this case, video and audio. However, I only have one dataset for video emotions and one dataset for audio. Is it possible to train a Deep Learning classifier on each dataset separately? One way I can imagine doing this is creating some sort of shared hidden units, similar to the figure below:

However, in the publication this is taken from, these weights are trained simultaneously.

Are there examples of this type of multi-modal learning in the literature? I'm not sure what to look up and all I can come up with myself is "something-something Deep Belief Network".

# Answer
Back in 2012, this was accomplished by Srivastava and Salakhutdinov in "Learning Representations for Multimodal Data with Deep Belief Nets" where they mixed textual and visual features using the following Deep Belief network architecture:

Note the specially defined hidden layer that can be trained independently.

More recently in 2015, this was accomplished by Huang, Y.; Wang, W. and Wang, L. in "Unconstrained Multimodal Multi-Label Learning" where they use a conditional Restricted Boltzmann Machine applied to creating text labels for images:

Note that each observed variable, `t` for tags and `m` for images are connected to `h`, but there is the built in assumption that `m` is more frequently available than `t`.

One problem with both of these approaches is I'm unclear on how well they're going to scale.
> 2 votes

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


# Question
Title: How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time?
**The real problem I am facing is the following.**

*INSTANCE*: I have sets $N:=\\{1,\ldots,n\\}$ and $K:=\\{1,\ldots,k\\}$ and matrix $a\_{ij}\>0$ for all $i\in K$ and $j\in N$.

*QUESTION*: I need to find a subset $S$ of $N$ of size as small as possible and partition the set $K$ into $|S|$ disjoint sets $K\_j$ whose union equals $K$ such that for all $j\in S$, I have $$\sum\_{j'\in S\\j'\neq j} a\_{ij'} \leqslant a\_{ij}-1,$$ for all $i\in K\_j$.

*Example:*

Given $n=k=3$ and the matrix $$ \begin{bmatrix} 0.6 & 2.7 & 1.2\\ 1.3 & 2.6 & 0.8\\ 1.5 & 0.4 & 0.6 \end{bmatrix}. $$

In this example, $S$ should be equal to $S=\\{1, 2\\}$ and $K\_1=\\{3\\}$ and $K\_2=\\{1,2\\}$.

I noticed two facts:

* If there exists some $j\in N$ such that $a\_{ij}\geqslant 1$ for all $i\in K$ then $S=\\{j\\}$ and $K\_j=K$; and
* If there exists some $i\in K$ such that $a\_{ij}\<1$ then $S=\emptyset$.

**My question**: Is it possible to solve this optimization problem in polynomial time (at least with approximation algorithm)?

The first thing I tried to do is to transform it into a known problem and then applied a known algorithm for that. I thought about transforming it to a *set cover* or *bin packing* but I failed and also I do not think that this is interesting.

---

**The problem I tried to formulate.**

I have sets $N:=\\{1,\ldots,n\\}$ and $K:=\\{1,\ldots,k\\}$ and matrix $a\_{ij}\>0$ for all $i\in K$ and $j\in N$. Also, I have $n$ disjoints sets $K\_j\subset K$ for each $j\in N$, (I added $K\_j$ as inputs because I could not formulate it otherwise.)

Finally, I get this: $$ \begin{align\*} & {\underset{S}{\text{minimize}}} & & |S|\\\\[3pt\] & \text{subject to} & & \sum\_{j'\in S\\j'\neq j} a\_{ij'} \leqslant a\_{ij}-1,\forall\\, j\in S,i\in K\_j,\\\\[3pt\] & & & S\subseteq N.\\ \end{align\*} $$

Thanks.

# Answer
Even the decision version of this problem, in which we try to determine simply if there *exists* any feasible solution, is **NP-hard** by reduction from Exact Cover. (The optimisation version, where we seek a feasible solution that minimises $|S|$, is clearly at least as hard as this.)

The single-row, single-column matrix containing the value 0.5 is an example of an input for which there is no feasible solution. Here's another:

$$ \begin{bmatrix} 0.2 & 4\\ 3.1 & 3\\ 5 & 0.6 \end{bmatrix}. $$

## Building a "Choose at most one" gadget

First, notice that if the maximum value in some row $a\_i$ is $x \> 0$, and this row contains (at least) two copies of $x$, say at $a\_{ij}$ and $a\_{ij'}$, $j' \ne j$, then $S$ cannot contain both $j$ and $j'$, since if it did then one of the following two cases must arise, each of which leads to a contradiction:

1. $i \in K\_j \cup K\_{j'}$: Suppose w.l.o.g. that $i \in K\_j$. But then $\Sigma\_{m \in S, m \ne j}{a\_{im}} \ge a\_{ij'} = x = a\_{ij}$, contradicting the requirement that $\Sigma\_{m \in S, m \ne j}{a\_{im}} \le a\_{ij} - 1$.
2. $i \notin K\_j \cup K\_{j'}$: Then suppose $i \in K\_p, p \notin \\{j, j'\\}$. But then $\Sigma\_{m \in S, m \ne p}{a\_{im}} \ge a\_{ij} + a\_{ij'} = 2x$, and since $x$ is maximal in row $i$, the highest that $a\_{ip}$ could be is clearly $x$, so we must be violating the same inequality as before.

Thus we can choose some maximum value that is safely higher than the sum of all non-maximum values in the row, and use copies of this maximum value to enforce that at most one of those columns is included in $S$.

We can turn this "choose at most one" constraint into a "choose exactly one" constraint by using any positive value less than 1 as the "non-maximum" value. That's because every row $i$ belongs to some part $K\_j$ of the row partition, and if $a\_{ij} \< 1$ then the RHS of the inequality becomes negative for row $i$, so there is no way to satisfy it: thus at least one $j$ must be forced into $S$ such that $a\_{ij} \ge 1$.

So, to ensure that exactly one of the columns in some set $T \subseteq N$ is forced into $S$, create a row $a\_i$ as follows:

* Set $a\_{ij} = n+1$ for each $j \in T$.
* Set $a\_{ij} = 0.5$ for every other $j$.

Thus the reduction from Exact Cover is straightforward: there is a row for each element, a column for each set, with $a\_{ij} = n+1$ whenever set $j$ includes element $i$ and $a\_{ij} = 0.5$ otherwise. Both directions ("Input EC instance is a YES-instance $\implies$ constructed instance of OP's problem is a YES-instance", and "Constructed instance of OP's problem is a YES-instance $\implies$ input EC instance is a YES-instance") are clear.
> 4 votes

---
Tags: algorithms, optimization
---


title: Does every DFA contain a loop?

text:
# Question
Title: Does every DFA contain a loop?
Is there a rule that either every DFA contains or not, a loop(cycle in graph terminology)?

I do not seem to be able to generalize this idea in either direction.

Also if either of these is true, can we assume through DFA - NFA equivalence that the same is true for NFAs?

# Answer
Every finite directed graph in which every vertex has outdegree at least 1 has a cycle. This is a nice exercise. Thus, even if you look only at edges labeled by a particular symbol, you will find a cycle in every DFA.
> 12 votes

# Answer
There are two ways of looking at a DFA.

Some folks insist that every state must have a transition for every symbol in the alphabet (the transition function is a total function). If you look at a DFA this way, then, yes, as according to the accepted answer there will always be a cycle. But this cycle might be self-loop to some "dead" or "error" state.

On the other hand, some say that if there is no transition for a given symbol from a given state, then if the machine is in that state and that symbol is encountered, then the string is rejected.

Alas, many books on the subject define the transition function as per first example, but then draw state diagrams as per the second example.

But when it comes to a sequence of states that could potentially lead to the acceptance of a string, some have cycles, some do not. If a DFA recognizes an infinite language, its graph must contain at least one cycle that is not a self-loop to a dead state (this is a corollary of the Pumping Lemma for Regular Languages). If the graph of a DFA does not contain such a cycle, then it cannot recognize an infinite language.
> 5 votes

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


# Question
Title: Generating all directed acyclic graphs with constraints
I am interested in listing all the unlabeled1 acyclic digraphs with *n* vertices which satisfy some additional constraints, such as (a) the resulting graph is connected and (b) except for `R` identified root vertices, all vertices have two incoming edges and zero or one outgoing edges.

There may also be additional domain-specific constraints, but they are probably easy enough to implement by simply generating and rejecting graphs that do not meet the constraints. In principle, conditions (a) and (b) above could be satisfied in this way above, but at least in the case of (b) it seems very advantageous to consider them directly in generating process since the output is likely to be quite *sparse* (i.e., a large majority of graphs will fail to satisfy (b) and this ration increases with increasing *n*).

My problem is twofold:

1. Even ignoring the constraints part, I have not be able to determine how to efficiently generate DAGs. I know there are a lot of them so I'll mostly be dealing with smallish n, let's say `n < 15`. There seem to be some promising papers, although may of them are focused on the closed-form *counting* of the number of graphs rather than actual generation, and any remaining ones are paywalled.
2. I want to apply the at least enough of the constraint part during the generation to avoid the case where nearly all generated graphs are simply rejected. That is, I hope the generation of the constrained graphs is considerably faster than the generation of the much larger number without constraints.

You can find lots of information on *random* generation of such graphs, but not much on exhaustive generation (which seems like the easier of the two problems).

---

1 That is, I want to exclude generation of isomorphic graphs.

# Answer
For small $n$, the easiest solution might be to download a list of all non-isomorphic graphs and then filter them according to your condition.

You might take a look at Brendan McKay's collection, constructed using `geng` as part of the Nauty graph isomorphism package.

See Enumerate all non-isomorphic graphs of a certain size for more details and citations.
> 4 votes

# Answer
You can use nauty to generate all isomorphism classes of undirected graphs, then generate all acyclic orientations of each graph.

An algorithm to generate all acyclic orientations of a given undirected graph can be found here:

http://www.sciencedirect.com/science/article/pii/S0196677497908919
> 1 votes

---
Tags: algorithms, graphs, graph-isomorphism, graph-algorithms
---


title: Mac question about flowcharting

text:
# Question
Title: Mac question about flowcharting
Is there a flowcharting application like Raptor for Mac. I am using the OS X (Sierra) version. I use Raptor in Windows and need a similar application for Mac.

# Answer
You could use MindNode or OmniGraffle (though OmniGraffle is more expensive), although these are more oriented towards mind-mapping than for flowcharting.

If you were looking for a free, web-based software, I've heard draw.io works pretty well. There really isn't much choice for macOS unfortunately, after all.
> 1 votes

---
Tags: algorithms
---


title: Alternatives to Defunctionalization

text:
# Question
Title: Alternatives to Defunctionalization
Defunctionalization is a transformation first described 1972 by John C. Reynolds to eliminate higher-order functions. Are there alternative transformations (more efficient?) to eliminate higher-order functions?

# Answer
> 6 votes
There are three main approaches (that I'm aware of) for implementing higher-order functions. Defunctionalization, closure conversion/lambda lifting, and combinators.

Let's write $A \Rightarrow B$ for the type of a higher-order function from $A$ to $B$ and $A \to B$ for the type of C-style function pointers from $A$ to $B$. (If we wanted to formalize this, we could say that function pointer abstraction is only allowed in the empty environment.)

Closure conversion is the idea that we choose the representation $$A \Rightarrow B \equiv \exists E.(E, (E, A) \to B)$$ The $E$ will typically be the tuple holding the values of free variables at the site of lambda abstraction. It could be some other representation though.

Lambda lifting takes a somewhat different and more global approach where a lambda abstraction is pulled outward into containing scopes adding free variables as parameters along the way, until it reaches the top-level scope. While this deals with block structuring, to actually handle higher-order uses of functions requires allowing partial application. You can then pass around partially applied functions, but this is basically the same representation as closure conversion.

If you wanted to eliminate function pointers we can use defunctionalization, which, in this special case, simply produces an enumeration. There's little reason to do this though, as function pointers are natural constructs in most assembly languages.

The next approach is to use combinators. This is basically the same as lambda lifting and using partial applications except a fixed set of top-level functions are used, and all other functions are expressed as combinations of those. (If they don't have a predefined fixed set of combinators, then this is usually just a lambda lifting based approach like I described above.) A higher-order function would then be effectively represented by a value in a data type using Haskell syntax like the following (using `SK` combinators):

```
data CA = S | K | App CA CA -- plus other things in reality, like primitive values

```

A representation more like the spine calculus probably makes more sense for efficiency. Or you could do something like:

```
data CA = S0 | S1 CA | S2 CA CA | K0 | K1 CA

```

Applying a higher-order function splits into two cases: either a combinator has been fully applied and thus it should be executed, or we return a new value that represents the (partial) application.

I haven't done an exhaustive survey, but I'm pretty confident variations on closure conversion are by far the most common implementation strategy for higher-order functions (hence them often being called "closures"). It has the nice properties of being modular, simple, and reasonably efficient even in its naivest form. It takes a good choice of base combinators and some cleverness to get combinator-based approaches to perform well. Defunctionalization just isn't widely used as far as I can tell, but there is little reason *not* to take advantage of function pointers. To the extent that you do, e.g. instead of a large case analysis you have a table of function pointers that you index into, you've basically recreated closure conversion.

There are some other approaches. One is template instantiation which is basically to take $\beta$-reduction literally, and simply literally substitute terms into other terms. Usually, this requires having and manipulating an abstract syntax tree-like structure. Higher-order functions are then represented by their (syntactic) lambda terms or "templates" thereof which can simplify performing the substitutions.

---
Tags: programming-languages, functional-programming
---


# Question
Title: Consider a social network. The goal is to find in the in the network a largest group of people who are all friends with each other.
Describe the problem as a graph problem. I've tried to modify the breadth first search algorithm, but haven't gotten anywhere. Any ideas?

# Answer
This is the Maximum Clique problem, one of the canonical NP-complete problems. On general graphs it probably cannot be solved efficiently, though social networks, with their very particular structures, may lend themselves to more efficient solutions.
> 3 votes

# Answer
You might try finding The strongly connected components , By using modelling the connections as a directed graph and using DFS for the same.

The DFS on directed graphs produces a DAG of strongly connected components . Finding the largest group from this group of connected components is going to take linear time in terms of number of vertices.
> 0 votes

# Answer
Rather than breadth first search, start with depth first search.

1. Select your first user , your starting node. This is "Bob".
2. Go to a random friend. This is "Alice".
3. This is the **modified step.** In a list store the nodes you have visited, now it's only "Bob". In Alice's friends search the ones who are also friends with everyone in the list. Go to one of them. This is "Kate".
4. Now you have "Bob" and "Alice" in your list. Repeat Step 3 for Kate. If Kate does not have any mutual friends return back to Alice and select another friend. Don't add Kate to list. *(Depth First Algorithm)*. In each backtracking save the maximum number of people in list. Change it if you have a new maximum.
5. In you final step, you won't have anyone who has an unvisited friend that is also friends with everyone in the list. At that step, add the last person and save your list. This list certainly has Bob, and the biggest group that Bob is in. That's why you save the maximum count.
6. You have to repeat this step for everyone and get the list with maximum number of elements. Someone in one list can also be in another list, so you have to run this for everyone. *This step can be improved*

You can also check whether a group has the maximum number of people by comparing it with the total number of friendship relations(edges) in the graph. I believe that this whole process can be shortened by using the data from previous groups. For example, after the first run, you will have the biggest group that Bob is in, in your second run you can bypass visiting Bob.

* For example if you have a group that has more people than the half of the whole population, it's maximum.

This solution is open to objection and faster algoritms, but if you have enough time or your database is not huge, this algorithm gives you the right answer.
> -1 votes

---
Tags: graphs
---


# Question
Title: occur-check, does nominal unification has it?
In unification, there is a "occur-check". Such as $X = a \\, X$ fails to find a substitution for $X$ since it appears on right hand side too. The first-order unification, higher-order unification all have occur-check.

the paper nominal unification described a kind of unification based on nominal concepts. But I did not mention "occur-check" at all.

So, I am thinking why? does it has occur-check?

# Answer
> 1 votes
Yes, it has the occur check. The ~variable transformation rule of nominal unification has a condition which states

```
   provided X does not occur in t

```

what it is saying is exactly occur check.

---
Tags: unification
---


# Question
Title: Which scheduler uses scheduling algorithm?
From what I know, the high level scheduler decides which process is to be taken from backing store and placed into memory/ready queue, while the low level scheduler decides which process in the ready queue is executed by the CPU. If this is the case, which of the two schedulers actually use the scheduling algorithms (such as Round Roben, First Come First Serve,...)??

# Answer
> -1 votes
The short term scheduler or low level scheduler. Short term Schedulers are used to manage the ready queue of the computer. These are responsible for selecting the job based on which type of algorithm you are using.

If you are using priority based the it will allow a high priority process to go in running state while preempting the low priority process.

For round robin when ever the time quantum expires running process will come back to the ready state.

So here another major hand in hand component which work with short scheduler is **Dispatcher** his work is jo dispatch the process which chosen by the short term scheduler and to perform context Switching.

Context Switching need to perform so that old context or info. Of the currently preempted process can be save so that after completing its I/O operations or when ever it will get its chance to get execute. It will start from where it is preempted.

---
Tags: scheduling
---


# Question
Title: What algorithm solves high-order unification for untyped terms in most cases?
High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation `a => b`, where `a` and `b` are terms on the simply typed lambda calculus, `a` containing free variables, finds a substitution `S` such that `aS => b`, where `=>` stands for "has the same beta normal form" (up to variable renaming). For example, given the following problem:

```
a = (λt . t
    (F (λ f x . (f (f (f x)))))
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

```

One can come with the solution:

```
 F = (λ a b c . (a b (a b c)))

```

Since that substitution makes `a = b` hold. My question is: what's an efficient (i.e., polytime) algorithm that solves this problem for as many cases as possible?

# Answer
Maybe you should try nominal unification. In the paper nominal unification, it gives 4 examples which are untyped $\lambda$-terms.
> 1 votes

---
Tags: algorithms, programming-languages
---


# Question
Title: 2-clause satisfiability associated graph
A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P:

2-SAT: Input : A conjunction $\Phi$ of 2-clauses. Question : Is it satisfisable?

For each set of 2-clause $C$ we associate $G\_C$ defined as

* $V\_{G\_C}$ contains two vertices $x$ and $\neg x$ for each variables in $C$.
* $E\_{G\_C}$ contains an edge $\alpha \rightarrow \beta$ if and only if $\neg \alpha \vee\beta$ or $\beta \vee\neg\alpha$ is in $C$.

This graph should help me show this problem belongs to **P**. Yet,

* **Why is $C$ satisfiable if and only if $G\_C$ doesn't have any loop?**
* **Why does $G\_C$ space is polynomial?**
* **Why is $G\_C$ calculation from $C$ is polynomial?**

# Answer
> 1 votes
You already have a description of how the graph is built from the formula. Think about a possible algorithm for doing the job. For example, you first scan over all variables in the formula, and you add two vertices into your graph for each. Now you only need to add in the edges into the graph. You can scan over the clauses, and if you see either form you describe, you add in an edge into your graph. This all can be implemented to run in polynomial time; just observe you are performing two scans over the formula, and you do a bit of work for every step of the scan. Similar reasoning will make you see the graph only needs polynomial space.

For your first question, an answer is given in the Wikipedia article on 2-SAT, but has also been touched upon in other question (see e.g., here).

---
Tags: complexity-theory, satisfiability, polynomial-time, 2-sat
---


# Question
Title: Time complexity of a precedence constrained selection problem
I wonder if you have an idea over the time complexity of the following problem, or a problem similar to this one (generally a selection problem)

\[Assuming operations on integers take O(1) time\]

We are given a set $N$ of $n$ items, that are subject to general precedence constraints (a partial order $E$ on $N$). The problem could then be represented by an acyclic directed graph $G(N,E)$ where the nodes represent items and edges represent precedence constraints. Each item has a selection cost $c\_i$ that may be positive, zero, or negative. The objective is to find a subset $S \subseteq N$ of items that is precedence feasible, i.e., $\forall i \in S:\\{j \in N|(j,i) \in E\\}\subset S$, and minimizes the total selection cost $F(S)=\sum\_{i \in S}c\_i$.

I tried to find a reduction from CLIQUE or 3-Dimensional Matching, but I couldn't.

Thank you in advance :)

# Answer
If you flip the signs on your costs and reverse edge directions, this is the Closure Problem, also known as the Open-Pit Mining Problem, and it's actually solvable in polynomial time using a rather non-obvious transformation into maximum flow.

The algorithm is described in the Wikipedia page linked above. Briefly, it involves setting the capacity of each edge to infinity, which has the effect that any minimum cut *avoids* all original graph edges in the forward direction (since any cut that included such an edge would have infinite flow), and adding a new edge to each vertex from one of two new vertices, $s$ (for positive-weight vertices) or $t$ (for negative-weight vertices). The capacity of any $s$-$t$ cut magically works out to be a constant minus the total weight of vertices on one side of the cut, so minimising this (which can be done by a max-flow algorithm) maximises said total weight!
> 2 votes

# Answer
The problem should be easily solvable, even in linear time: Just consider a topological sorting $v\_1,\ldots,v\_n$ of the nodes of the induced graph and let $C(v\_i)$ denote the minimal costs if you choose to select item $v\_i$. Clearly, it holds that $C(v\_1) = c\_1$. For some $i \> 1$, if you choose to select item $v\_i$, you **must** select all the preceding items, so you get $c\_i$ plus the (already computed) values $C(v\_j)$ for each edge $(j,i)$. In the end, you only have to look for a node $v\_i$ with the minimum value $C(v\_i)$ among all nodes (or choose none if all of them have positive costs).

If the graph is not connected, you can do the same separately for each connected component.
> 0 votes

---
Tags: complexity-theory, time-complexity, selection-problem, precedence-graph
---


# Question
Title: Automated lip-reading: inferring what someone is saying, based upon video of them speaking
Some humans can lip-read fairly well: by watching someone who is speaking, they can tell what the speaker is saying (even without hearing the speech).

Has there been any work on building computer software to lip-read? In other words, given a video of someone speaking, is it possible to build software to infer what the person is saying (with access only to the video stream, without audio)? Has there been any research on this problem, or even deployed systems?

Background and motivation: In the US, certain laws may forbid recording audio without consent. However, there is generally no prohibition on recording video without consent of the people being recorded. (That's why you see surveillance cameras all over the place, and why they record only video but never audio.) I am curious whether technology has advanced enough that, solely from video, it might be possible for automated methods to tell what people are saying -- or whether that might become feasible in the near-future. And, apart from the privacy implications, such a technology might be pretty useful.

# Answer
> 3 votes
There appears to be some work in that area. See for example this paper and the references therein. There are also demonstrations of implemented systems on youtube, see for example this video

# Answer
> 2 votes
There is some recent work here:

LipNet: Sentence-Level Lipreading. Yannis M. Assael, Brendan Shillingford, Shimon Whiteson, and Nando de Freitas.

They achieve 93% accuracy on a corpus of 3-second videos with a talking head, compared to accuracy of 52% from experienced human lipreaders. They have a video demoing their results.

---
Tags: reference-request, computer-vision, pattern-recognition, facial-recognition
---


# Question
Title: What is the time complexity in big-O notation of Algorithm X?
*Knuth's Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm* that solves the NP-complete problem exact cover (EC). (It actually finds all solutions to EC.)

I do not understand how such algorithm could do that. What is the time complexity of this algorithm in terms of big-O notation?

Here is the algorithm from Wikipedia.

> 1. If the matrix $A$ has no columns, the current partial solution is a valid solution; terminate successfully.
> 2. Otherwise choose a column $c$ (deterministically).
> 3. Choose a row $r$ such that $A\_{r,c} = 1$ (nondeterministically).
> 4. Include row $r$ in the partial solution.
> 5. For each column $j$ such that $A\_{r,j} = 1$,
>
> * for each row $i$ such that $A\_{i,j} = 1$,
>
>     + delete row $i$ from matrix $A$.
>     * delete column $j$ from matrix $A$.
> 6. Repeat this algorithm recursively on the reduced matrix A.

Step 3 of the algorithm is done nondeterministically. What does this mean? (I think this is the point why I cannot find the big-O complexity of the algorithm.)

An implementation of Algorithm X in python can be found in Algorithm X in 30 lines! where I cannot find the nondeterministic choice of step 3.

# Answer
> 4 votes
Its worst-case running time is exponential.

By "nondeterministic", this essentially means "try all possibilities".

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


# Question
Title: What is the difference between operator and function?
We have operator and operands, function and formal arguments. Is the difference purely lexical (we use alphanumerics for funciton identifiers but identify operators with special characters, e.g. "+" and "\>=") or it is syntactical, like I guessed here

```
f(a,b) -- prefix notation used for functions
a.f(b) -- infix notation for method invocation (used in OOP)
a f b  -- infix notation without dot and parenthesis used in operator invocations

```

so that when we write `a + b` we have an operator but `"+"(a, b)` (both ways are acceptable in VHDL) makes it a function? Do tools treat them differently? Can you differentiate them? Can you say that this is not a function, it is an operator or vice-verse? When I read the definitions in wikipedia, I do not see that syntax is a distinguishing feature of a concept. So, is it right that operators and functions are synonyms, two different words for the same thing, same meaning, same notion? I have such guess but have never seen it stated explicitly. Please agree with my guess or say what is the difference.

# Answer
> 8 votes
Historically, my guess is that the difference is rooted in how things were (and still are) translated into machine code.

An *operator* such as addition of integers or exclusive-or of booleans would be translated into one (or few) assembler commands which would be directly executed by the processor (resp. its ALU). It would also be part of the *syntax*.

A *function* (or procedure, method), on the other hand, is a subprogram the (main) program would explicitly jump to during execution. That is, a new stack frame is allocated, register values are saved, parameters are passed and only then is the function executed. See here for details. Furthermore, functions are defined by the programmer.

Younger programming languages have introduced more abstraction, partially or totally removing the distinction. In C#, for instance, you can overload operators for your own types. In Scala, there are no operators but only syntactic sugar for binary methods. Once these languages are compiled, though, you can see which language elements are translated to flat instructions and which to subroutine calls. Keep in mind that optimising and/or just-in-time compilers may liberally move between worlds.

# Answer
> 1 votes
An operator is typically a *short-hand notation* of a function. For instance, in C++, for an appropriate object a, "a + b" is equivalent to "a.+(b)". Such an equivalence is often available only for operands/arguments whose data types are *natural* to such an expression. For instance, for a string object, it may make sense to provide such a short form; but for a person object, it is unlikely to write "person1 - person2" because the expression is not *intuitive*, and therefore, the *subtraction* operation would not be provided for the type *Person*.

# Answer
> -2 votes
There's is no real difference in computer science. The distinction occurs to those who do lambda calculus. There, the difference is akin to math\`s distinction between f(x) and f. Both are functions in some sense, but the latter is the name of the function, while the former is the function itself.

---
Tags: terminology, programming-languages
---


# Question
Title: Theory of computation introductory curriculum
I want to study theory of computation on my own, so I am looking for books.

What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation?

Please post answers that describe a complete curriculum, explaining which chapters of each book are relevant at which stage of the course or self-study.

# Answer
> 11 votes
*Introduction to the Theory of Computation* by Michael Sipser is a relatively recent entry into this field. It was the required book for a class my friend was taking, and I asked him for the PDF so I could browse through at my leisure. I ended up reading almost the whole book, even the chapters on topics I was already very familiar with, just because the book is such a joy to read. It's written at an introductory level, which means less notation, more exposition, and more intuition. The motivation behind every idea and theorem is crystal clear. He precedes every proof with a "proof idea" section that lays out the path the proof is going to take without getting into the gory details. The book covers Automata Theory, Computability Theory, and Complexity Theory to a satisfactory depth for an undergraduate level. I've read many textbooks in computer science and math, and this is probably my favorite.

# Answer
> 8 votes
For someone just getting started in Computer Science I would recommend

> Douglas Hofstadter, *Gödel, Escher, Bach: an Eternal Golden Braid*, Basic Books, 1979.

It is a philosophy book discussing the meaning of truth, proof, and computability, (and self referential music and art and ... a bunch of other stuff) aimed at people with a little bit of mathematical sophistication (say at least a semester of college calculus) and was the book that inspired me to study computer science. It walks the reader through a complete proof of Gödel's incompleteness theorem.

I know I am going to get downvotes from the theorists for this, but I actually think that the first few chapters of most books on compilers do the best job of introducing basic automata theory (regular and context free languages, finite and pushdown automata). Aho, Sethi and Ullman (the red dragon book) does a particularly good job, but Appel's *Modern Compiler Implementation in ML/Java/C* book is decent and Cooper and Torczon's *Engineering a Compiler* is also great. The mathematics won't be particularly rigorous but the point is to get you to understand how to actually use and implement these things in real life. They won't teach you about Turing Machines, computability or decidability though.

The best book, the one that should be at the core of learning automata and computability, and the classic in this field for 20 years was

> John E Hopcroft and Jeffrey D Ullman, *Introduction to Automata Theory, Languages, and Computation*, Addison Wesley, 1979.

Sometimes known as "the loom book" because of the strange cartoon on the cover. It is appropriate for 4th year undergraduates or 1st year graduate students in computer science. It covers automata theory and computability. (It also ends with a couple of chapters on complexity theory, but that's not really its focus.) In about 2001 Addison Wesley started to "churn" the book (releasing new editions with modifications to kill the used book market.) I haven't looked at the 2nd (2001) or 3rd (2007) editions that added Rajeev Motwani as an author, so can't tell how or if they are improved over the original 1979 edition.

The book discussed in Stephen Bly's answer

> Michael Sipser, *Introduction to the Theory of Computation*, Thompson, 1996 (now in 3rd edition, Cenage Leraning, 2012.)

is truly excellent. It is easier to read than Hopcroft and Ullman. Sipser is a good writer and explains everything extremely well. It doesn't go into the depth and range of topics that Hopcroft and Ullman, so may not include enough for a graduate course focused on automata and computability. Sipser is about 1/2 automata and computability and the other half is complexity theory (which he covers in more depth than Hopcroft and Ullman's first edition did.)

For a student who is taking a course in computability I recommend they read the following when they need to relax:

> Raymond M Smullyan, *The Lady or the Tiger?: and Other Logic Puzzles*, 1982 (Dover reprint, 2009)

which ends with a series of chapters that requires you to do an undecidability proof to solve the puzzle.

Once you've got a good background on computability, you might like to continue on with a deeper look into other aspects of mathematical logic (including a rigorous treatment of Gödel's completeness and incompleteness theorems.) A good book for that might be

> Herbert B Enderton, *A Mathematical Introduction to Logic*, 2/e, Academic Press, 2001.

# Answer
> 0 votes
I know this answer is late, but it might help the next person. I am not studying CS officially, but as a hobby. For theory of Computation, I started with:

* Theory of Computation, first edition (Michael Sipser)

The book was for me very uninspiring, it felt like a raw collection of random math theorems and its proofs. No intuition, no overview, no inspiration, no insight, no nothing.

After this, I ordered together:

* Formal Languages, Automata, and Complexity (Brookshear)
* Automata Theory, Languages, and Computation (first and second editions) from Hopcroft
* Formal Language: A Practical Introduction (Adam Brooks Webber)

Brookshear\`s book was more clear than Sipser for me on the first chapters, but then got uninspired as well.

Hopcroft and Webber books arrived at the same time, and I tried reading them all. I was amazed that reviews on Amazon.com indicates that Sipser book is more acessible than Hopcroft, but I found exactly the opposite. Anyway, the Webber book was infinitely more inspiring than all of the other books, so I just took all others out of my shelf and read Webber\`s entirely.

On the end, I got "Understanding computation" (Tom Stuart) as well. I was sure my quest was over with Webber's book, but I tried it out of curiosity anyway, and it was also nice for being intuitive. But I would prefer Webber\`s if I had to pick only one.

The best mix for me is Webber+Stuart for intution, and Hopcroft for the math.

# Answer
> -1 votes
There are probably no worthy books. Danny Hillis\`s book comes to mind, but much theory can be introduced with very little text. Binary arthimetic (with a little philosophy of *number*) and minimal Turing Machines, what?

It's **understanding** that takes time to *grok* how simple it is -- that's the job of the teacher, not a textbook (at least if you want to accomplish it in one semester). Only real-time, in the classroom, can you get a read on how to proceed with such a task.

---
Tags: computability, automata, computation-models, books
---


# Question
Title: Showing that given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$ is NP-complete
> Let be the following problem : "Given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$. Show that it is NP-Complete

I know how to show that

* a set of vertices $S$ is a stable set in $G$ iif $S$ is a clique in $G\_C$.
* the Hamiltonian cycle problem is in $NP$

And I know the definition of NP complete problems.

**Do you have any tips to show that this problem is NP-Complete?**

### My attempt

I count how much $G\_C$ is a stable, at most $n$ operations, I store the best value, for instance $4$. Therefore, it will give a clique of length $n-4$. But I show there that we can search for a solution in a polynomial time. Not that we can verify the solution in polynomial time. Thus, I show that it is $P$, not in $NP$...

# Answer
> 0 votes
It is a classical example of reduction the Hamiltonian cycle to vertex cover. Also, if $S \subset V$ is a vertex cover then $V \setminus S$ is an independent (stable) set. Thus, taking the graph complement you obtain a clique.

According to your attempt, firstly how can you find stable set in $G\_c$ in $n$ steps? Secondly, review what is a complement graph.

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