# Question
Title: Can I use machine learning to predict someone will buy something in a specific time?
I have a dataset which has timestamp and goods variable for an object like the following example:

* On Moday, John bought Beer, chicken, pizza.
* On Tuesday, John bought pizza, pork and beef.
* On Wednesday, John bought beer, coke and Vegetable

Can I use machine learning to predict what good will he buy in a specific time and what model can be applied?

Can we answer the question: "What will he buy on Thursday?"

# Answer
## Short answer:

Yes it can be done using machine learning if you have features with sufficient information.

## Long answer:

You can model this either as a *multilabel* problem (i.e Beer, chicken, pizza are multiple labels \[non mutually exclusive\] for the same data point) or as a *multiclass* problem (by creating a combination like "Beer, chicken, pizza". In the multiclass case the labels would be mutually exclusive). You can use day of the week, name of person and some other attributes as features (aka predictors) for the model.

For a more detailed answer you'd need to tell us what you have already tried out so that the community can help you. Also, see this related question.
> 2 votes

# Answer
You might be interested in techniques from data mining, especially association rule mining and frequent itemset mining. They try to detect which combinations of products tend to be bought together (e.g., if you buy pizza you'll often buy beer too).
> 1 votes

---
Tags: machine-learning, classification
---


# Question
Title: Finding a fixed-size set whose members are contained by the largest number of other sets
I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to communicate with as many students as possible.

Consider some finite population of people, each of whom speak any number of languages. For the purposes of the problem, we'll ignore some of the things that make languages complex in real life (for example, that people speak several languages but at different levels, that people who understand one language might be able to understand closely-related languages, and so forth).

So, for example:

* P1 speaks `{English, German}`.
* P2 speaks `{Spanish, Italian, French}`.
* P3 speaks `{Mandarin, English}`.
* P10000 speaks `{Afrikaans, Swahili, English}`, and so forth.

I am writing some document which I wish to have translated so as to be understood by as many people as possible. Unfortunately, my budget is limited, and I can only afford a translation into N different languages.

For a given value of N, how do I calculate the optimimum set of N languages to reach the largest number of people out of the intended population?

The problem sounds like it could be easily generalized as a set-theory/combinatorics problem, and so I'm certain somebody has done work on something like it before. I would like to take a look at the existing literature, but I don't know how to find it.

Is there a name for this type of problem? If not, could it be reduced to another known problem?

# Answer
I believe your problem is a direct instance of the NP-hard Maximum Coverage Problem, which is related to Set Cover.

From wikipedia, Maximum Coverage Problem:

> As input you are given several sets and a number *k*. The sets may have some elements in common. You must select at most *k* of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size.

So, in your case, there is a set for each language with cardinality equal to the number of students speaking that language. The input is the number N of maximum number of translations.
> 6 votes

# Answer
If we ignore the number of native speakers of language for the moment, your problem is *Set Cover* -- you ask if it is possible to cover all languages with at most $k$ translators.

Adding *weights* -- the number of native speakers of each language -- adds a mode of optimization -- we may cover only some languages but want maximum total weight. This is certainly not easier; the reduction from Set Cover itself is trivial.

Thus, your problem is NP-hard.

Since it is also easy to express using integer programming, we can conclude it is NP-complete.

Regarding names, I don't know one. "Weighted Set Cover" is already taken for the variant where sets have costs, but I'd invent something around these lines. "Maximum-Weight Set Cover", maybe.
> 2 votes

---
Tags: terminology, reference-request, optimization, combinatorics, sets
---


# Question
Title: Example of a simple recognizable language, whose complement is not recognizable
Can any one provide me with a simple language that is recognizable, but that it's complement is not?

I have read that recognizable languages may have this property but I am yet to find an example to think about. If you could provide the recognizable proof for both language and complement I would be very thankful, but just the language itself would be a nice help.

Thank you

# Answer
> 2 votes
The set of recognizable languages whose complement is not recognizable is $RE\setminus R$. This holds since if $L,\overline{L}\in RE$, you can run the machines for $L,\overline{L}$ simultaneously and decide $L$. An example of a language in this set is the famous halting problem.

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


# Question
Title: Long multiplication school method: number of primitive operations to calculate first partial product?
Having got some basics down in regard to addition and explaining it in terms of primitive operations (addition and multiplication), I am now again stuck on understanding the more complicated long multiplication.

I have read in my introductory book (Mehlhörn's 'Algorithms and Data Structures') that each partial product requires 2n + 1 primitive operations.

Now I understand, I think, where the +1 comes from for the first partial product at least, as in there being one extra digit in the result for the first partial product, but I don't understand why it is "2n" + 1, as it seems to me it would be more like n + 1, so I am defintely missing something important here. By 'partial product', I mean the result arising from the first intermediate calculation of the multiplication problem.

I am of course also totally confused about quantifying the rest of the primitive operations required to get the final result/product! But I would just like to understand where the 2n is coming from for now for the first partial product. Just to add my guess from what I have seen in addition: does the 2 in 2n refer to a maximum guiding number, rather than a definitive one?

Here is a link to the chapter in the book I am learning from: http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Appetizer.pdf

I understood primitive operations to mean: addition and multiplication. The author does write at bottom of pg.1

"...we have two primitive operations at our disposal: the addition of three digits with a two-digit result (this is sometimes called a full adder), and the multiplication of two digits with a two-digit result"

The product of two n-digit numbers when they multiplied together needs then: 3n^2 + 2n primitive operations.

It is the algorithm as per the method taught at school for long multiplication problems.

(All of this is on pgs 1 and 2 of chapter)

# Answer
> 1 votes
Perhaps the following example will be useful. Suppose that $n = 3$, and we want to multiply $a\_2 a\_1 a\_0$ by $b$. We first compute $$ \begin{align\*} a\_0 \times b &= c\_0 d\_0 \\ a\_1 \times b &= c\_1 d\_1 \\ a\_2 \times b &= c\_2 d\_2 \end{align\*} $$ (Here $c\_0 d\_0$ is a two-digit integer.) So far we have done 3 operations (for general $n$, this will be $n$ operations).

Now we wish to perform the addition $$ \begin{array}{cccc} 0&d\_2&d\_1&d\_0\\ c\_2&c\_1&c\_0&0 \\\hline r\_3&r\_2&r\_1&r\_0 \end{array} $$ The book states that you need 4 operations for this (and in general, $n+1$), though 2 are enough (in general, $n-1$): $$ \begin{align\*} r\_0 &= d\_0 \\ s\_1 r\_1 &= d\_1 + c\_0 \\ s\_2 r\_2 &= d\_2 + c\_1 + s\_1 \\ r\_3 = s\_2 \end{align\*} $$ Here $s\_1,s\_2$ are carry bits, and the first and last operations are for free (though the author charges one operation for each).

Summarizing, if you only charge addition and multiplication, only $2n-1$ operations are needed. If you also charge moves, $2n+1$ operations are needed. (The moves can be eliminated, though. Exercise.)

---
Tags: algorithm-analysis, runtime-analysis, arithmetic, multiplication
---


# Question
Title: Showing that all vertex degrees in MSTs of Euclidian graphs are in O(1)
There is a finite set of points $S$ in the plane with $ |S| = n$. MST is the minimal spanning tree of S. "Minimal" here refers to the Euclidean distance between the points of $S$, so the MST is the minimum spanning tree with the lowest overall distance.

I want to prove that the degree of every node is in O(1).

I tried to use Euler's Theorem but unfortunately this did not lead to a solution. Any ideas?

# Answer
> 7 votes
Here is a proof sketch from Robins and Salowe, On the Maximum Degree of Minimum Spanning Trees. Let $x$ be some vertex in the MST. We want to show that its degree $d$ is small.

Let $y\_1,\ldots,y\_d$ be its neighbors. Draw a small circle of radius $\epsilon$ around $x$, and "project" each $y\_i$ to a point $z\_i$ on the circle: the point $z\_i$ is just the intersection of the line $\overline{x y\_i}$ and the circle. The idea is to show that all of these projections are far from each other.

Indeed, consider any pair of points $y\_i,y\_j$, and suppose without loss of generality that $\\|x-y\_i\\| \leq \\|x-y\_j\\|$. Repeat the same process as before, but with a circle of radius $\\|x-y\_i\\|$. The projections are $w\_i = y\_i$ and $w\_j$. The triangle $\Delta xz\_iz\_j$ and $\Delta xy\_iw\_j$ are similar, and so $\\|z\_i-z\_j\\|/\epsilon = \\|y\_i-w\_j\\|/\\|x-y\_i\\|$.

On the other hand, consider the circle $\Delta xy\_iy\_j$. Two of the edges are in the minimum spanning tree, so the remaining edge must be a heaviest edge. Since we assumed that $\\|x-y\_i\\| \leq \\|x-y\_j\\|$, this means that $\\|y\_i-y\_j\\| \geq \\|x-y\_j\\|$. Therefore $\\|x-y\_j\\| \leq \\|y\_i-y\_j\\| \leq \\|y\_i-w\_j\\| + \\|w\_j-y\_j\\|$. Since $w\_j$ is on the line from $x$ to $y\_j$, we have $\\|x-y\_j\\| = \\|x-w\_j\\| + \\|w\_j-y\_j\\|$, and so $\\|x-w\_j\\| \leq \\|y\_i-w\_j\\|$. Since $w\_j$ is on the circle of radius $\\|x-y\_i\\|$ centered at $x$, this shows that $\\|x-y\_i\\| \leq \\|y\_i-w\_j\\|$.

Combining the formula $\\|z\_i-z\_j\\|/\epsilon = \\|y\_i-w\_j\\|/\\|x-y\_i\\|$ with the inequality $\\|x-y\_i\\| \leq \\|y\_i-w\_j\\|$, we deduce that $\\|z\_i - z\_j\\| \geq \epsilon$. Summarizing, $z\_1,\ldots,z\_d$ are points on a circle of radius $\epsilon$ which are at distance at least $\epsilon$ from each other. This forces $d \leq 6$.

Perhaps the following diagram will be useful:

Suppose that the inner circle has radius $\epsilon$. We want to show that $\\|z\_i-z\_j\\| \geq \epsilon$. Due to the MST property, we know that $\\|y\_i-y\_j\\| \geq \\|x-y\_j\\|$. Thus necessarily $\\|y\_i-w\_j\\| \geq \\|x-w\_j\\|$. This implies $\\|z\_i-z\_j\\| \geq \\|x-z\_j\\|$ due to similarity of triangles.

Robins and Salowe note that when $d = 6$, the points are packed tightly. It turns out that there is always an MST in which there is always some jiggle room, and so some MST has maximum degree at most $5$.

The same argument works in $D$ dimensions and in any metric, as long as there is a bound on the number of points on a unit ball which are at least a unit distance away from each other. This property holds in all $L\_p$ metrics (for finite $p$!) in any dimension.

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


# Question
Title: Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?
Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need the value $P(x) \bmod M$?

# Answer
The answer given at Multi-point evaluations of a polynomial mod p actually answers the question.

Given a primitive root g of M, it is possible to evaluate $P (g^0), P (g^1), \ldots, P (g^{M-1})$ in $O (\max (N, M) \log \max (N, M))$ steps, and then you just rearrange the resulting values and add $P (0)$ which is just the constant coefficient of the polynomial $P$.

Thanks D.W. for the link. The answer given there says that for an arbitrary set of points evaluating all the polynomial values faster than $N$ times number of points can't be done, but of course the result above is useful whenever the number of points is substantially more than $N \log N$.
> 2 votes

---
Tags: algorithms, time-complexity, polynomials, modular-arithmetic
---


title: Find all cycles through a given vertex

text:
# Question
Title: Find all cycles through a given vertex
Given a directed graph $G$ and a vertex $v$, how can we enumerate all simple cycles that pass through $v$?

I found a question that describes how to enumerate all simple cycles in $G$, but I want only the cycles that pass through $v$, so this question is a bit different. The total number of cycles in $G$ can be exponentially larger than the number of cycles passing through $v$, so just enumerating all cycles in $G$ and keeping only those that go through $v$ might be inefficient.

I'm not asking to *count* the number of cycles; I want an algorithm to *list* them all. I would like an output-sensitive algorithm, where the running time is some low-order polynomial of the number of cycles that go through $v$. I know there can be exponentially many cycles, so there is no hope for an algorithm whose running time is polynomial in the size of the graph.

Motivation: This is a cleaned-up version of Given a directed graph and a vertex v, find all cycles that go through v?. I wanted to ask the more general version of the question.

# Answer
> 3 votes
## Solution: Modify Johnson's algorithm

Johnson's algorithm can be used to enumerate all cycles in $G$. It can be easily modified to enumerate only and all the cycles that contain $v$.

Johnson's algorithm works by numbering the vertices from $1$ to $n$, and classifying each cycle according to the smallest-numbered vertex in the cycle. It first enumerate all cycles whose smallest-numbered vertex is $1$, then all whose smallest-numbered vertex is $2$, and so on.

So, here is the modification to Johnson's algorithm. Choose a vertex numbering where $v$ receives the number $1$, and the other vertices are numbered in any order. Run Johnson's algorithm, but only enumerate the cycles whose smallest-numbered vertex is $1$. This will enumerate all the cycles containing $v$, and only the cycles containing $v$.

## Running time

The running time of this algorithm is $O((m+n)(q+1))$, where $q$ is the total number of cycles containing $v$, $n$ is the number of vertices, and $m$ is the number of edges. Its space consumption is $O(n+m)$.

## References

Here is a full citation to Johnson's paper describing the algorithm:

\[Finding all the elementary circuits of a directed graph\]\[1\]. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975

See also Find the Simple Cycles in a Directed Graph. For help understanding Johnson's algorithm, see

For pointers to implementations of Johnson's algorithm and discussion of other algorithms to find all cycles in a graph, see https://stackoverflow.com/q/546655/781723. I don't know if there's a way to modify them to enumerate only cycles that contain $v$.

---
Tags: algorithms, graphs, enumeration
---


# Question
Title: Comparative study between Deep neural nets and Bayesian Networks
Is there any comparative study that showcases the powers of Bayesian Networks and Deep learning in their respective favorable setup and how they compare?

I tried to go through blogs but couldn't find out any experimental study where the respective models where described based on a example?

Rationale in putting this question: I am planning to work on Bayesian networks and I know they are great for inference and answering complex queries. But I couldn't find any convincing experimental results where they seemed to be more favorable as compared to other sophisticated machine learning tools like deep neural nets or conventional deep neural nets.

# Answer
They're not directly comparable. They do different things. They solve different problems.

A Bayesian network is a probabilistic model of the relationship between multiple random variables. It is a generative model. It builds a model of the joint probability distribution between multiple random variables. It typically requires some priors or assumptions about the structure of the joint distribution. While it could be used for classification, it normally isn't.

Deep learning is typically used for classification: supervised learning. It is a discriminative model. It does not try to model/estimate the joint probability distribution between multiple random variables. It typically does not require you to specify priors or assumptions about the structure of the joint distribution.
> 2 votes

---
Tags: reference-request, machine-learning, neural-networks, graphical-models
---


title: Is this a divide-and-conquer algorithm?

text:
# Question
Title: Is this a divide-and-conquer algorithm?
I'd like to start by stating this isn't homework! I'm studying for a job interview and would appreciate a second opinion. (Well, I guess it is homework, but not for school!).

I've written an algorithm (see pseudocode below) to merge two *sorted* lists into one sorted list. The problem requires that I implement it as a recursive divide-and-conquer algorithm. My algorithm is recursive and works *but does it count as divide-and-conquer*?

The reason I'm asking is that the other people working on the same problem insist D&C must divide the lists in half every time and have $O(n \log n)$ complexity, like quicksort and mergesort. My algorithm doesn't divide the lists in the middle and has a complexity of $O(n+m)$ (where $n$ and $m$ are the lengths of the lists).

To summarize my question: **Does a D&C algorithm have to have $O(n \log n)$ complexity and divide the problem in half every time? Or does this algorithm count as D&C?**

```
merge_sorted_lists(list1, list2)
    if(list1 and list2 are empty)
        return empty list

    if(list1 is empty)
        return list2

    else if(list2 is empty)
        return list1

    else if(head of list1 < head of list2)
        smaller = pop head of list1

    else if(head of list2 < head of list1)
        smaller = pop head of list2

    return smaller + merge_sorted_lists(list1, list2)

```

P.S. I've implemented the algorithm in Java and it works.

# Answer
"Divide & Conquer" is not a very fixed notion. It usually goes along the lines of

> D&C algorithms divide the problem and solve recursively.

That's not very strong, for the following reasons.

* What I would call *inductive* algorithms do this, but are usually not considered divide & conquer algorithms. Given a problem of size $n$, inductive algorithms solve subproblems (typically one) of size $n-c$ for some constant $c$ and derive a solution for the original problem. See here for an example.
* *Dynamic programming* does exactly that, but it's not usually considered d&c. The difference is that in DP, subproblems *overlap*, which they don't in d&c. Also, we often don't know which subproblem is the "right" one, so we try out all possible partitionings (which causes overlapping).

Now, one might say that inductive and d&c algorithms are orthogonal special cases of dynamic programming, but that's for another discussion.

In order to "define" divide & conquer against those other types of algorithms, consider this:

> D&C algorithms divide the problem of size $n$ into *non-overlapping*¹ subproblems *of size $\frac{n}{c}$*, solves (some of²) them recursively and combines the solutions to a solution of the original problem.

By this "definition", your algorithm is *not* divide & conquer.

As for runtimes, d&q algorithms can typically be analysed (roughly) using the master theorem. As you can see from the three cases, all kinds of runtimes of the form $n^a\log^bn$ can result, depending on the quality of the division and the runtime of the combining step.

---

1. As I write the part about runtimes, it occurs to me that this may be too strong. Overlaps by a *constant* (sized part) are fine.
2. Binary search can be considered the ultimate divide & conquer: by dividing cleverly, combining is unnecessary.
> 6 votes

# Answer
> **Does a D&C algorithm have to have O(nlogn) complexity and divide the problem in half every time?**

## No.

Consider Karatsuba's multiplication algorithm. Given two $n$-bit integers $x$ and $y$, the algorithm multiplies them as follows:

```
a = x >> n/2;
b = x - (a << n/2);
c = y >> n/2;
d = y - (c << n/2);

u = a*c           // recurse!
v = (a+b)*(c+d)   // recurse!
w = b*d           // recurse!

return (u << n) + ((v-u-w) << n/2) + w

```

The algorithm reduces one $n$-bit multiplication to three recursive $n/2$-bit multiplications, using $O(n)$ time for the various additions, subtractions, and shifts. Thus, the running time of the algorithm satisfies the recurrence $T(n) = 3T(n/2) + O(n)$, whose solution is $O(n^{\lg 3}) = O(n^{1.585})$. In particular, the running time is **not** $O(n\log n)$.

In this example, the problem is divided "in half" in every recursive call, but that's not a requirement, either. A more complex generalization of Karatsuba's algorithm, due to Toom and Cook, uses five recursive $n/3$-bit multiplications, to get a running time of $O(n^{\log\_3 5}) = O(n^{1.465})$.
> 4 votes

# Answer
Your algorithm, while recursive, is not really D&C.

An algorithm is usually referred to as D&C if it solves the problem by dividing the instance into smaller instances of the same problem, and solving each smaller part using the same algorithm. The division does not have to be into two parts (and in particular not to two equal parts), nor does it have to run in $O(n\log n)$.

Dividing to halves and running in $O(n\log n)$ happens in Merge Sort, which is one of the most famous examples of D&C. Perhaps this is the source of your confusion.

The reason your algorithm is not really D&C is because you don't really divide the problem. Indeed, you handle the "edge" of the problem, and then use recursion to solve what's left.

By the way, observe that your algorithm just merges sorted lists, as you said. This algorithm is usually used as the "conquer" part of Merge Sort. If you incorporate it into a recursive algorithm that sorts, you get Merge Sort, and the running time of $O(n\log n)$.
> 3 votes

# Answer
Let's say you have two lists A and B of length n, where n is even.

Merge the first half of A with the first half of B, giving an array X.

Merge the second half of A with the second half of B, giving an array Y.

Merge the second half of X with the first half of Y, giving an array Z.

The result is (first half of X) followed by Z followed by (second half of Y).

This is an awful algorithm, doing a job that can easily be done in $O (n)$ but using $O (n^{1.585})$ steps instead. Just as Karatsuba's multiplication algorithm, but without having any good excuse :-) But if you want a recursive divide-and-conquer algorithm, you got it. (If n is odd, add a huge number at the end of each list, merge them, remove the two huge numbers at the end of the list).
> 0 votes

---
Tags: algorithms, terminology, divide-and-conquer
---


# Question
Title: Can't understand this division algorithm in Computer Architecture
So, I'm preparing for an exam where I have solve divisions using this division algorithm:

While I understand the theory (image above), I couldn't understand this example below:

My problem is with the "First Step", apparently you place the dividend in the "Remainder" box but I don't undetrsand how did they come up with the divisor (10 000), where did this number come from?

# Answer
> 1 votes
The divisor is the 2 put into the upper 4 bits of the 8 bit divisor register.

---
Tags: computer-architecture
---


# Question
Title: Why is reduction mostly associated with proving hardness?
Reduction is a powerful problem solving technique that is helpful in solving problems in terms of the solution to other problems, it can also be used for complexity analysis. Why does most of the literature restrict mentioning reduction to proving hardness which seems to be a pessimistic point of view for reduction (unless P=NP ofcourse :) )?

**EDIT:** Just to make sure my question is well understood. I am aware that reduction is used for problem solving and designing or analyzing algorithms, I have solved hundreds of contest problems with reduction which leads to my question of why is a random search for reduction lead to the NP completeness context with book chapters and papers illustrating its power from the complexity theory point of view when the same basic definition for reduction can be used for designing algorithms but just rarely (or implicitly) mentioned. In other words, why does a random sampling of the occurrences of the term "reduction" show a clear bias towards its use in complexity theory.

# Answer
Actually, people *do* commonly use reductions for both purposes: both for proving lower bounds, and for designing algorithms to handle a certain problem.

For instance, it's very common to reduce a problem to linear programming, to a max-flow problem, or to another well-studied problem. This is using reductions for solving problems.

Any particular textbook might focus more one or the other use of reductions. That's a philosophical choice on the part of the author.
> 3 votes

# Answer
I've seen reduction used implicitly. A good example is the problem of finding a maximum spanning tree. In that case, you reduce the problem to the minimum spanning tree problem by multiplying all edge weights by -1, then apply Prim's or Kruskal's algorithm to the new graph.

In this case, reduction was used to "rephrase" the problem in a slightly different way to make it more amenable to an easy solution as opposed to showing that it falls in a particular complexity class.
> 2 votes

# Answer
The need to define reduction formally arises only when defining classes of hard problems. Consider polynomial time reducibility as an example. The same notion is used for both "positive" and "negative" purposes:

* If a problem $A$ can be solved in polynomial time and there is a polynomial time reduction from problem $B$ to problem $A$, then $B$ can also be solved in polynomial time.
* Problem $A$ is NP-hard *by definition* if there is a polynomial time reduction from any problem $B$ in NP to the problem $A$.

In the first example, there is no need to define reduction formally. We just use the reduction. In the second example, we have to define reduction formally – otherwise we cannot define NP-hardness.

Reductions are used commonly for algorithms. A good example is the paradigm of linear programming. Whenever we use linear programming in an algorithm, we are in effect giving a reduction from our problem to linear programming (not necessarily a many-one reduction, though). Since linear programming can be solved efficiently (in practice and theoretically), the original problem can be solved efficiently.
> 2 votes

---
Tags: algorithms, reductions, algorithm-design
---


# Question
Title: HOG vs. neural networks for person detection
I am very new to computer vision, (a high school student) and I am working on a project to count the number of people present in a room. I have tried to use the HOGDecriptor for person detection provided by OpenCV (`HOGDescriptor_getDefaultPeopleDetector()`) but it is very inaccurate, understandably. I was thinking that it may be advantageous to train my own system, since each camera setup would be specific to a certain room. This would greatly restrict the bounds of what the computer has to recognize. (What I mean by this is that if I am analyzing a conference room, little about the environment changes, other than the addition of people. This would limit the scope of the detection problem.)

My question is whether to use a HOGDescriptor or a Neural Network. I was planning on using a HOGDescriptor but was advised that a Neural Network may be more accurate. At the same time however, the way I understand a Neural Network works is that I provide the number of input neurons as well as the number of output neurons, and the training algorithm creates the hidden neurons in between. The problem with this approach is that I would like to be able to count an arbitrary number of people in the camera frame, and thus I could not provide the training algorithm with a definite number of end neurons. I addition, I am able to mark frames positive or negative (whether or not they include people in them) quite easily, but providing the description of the number of people in them would be significantly harder. For both these reasons, it would seem to me that HOGDescriptors would work better, because they do not need to be told how many people are in the frame, and they can create an arbitrary number of "end neurons."

Any help clarifying the benefits of both technologies, as well as advice on which to use, would be greatly appreciated. I realize that this question might be very elementary, but I am willing to learn and will take all responses very seriously. Thank you.

# Answer
Unfortunately, this remains a very challenging problem, that even state-of-the-art techniques find difficult to do accurately. It's probably too hard for a high school project.

The closest work is probably on "pedestrian detection". Do a search on Google Scholar, and you should find a bunch of research papers on this from the computer vision community. However, the state-of-the-art techniques are complex, and even the best techniques aren't super accurate.

You should also read about "object detection", "object recognition", and related topics. That will give you the basics of how to use machine learning (like neural networks) to recognize the location of objects in an image. One standard technique is to crop out a small rectangle from the image, use your classifier to check it contains the object you're looking for (e.g., a person), and then repeat this for many crops of many different regions of the image -- this tells you the location of all people. There are other approaches as well, based on regression to infer the location of the object.

You might find Stanford's CS231N useful for learning more about these techniques.

For your specific problem, doing this in the general case is probably too hard. I'd advise you to look for a way to make the problem easier. One way is to make the problem more constrained and place your cameras carefully to make the machine learning problem easier.

For instance, if the room is a lecture hall where everyone will be seated and facing the same direction, you could experiment with placing a camera that will see everyone from the front, and using facial detection to identify and count the number of faces in the image. Or, you could place a video camera at each entrance and exit and use facial detection or other methods to try to recognize people when they are entering/leaving the room, and count the number who have entered and the number who have left. This will probably be easier if you have *two* video cameras over each door: one on the outside pointing in, and one on the inside pointing out. Or, you could experiment with entirely different sensors, such as a FLIR camera which can see in the infrared. People are warm and glow in the FLIR wavelengths, which might make it easier to distinguish people from other elements of the scene.
> 1 votes

---
Tags: machine-learning, neural-networks, computer-vision
---


# Question
Title: modify Dijkstra's algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex
i want to modify Dijkstra algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

I tried it with BFS(breadth first search). Initially calculates the number of edges away from source to each vertex v. Then run Dijkstra's algorithm with a constraint like relaxation u if and only if edges size from the source to u is no longer than three. Is it correct or Are there another method to find it.(using Dijkstra algorithm)

# Answer
> 0 votes
What if we add a simple if condition to check the parents since the number of parents to check is less (i.e. 3)?

In the dijkstra's algorithm,

```
  Dijkstra(G,W,s)
       Initialize_Single_Source(G,s)
       S= {}
       Q = V[G]
       while Q != {} do
          u = extract_min(Q)
          S = S U {u}
          for each vertex v element of Adj[u] do
                if(parent[u]==NIL || parent[u]==s || parent[parent[u]]==s)
                     relax(u,v,w)

```

# Answer
> 1 votes
I assume you want to **only** calculate shortest paths, starting from $s$, to vertices in its 3-hop neighborhood, i.e. vertices which are reachable from the start vertex $s$ with a path length $\leq 3$.

Use a limited breadth-first search and save the frontier vertices in a queue which is sorted according to its edge-weights. By doing that you have a priority queue and can update vertices like in the regular Dijkstra's algorithm. Note that you need to keep track of the current depth of the breadth-first search.

---
Tags: algorithms, shortest-path
---


title: Stable matching with constraints

text:
# Question
Title: Stable matching with constraints
I'm reading through Algorithm Design by Kleinberg and Tardos and was working on Ch1 Q1. The question is about stable matching and their 'proof' is presented by contradiction. I have an alternative argument and want to know if its right. The question paraphrased is:

> Consider a town with n men and n women. Each man as a preference list that ranks the women and each women has a similar preference list. Of these men and women, k men are bad and k women are bad. So there are n-k good women and n-k good men. Each man prefers to match with a good women and vice versa. Therefore all preference lists rank the good people higher than bad people. Show that in every stable matching every good man is married to a good women.

My 'proof':

Assume that there is a pairing where a good man is matched with a bad women. Because there are the same number of good men and women, it means that there is one good woman, currently paired with a bad man, who rejected this good man. If she rejected this good man it means that he must be of lower preference than the bad man she is paired with. But this is a contradiction because a good man cannot be ranked lower than a bad man. It means that the good man is actually bad and there are more bad men than good women and the initial problem statement is false.

# Answer
I assume you want to start your proof with "suppose there is a pairing where a good man $m\_1$ is matched with a **bad** woman $w\_1$".

This indeed means that there exists a good woman $w\_2$ matched with a bad man $m\_2$ (by the pigeonhole principle). However, the contradiction here does not follow from the fact that $w\_2$ prefers $m\_1$ but is actually matched to $m\_2$ (it is possible for a woman to not be matched with her top ranked man).

The contradiction follows from the fact that a matching which contains $(m\_1,w\_1),(m\_2,w\_2)$ is not stable, since $m\_1$ prefers $w\_2$ and $w\_2$ prefers $m\_1$.
> 1 votes

---
Tags: algorithms, matching
---


# Question
Title: Sorting a stack of cards with help of a computer
I have a physical stack of cards, with numbers on them (or, in reality, I have a stack of exams, with students names on them ;)). I want to sort the cards in ascending order.

This is an extremely boring task. I usually use mergesort myself (quick question: what do you use?). But say each card has a QR code. I can scan all the codes as I go through the stack using my mobile phone and then I have the list of cards and the order in which they appear.

What would be a clever way to use this information in order to tell a human how to sort the stack of cards? I imagine that the computer could somehow give me instructions of what to do so as to arrive at the sorted order. Notice that things like "take the 52nd card and place it on the top" are not nice, since I don't want to count to the 52nd card. What would you do?

I realize this question is rather subjective: what constitutes a "nice" strategy depends on the person. I just want to know what kinds of ideas you people could come up with.

# Answer
> 7 votes
1. Setup an array of initially empty file folders (even better buy a mail sorter and you are in the pigeonhole sort case).
2. The computer, knowing the initial order of the cards, will tell you, one by one, where to put each card (you have a limited number of folders so instructions like "take the current card and place it on **top** / **bottom** of folder **3**" are quite easy to follow).
3. Manually sort each non empty folder using insertion-sort.
4. Visit the folders in order and put all cards back onto the table.

(repeat `n` times and you're ready for the parcel delivery office, almost... a railway post clerk was required to sort 600 pieces of mail in an hour with 97% accuracy in order to keep his job :-)

---
Tags: sorting
---


# Question
Title: How would the Internet work between planets?
Say that in the future there are people on other planets, e.g., Mars. The one-way communication delay to Mars is between 3 and 21 minutes.

Say we want to connect the people on Mars to the Internet. How would we deal with the communication delay? For example, we don't want to get request timeouts as fast as we have them normally (on Earth). Would network protocols need to be adjusted or modified to deal with the increased latency?

# Answer
There would be special protocols for interplanet communication. Right now there are already different routing protocols for connecting different cities, different countries and different continents.

BGP (Border Gateway protocol) is a routing protocol used between continents mainly. It has different parameters and behavior than OSPF or RIP or other protocols used between different LAN's or WAN's.

Read about BGP. Some other protocols would probably be developed for even larger distances and for connecting different planets.
> 3 votes

---
Tags: computer-networks
---


# Question
Title: Why the number of equivalence classes for the intersection of an irregular language L2 and a regular languge L3 (with 3 EC) can't be determined?
I'm trying to understand why can't we determine the number of equivalence classes of the intersection of L2 which is irregular and L3 which is regular and known to have 3 equivalence classes (L3 can't be empty). Can't we say it has minimum of 1?

Can we determine the number of equivalence classes for an Irregular language L with a star (L\*)?

# Answer
> 4 votes
Assuming you are meaning Nerode equivalence classes, the number of classes of a language is finite iff that language is regular.

We cannot make any statement for the intersection of a regular and a non-regular language. That intersection can non-regular, but also regular. Similar for the star of a non-regular language.

Stating that the number of classes is at least one is not very instructive. Isn't that true for all equvalence relations?

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


# Question
Title: Are results after performing operations on AVL trees ambiguous?
After performing operations (e.g. insertion/deletion of a node - rotations) on an AVL tree, is the result fully determined by the order of insertion on the initial tree, or do multiple solutions exists that satisfy all AVL properties?

# Answer
> 1 votes
In standard way the order of operations determines the tree shape - there are no ambiguous choices during insertion / deletion or rebalancing so it is unique.

There are more possible trees if you consider some additional operations that do not violate AVL properties like introducing stricter balance or rotating -1 to +1, please remember that this operations are non-standard and changing -1 to +1 serves only one purpose - to show different existing trees with AVL properties.

---
Tags: trees
---


# Question
Title: How do I find running time for the following divide and conquer problem?
Question is to find the runtime $T(n)$ of following problem by solving the recurrence.

$T(n)=16\cdot T(\frac{n}{4}) + n!$.

I went through the following theory.

*If the recurrence relation is of the form $T(n)=aT(\frac{n}{b}) + \Theta(n^k(\log n)^p)$,where $a \geq 1$ , $b \gt 1$, $k \ge 0$ and $p$ is a real number, then:*

1. If $a \gt b^k$, then $T(n)=\Theta(n^{\log\_b a})$.
2. If $a=b^k$

1. If $p \gt -1 $, then $T(n)=\Theta(n^{\log\_b a}(\log n)^{p+1})$.
    2. If $p=-1 $ then $T(n)=\Theta((n^{\log\_b a}\log \log n)$.
    3. If $p \lt -1 $, then $T(n)=\Theta(n^{\log\_b a})$.
3. If $a \lt b^k$

1. If $p \ge 0 $, then $T(n)=\Theta(n^k(\log n)^p)$.
    2. If $p \lt 0 $, then $T(n)=O(n^k)$.

Now I want to know how do I compare the second terms of the the equations ($n!$ and $\Theta(n^k(\log n)^p) $) to obtain $k$ so that I can check which of the above case holds true ?

# Answer
You cannot use the Master Theorem to solve this recurrence, since $n!$ doesn't grow like $n^c$ for any $c$. Instead, Stirling's approximation shows that $n! \sim \sqrt{2\pi n} (n/e)^n$. Rather, expand the recurrence to get $$ T(n) = n! + 16 (n/4)! + 16^2 (n/16)! + \cdots. $$ Stirling's approximation shows that the latter terms are tiny compared to the first one. Therefore $$ T(n) \sim n!. $$ This is just shorthand for $$ \lim\_{n \to \infty} \frac{T(n)}{n!} = 1. $$

If you want to prove this formally, one way is as follows. Start with the observation that $n/16 \geq 4$, $$ 16 (n/4)! \leq (n/4+1)(n/4)! = (n/4+1)! \leq \frac{1}{n} n!. $$ The first inequality uses $n \geq 60$, and the second $n \geq 4$. Continuing in this vain, for $n/16^2 \geq 4$, $$ 16^2 (n/16)! \leq \frac{1}{n/4} (n/4)! \leq \frac{1}{n/4} \frac{1}{n} n! \leq \frac{1}{n} n!. $$ In the same way we show that $16^k (n/4^k) \leq n!/n$ for $n/4^k \geq 4$. Therefore $$ T(n) = n! + 16(n/4)! + 16^2(n/4^2)! + \cdots \leq n! + n!/n + n!/n + \cdots + 16^r T(4), $$ where $n/4^r = 4$, and so $r = \log\_4 n - 1$, which implies $16^r = n^2/16$. Since there are $r-1 = \log\_4 n - 2$ summands of the form $n!/n$, we certainly have $$ T(n) \leq n! + \frac{\log\_4 n}{n} n! + \frac{T(4)}{16} n^2. $$ This shows that $T(n) = n! + f(n)$, where $$ f(n) = \frac{\log\_4 n}{n} n! + \frac{T(4)}{16} n^2 $$ is a function satisfying $$ \lim\_{n \to \infty} \frac{f(n)}{n!} = 0. $$ On the other hand, clearly $T(n) \geq n!$. This implies what we claimed above, $T(n) \sim n!$.
> 2 votes

---
Tags: complexity-theory, asymptotics, discrete-mathematics, divide-and-conquer
---


# Question
Title: Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n
The questions is to find the running time $T(n)$ of the following function:

$$T(n)=3\cdot T(n/2) + n \tag{1}$$

I know how to solve it using Master theorem for Divide and Conquer but I am trying to solve it by expanding: $$\textstyle T(n) = n+\frac{3}{2}n +(\frac{3}{2})^2n + (\frac{3}{2})^3n + \cdots \tag{2}$$ which implies $$T(n)=n\sum\_{k=1}^{n}({\textstyle \frac{3}{2}})^{k-1} \tag{3}$$ and so $$T(n)=2n\cdot(({\textstyle\frac{3}{2}})^n-1) \tag{4}$$

The right answer to this problem is $\Theta(n^{\log3})$. How can I reach to right answer through my approach as shown above.Is my approach wrong ? How can I solve it without using Master theorem.

Any help is appreciated.

# Answer
Your approach is almost correct, except for the fact that the upper limit of your summation should be $\log\_2n$, rather than $n$. You should have $$ T(n)=3^kT\left(\frac{n}{2^k}\right)+\left\[n\left(\frac{3}{2}\right)^{k-1}+n\left(\frac{3}{2}\right)^{k-2}+\dotsm+n\left(\frac{3}{2}\right)^0\right\] $$ and your goal is to drive $n/2^k$ down to a value that will allow you to replace $T(n/2^k)$ with to a value you know, like, say, $T(1)$. That will happen when $n=2^k$ so $k=\log\_2n$. Using that value for $n$ gives you $$\begin{align} T(n)&=3^{\log\_2n}T(1)+n\sum\_{j=1}^{\log\_2n}\left(\frac{3}{2}\right)^{j-1}\\ &=3^{\log\_2n}T(1)+2n\left\[\left(\frac{3}{2}\right)^{\log\_2n}-1\right\]\\ &=n^{log\_23}T(1)+2n\[n^{\log\_2(3/2)}-1\]\\ &= n^{\log\_23}T(1)+n^{log\_23}-2n\\ &= \Theta(n^{\log\_23}) \end{align}$$
> 2 votes

# Answer
You have a mistake going from (2) to (3) because you lost $n$ and it is not clear why your sum should range from $i = 1$ to $i = n$ (it does not). Then it is not clear how you got from (3) to (4) where $n$ reappeared. Perhaps you just los $n$ in (3) but otherwise you had it on paper.

Let us try again: \begin{align\*} T(n) &= n + (3/2) n + (3/2)^2 n + \cdots \end{align\*} **But when does sum end?** (This is what created your mistake.) It ends when we get to the base case, which is $T(1)$. After $k$ unfoldings we have $T(n/2^k)$ so we will reach $T(1)$ when $k = \log\_2 n$. Thus, we continue like this: \begin{align\*} T(n) &= n + (3/2) n + (3/2)^2 n + \cdots + (3/2)^{\log\_2 n} T(1) \\ &= \textstyle \sum\_{i=0}^{\log\_2 n} (3/2)^i n\\ &= n \cdot \textstyle \sum\_{i=0}^{\log\_2 n} (3/2)^i. \end{align\*} It remains to add the sum. It is a geometric series, so we can look up the formula $\sum\_{i=0}^k a^i = (a^{k+1} - 1)/(a - 1)$ and get \begin{align\*} {\textstyle \sum\_{i=0}^{\log\_2 n} (3/2)^i} &= \frac{(3/2)^{1 +\log\_2 n} - 1}{3/2 - 1} \\ &= 2 \cdot ((3/2) \cdot (3/2)^{\log\_2 n} - 1) \\ &= 3 \cdot (3/2)^{\log\_2 n} - 2 \\ &= 3 \cdot (n^{\log\_2 (3/2)}) - 2 \\ &\in \Theta(n^{\log\_2 (3/2)}) \approx \Theta(n^{0.58}) \end{align\*} The final result is this sum multiplied with $n$, so it is $$\Theta(n \cdot n^{\log\_2(3/2)}) = \Theta(n^{\log\_2 2 + \log\_2 (3/2)}) = \Theta(n^{\log\_2 3}),$$ assuming I can still do logarithms....
> 2 votes

# Answer
You are correct that $$ \begin{align\*} T(n) &= n + \tfrac{3}{2} n + (\tfrac{3}{2})^2 n + \cdots + (\tfrac{3}{2})^{k-1} n + 3^k T(n/2^k) \\ &= n \sum\_{t=0}^{k-1} (\tfrac{3}{2})^t + 3^k T(n/2^k) \\ &= 2\[(\tfrac{3}{2})^k-1\]n + 3^k T(n/2^k). \end{align\*} $$ Let's assume that $n$ is a power of $2$, and the base case is $T(1) = C$. In order to reach the base case, we need to choose $k$ so that $n = 2^k$. In other words, we need to take $k = \log\_2 n$. We then have $3^k = n^{\log\_2 3}$ and $(3/2)^k = n^{\log\_2 3 - 1}$. Substituting these values, we find out that $$ T(n) = 2\[n^{\log\_2 3-1}-1\]n + Cn^{\log\_2 3} = (C+2)n^{\log\_2 3} - 2n. $$ This shows the stronger result $$ T(n) \sim (C+2) n^{\log\_2 3}, $$ which implies $T(n) = \Theta(n^{\log\_2 3})$.
> 2 votes

---
Tags: complexity-theory, asymptotics, master-theorem, divide-and-conquer
---


title: How to minimize the following DFA?

text:
# Question
Title: How to minimize the following DFA?
Consider the DFA, M=({1, 2, 3, 4, 5, 6}, {a, b}, 1, {2, 5}, δ), whose δ is specified below.

I calculated the following and got unmarked states (5,2) and (6,3)

(6,3) looks okay but there is something wrong with (5,2).It is not deterministic so where did I go wrong?

# Answer
> 1 votes
States 2 and 5 are distinguishable. We have $(2, 5)\stackrel{b}{\longrightarrow}(1,5)$ and state 1 is a non-final state while state 5 is final. In addition, as HueHang and Amy have noted, $(6, 3)$ is also distinguishable, so the original DFA is already mimimized.

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


# Question
Title: Is It possible to change the side of 0 and 1 in Huffman tree?
When we are constructing the Huffman tree to get the Huffman codes, Is it possible to give "1" to left side and "0" to right side rather than giving "0" to left side and "1" to right side of the tree?

# Answer
> 2 votes
You can assign the $1$ and $0$ as you like, but be consistent. Only your code change, i.e. a 1011 becomes a 0100.

# Answer
> 2 votes
Yes, You can.
But you'll need the Huffman tree to decode since the placing of left child and right child is arbitrary. If you're given an encoded string and ask you to decode, you can't do that since you don't know the exact algorithm which is used in building the Huffman Tree.

---
Tags: algorithms, huffman-coding
---


# Question
Title: Big Theta for finding combinations of arbitrarily sized subsets from n total elements
Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset?

Assume the elements are all unique.

For example:

```
n=2, `a b` there are two cases.
`(a), (b)` which has one permutation 1: `a, b`
`(a, b)` which has two permutations 1: `a`, 2: `b`

```

And then for a larger `n`:

```
n=3, `a b c` there are three cases.

3 subsets of 1 element: 1^3 permutations
`(a), (b), (c)` which has one combination 1: `a, b, c`

1 subset of 2 elements and 1 subset of 1 element: 2^1*1^1=2 permutations
`(a, b) (c)` which has two combinations 1: `ac`, 2: `bc`

1 subset of 3 elements: 3^1=3 permutations
`(a, b, c)` which has two combinations 1: `a`, 2: `b`, 3: `c`

```

Basically for a given `n` its the maximum value of `S1*S2*S3...` where `S#` is the size of subset `#`.

It's easy enough to demonstrate that big lambda is `2^(n/2)`.

And I *think* that `3^(n/3)` may be a big omega.

I've been mulling this problem over for a little while now, if it's a known problem then I'd love to be pushed towards the right solution, but I've found that it's a bit difficult to search for.

# Answer
> 3 votes
If we denote by $q(n)$ the number of permutations, the first few values are $$\begin{array}{ccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ q(n) & 1 & 1 & 3 & 6 & 14 & 25 & 56 & 97 \end{array}$$ This sequence can be found at the online encyclopedia of integer sequences, which is a really helpful site. It has a lot of information about the sequence in question, including the fact that you were right in your guess that $q(n)=\Theta(3^{n/3})$.

\[Yes, I'm aware that this doesn't answer all of your question, since this only counts how many permutations there are, and doesn't enumerate them.\]

---
Tags: algorithms, asymptotics, combinatorics
---


title: Unsure about parse tree of PCFG

text:
# Question
Title: Unsure about parse tree of PCFG
I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S-\>Sa, S-\>aSa, S-\>a) and the word I'm parsing is simply aaaa.

My solution would look like

Is this right and is this the only possible parse tree?

# Answer
Your tree is correct. However, it's not the only possible one. Your tree came from the derivation $$ S\Rightarrow Sa\Rightarrow aSaa\Rightarrow aaaa $$ a different one would be from $$ S\Rightarrow aSa\Rightarrow aSaa\Rightarrow aaaa $$
> 0 votes

---
Tags: trees, parsers, tree-grammars
---


title: Spanning tree display conventions

text:
# Question
Title: Spanning tree display conventions
On page two of this discussion of spanning trees there are two different tree structures shown, one labeled *DFS tree starting from a as the root* and the other labeled *Spanning tree created by DFS*. If I were to write this out on paper my spanning tree would have looked more like the former than the latter.

Are these distinguished here for convenience, one to show the tree structure of the algorithm vs one showing how the spanning tree fits within the original graph layout? Is this a standard convention, to show the spanning tree in the same layout as the original graph? Would it be *wrong* to diagram the spanning tree using the first layout?

# Answer
> 2 votes
Yes, the right one is shown for convenience. Whether it is a *standard* convention I do not know and I think it is not so important as both trees are the same, the right one is just formatted neatly so that it matches the structure of the original graph.

It is not wrong to use the first layout (as shown on the left). However, readers might prefer the right one.

---
Tags: algorithms, discrete-mathematics, spanning-trees
---


# Question
Title: Difference between cordic algorithm and table based methods for elementary functions computation
In this book both Table Based methods and Cordic iterations are explained. computationally speaking i suppose the Table based is usually faster, even though it probably requires more resource, while Cordic is probably slower, but probably less resource consuming (if my understanding is correct, it should be a specific instance of shift and adds algorithm). But are there other benefits/drawback in both approach? I suppose also the CORDIC doesn't suffer of the table maker dilemma, even though it in general requires a LUT.

# Answer
CORDIC uses small table to work, it calculates one bit at the time and being *shift and add* algorithm it is preferable when there are no multipliers available. Whenever multipliers are present, table based methods or power series are faster. Also one point worth notting - the scalling factor is also needed which sometimes is argument to use BKM, but this one is slower than CORDIC.

CORDIC is still used in x87 FPU, but nowadays Chebyshev polynomials are preferred way to compute special functions (or transcendental, but not elementary - this is rather bad name) (also do not consider Taylor here, it is very slow and works for small angles).

Drawbacks in both methods are increase in number of iterations and tables provided. Good to know how they work and grasp a piece of history, but not practical in software and not preferrable in hardware.
> 2 votes

---
Tags: computer-architecture, arithmetic, digital-circuits
---


# Question
Title: Batch regularization & L2 regularization
Is performing batch regularization in addition to L2 regularization redundant?

Batch regularization: http://arxiv.org/abs/1502.03167

Notice how when performing batch regularization, you forgo using a bias term (and instead normalize your layer output, followed by scaling with a 'scale' term, and shifting with a 'beta' term. I was under the impression that L2 regularization punishes large weights & biases... but if I'm not using biases because of batch regularization, then would I just punish the weights with L2 regularization?

Thanks--

# Answer
> 3 votes
No. They are not equivalent. They are two different techniques, that each provide some kind of regularization, but using one doesn't necessarily make the other redundant. For instance, in the paper you cite, the authors are using both (see Section 4.2.1 for mention of L2 regularization).

Specifically: whether or not it is more effective to use just batch regularization or to use both will probably depend on the specific learning task you have in mind. But there is no theory that implies the two are equivalent.

Batch normalization still has a bias term that is added after the normalization step (the $\beta$); it does not eliminate it. L2 regularization penalizes large weights and large biases. As far as I can tell, batch regularization doesn't try to do either (at least not explicitly).

When using L2 regularization with batch regularization, I imagine you could either L2-penalize just the weights; or L2-penalize the weights, the $\gamma$ terms (scaling), and the $\beta$ terms (shift). I don't know which will produce better results. My intuition says the latter might be preferable, but experiments and data beat intuition any day.

---
Tags: machine-learning, neural-networks
---


# Question
Title: Maximizing the rank of a binary matrix by zeroing matrix entries
Given a Square Binary Matrix.

The entries of the Matrix are the integers modulo 2 (i.e., GF(2)). The Rank of the Given Matrix is an Integer value R0.

What is the fastest known Algorithm to maximize the Rank of the matrix if the following operations are permitted:

1. Each 1 entry in the matrix can be replaced by a 0.
2. No 0 entry can be set to 1.

Approaches Tried:

Since Rank is the measure of number of independent vectors, the current attempt involved using a Gaussian elimination to simplify the matrix. The idea behind it was, if a larger Rank is possible we would be able to obtain the matrix for that Rank, by using the original and the simplified matrix. I am not sure if that is going to work.

Tried searching for some references, but not much success.

# Answer
The largest rank equals the size of a maximum matching of the corresponding bipartite graph, for which there are known efficient algorithms; see for example Wikipedia.

On the one hand, if the graph contains a matching of size $m$, then we can delete all other entries, thus obtaining a matrix in which an $m\times m$ minor is a permutation of the identity, and so of rank $m$. Thus the maximum achievable rank is at least the size of any matching.

On the other hand, suppose that by deleting entries of the original matrix $A$, we can obtain a matrix $B$ whose rank is $m$. The matrix $B$ must contain an $m\times m$ minor $C$ whose rank is $m$ (find a set of $m$ rows which form a basis for the row space, then a set of $m$ columns which form a basis for the column space). In particular, $\det C \neq 0$ and so there must be a "generalized diagonal" in $C$ which consists only of $1$s (since $\det C$ is the sum of the products of all generalized diagonals). This generalized diagonal appears already in $A$, and constitutes a matching of size $m$ in the corresponding graph.
> 4 votes

---
Tags: algorithms
---


# Question
Title: TM that accepts all strings is recognizable or not?
Lets say we have the following language $L = \\{\text{$M$ is a TM such that $M$ accepts all strings}\\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct could anyone provide me with a proof?

My current reasoning is that since the set of all strings is infinite, the "recognizer" TM will never be able to test all strings thus never be able to accept a given TM.

Please give me your thoughts on this.

# Answer
Your intuition is correct: your $L$ is unrecognizable. Here's a hint on how to proceed.

If we define $A\_\text{TM}= \\{(\langle M\rangle,w)\mid M \text{ accepts }w\\}$, then it's known that its complement, $\overline{A\_\text{TM}}$, is unreconizable so if we can construct a mapping reduction $\overline{A\_\text{TM}}\le\_M L$, then we'll have shown that $L$ is unrecognizable.

Define the mapping $f(\langle M\rangle, w)\rightarrow \langle N\rangle$ where the TM $N$ depends on $M$ and $w$ and is defined by

```
N(x) =
   run M on w for |x| moves
   if M hasn't accepted yet,
      accept

```

The key idea here is that if $M$ accepts $w$, then it will do so in $k$ moves, for some number $k$, so if $M$ accepts $w$, then $N$ will accept all and only those strings of length less than $k$, and so the language of $N$ will be $L(N) = \Sigma^{k-1}$. On the other hand, if $M$ doesn't accept $w$, then $N$ will accept all strings.

With this hint, you should be able to show that $(\langle M\rangle, w)\in \overline{A\_\text{TM}}\Longleftrightarrow\langle N\rangle\in L$, which is the reduction we need.
> 2 votes

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


# Question
Title: Is it possible to produce different shortest path trees using bellman ford and Dijkstra algorithm?
Given a graph G=(V,E) with positive edges weights, Is it possible to produce different shortest path trees for the Bellman-Ford algorithm and Dijkstra's algorithm?

# Answer
If there are multiple shortest paths (equal distances), you could get different results even between two runs of Bellman Ford, if for instance, the two runs consider edges in different orders. But, for any graph with unique shortest paths, they obviously must both return the unique answer.
> 5 votes

---
Tags: algorithms, shortest-path
---


# Question
Title: Solving recurrence relation $T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$ using method of guessing and confirm?
The book I am following explains the solution as,

> As we can see,the size of sub problems at the first level of recursion is $n$.So, let us guess that $T(n)=O(n\log n)$ and try to prove that our guess is correct.

**Doubt-** Does initial problem size(i.e **n**) give a hint to reach $O(n\log n)$ ? How it does?

furthermore ,the book says

> Let's start by trying to prove an *upper bound* $T(n)\le c\cdot n\log n$
>
> \begin{align\*} T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n \tag{1} \\ \le \sqrt{n}\cdot c\sqrt{n}\log(\sqrt{n}) + n \tag{2} \\ =n\cdot c\log (\sqrt{n})+ n \tag{3} \\ =n\cdot c\cdot\frac{1}{2}\log n+ n \tag{4} \\ \le c\cdot n\log n \tag{5} \end{align\*} Last inequality assumes only that $$1\le c\cdot\frac{1}{2}\cdot \log n$$ This is correct if n is sufficiently large and for any constant c,no matter how small.So we are correct for upper bound.

I am not getting what's happening from $(1)$ to $(2)$ and that from $(4)$ to $(5)$. Also What does the last line prove ?

# Answer
> 5 votes
The book answer skips over some things. Here's a more detailed explanation.

You want to show $T(n)=O(n\log n)$, in other words there exists a $c\>0$ such that $T(n)\le c\cdot n\log n$. \[Actually, you need also to show that this inequality holds for all $n$ greater than some constant $N$, but we'll put this off temporarily.\]

We'll use strong induction here; our induction hypothesis is that

> $T(k)\le c\cdot k\log k$, for all $k\<n$.

Now we'll expand the book's answer. $$\begin{align} T(n) &= \sqrt{n}\\;T(\sqrt{n}) + n &\text{by definition} \\ &\le\sqrt{n}\\;\[c\cdot\sqrt{n}\log{\sqrt{n}}\]+n &\text{by induction hypothesis, since $\sqrt{n}\<n$}\\ &= cn(\log\sqrt{n})+n \end{align}$$ which answers your question about the step from $(1)\rightarrow(2)$. To get $(4) \rightarrow(5)$ the text wants to end up with $T(n)\le c\cdot n\log n$, so to conclude this they need $$ n\cdot c\cdot\frac{1}{2}\log n+n\le c\cdot n\log n $$ Dividing both sides of the desired equality by $n$ yields the needed condition: $$ \frac{c}{2}\log n+1\le c\log n $$ and this will be true when $1\le \frac{c}{2}\log n$. \[The book actually doesn't need an unspecified $c$: in fact, $c=2$ will work perfectly here, since as long as $n\ge 2$ we'll have $1\le\log n$, satisfying our needed condition.\]

In sum, we've shown by induction that the recurrence $T(n)= \sqrt{n}\log\sqrt{n}+n$ is satisfied by any function $T(n)=c\cdot n\log n$, as long as we pick a suitable $c$, which is exactly what was required.

---

It's worth pointing out that $O(n\log n)$ is an upper bound, but it's not the tightest upper bound possible. As gnasher729 pointed out, a better bound is $O(n\log\log n)$. It's a good exercise to do the same argument (with $c=1$) to show that $T(n)=n\log\log n$ is a solution to $T(n)=\sqrt{n}\\;T(\sqrt{n})+n$.

# Answer
> 3 votes
No. The problem size is defined to be $n$; that doesn't tell us anything about the solution to the recurrence.

See https://cs.stackexchange.com/a/2799/755 for details on how to use guess-and-check. How do you find a guess? Try a bunch of possibilities. Or, have an inspired guess. Or, graph the recurrence for $n=1$ to $n=100$ and use curve-fitting.

# Answer
> 3 votes
The recursion formula obviously doesn't work for n = 1, since in that case it says that T (1) = 1 * T (1) + 1. So let's guess that T (2) = c, where c is unknown.

T (4) = 2 T (2) + 4 = 2c + 4.

T (16) = 4 T (4) + 16 = 8c + 32.

T (256) = 16 * T (16) + 256 = 128c + 16 * 32 + 256 = 128c + 16\*16\*3.

T (65536) = 256 T (16) + 65536 = 32768c + 256\*256\*3 + 256\*256 = 32768c + 256\*256\*4.

It's time to guess that $T (2^k) = 2^{k-1}c + 2^k * log\_2 (k)$.

Or $T (n) = cn/2 + n * log\_2 (log\_2 (n))$

Does this solve the recurrence relation? Assume that n is the square of an integer ≥ 2. Then according to the recurrence relation and the guess,

$T(n)= \sqrt{n}(c\sqrt{n}/2 + \sqrt{n} * log\_2 (log\_2 (\sqrt{n})))+n$

$T(n) = cn/2 + n * log\_2 (log\_2 (\sqrt{n}))+n$

$T(n) = cn/2 + n * log\_2 (log\_2 (n)/2)+n$

$T(n) = cn/2 + n * (log\_2 (log\_2 (n))-1)+n$

$T(n) = cn/2 + n * log\_2 (log\_2 (n)) - n + n = cn/2 + n * log\_2 (log\_2 (n))$

which is exactly what was proposed.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: How many bits are needed? Advantages/disatvantages of this configuration?
So the question is:

Assume we had 15 CPU instructions and, for each instruction, we were trusting one particular component of the kernel to handle it. How many modes do we need to support (including the user mode), and how many bits we had to use to represent these modes? What is an advantage and a disadvantage of using this scheme instead of the kernel/user mode scheme, where one kernel component is trusted to handle all 15 instructions?

Is it 16 modes (1 kernel mode for each component, then the 1 user mode) or is it just the regular 2 modes?

Would it be 4 or 1 bit(s) for 16 modes or 2 modes respectively?

I want to say an advantage are that 15 components would be more powerful, but I feel like I should be able to explain more. I think a disadvantage would be power and memory allocation.

Is that somewhat in the right direction?

# Answer
> for each instruction, we were trusting one particular component of the kernel to handle it

This seems to represent a misunderstanding of how code is executed. That's not how CPUs work. Instructions are executed by the CPU -- not handled by the kernel. So, the question seems to be based on a faulty premise.

---

(OK, there are sometimes occasional exceptions to this in real-world architectures -- e.g., in old x86 platforms, some floating-point instructions might be emulated by the kernel when running on a CPU that didn't have floating-point support -- but that's a detail. Treat what I've described above as the basic rule.)
> 1 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Vertex cover of a graph by removing leaf-vertices from a DFS tree
Question taken from "The Algorithm Design Manual" by Steven S. Skiena, 1997.

A vertex cover of a graph $G=(V,E)$ is a subset of vertices $V'\subseteq V$ such that every edge $e\in E$ contains at least one vertex from $V′$.

Delete all the leaves from any depth-first search tree of $G$. Must the remaining vertices form a vertex cover of $G$? Give a proof or a counterexample.

**Answer given** :

If the tree has more than one vertex, then yes. The remaining vertices are still the vertex cover because for every edge e∈E incident on the leaves, their other end-point is still in the remaining tree.

**My question**:

The answer is right for undirected graphs. But I think there exist counterexamples to this question using directed graphs.

For example:

If we are using DFS starting from vertex $a$ and we are traversing in alphabetical order, i.e. explore b first, then we end up with two tree edges, which are $(a,b)$ and $(a,c)$. Therefore, $b$ and $c$ are leaf-vertices.

But here if are going to delete vertices $b$ and $c$ the edge $(c,b)$ has no incident vertices which are contained in our vertex cover.

Am I right? I am confused actually.

# Answer
> 5 votes
Look at the definition of vertex cover (as provided by the book). It is strictly defined on *undirected* graphs. Thus, the answer doesn't apply to directed graphs, nor to any other kinds of graphs you might think of. So your counterexample is invalid, as it makes invalid assumptions (graphs are always undirected here). These invalid assumptions are the source of your confusion.

To consider directed graphs, we first need to define what a vertex cover is on a directed graph. Well, we can say it is a subset of vertices such that every arc is incident to at least one vertex in the subset. Again, the book makes *no claim* about such directed vertex covers. If you are now asking "does $\\{ a \\}$ form a (directed) vertex cover as per our definition?", the answer is NO as you correctly observed.

---
Tags: algorithms, algorithm-analysis, graph-traversal
---


# Question
Title: NFA corresponding to the regular expression α = (a*b | ϵ) (b*(a | ϵ))
I'm currently studying for an upcoming exam in theoretical computer science, but one of the exercises is confusing me: in the exercise sheet it says that the NFA $$M=(\\{z\_0,z\_1,z\_2\\},\\{a,b\\},\delta,\\{z\_0,z\_1,z\_2\\},\\{z\_2\\})$$ corresponding to the regular expression $\alpha=(a^\*b|\epsilon)(b^\*(a|\epsilon))$ is defined by $$\begin{array}{c|ccc} \delta&z\_0&z\_1&z\_2\\\hline a&\\{z\_2\\}&\\{z\_1\\}&\emptyset\\ b&\\{z\_0\\}&\\{z\_0,z\_2\\}&\emptyset \end{array}$$ where $\delta$ is the transition function.

I don't understand how this can be right - if I'm not mistaken, the word $bb$ is an element of $L(\alpha)$ but it's not an element of $T(M)$.

So... basically, my question is: is the exercise sheet flawed or am I misunderstanding the concept of regular expressions?

# Answer
I think the inner pair of parentheses is out of place - without this pair of parentheses, we get the regular expression $$\alpha=(a^\*b|\epsilon)(b^\*a|\epsilon),$$ which seems to satisfy $L(\alpha)=T(M)$... can anyone confirm this? (Sorry, I'm a beginner.)
> 1 votes

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


# Question
Title: Qualifications for a problem to be solved as a single source shortest path problem
What are the pre-conditions for any problem X to be qualified for being solved in a single source shortest path problem (SSSP) setting?

Lets, say we have a problem X. What should be the pre-conditions that we check in problem X definition that would allow us to formulate it as a SSSP.

Initial Idea for solution: I believe if it satisfies the property of optimal substructure. One can formulate the problem as SSSP as well.

# Answer
Wonderful question!

In spite of the question been very general, this is indeed a research topic by itself. I will rephrase slightly the question as follows: "*what are the conditions that enable the applicability of Dijkstra and/or A$^\*$ to solve a problem?*" Obviously, for those cases that could be identified, the translation you mention to a single-source shortest path comes from the fact that either Dijkstra or A$^\*$ (if a heuristic function is available) can solve the problem.

As a matter of fact, your initial guess, *optimal substructure* is not far from the real answer. As others might not know this concept, let me please introduce a related concept to that:

**Definition** (*Prefix Optimality*) A solution path $\pi=\langle s, v\_1, v\_2, \ldots v\_k\rangle$ is *prefix-optimal* if each of its prefixes is an optimal solution to the corresponding partial problem.

This definition is a specialized version of *optimal substructure* for the *path-finding problem*.

This said, the answer to your problem are *Cost Algebras*. Cost algebras propose a general notion of costs under which various search algorithms can be reformulated. More recently, an abstract formalism based on cost algebras has been introduced for costs suited for heuristic search algorithms such as A$^\*$. See Stefan Edelkamp, Shahid Jabbar and Alberto Lluch Lafuente. Cost-Algebraic Heuristic Search. American Association for Artificial Intelligence, 2005, 1362-1367.

**Definition** (*Monoid*) Let $A$ be a set and $\times : A\times A\rightarrow A$ be a binary operator. A monoid is a tuple $(A, \times, \mathbf{1})$, if $\mathbf{1}\in A$ and for all $a,b,c\in A$: (1) $a\times b\in A$; (2) $a\times (b\times c)= (a\times b)\times c$; (3) $a\times\mathbf{1}=\mathbf{1}\times a=a$.

We have a set, and an operation defined over the elements of our set. Let us now define a total order over them:

**Definition** (*Total order*) Let $A$ be a set. A relation $\preceq\in A\times A$ is a total order whenever for all $a,b,c\in A$: (1) $a\preceq a$; (2) $a\preceq b \wedge b\preceq a\Rightarrow a=b$; (3) $a\preceq b\wedge b\preceq c\Rightarrow a\preceq c$; (4) $a\preceq b\vee b\preceq a$.

Additionally, the *least* and *greatest* operations, denoted as $\sqcup$ and $\sqcap$ respectively, are defined as follows: $\sqcup A=c$ such that $c\preceq a, \forall a\in A$ and $\sqcap A=c$ such that $a\preceq c, \forall a\in A$. A set $A$ is *isotone* if $a\preceq b$ implies both $a\times c\preceq b\times c$ and $c\times a\preceq c\times b$, $\forall a, b, c\in A$.

With all these elements we can finally introduce Cost Algebras:

**Definition** (*Cost Algebra*) A cost algebra $\mathcal{A}$ is defined as a 6-tuple $\langle A, \sqcup, \times, \preceq, \mathbf{0}, \mathbf{1} \rangle$, such that:

* $\langle A, \times, \mathbf{1} \rangle$ is a monoid
* $\preceq$ is a total order induced by $\sqcup$
* $\mathbf{0}=\sqcap A$
* $\mathbf{1}=\sqcup A$
* $A$ is isotone

Now, any problem whose formulation satisfies the defintion of a Cost Algebra, can be solved with Dijkstra and/or A$^\*$. The following are instances of cost algebras given by the authors:

* $\langle \\{\top, \bot\\}, \vee, \wedge, \Rightarrow, \bot, \top \rangle$ (boolean): Network service availability
* $\langle \mathbb{R}^+\cup \\{+\infty\\}, \min, +, \leq, +\infty, 0\rangle$ (optimization): Price, propagation delay
* $\langle \mathbb{R}^+\cup \\{+\infty\\}, \max, \min, \geq, 0, +\infty\rangle$ (max/min): Bandwidth
* $\langle \[0,1\], \min, \cdot, \geq, 0, 1\rangle$ (probabilistic): Performance and rates
* $\langle \[0,1\], \max, \min, \geq, 0, 1\rangle$ (fuzzy): Performance and rates

Just a minute! What about your initial guess? Well, the authors proved that Cost Algebras actually imply prefix optimality (and hence, *optimal substructure*) so that their answer is more general than just saying that the problem has to verify the latter. As a matter of fact, Cost Algebras are verifiable whereas optimal substructure can not be immediately decided.

Hope this helps,
> 3 votes

---
Tags: graphs, shortest-path
---


title: Why is this flow a max flow?

text:
# Question
Title: Why is this flow a max flow?
According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how can this be the max flow?

# Answer
> 6 votes
You've left out part of the statement. It should be *"If there's no path between the source and the sink **with unused capacity** the flow is a max flow."* If you look at your graph you'll see that there is no path with unused capacity all the way from $s$ to $t$. The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated. The $s$ to $c$ link is saturated.

# Answer
> 3 votes
> if there was no path from s to t, then the flow would be a max flow.

The correct statement is,

> if there is no path from $s$ to $t$ *in the residual network*, then the flow is a max flow.

If you build the residual network, you'll see that there is no edge from $a$ to $b$ and none from $c$ to $b$ or $d$, so $s$ and $t$ are disconnected.

# Answer
> 1 votes
The flow is maximum if there is no augmenting(i.e. improving) path between `s` and `t`. A path would contribute to the maximum flow if all its edges have strictly positive capacity left. In your case although you have some paths between `s` and `t`, all of them will have at least one edge that has used its whole capacity. Thus you can't improve the current flow and it is maximum.

# Answer
> 1 votes
You need to draw the residual network for this.The augmented path finding procedure should be done in the residual network.

There are no augmented path from S to t here. So this is a max flow.

# Answer
> 0 votes
There is another way to see it that might help you:

if you cut the net in two subnets, i.e. s,a,c and b,d,t you can see that the net flow from the source subnet to the sink subnet is maximized: there are two saturated paths and one empty one. In any net, if you can find such a bipartition that highlights such a property then you know you've found a max flow. That works even if there is some returning path that is not empty, as per this answer: Kyle's bipartition is s,a and c,b,d,t. It works because if you have some non empty return path you can argue that emptying it would increase net flow towards the sink, but to decrease it you will certainly need to decrease also a going path thus keeping net total flow the same.

For my cut net flow is 5+3-0=8 while Kyle's leads to 5+6-3=8, and of course that's the same.

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


title: Generators in category theory

text:
# Question
Title: Generators in category theory
> An object K in a category C is called a generator if, for all pairs of morphisms f, g : A → B between arbitrary objects A and B, f = g iff ∀e : K → A. f ◦ e = g ◦ e.

Source: http://events.cs.bham.ac.uk/mgs2012/lectures/ReddyNotes.pdf (Page 7, Definition 3)

Can someone help me break down the meaning of this definition?

> for all pairs of morphisms `f, g : A → B` between arbitrary types `A` and `B`

A morphism can be thought of as a a mapping from one type to another?

`f` and `g` are morphisms from type `A` to type `B`?

> f = g iff ∀e : K → A. ...

Morphism `f` is equivalent to morphism `g` if and only if for the morphism type `K` to type `A`

> f ◦ e = g ◦ e

`e` applied to `f` is equivalent to `e` applied to `g`

Is my interpretation of this correct?

The number of steps in this definition blows my mind, can anyone help me visualize the entire definition?

# Answer
> 7 votes
The most obvious intuition comes from the notion of *well pointed categories*. A well pointed category is simply a category $\cal C$ in which the final object $1$ exists and is a generator for $\cal C$. This means that for every $f,g:A \rightarrow B$, $$ f = g \ \Leftrightarrow \forall p:1\rightarrow A, f\circ p = g\circ p$$

Note that $\circ$ is **composition** and not **application**! In haskell you would define:

```
f `comp` g = \x -> f (g x)

```

In programmatic notation the definition of well-pointedness gives

```
f == g iff for all p : () -> A, f `comp` p == g `comp` p

```

or unfolding the definitions

```
f == g iff for all p : () -> A, \x:() -> f (p x) == \x:() -> g (p x)

```

if we assume that the only inhabitant of `()` is in fact `()` (which is **not** the case in haskell, btw), then we get

```
f == g iff for all p : () -> A, \_ -> f (p ()) == \_ -> g (p ())

```

assuming extentionality (functions are equal if they are equal on all arguments)

```
f == g iff for all p, f (p ()) == g (p ())

```

Now the crucial observation, is that in "reasonable" categories, like $\mathrm{Set}$, morphisms $1\rightarrow A$ can be identified with *elements* of $A$ which gives

```
f == g iff for all x : A, f x == g x

```

which is obviously true in $\mathrm{Set}$ (this is exactly extentionality). Now note that "elements of an object of $\cal C$" doesn't even make *sense* in a general category, where objects are just "things" that can have morphisms into or out of them.

So the notion of well-pointedness says 2 things:

1. It's reasonable to treat morphisms $1\rightarrow A$ as "elements" of the object $A$
2. Extensionality holds.

It's reasonable to generalize this notion by replacing the terminal object $1$ by some arbitrary object $K$.

---

Now it might be useful to see a category where this **doesn't** hold (i.e. a category that is *not* well-pointed) just to see where this intuition can fail.

The simplest example I know of is the category of groups and group morphisms $\mathrm{Grp}$. Here the terminal (and initial) object $1$ is the group $\\{e\\}$ with a single element $e$, which is the unit for that group, and the operation $e\*e=e$.

Because group morphisms *must* send $e$ to $e\_G$ (the unit of $G$), there is always exactly 1 morphism $1\rightarrow G$ for any group $G$, namely, $\phi(e)=e\_G$.

But now take any 2 distinct morphisms $f,g:\mathbb{Z}\rightarrow \mathbb{Z}$, for example $f(n) = n$ and $g(n) = 2\cdot n$.

It's **not** true that $f = g$ iff $\forall p : 1\rightarrow \mathbb{Z}, f\circ p = g\circ p$. Indeed there is only one $p$, namely $\phi$ from above, and $f\circ \phi(e) = g\circ \phi(e) = e\_{\mathbb{Z}} = 0$. But $f \neq g$!

So $\mathrm{Grp}$ is not well-pointed, and it's not useful to treat morphisms $1\rightarrow G$ as points of $G$. However, in this case, there happens to be a generating object $K\neq 1$, so the generalization is useful after all! I'll leave it as an exercise to figure out what $K$ is...

---

I'll try to answer the questions more directly.

> A morphism can be thought of as a a mapping from one type to another?

Sort of. It's a good *intuition*, but you shouldn't think that it always makes sense to talk about *elements of type $A$*, unless you're working in a well-pointed category as explained above..

> Morphism `f` is equivalent to morphism `g` if and only if for the morphism type `K` to type `A`

It's *equal* rather than *equivalent* (though computer scientists tend to define equality in a much stricter sense than category theorists, e.g. by syntactic equality).

Also, it's "if and only if for **every** morphism from `K` to `A`", in general you can have many morphisms in `K -> A`

> `e` applied to `f` is equivalent to `e` applied to `g`

Composition (written $\circ$) is **not** application! I've tried to break it down above.

> The number of steps in this definition blows my mind, can anyone help me visualize the entire definition?

Category theory often offers very abstract definitions, and it's useful to work through examples and basic lemmas yourself to gain intuition.

However, if this helps, in the $\mathrm{Hask}$ category with types as objects and *total* programs of type `A -> B` as morphisms between `A` and `B`, **the unit type `()` is a generator**, as I tried to explain above.

---
Tags: category-theory
---


# Question
Title: Why is fail[1] in KMP Algorithm always 0?
I'm studying KMP Algorithm. In the failure function (or the sp table), why do we always assign the value 0 to the first element (character) of the pattern? I understand about the later elements of the pattern, as we assign the sp values according to length of correctly matched suffixes and prefixes, but why does the sp value of the first element has to be 0?

# Answer
> 2 votes
This is by definition, since:

> For each position **i** in pattern **P**, **spi** is defined as the length of longest proper suffix of **P\[1...i\]** that matches a prefix of **P**.

So, we can conclude that for **i=1** the length of longest proper suffix that matches the prefix is **0** since longest **prefix = suffix = EMPTY\_STRING.**

Visit this page for details.

# Answer
> 1 votes
At first you need to identify the idea of proper-prefix and proper-suffix.

```
s-suffix
p-prefix
pp-proper prefix
ps-proper suffix
PT-pattern

|s| <= |PT|
|p| <= |PT|
|pp| < |PT|
|ps| < |PT|

```

proper suffix is a string that is not equal to string itself.

In the KMP algorithm we need to identify longest prefix of p that is also **proper suffix** of p. So we can't take whole pattern as a proper-prefix or proper-suffix.So for a single character there is not exist proper-prefix or proper-suffix.Then sp value of the first element has to be 0.

---
Tags: algorithms, strings
---


# Question
Title: Which neural network topology is the most efficient to generate randomly shaped letters?
I have created some unique shapes, so-called "letters" for a custom alphabet, all of which can fit into 9x9 pixels. Instead of drawing countless more, I try to combine two solutions I saw in a relevant part of Reddit, and decided to let a neural network create some additional examples.

**Desconstructing the problem:** letters are formed in a graph of 25 nodes (always ordered into a 5x5 square) by spontaneously connecting **only the adjacent nodes** \- no diagonal or non-adjacent edges are present.

For a neural network input, I drew these runes into 9x9 blocks, where each row has 5 "pixels" for each nodes, and 4 more as a place for indicating connection.

Below is the current letter set, with an example of an empty graph and the only example generated by my network in the last line.

I've made a perceptron (tried 1, 2 and even 3 hidden layers) where input layer had 6 neurons, using them as a binary code (zero values mean -1 activation, and one values are the 1 activation), andthe output layer had 81 neurons. (9x9 to plot out the desired shapes)

My aim was to be able to produce additional letters by defining letters as sample and making the network to learn it. Then, I assumed that by activating the network with undefined inputs, I can find new letter shapes.

I used built-in functions froM JavaNNS and backpropagation as learning method.

Which are the parts of my topology, where I could possibly go wrong? What is the most suitable solution for this task?

# Answer
> 2 votes
I think it's unlikely you're going to get good results. Neural networks typically require a large training set. With only a few dozen or so examples, I doubt you'll have a large enough training set for this to work well.

So, what could possibly go wrong? I suspect the most likely outcome is that you'll get useless results.

That said, if you really insist on trying neural networks, you could try using a variational autoencoder. An autoencoder consists of two halves: the first half maps the input $x$ to a value $z$ in the "latent space", and the second half maps $z$ to an output $x'$. You train the autoencoder to ensure that (hopefully) $x$ and $x'$ are very similar, for all the instances $x$ in your training set. The idea is that you make the latent space much smaller than the space of inputs/outputs, and you hope this forces it to generalize.

For instance, the input might be a 40-vector $x \in \mathbb{R}^{40}$, encoded by a one-hot encoding ($x\_i=1$ means that you include a black line in the $i$th position; $x\_i=-1$ means you don't include it). The latent space might be $\mathbb{R}^2$ or $\mathbb{R}^3$ or so. You might include a few layers of a convolutional network to map from $x$ to $z$, and then the inverse architecture to map from $z$ to $x'$. Then, you could train the network using a standard loss function for variational autoencoders, along with some regularization term.

---
Tags: graphs, neural-networks, randomness, network-topology
---


# Question
Title: Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?
I've been reading Sedgewick's intro to algorithms book, and he says that *the reverse postorder of a digraph's reverse* is not the same as *the postorder of the digraph*, however in both cases it seems that we get the reverse of topological order, so at first I thought that it's the same, but then I looked on his website and he answers "False".

If you think about it, in postorder of a digraph, we first visit every child of the vertex and add it to some queue, hence since the children are visited first, we get the order which is the reverse of topological.

Why does Sedgewick say they're not the same?

# Answer
> 4 votes
I wrote a short example to test the hypothesis and found out that the reverse postorder of a reverse graph is indeed not the same as the postorder of the original graph.
Consider the following graph:

Link to source (archive of image used in original post)

Postorder for the above graph is: 0 1 3 2 4 5.

Postorder for the reverse graph is: 4 5 0 2 3 1.

Reverse Postorder for the reverse graph is: 1 3 2 0 5 4.

You are thinking on the correct lines, but what we should understand is that the postorder of a graph is not necessarily the reverse of the postorder of the reverse graph. This is because of the way we iterate over the vertices when calling the depth-first search. There could be different solutions to the same problem, given the iteration method is different.

And because of this, the reverse postorder of a digraph's reverse is not necessarily the same as the postorder of the digraph.

---
Tags: algorithms, graphs, discrete-mathematics, graph-traversal
---


# Question
Title: How to determine if prolog query will give an answer or not?
Explain what will happen if we try to evaluate the query “path(a,e).”. When the query was actually run, it kept looping.I used the following method. Is it correct?

When evaluating $path(Z,e)$, if $path(Z,e):-edge(Z,e)$ was chosen, it would have returned true since there is $edge(b,e)$. But why did the program choose the recursive rule? Or am I missing something here?

Another similar question was evaluated the same way,

# Answer
The order of clauses matters in Prolog: they are tried in order. So, the first clause is always tried first, and the second one would only be considered after the first clause fails. As you discovered, this never happens because the first gets stuck in a loop.

If Prolog used a breadth-first resolution algorithm, the clause order would not matter (but it would be far more consuming in terms of memory). Since instead SLD resolution is depth-first, the order does matter because of infinite paths which can lead to non-termination.
> 3 votes

---
Tags: prolog
---


# Question
Title: A version of the longest simple cycle problem - NP-completeness reduction proof
I've been learning about proving NP-completeness via reduction, and came across the following problem:

Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using $\ge \frac{1}{2}$ of the vertices is a NP-Complete problem.

The first part is to show that the above problem is in NP. That's simple enough, since a solution is verifiable in linear time by just traversing through the vertices to ensure they form a cycle, and that the no. of vertices in the solution set are $\ge \frac{1}{2}$ of the total no. of vertices.

As far as polynomial-time reduction...my thoughts so far are that you can probably reduce Hamiltonian circuit problem to it, but I'm unsure how to proceed. I suppose that, given the original graph $G$, you could first check whether the entire graph is a Hamiltonian circuit. Then if not, you could delete a random vertex from $G$ (there are a total of $|V|$ ways of doing this), and check for Hamiltonian circuit again...then if not, delete two vertices from G (there are $\binom{|V|}{ 2}$ ways of doing this), and check again for Hamiltonian circuit...and so on, all the way down to deleting $\frac{|V|}{2}$ vertices from $G$. But reducing it this way sounds cumbersome, and may even be an exponential-time reduction.

Any help would be appreciated.

# Answer
In order to prove NP-completeness of a given problem $\Pi$, it is enough to prove that $\Pi \in$ NP and that there exists a polynomial time reduction from any NP-complete problem $\Pi^\*$ to $\Pi$. The reduction must take instances of $\Pi^\*$ and return instances of $\Pi$, in polynomial time, such that the answer is the same in both $\Pi^\*$ and $\Pi$.

A suitable reduction from Hamiltonian Circuit has been proposed in a comment to the question: just add enough (that is $n$) isolated vertices to the graph.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions, hamiltonian-circuit
---


title: Identity of object in OOP

text:
# Question
Title: Identity of object in OOP
In the object oriented programming concepts I found the term "Identity of object". What does it mean by "Identity of object"?

# Answer
> 4 votes
Depending on the programming language, some or all objects might have reference semantics. What this means is that when you assign the object to a variable or pass it to a method, it's still the same object, not a copy. This means the object maintains *identity* independent of the values it holds.

For example, in C#, `class`es have reference semantics, while `struct`s do not. This means that for a `class C` and `struct S`:

```
C c1 = new C();
c1.Name = "c1";
C c2 = c1;
c2.Name = "c2";
WriteLine(c1.Name); // writes "c2"
WriteLine(c1.Equals(c2)); // writes "True"

S s1 = new S();
s1.Name = "s1";
S s2 = s1;
s2.Name = "s2";
WriteLine(s1.Name); // writes "s1"
WriteLine(s1.Equals(s2)); // writes "False"

```

As you can see, changing the `class` instance through one variable affects the other variable too, showing that both refer to the same object. Also, you can see that the two variables are equal. So, `class`es in C# maintain object identity.

For the `struct`, each variable is independent: changing one does not affect the other. This means that `struct`s in C# do not have object identity in C#.

Other languages behave differently. For example, Java does not have `struct`s at all, all user-defined types have reference semantics.

As another example, in C++, you can decide to use reference semantics or not on a case-by-case basis, by choosing to use pointers (or references) or not.

---

Note: `Equals()` in C# can be overridden. But since `C` or `S` do not override it, the default implementation of `Equals()` mostly behaves the way we want for both.

# Answer
> 1 votes
I think what is trying to be said here, is even if you have 2 objects that have the same state (i.e, two **different** instances of the same object that have the **same values** to their variables.

For example, let's assume we have a Java Class called Dog.

```
public class Person{
    private String breed;
    int weight;
    int height;
}

```

If I had created:

```
Dog dog1=new Dog("Lab", 15, 40);
Dog dog2=new Dog("Golden", 20, 20);
Dog dog3=new Dog("Lab", 15, 40);

```

You wouldn't say that dog1 and dog3 are the same dog, would you? Because you could identify that they are representing different dogs. However, in the sense of object representation (By its values), they are basically representing the same object.

If I had added a variable called "Name" to each dog, and giving each one a different name, we could no longer say that dog1 and dog2 have the same identity.

Hope it's all clear

---
Tags: terminology, programming-languages, object-oriented
---


# Question
Title: Terminology - What does alphanumeric order mean in relation to decimals?
It is also called Natural sort order.

> "It's hard to find information on natural sorting"-Jeff Atwood on Coding Horror.

And it seems true today as the Wikipedia entry seems pretty bare.

Definition 1: Non-numeric word-character substrings are sorted lexically, case-insensitively. Numeric substrings are sorted numerically. non words-characters, non-digits are ignored.

Definition 2: Natural sort order is an ordering of strings in alphabetical order, except that multi-digit numbers are ordered as a single character.

The main difference is that Definition 1 allows decimals while Definition 2 does not. For example I have the list \["t8.1", "t8.11", "t8.2", "t7.2", "t7.11"\].

Definition 1 would yeild: \["t7.11", "t7.2", "t8.1", "t8.11", "t8.2"\].

Definition 2 would yeild: \["t7.2", "t7.11", "t8.1", "t8.2", "t8.11"\].

Python's natsorted function was definition 1 until v4.0.0 and now uses realsorted for this behavior. Python's natsorted function currently follows definition 2.

Perl follows definition 1 (which is where I found it.

Php follows definition 2

MATLAB uses definition 2 for non-version numbers.

Dave Koelle implements definition 1 for his examples but says it's a 'glitch' and thus supporting definition 2 as correct. In most the linked code, the code treats '.' as a string but what if it was a decimal in a numeric substring? Dave Koelle notes this as a glitch by saying "There is currently a glitch when it comes to periods/decimal points - specifically, periods are treated only as strings, not as decimal points.".

To me, the word numeric would imply decimals but in practice it seems that this is not the case unless specifically noted to include decimals.

What does Alphanumberic/Natural Order Sort mean exactly without additional qualifiers? For example: In "Natural Order Sort with decimals", "with decimals" would be an additional qualifiers. Which definition is correct for "Natural Order Sort"?

Alphanumberic (Non-Decimal) vs Alphanumberic (Decimal)

# Answer
> 4 votes
Alphanumeric sort means that every character is compared according to ascii representation.
Natural sort treats consecutive digits as one chatacter, so actually compares as integer. There is no place for decimals, but when you compare two numbers in the form $X.Y \> W.Z$ it looks like decimal compare.

So what does "natural sort does not compare decimals" really mean?
The example above is just coincidence, like reading month.day as float and sorting will give good order, but adding and subtracting is not defined. Same here, "-" will not be identified as part of decimal, so comparison will be shifted. The separator might be given as anything, but will change results when inconsistent.

---
Tags: terminology, sorting
---