Can Breadth-First Search be Implemented Recursively without Data Structures? I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through a maze. Is there a way to do this just using the basic structure of recursive calls and base cases? Or will I need data structures such as queues or stacks to implement breadth-first recursion?

You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity.

Embedded-Queue Cheating

If you look at virtually any description of BFS, e.g., this one on Wikipedia, then you can see that the algorithm adds attributes to nodes. E.g., the Wikipedia version adds to each node the attributes distance and parent.

So, even if you aren't allowed to use some clearly-cut external queue data structure, you can easily embed one using node attributes:

def BFS(G, root):
    for each node in G:
        n.distance = inf
        n.parent = None
        n.next = None

    root.distance = 0
    head = tail = root

    while head is not None:
         current = tail
         tail = tail.next

         for each node adjacent to current:
             if n.distance == inf:
                  n.distance = current.distance + 1
                  n.parent = parent
                  head.next = n
                  head = head.next
                  if tail is None:
                       tail = head

Note that the above code is iterative, but it's trivial to make it recursive.

Higher-Complexity Simulation

It's possible to run BFS recursively without any data structures, but with higher complexity. DFS, as opposed to BFS, uses a stack instead of a queue, and so it can be implemented recursively.

Suppose we modify DFS so that it takes a max_depth parameter:

 MaxDepthDFS(G, s, max_depth)

It should perform DFS until it reaches the first unvisited node at max_depth level, and returns whether it indeed found such a node. Then we could write the following variation of BFS:

 def BFS(G, s):

     depth = 0
     for i = 0, ..., |V|:
         if not DFS(G, s, depth)
             depth += 1

Again, note that the above code is iterative, but it's trivial to make it recursive.

Besides such (cheap) tricks, you cannot run BFS, as it uses a queue, and not a stack. Say, to the contrary, you have a recursive function

BFSVisit(G, s, current, more)

and consider the case where $s$ has $m$ neighbors. Then at the $m$th invocation, more needs to carry $\omega(1)$ information, and thus is already a data structure.


How to do pixel array rotation whose angle not a multiple of 90 degree? It is easy to rotate pixel array if the angle is a multiple of 90 degree.

For example, (quote from Computer Graphics with OpenGL)

  We can rotate a two-dimensional object or pattern 90' counterwise by
  reversing the pixel values in each row of the array, then
  interchanging rows and columns.

But I could not understand how to rotate pixel array when the angle is not a multiple of 90 degree from the textbook.

  Each desitination pixel area is mapped onto the rotated array and the
  amout of overlap with the rotated pixel areas is calculated.

Why does this means?

Choose an origin for your coordinate system. A corner or the middle of the image is typical.
For each pixel, compute its (x, y) coordinates relative to the origin.
For each pixel, compute its new coordinates when keeping its distance from the origin the same and adjusting its angle by the desired rotation.
In a temporary buffer, copy pixels from the original image using the new coordinates.
Go over the temporary buffer, and for each pixel that wasn't assigned a color, interpolate the colors from surrounding pixels.

There are some details glossed over there, but the basic idea is sound. Coordinate transformations can be accomplished using basic trigonometry.


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.

"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.

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.
Binary search can be considered the ultimate divide & conquer: by dividing cleverly, combining is unnecessary.


Two Minimax AIs playing against each other I am trying to have my Minimax AI chess players play against each other.

I was a bit confused about an implementation detail.

Let's call black my first minimax AI chess player that plays first.

white is the other minimax AI that goes second.

My question s about the turn. Should black maximize and white minimize OR should they just try to maximize when at their respective turns, with the evaluation function flipped?

I have thought up of two ways to go about this. I have a feeling that they are doing the same thing, but just wasn't sure whether I am right or the two solutions are in fact doing something different.

First solution:

Instantiate a MinimaxAI object for black and white separately. Make sure that black's evaluation function is the opposite of white. For a simple example, the object black's evaluation function is
number of black pieces on board - number of whites on board.

The white object will have an opposite evaluation function number of white pieces on board - number of blacks on board.

Now, when each object takes turns to call the same get_next_move method, they will both be the maximizing player of the minimax algorithm.

Second solution:

Instantiate one Minimax AI object ai to be used by both the black and the white as they alternate turns. black and white will have the same evaluation function
number of white pieces on board - number of blacks on board

Assuming white always goes first in chess, when white calls ai.get_next_move with an even turn number, it will be given the maximizing player role. On the other hand, when black calls ai.get_next_move with an odd turn number, it will be given the minimizing player role.

(this is what I have so far)

I think both should result in the same behavior, but it is more of a feeling than an educated opinion. Please let me know if my feeling is actually correct or not. A semi-formal reasoning process will be welcome!

First of all, note that in chess, white players plays first and it is a quite complicated game to build a AI for. The fact it exists several "draw" situations makes the evaluation function even more complicated to build. You may consider practice on another strategy game like checkers.

The evaluation function:

Most of IA are indeed based on an evaluation function. Let's talk about 2 opponents strategy games without random like chess. if we neglect "draw" situation, either you have a possible winning strategy, that will make you win whatever plays the opponent, either your opponent has one. When a "draw" situation exists, one player has a possible win strategy or both have a draw strategy.

All possible combinations are nevertheless impossible to explore and finding this strategy is matter of heuristic. The evaluation fuction is an heuristic to judge if a state of the game is likely to lead to a win. It can be a value the player tries to maximize.

Generally symmetric evaluation function like yours (nb white-nb black) works well for 1vs1 games. If the two players are equivalent AI, you will indeed have

eval player 1 = - eval player 2

Your second proposition is indeed the same thing. As maximizing $A$ is like minimizing $-A$. But for a proper simulation, I would rather prefer your first proposition that treat the 2 IA independantly.

Now about the "draw" situations, a player that can hardly win (having negative eval) can decide to look for a draw instead of a win. His evaluation function may therefore not be symmetric anymore. In the same way, a player dominating the game may use an assymetric evaluation to prevent a draw.

Depth/Minimax:

I think you misunderstood what is the minimax strategy. When it is your turn to decide what to play, you will explore some possibilies. You can for instance try all your possible moves and chose the one maximizing the evaluation function. This is a depth 1 exploration.

You may also try all your moves with all the moves the opponent may do on his next turn. This is depth 2 exploration. But in all these combinations, you have no information on what your opponent will play. The minimax strategy is to assume he will play the move maximizing his evaluation function, therefore minimizing yours.

For instance, let say you have 3 possible moves $M_i$  Each leads to several possible subsequent moves $M_{i,j}$ for your opponent. $E_k$ = $evaluation(M_k)$:

$M_1$ : $E_1 = 3$,  $E_{1,j} = [4, 1]$
$M_2$ : $E_2 = 5$,  $E_{1,j} = [7, 2, -1]$
$M_3$ : $E_3 = -1$,  $E_{1,j} = [-3, 0]$

in $depth 1$, you pick $argmax_i(E_i)$, that is to say $M_2$

in $depth 2$, you pick $argmax_i(min_j(E_{i,j}))$, that is to say $M_1$

You can of course go even deeper, applying minimax strategy on each opponent action. The deeper you go, the better is the heuristic approximation to find the best strategy. But the number of states to explore generally grows as a power law of the depth ($O(a^{depth})$). Thus, all the difficulty is to focus computation on interesting branch. You can have a look to some methods:

Monte Carlo Tree Search
Pruning


When states that are not accepting states become accepting states in NFA, what happens? It is known that when NFA's accepting states are swapped with rejecting states, the recognized language is not complement of the original language. For some language, it may be the case that some strings that were recognized in the original NFA may still be recognized in the state-swapped NFA.

My question is, is there a language $L$ that in the original NFA a string is not recognized(rejected), but in the NFA where accepting states become rejecting states and rejecting states become accepting states the string is also rejected?

It depends on whether the NFA contains a path for every possible word.

If there is an input word where there is no path through the NFA at all labelled with that word, then yes, this can happen.  See Hendrik Jan's answer.

On the other hand, it is often assumed that the automaton is complete: that for every possible input word, there is at least one path in the automaton labelled with that word.  (For instance, this can be arranged by ensuring that for every state $q$ and every possible input letter $x \in \Sigma$, there is a transition out of $q$ labelled with $x$.)  If you assume the automaton is complete, the answer is: No.

In particular, if the automaton is complete, the answer is: No, the magic of nondeterminism is that if there's any valid computation path that will end in an accept state, the string is accepted. In this case, all possible computation paths in the original NFA led to rejection (had there been any valid path the string would be accepted, so they must all reject), so in the inverted NFA, they all lead to acceptance.


Problem in computational complexity (superior class) Say that a class $C_1$ is superior to a class $C_2$ if there is a machine $M_1$ in class $C_1$ such that for every machine $M_2$ in class $C_2$ and every large enough $n$, there is an input of size between $n$ and $n^2$ on which $M_1$ and $M_2$ answer differently.

Is DTIME($n^{1.1}$) superior to DTIME($n$)?

Is NTIME($n^{1.1}$) superior to NTIME($n$)?

This is an exercise from book Computational Complexity: A Modern Approach. But I have no idea to handle it. Does it have relationship with theorem that DTIME$(n)$ $\subsetneqq$ DTIME($n^{1.5}$)?

The proof of the time hierarchy theorems can be paraphrased like this. We want to show that $\mathsf{X} \subsetneq \mathsf{Y}$ for appropriate $\mathsf{X},\mathsf{Y}$. The idea is to construct a diagonalizing machine $M \in \mathsf{Y}$ (slight abuse of notation here) whose language is different from all languages in $\mathsf{X}$. On input $x$, the machine $M$ runs $x$ on $x$ up to some specified time bound, and then answers the opposite. If the simulation is efficient enough, $M \in \mathsf{Y}$.

Your question is very similar. Go over the proof of the time hierarchy theorems, and check whether the diagonalizing machines there fit your bill.


Why do people insist to use the term "multilayer perceptron" instead of "multilayer perceptron network"? The perceptron model describes a linear classifier. Often people use the term "multilayer perceptron" to describe a feedforward neural network that uses perceptrons. This terminology simply sounds wrong to me, since this type of network does not necessarily behave like a perceptron; that is to say - it may act as a nonlinear classifier, which is clearly not a perceptron; it is not a single perceptron containing multiple layers, but a multilayer network containing perceptrons.

Wouldn't it be proper to use the term "multilayer perceptron network" to describe this type of network instead? I can't seem to find a reliable reference that discusses this issue, but there is a section about it in the corresponding Wikipedia article.

Personally, I've seen "multilayer neural network" used more commonly than "multilayer perceptron".  If you like the former term better, use it.

That said: multilayer perceptron is an accepted term of art.  Your criticism is not unreasonable, but it is what it is.  Language exists to help us communicate... so pick terms that will help you communicate your intended meaning to your intended audience as effectively as possible.

If it helps you come to some kind of acceptance for this usage, you can think of "multilayer perceptron" as a single term that has a particular definition: don't think of "multilayer" as an adjective modifying "perceptron", but thik of "multilayer perceptron" is a single atomic phrase that has a particular definition.  For example, some mathematics textbooks define the term "ring" in a way such that a "commutative ring" is not actually a "ring"; that's just how it is, so just go with it and don't let it throw you.  As another example, an "algebraic integer" is not an "integer"; it's a complex number with some special properties.  This kind of situation appears all over the place in mathematics.

Ultimately, it's just a convention.  And that's ultimately what language boils down to: a convention.  These conventions sometimes can look a bit inconsistent or "improper", but if they are widely understood, then they still serve the ultimate goal, of clear and concise communication among folks who are knowledgeable in the field.

Bottom line: don't let a sense of what is "proper" overcome the real goal.  Keep in mind the real purpose of these kinds of terms: namely, effective and efficient communication.


Is an irregular language concatenated with a language with which it has no common symbols irregular? Here's an example of what I'm talking about. Suppose I have a languages
$$
L_{1} = \{a^ib^i \mid  i>0\},\\
L_{2} = \{c^i \mid i>0\}
$$

and
$$
L_{1}L_{2} = \{a^ib^ic^i \mid i>0\}
$$

Is it true that if $L_{1}$ is irregular and $L_{1}$ has no common symbols with $L_{2}$, then $L_{1}L_{2}$ is irregular? How would you prove this?

First, your $L1L2$ is wrong. $$L1L2 = \{a^ib^ic^j\ | \ i>0, j>0\}$$
Your conclusion is right, $L1L2$ is irregular(as long as $L2\neq\phi$, otherwise  $L1L2=\phi$ is clearly regular). This can be proved using Myhill–Nerode theorem.

Suppose $X$,$Y$ are any 2 different equivalence classes of $R_{L1}$, $x\in X, y\in Y$, then there exists string $z$ such that $xz \in L1$ while $yz \notin L1$.

If $L2=\{\epsilon\}$, then $L1L2$=$L1$ is irregular. Otherwise, take any string $w\in L2, w \neq \epsilon$, then $xzw \in L1L2$, but $yzw\notin L1L2$
(consider that, due to no common symbol, no suffix of $yzw$ longer  than $|w|$ in L2, and no prefix of $yzw$ shorter than $|yz|$ in $L1$).

This shows that $x$,$y$ belongs to different equivalence classes of $R_{L1L2}$, too. ie. there must be at least the same number of equivalence classes in $R_{L1L2}$ as in $R_{L1}$

From Myhill–Nerode theorem, $L1$ has infinite number of equivalence classes. Thus $L1L2$ also has infinite number of equivalence classes, which means $L1L2$ is irregular also.


why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge? I'm trying to understand a poly-time reduction proof from dominating set to vertex cover. If I'm understanding correctly, it goes something like this: suppose we have a vertex cover of size $k$ in graph $G$. Then we construct a new graph $G^\prime$ with the same vertices and edges, except for every edge $(u,v)$ we add a new vertex $w_{uv}$, which has an edge to both $u$ and $v$.
Then, here's the oddest part: it says that if there's some dominating set in $G^\prime$ that includes any of the $w_{uv}$, then we can construct another dominating set, that's at least as good, by replacing that $w_{uv}$ with either $u$ or $v$. That is, we end up not including any of the $w_{uv}$ at all, and thus the dominating set in $G^\prime$ is the vertex cover in $G$ plus any remaining isolated vertices not in the cover.
This raises the obvious question: what's the point of $w_{uv}$ if we're gonna include them and then argue that the original $u$ and $v$ can render them obsolete anyway? The proof in the link above conspicuously does not explain this. If the dominating set of $G^\prime$ doesn't even include $w_{uv}$, and the vertex cover dominates just fine (except for the isolated vertices, which are trivial and have nothing to do with $w_{uv}$), why even add the $w_{uv}$? Why does the proof fail if we never introduce the $w_{uv}$ at all?

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


Can Inverse of weights(1/weight,not negation) be used to find the longest path between two points by using dijkstra's algorithm? Considering that there no cycles in the graph.

I have seen the posts where the negation of the weights is suggested and to use Bellman-ford. But I was wondering if the inverse is possible.

Hint: take a graph with all weights equal 1.


Possible to connect arbitrary number of dots without intersections? A (now closed) question on SO made me think about the following problem:

  Given an arbirtary number of points (2D), draw a path that consists of
  straight lines between points, visits each point exactly once and does
  not intersect with itself.

I came to the conclusion that this is easy if I can chose starting and ending point:

sort points by their x coordinate
use point with mininmal x coordinate as starting point
connect remaining points in left-to-right order

If there are multiple points with the same x value, start with the point with minimal y value and go bottom-up. This way, no intersections can occur.

Now my question is: is this still possible if start and end point are fixed?
I assume that there are well known algorithms for this problem, but my search didn't reveal any useful results.

As @hyde points out, there is no solution if more than two points are on a straight line and start/end points are not the outermost points.

It is (almost always) possible. Let the two points be $p_1=(x_1,y_1)$ and $p_2(x_2,y_2)$. Wlog, assume that $x_1<x_2$. Denote by $q_1$ ($q_2$) the point with smallest (largest) $x$-value greater (smaller) then $x_1$ ($x_2$) (and smallest (largest) $y$, if there are multiple candidates). Then you can do the following:

Determine the set $S_1$ of all the points with $x\leq x_1$.
If $|S_1|=1$, connect $x_1$ and $q_1$.
If $|S_1| > 1$ and all the points in $S_1$ are on the same straight line:

If all points outside of $S_1$ are on the same straight line, there is no solution
Otherwise denote by $r_1$ the point with smallest $x$-coordiate not on the straight line. (If there are multiple such points choose the one with smallest $y$-coordinate.)
Connect the points in $S_1$ starting with $x_1$. Connect the last of these points with $r_1$ and (if $r_1 \ne q_1$) connect $r_1$ with $q_1$.

If $|S_1| > 1$ and the points are not all on one straight line, determine the convex hull of $S_1$.
At least one of the neighbours $n_1$ of $p_1$ on the convex hull can be reached from $q_1$ without intersecting the convex hull.

Draw a (reverse) path from $q_1$ to $n_1$ and then along the convex hull to the point with smallest $x$. Continue in left-to-right-order (skipping points already included) until $p_1$.

Analoguously connect the points with $x\geq x_2$.
Connect the points with $x_1<x<x_2$ (i.e. from $q_1$ to $q_2$) in left-to-right-order (ignoring $r_1$ resp. $r_2$, if applicable).


What is the Number of Possible Nonequivalent Propositions with $P_1, P_2, P_3$ Using $\iff$ Operator? A multiple choice question asks this:

Number of nonequivalent propositions that only consist of $P_1, P_2, P_3$ and use the $\iff$ logical operator is?$$A)7\text{ }B)8\text{ }C)1\text{ }D)16$$

I am really uncertain about what the question is asking. Is it asking me to find all the possible propositions using the $P_1, P_2, P_3$ terms and logical operators (e.g. $\land, \lor, \neg$...) and see which ones have the same value?

You just need to use $P_1$, $P_2$, $P_3$ and $\Leftrightarrow$ symbols, for example $P_2$ is a formula, $(P_1 \Leftrightarrow P_3) \Leftrightarrow P_2$ is a formula. As stated in the question, you must not use $\vee$, $\wedge$ or $\neg$.
You need to find the number of non-equivalent formulae. For example, $P_1 \Leftrightarrow P_2$ is equivalent to $P_2\Leftrightarrow P_1$, but $P_1\Leftrightarrow P_2$ is not equivalent to $P_1 \Leftrightarrow P_3$.


Gyorgy E. ReveszExercise 1.1: Show the grammar $G$ generates the language $L$ The exercise says

"Show that the grammar $G = \langle\{S\}, \{a, b\}, S, \{S \to \lambda, S \to aSb\}\rangle$
generates the language $L = \{a^i b^i \mid i = 0, 1, 2, \ldots\}$."

Now, I'm new to this subject although I'm familiar with the theory of Turing machines and automata. I'm teaching myself (not in a class, completely independently) from scratch. Please go easy on me.

Now, two questions:

(1) I suspect the way to do this proof is by induction on $i$, which is to say induction on the iterations of letters in the alphabet or the length of the word formed by iterations of $a, b$. Is this assumption correct?

(2) If the assumption in (1) is not correct, what is the correct strategy?

Generally speaking, you need to do two things:

Prove that every word generated by $G$ is in $L$.
Prove that every word in $L$ can be generated by $G$.

Hints for (1): Prove by induction on the length of the derivation.

Hints for (2): Prove by induction on $i$.


Is it a problem that "successful" machine learning algorithms have large VC dimension? In my limited exposure, it appears that "successful" machine learning algorithms tend to have very large VC dimension.  For example, XGBoost is famous for being used to win the Higgs Boson Kaggle competition, and Deep Learning has made many headlines.  Both algorithm paradigms are based on models that can be scaled to shatter any dataset, and can incorporate boosting which increases VC dimension.

According to VC dimension analysis, a large dimension is supposedly a bad thing, it allows models to overfit or memorize the data instead of generalize.  For example, if my model shatters every dataset, e.g. a rectangle around every point, then it cannot be extrapolated outside the dataset.  My grid of rectangles tells me nothing about points outside the grid.  The larger the VC dimension, the more likely the model will shatter a dataset instead of generalizing, and thus once exposed to new data outside the training dataset, it will perform badly.

Back to the original point, many of the most "successful" machine learning algorithms have this common trend of having a large VC dimension.  Yet, according to machine learning theory this is a bad thing.

So, I am left confused with this significant discrepancy between theory and practice.  I know the saying "In theory there is no difference between theory and practice, in practice there is" and practitioners tend to brush aside such discrepancies if they get the results they want.  A similar question was asked regarding Deep Learning, and the consensus was that it did have large VC dimension, but that doesn't matter because it scores very well on benchmark datasets.

But, it is also said "there is nothing more practical than good theory."  Which suggests such a large discrepancy has a significance for practical application.

My question then, is it true that the only thing that really matters is low error scores on test datasets, even when the theoretical analysis of the algorithm says it will generalize poorly?  Is overfitting and memorizing instead of generalizing not that big of a deal in practice if we have hundreds of billions of samples?  Is there a known reason why the theory does not matter in practice?  What is the point of the theory, then?

Or, are there important cases where a very large VC dimension can come back to bite me, even if my model has great scores?  In what real world scenario is low error and large VCD a bad thing, even with hundreds of billions of samples in the training data?

When left with a discrepancy between theory and data, data is king.  Theory is intended to be predictive -- to make predictions about the world -- but when it fails to predict what we actually observe and experience, when its predictions disagree with our experience, then there is obviously something lacking in the theory.

In this case, VC theory just isn't adequate to understand modern practice in machine learning.

Unfortunately, VC theory ignores methods like regularization.  Regularization is widely used in practice, so that's a pretty important gap in VC theory.  VC theory counts the number (size, dimension) of possible models, and treats all of them as "equally valid/likely".

When we train a model with regularization, we depart from that paradigm.  Regularization implicitly encodes the assumption that "all else being equal, simpler models (explanations) are more likely to be correct".  In other words, regularization is essentially an application of Occam's Razor.  In effect, regularization encodes some kind of prior on the distribution of likely models: not all models are equally likely; simpler models are more likely to be right.  Classical VC theory doesn't take that into account, and thus can't make useful predictions about the behavior of machine learning methods that use regularization.

Practitioners aren't "brushing aside" the theory.  Rather, VC dimension simply doesn't seem to be super-relevant to practice.  It is too limited.

It's still an open question to understand why techniques like deep learning work so well.  VC dimension was an early attempt to understand machine learning -- a powerful, beautiful, valiant attempt, one that may still be of some interest -- but ultimately one that doesn't seem to give us the whole picture, perhaps partly because it does not account for things like regularization and our priors on the model.


Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations So I was thinking after discussing with my friend the other day, how would I use something like breadth-first or depth-first search to find the fastest time to go from one station to another station if there are a number of different train lines in a subway system. They may cross over each other, maybe multiple times even.

Train line in this case means a train that goes from a starting station to a ending station, with many station stops on the way, where certain station stops may give the option for the rider to swap to another "line" that also has its starting and stoping station. A simple example is a two-line subway system like so:

o : station   - : track

                     Line 2
                     START
                       |
                       o
                       |
Line 1 START o -- o -- o -- o -- o -- o END
                       |
                      END

I live in Taipei, Taiwan, so you may reference the MRT train map there for reference but it may look fairly complicated. I was looking for tips for a simpler start and ways to work out a solution to a smaller problem first, but the MRT system is my friend and I's target goal.

What I have though of so far

Have an array that holds each stop name on along with the time it
takes for previous stop to reach this stop represent a single train
line, with each connection to another train line being a nested array
at that item.
Figure out how to tell the algorithm to look through each route to find the destination stop, adding the time taken along the way
comparing to find the shortest time.

Things to Consider

The time between each station is known to us. But for the purpose of this question just assume its 5 minutes between each station.
A train line has a starting stop and a ending stop, but on the way it may stop on a stop that connects to any other train line.
Any connection to another train line may connect to another line - but access to this third line may be reached by taking a further more complicated route by switching train lines. Meaning if I try out all possibilities it may take looping routes and test forever.

Its possible to take a transfer from one line to another, and go either left or right on the new line, i.e. the trains are not one-way.

So how is it possible to

Avoid our algorithm making loops, e.g.:

If line 1 connects to line 2 on its third stop, and that connects to a third line, and then back to line 1 later on down line 3. Then if we were to try find the shortest way to go from a stop in line 1 to another stop in line 1, the algorithm may test going from line 1 to line 2 taking the connection then to line 3 back to line 1 and back around.

And also, how do we make it decide where to make the turns, and what is a better way to represent this problem and find the shortest time?

Transform your input to a graph in which each vertex represents a stop on a line. If a stop is shared by multiple lines, then add one copy of the vertex per line and a new super-vertex connected to all such copies with edges of weight 2.5 (so there is a path of length 5 between any two of these stops). Add edges between consecutive stops of the same line with weights matching the travel times.

Use Dijkstra's algorithm to find the shortest path between the starting stop and the last stop.

The time required is $O(n\log n)$ where $n$ is the overall number of (not necessarily distinct) stops across the different lines. This is because is possible to assign edges to vertices so that: 1) each edge is assigned to a "stop" vertex, and 2) each "stop" vertex has at most $2$ edges assigned (i.e., the one towards the "next" stop w.r.t. an arbitrary direction of the line the vertex belongs to, if any, and possibly the one to a super-vertex), showing that the number of edges is at most $2n$.

EDIT:

Here is the graph obtained by applying the above transformation to the example in the question.
The edges of the horizontal line are in red, those of the vertical line are in blue. All the vertices representing stops on a specific line are white, while the only super-vertex is in black. Black edges have a weight of $2.5$ each (not shown). The tree vertices in the gray circle together represent the stop at the intersection of the horizontal line and vertical line.


Can I compute closest split pair of points where distance is strictly less than delta I've been studying the closest pair algorithm lately and I found this to be an extremely good and intuitive resource: http://serverbob.3x.ro/IA/DDU0221.html. It is also explained in section 33.4, "Finding the closest pair of points" of introduction to algorithms, third edition  by CLRS.

I understand why I'd need 7 comparisons for a non pairwise distinct set of points and only 5 otherwise (33.4-2). Both of them follow from the fact that I can fit only 4 points, at least Delta away from each other, on a Delta x Delta box.

What I've been wondering though, is if I could trim the number of comparisons down to 3 if I included only points strictly less than Delta away from the middle line, in the middle Delta x 2 Delta strip. The reasoning is that I already have a pair of points Delta away from each other from the recursive calls, I only need points less than Delta and I can only fit 2 points Delta away from each other AND less than Delta from the middle line on each side.

Have I missed something or can I really just compare the 3 following points of every point in a middle strip only containing points strictly less than Delta from the center?

Edit:
I have started a bounty for a very similar question on stack overflow also and we have come up with a very interesting discussion there. So I'm linking it here. We've also started a very insightful chat here.

Yes, as you have observed, we can just compute pair of points whose distances are strictly less than $\delta$ in the "combine" step of the "divide-conquer-combine" algorithm, where we examine the minimal distance between the points to the left and the points to the right.

However, it is not enough to just compute the next 3 points.

The above graph, taken from CLRS, illustrates the original argument for 7 in the case of non-pairwise distinct points and for 5 in the case of pairwise distinct points. For the sake of clearer explanation, assume the central line $l$ is the vertical axis and $\delta=\delta_L=\delta_R=1000$. Let the strip consist of the area between the line $x=1000$ and $x=1000$, excluding those two lines. This strip contains only the points that are strictly less than 1000 away from the central line $l$. Suppose all distinct points in the strip in the ascending order of vertical coordinate are $s_0, s_1, s_2, s_3, s_4$.

Suppose we have verified that $d(s_0,s_i)\ge1000$ for $i=1,2,3$. Can we conclude that there is no point $s$ such that $d(s_0,s)<1000$?

No. It might happen that
$$\begin{align}\\
s_0&=(79,0)\\
s_1&=(-921,1)\\
s_2&=(999,500)\\
s_3&=(-999, 998)\\
s_4&=(79, 999)
\end{align}$$

Note that $d(s_0, s_4)= 999<1000$. In fact, $d(s_i,s_j)\gt1000$ for all $i$ and $j$ except $d(s_0, s_4)$.
$$\begin{align}
d(s_0, s_1)&=\sqrt{1000001}  \\
d(s_0, s_2)&=\sqrt{1096400}  \\
d(s_0, s_3)&=\sqrt{2158088}  \\
d(s_0, s_4)&=\sqrt{998001}  \\
d(s_1, s_2)&=\sqrt{3935401}  \\
d(s_1, s_3)&=\sqrt{1000093}  \\
d(s_1, s_4)&=\sqrt{1996004}  \\
d(s_2, s_3)&=\sqrt{4240008}  \\
d(s_2, s_4)&=\sqrt{1095401}  \\
d(s_3, s_4)&=\sqrt{1162085}  \\
\end{align}$$
So if we only compute the distance with the next 3 points, we will not find that shortest edge from $s_0$ to $s_4$ at the end of the algorithm.

The above counterexample shows that it is not sufficient to just compare 3 following points of every point in a middle strip only containing points strictly less than $\delta$ from the center line, even if we assume that all points are distinct.


Initial States in Moore Machine? I went through the rules of Moore and Mealy Machine or FA. I read that both could have one initial state and no final state.

If Moore Machine has one initial state then there is a problem for converting those Mealy Machines into Moore Machines in which inputs coming towards the initial state give different outputs. In this case we will get a Moore Machine which will have many initial states.

For example: if we convert the following Mealy Machine then we will get a Moore Machine with two initial states!

Is there any way to convert such Mealy Machines into single initial state Moore Machines?

The tutorial that you link to does not explain what "translating" between Mealy and Moore machines actually means, which is however crucial. In every step of its computation, a Mealy machine first reads the next input character, and then produces the next output character while transitioning to the next state. A Moore machine, one the other hand, first produces the next output character and then reads the next input, after which it transitions to the next state.

These two modes of computation are different and hence there is no translation between them that does not alter the semantics of the machine. When you translate from Moore to Mealy, you can build a machine that ignores the next input, produces the next output, and only then takes input and state into account to transition to the next state. The resulting Mealy machine in a sense ignores the next input until it wrote the next output.

When you translate from Mealy to Moore, you have a problem: to compute the next output, you need the next input....which is only available to the machine after producing the next output. What you can do during the translation is however to build a Moore machine that produces its output delayed by one step. This requires you to store the last output in the state component, which blows up the automaton. Whether the resulting Moore machine is good for anything practical is a different question. Even with this semantics-altering translation, there is still the problem that the Moore machine needs to give some initial output, which needs to be defined. This could be an arbitrary one or a designated "no data" output character. This seems to be the choice of your tutorial - rather than having more than one initial state, you declare the one to be initial that is labeled by the output character representing ``nothing''.

Having to choose some initial output shows you that this is no one-to-one translation.


Binomial trees in binomial heap with 27 elements How many binomial trees are in a binomial heap with 27 elements and how would you find this number?

A binomial heap stores a collection of binomial trees whose sizes are powers of two and such that there is at most one tree for each size.

How can you write 27 as a sum of distinct powers of 2? How many powers do you need?


How does recursion works when there are 2 or more consecutive recursive calls? I was learning about recursion and i came across the following pseudo code for quicksort.

QUICKSORT(A,p,r)
1   if p < r
2      then q := PARTITION(A,p,r)
3           QUICKSORT(A,p,q-1)
4           QUICKSORT(A,q+1,r)

In this code there are two consecutive statements that recursively call quicksort function. It confuses me. I want to know how these statements gets executed. Does the partition of left half of the array happens recursively or does both left and right of the array gets partitioned at the same time?

Just like any other two consecutive statements in an ordinary programming language, they're executed one after the other.

However, since the two recursive calls operate on disjoint sections of the array, you could, in principal, execute them in parallel.


Does exist any horn formula that is equisatisfiable to the clause that is disjunction of two literals? Does also exist equivalent? I just and simply want to know if whether or not exist any horn formula that is equisatisfiable to $(p\lor q)$. I would also be interested to know if there also exists equivalent.

The answer is no: this is not possible. I assume a horn formula is a CNF formula with at most one positive literal (=nonnegated variable) in each clause. Now, for the sake of contradiction, suppose we have a horn formula $\phi$ that is equisatisfiable to $p\vee q$. Since $\phi$ is a horn formula, each clause in it contains a negative literal OR there is a clause consisting of only one (positive) variable. If the latter is the case, that positive variable must be a helper variable, since if it were p, it would mean that p must be necessarily true for satisfaction, which is not the case in "$p\vee q$" (same argument for q). So in this case, we derive an equisatisfiable formula by replacing that variable with true. In this new formula, we have one less clause that contains only a positive variable. We repeat this process until this is no longer the case, until we have a formula that has a negative literal in each clause. But such a formula is satisfiable by setting every variable to false. However, that's not the case in $p\vee q$, hence the contradiction.


How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem? For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$.

I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I can't find a way to define an algorithm that halts only if $w \in L$. Either way:

if $w \in L$ I would have to find at least 42 words that are in $T(M_w)$, which might be undecidable for certain languages.
if $w \notin L$ then $M_w$ would accept only 41 or less words. Then we do know, that the language $T(M_w)$ is regular, but still we can't test if the language is regular or not.

Simply trying random words until we have at least 42 doesn't work as for some words the TM will not halt.

Is there any idea I could try? Or in other words: how would one prove $L \leq H_0 $?

This answer assumes that $T(w)$ is the set of inputs that the Turing machine $M_w$ halts on.

Given a Turing machine $M$, construct a new Turing machine which runs $M$ in parallel on all inputs. Once $M$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.)

In order to run $M$ on infinitely many inputs, you do the following:

Start with some enumeration $x_1,x_2,\ldots$ of all inputs.
Run $M$ for one step on $x_1$.
Run $M$ for one step on $x_1,x_2$.
Run $M$ for one step on $x_1,x_2,x_3$.
And so on.

This is known as dovetailing.

The argument above reduces $L$ to the halting problem, and so shows that $L$ is r.e. We can also reduce the halting problem to $L$, hence showing that $L$ is r.e.-complete. To do this, suppose that we are given a Turing machine $M$ as input to $H_0$. We construct a new Turing machine which:

On input $\epsilon$, transfers control to $M$.
On input $0,00,\ldots,0^{41}$, halts.
On all other inputs, doesn't halt.

The new machine belongs to $L$ iff the original one belongs to $H_0$.


difference between multilayer perceptron and linear regression What is the  difference between multilayer perceptron and linear regression classifier.
I am trying to learn a model with numerical attributes, and predict a numerical value.

Thanks

If you have a neural network (aka a multilayer perceptron) with only an input and an output layer and with no activation function, that is exactly equal to linear regression. In your case, each attribute corresponds to an input node and your network has one output node, which represents the target value you're trying to predict.

However, most neural networks are more complex. Usually, the input nodes first feed into a layer of hidden units. These hidden units take the sum of their weighted inputs, as the output node did in the simple network, but apply an activation function to them (usually a sigmoid function which compresses the domain $(-\infty, \infty)$ to $(-1, 1)$). The output nodes are each a linear combination of all the nodes in the hidden layer. These days there are even effective methods to train networks with many hidden layer each feeding into the next.

Practically, there are two important differences:

Linear regression (and the linear network with no hidden layers) have a closed form solution. You can compute the optimal model directly and efficiently. Once you add an activation function, and possibly hidden layers, you cannot compute an optimal model directly anymore, and you're forced to use an iterative solution: an algorithm that goes through steps, usually improving the model with each step. There are no guarantees that the process will converge, or that you'll find the best model. It's also a lot slower than the direct solution.
The flipside is that with a hidden layer and activation function, you have a much more powerful model. You can even show that so long as you have enough nodes in your hidden layer, you can approximate any continuous function with an abritrarily small error. Linear regression and the simple neural network can only model linear functions. You can however use a design matrix (or basis functions, in neural network terminology) to increase the power of linear regression without losing the closed form solution.

Glossary

Neural Network: A collection of nodes and arrows. Computation flows through the network along the arrows. The value of node $n$ is determined by the nodes which have arrows from them to $n$. Each arrow contains a weight which determines the strength of the connection.
Activation function: A node in a neural network works as follows: it takes all the values of all nodes which are connected to it by an arrow, multiplies all these by their respective weights, and then sums them. It then passes this sum through an activation function to ensure that its output stays in the range $(-1, 1)$. Common activations functions are the logistic function and tanh.
Hidden layers: The nodes and arrows in a neural network can be arranged in any way, but the most common arrangement is in layers. This is called a multilayer perceptron. It groups the nodes into layers. Each node in layer $i$ takes all nodes in layer $i-1$ as input. The nodes in the first layer are the input nodes and the nodes in the last layer are the output nodes. The rest of the layers are called hidden layers.

The following image comes from this tutorial.


Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree I'm trying to reproduce the synthetic networks (graphs) described in some papers.

The topic is the same as a previous question of mine, but with a different focus.

It is stated that the Erdos-Renyi model was used to create $2$ networks with average degrees $\langle k_a \rangle$ and $\langle k_b \rangle$.

In the first paper, the average degree is $k = 4$ , while the number of nodes $n$ is 50000.

In the second paper the average degree is not called $k$, but it's stated that the mean degree is $1.999$ for $n = 200$ (in Fig. 2), while it is $2.45$ for $n = 4000 $ and $ n = 6000$ (in Fig. 7).

I looked for libraries implementing the Erdos-Renyi algorithm and they seem to require different parameters than average degree. One is NetworkX, another is igraph. They work in similar ways and ask for:

$n$ - number of nodes
$0 \leq p \leq 1$ - the probability for drawing an edge between two arbitrary vertices
$m$ - the number of edges in the graph (in alternative to $p$, only in igraph)

How can I calculate the settings to generate a graph with the same average degree as the ones described in the papers?

Here are the references:

Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
Small Cluster in Cyber Physical Systems, Huang et al. 2014
Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used generating functions to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.

Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the expected average degree is $np$. The actual average degree has normal distribution with mean $np$ and standard deviation $\sqrt{2(1-\tfrac{1}{n})p(1-p)}$, so it is pretty close to $np$ with high probability.

When $p=c/n$ for fixed $c$, the degree of a single vertex has roughly Poisson distribution (with mean $c$); formally, as $n\to\infty$ the distribution tends to Poisson. In practice, this means that for "small" $c$ and "large" $n$, the degree will be Poisson. Furthermore, while there is some dependency between vertices, we still expect the entire empirical degree distribution to be close to the same Poisson distribution (i.e., we expect the fraction of coordinates having degree $d$ to be roughly $e^{-c} c^d/d!$); this is probably proved formally in the literature.

When $p$ is constant, the degree of a single vertex has roughly Gaussian distribution, and it is probably the case that the joint distribution is also close to the appropriate multivariate Gaussian.


The given answer can't be correct: Just from the last digits it claims that the result of subtracting an odd number from an even number is even.

However, you also made a mistake in your calculation: The 2's complement should be 0111 0001 1111.


Is a^mb^n where m=n^2 a CFL? Is $a^mb^n$ where $m=n^2$ a CFL?

I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right?

On the other hand I have this doubt, do we know the number of $b's$ we are provided with, if not how can we pop $n$ number of $a's$ for each $b$? So this case doesn't make it a CFL right?

Which of these 2 cases are applicable? Are we always aware of the number of $b's$ we have? Then shouldn't it be a regular language?

This is not a context-free language, as an immediate consequence of Parikh's theorem.

In terms of pushdown automata, there is no way for a PDA to keep track of the number of $b$'s in the string in a way it can access repeatedly while reading (or popping) the $a$ part of the string. This is an essential feature of context-free languages; it is the same reason why languages such as $\{a^n b^n c^n d^n | n > 0\}$ are not context-free.

For more examples, check out our reference question on proving languages are not context-free.


Understanding PDA and Equivalence of PDA and CFG When we wanted to construct a PDA for $0^n1^n$ the idea was to put all the zeroes (which is a part of the input string) to the stack associated with the PDA, and then pop each of them when we get a $1$ from the latter part of the input.

But when we try to prove that, we can create a PDA for a given CFG we put nonterminals and terminals in the stack and try to match it with input and pop from the stack.

Why do we do something like this? For a problem, we push some part of my input to the stack and match rest of them, and for some problems do not push any input symbol rather only use inputs to compare?

Maybe I am missing some intuitive part of it.

Your question is, in essence,

  Why does the proof that every context-free grammar can be converted to an equivalent PDA proceed in a particular way rather than in another way?

It's hard to answer such a question unless it gets more specific. For example, you can ask why the resulting PDA have to invoke nondeterminism. The answer is that some context-free languages cannot be accepted by a DPDA. Indeed, while this particular proof uses PDAs acting in a certain way, another proof might use PDAs acting in a different way.

One alternative such proof uses the Chomsky–Schützenberger representation theorem. The theorem states that every context-free language can be realized as
$$ h(D \cap R), $$
where $D$ is a Dyck language (the language of all correctly nested strings of parentheses of some fixed number of sorts), $R$ is a regular language, and $h$ is a homomorphism. This theorem, which can be proved directly using context-free grammars (see, for example, Context-free languages and pushdown automata by Autebert, Berstel and Boasson, from the Handbook of Formal Languages), allows to convert a context-free grammar to a PDA which is more like the one for $0^n 1^n$, along the following lines:

Start with a PDA for $D$. This is a PDA that pushes whenever encountering a left parenthesis, and pops whenever encountering a right parenthesis (checking that the two parentheses, the one on the stack and the one being read, have the same type).
Construct a DFA/NFA for $R$, and use the product construction to construct a PDA for $D \cap R$.
Construct a PDA for $h(D \cap R)$ by replacing each transition on $\sigma$ to a transition on $h(\sigma)$.

If you apply this construction to $0^n1^n$ (which you can realize as $D \cap 0^*1^*$, where $D$ is the Dyck language with a single type of left parenthesis $0$ and the corresponding right parenthesis $1$) then you get a PDA which is remarkably similar to the one you describe.


Whats the best way to sort a dataset into groups by using a facial recognition algorithm that compares only 2 images at a time? I have a facial recognition algorithm that compares two images A and B and returns the likelihood that they match.

I also have 50,000 images, and I would like to sort these images into groups.

Here's the immediate way I thought of to do this:

Start with image 0, compare it to all 49,999 images. Store the similarities in an array
Move on to image 1, compare it to 49,998 images (skip img_0). Store the similarities in an array

At the end of it all I'm left with a verified_listof images that matched, and I can basically feed them into a network to combine them, ie if I have a verified_list like so:

[[1,2,3],[2,5,6],[8,9]] (verified_list is the same length as the number of images, so verified_list[1] contains references all the images that image_1 matches with)

then the network graph combines them into:

[[1,2,3,5,6], [8,9]

Indicating I have two groups.

Obviously this is a huge amount of processing, I think it equates to: nCr(50000,2), some huge number!

Is there a faster way to sort my dataset into groups?

So it appears you actually have vectors over $\mathbb{R}^n$, one vector per face, and you want to group the vectors, using $L_2$ distance (Euclidean distance) to measure similarity.

There are a number of techniques for this.  See data structures for nearest neighbor search (https://en.wikipedia.org/wiki/Nearest_neighbor_search).  I would suggest that locality sensitive hashing might be a promising choice for your situation.  You could also look into clustering algorithms (though they will probably still require nearest neighbor search as one step of their working).


Solving a CSP using AC-3 Peter (P), Mary (M), Otto (O) and Dicky (D) would like to rent an apartment house. The house has three floors: G/F, 1/F, 2/F. Every floor has only one apartment. P, M, O and D must be assigned to exactly one floor. Note that more than one person can live in the same apartment. Consider the following constraints.

P and M cannot live in the same apartment.
D must live on a higher floor than O.
D must live alone.
If P and O live together, they must be on 1/F.
If P and O live separately, one of them must live on the 2/F.

How do I use AC-3 to solve this question?
I found two possible solutions: P,M,O,D = 2,0,0,1 or 1,0,1,2

AC-3 is an algorithm for solving CSPs. In order to use it solve a question, you need to present the question as solving a CSP.
In your case, the CSP is on four variables $P,M,O,D$ ranging over $\{0,1,2\}$. The constraints are:

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

We can convert them into the following explicit constraints:

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

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


How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$? I am trying to find $T(n)=O(f(n))$, where  $$T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right],$$ where $m\in\{1,2,\ldots,n\}$.

Is it possible to find $f(n)$ such that $T(n)=O(f(n))$?

I started to fix $m=n/2$ (which I assume the worst scenario, isn't it?). I found $$\begin{align}T(n)&\leq n^2+\frac{n^3}{2}+\frac{n^4}{8}+\frac{n^5}{64}+\frac{n^4}{4}T(n/16),\\ &\;\vdots\\&
\leq n^2+T(1)\sum_{i=1}^{(\lg n)-2}\frac{n^{i+2}}{\sqrt{2^{i(i+1)}}}.\end{align}$$

On the one hand, we have
$$
\begin{align*}
T(n) &\geq n^2 + nT(n-1) \\ &\geq n^2 + n(n-1)^2 + n(n-1) T(n-2) \\ &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + n(n-1)(n-2)T(n-3)
\end{align*}
$$
and so on. Assuming, for simplicity, a base case of $T(0) = 0$, this gives
$$
\begin{align*}
T(n) &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n(n-1)\cdots (1)^2 \\ &=
n! \left(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \cdots + \frac{1}{0!} \right) \\ &=
n! \left(n + \frac{1}{(n-1)!} + \frac{1}{(n-2)!} + \cdots + \frac{1}{1!}\right) \\ &=
n! \left(n + e - 1 \right) - O(1).
\end{align*}
$$
This should also work as an upper bound. To prove this rigorously, choose an upper bound $S(n)$ for which you can prove $S(n) \leq n^2 + n(S(n-1) + S(0))$ as well as that $S(n)$ is convex. Convexity will ensure that the values of $m$ maximizing the sum $S(n-m) + S(m-1)$ are $m=1$ and $m=n$.


What does x-bit binary number means? What does x-bit binary number mean?
for example:

if x = 8

is 8-bit means:
any number consists of 8 bits, like : 10101110

or it has another meaning??

That is correct. An x-bit binary number can be expanded as "A number in the binary system that consists of x binary digits".


Big Theta Proof: May I chose any constant? I have the following assignment:

  Prove that $\sum^n_{i=1} i2^i \in \Theta(n2^n)$

My current approach thus far is the following:

Since we need to prove $k_1 \cdot n2^n \le \sum^n_{i=1} i2^i \le k_2 n2^n$ I chose $k_1 = 1$ and $k_2 = 2$. This holds true to my condition. However I'm unsure whether I can just freely decide on using those two.

Therefore my question is:

  Am I allowed to chose any constant factor I want in a $\Theta$ proof (given that the condition holds true)?

Yes, as long as the constant conforms to the definition of $\Theta$, that is it

is positive and
independent of $n$.

This follows directly from the definition of $\Theta$, which requires only the existence of some $c_1, c_2>0$ (in typical formulations).

You may find our reference questions helpful; in particular, there are more convenient ways to prove such claims besides checking the definition explicitly.


Checking for $3$-colorability by searching for $K_4$ as a minor Determining if a graph is $3$-colorable is NP-complete. But this is equivalent, by a resolved case of Hadwiger's Conjecture, to checking if the graph has $K_4$ as a minor.

Per https://en.wikipedia.org/wiki/Graph_minor#Algorithms, this can be done in $O(n^3)$ time, where $n$ is the number of vertices, as $K_4$ has a constant number of vertices. This would seem to be a contradiction (unless $P=NP$)

Hadwiger's conjecture states that if a graph is not $(k-1)$-colorable then it has a $K_k$ minor. Hadwiger himself proved it for $k \leq 4$. Thus, any graph which is not $3$-colorable has a $K_4$ minor. However, the converse doesn't hold: some graphs having a $K_4$ minor are $3$-colorable. For example, take $K_4$ and split each edge into a path of length $2$ edges. The result is bipartite, and so $2$-colorable.


Analysis of the following integer program So the knapsack problem has an integer programming formulation as follows,

$$ \max_x v\cdot x\\s.t \\x_i \in \{0,1\}\\w\cdot x \leq C$$

Now consider the second integer program which might be a variation of the knapsack integer program.

$$ \max_x v\cdot x\\s.t \\x_i \in \{0,L_i\}\\  x_i \leq R \cdot \delta_i\\ \delta_i  \in  \{0,1\}\\ \sum_i \delta_i = k$$
where $v_i$ is item's $i$ value, $L_i$ and $k$ are constants, and $R = \max{\{L_1,L_2,...L_d\}}$.

Is there a dynamic programming solution or an approximation algorithm
for the second integer programming problem ?
Is it possible to use the solution of the knapsack problem to warm
start or partially solve the second integer programming ?

Thanks!

A simple greedy approach works here: choose the $k$ elements having maximal $v_i L_i$.


How do I calculate Instruction Per Clock? Hi! I faced a problem with calculating IPC.

I can tell the answers were derived from IPC=instruction/number of cycles.

But I have no idea why it has to be calculated that way.

Just to understand the meaning of IPC, it seems like how many instruction
can one cycle(clock) handle which obviously is not the case for this question..

Hope to get some helpful answers from here!

Thank you in advance!

The computation of instructions per cycles is a measure of the performance of an architecture, and, a basis of comparison all other things being equal.  IPC can be used to compare two designs for the same instruction set architecture, as in the question you're asking comparing two design alternatives for a MIPS architecture.

Or, IPC can be used to compare vastly different designs (like CISC vs. RISC).  If the processor can execute one instruction per cycle, then the IPC=1. Especially processors in the 1970's were usually were microcoded, and instructions completed in a variable number of cycles, like some in 2 cycles or some instructions in 4.  So, for these machines IPC < 1.  Some processors using VLIW or EPIC or other architectural designs might complete several instructions in one cycle.

A MIPS processor attempts to execute one instruction per cycle using its pipelined design.  However, certain conditions cause it to stall:

waiting for a result that isn't ready, like multiply or divide
waiting for a cache miss to resolve

Other times, it does work, but the work must be thrown away — this is the case of the branch instruction.  More specifically, the issue of how soon the processor can get back onto the right instruction stream.

Let's look more closely at the pipeline for the question you're asking about:
Here the code sequence is

<x>
B trg
<a>
<b>
<c>

In the following, @trg represents the instruction at the target of the branch, and this is the proper instruction to execute immediately after the branch.

    IF       ID      EX     MEM      WB
-1  <x>
0   B trg   <x>
1   <a>     B trg   <x>
2   <b>     <a>     B trg   <x>
3   <c>     <b>     <a>     B trg   <x> <--- if the branch executes here in the MEM stage, then <a>,<b><c> are unwanted and have to be discarded.
4   @trg    <c>     <b>     <a>     B
5           @trg    <c>     <b>     <a>
6                   @trg    <c>     <b>
7                           @trg    <c>
8                                   @trg

The above shows the branch executing in the MEM stage.  Thus, the fetches the processor did for < a >, < b >, and < c > are invalid and have to be discarded.  Three cycles are lost or wasted.

    IF       ID      EX     MEM      WB
-1  <x>
0   B trg   <x>
1   <a>     B trg   <x>                 <--- if the branch executes here in the ID stage, then only <a> is lost
2   @trg    <a>     B trg   <x>
3             @trg  <a>     B trg   <x>
4                   @trg    <a>     B
5                           @trg    <a>
6                                   @trg

Since the ID stage is 2 stages earlier, this processor has a larger IPC.  We can use the IPC to ascertain exactly how much faster this design would be, and this demonstrates the value of the IPC definition.

(There is term in sailing and yachting called Velocity Made Good, VMG — the idea is that even though you're going a certain speed (in sailing: knots, in computing: cycles per second aka hertz), only some of that speed goes to useful work being done (in sailing: reaching the finish line, in computing: completing instructions from the program).  VMG for a processor would be instructions / hertz.  So, compared to VMG which includes a time component, IPC factors out the time component.)


The impact of caching on the system performance or on the user experience I am working on modeling a certain system's cache layer and comparing two algorithms.

One outperforms the other one; it shows the higher cache hit rate (%).

But what is important is the impact of such an improvement at cache layer on the entire system performance and on the user experience.

The system performs message deliveries from producers to consumers.
So the latency would be a good measure of the user experience.

However, because I am new to this area so I am a little lack of the background knowledge on it.

Is there any one who has worked on similar topics?
Could you give me reference papers to get some understandings on what kind of measure can be used, how those can be represented, ... etc.

(For example, a paper with title "Improving Web Caching System by Adaptive ABC algorithm" can have such information.)

I think that a good starting point to understand how the memory (including caching) works is What Every Programmer Should Know About Memory from U. Drepper. In fact, this is one of the best papers I have ever read about computers.

More recently, I found How misaligning data can increase performance quite entertaining. It is a direct application of the things you can learn from the first one.


Trouble finding loop invariant for this while loop I'm having trouble coming up with an invariant for proving partial correctness of this function.

def f(A):
    # Pre: A is a list of integers
    # Post: Returns true if and only if there is an even number of positive
    # numbers in A

    even = True
    i = 0
    while i < A.length:
        if A[i] > 0:
            even = not even
        i = i + 1
    return even

So far, I have something like:

i <= A.length and (even == True or even == False)

However, I don't really know whether this is correct or, if it is even, if I can prove that it is inductive. I don't really know how to start the proof and was just looking for some help to point me in the right direction.

Thanks.

Unfortunately, you can't prove partial correctness of your algorithm because it is incorrect.

EDIT: The algorithm provided is indeed correct.

Aditionally, you can't prove that an algorithm is "inductive". You can prove its correctness by using loop invariants,which are quite similar to mathematical inductions.

We must show three things about a loop invariant:

Initialization:

Before you start the loop,check if your initialization is correct.

You want to check if there is an even number of positive numbers in your list A. You set up the variable i to equal 0, therefore your loop begins at the first index of your list.

The variable even is set to True. If it were set to false, and you had 0 positive integers, it would return false, which is incorrect.
Therefore, initialization is correct.

You can see initialization as your base case.

Maintenance:

If your invariant holds from iteration to iteration.

The body of your while loop checks if an integer in index i of your array A is positive. If that condition is true, it sets the boolean variable "even" to "not even".

Since it flips the value of even equal to the amount of positive integers in your list,the maintenance is correct.

Termination:

What happens when the loop is over?

The last step increments the variable i by 1. When the loop ends, i < A.length, which is correct.

The algorithm will return either True or False based on the amount of positive integers. Since initialization and maintenance are correct, the algorithm is correct.


Does a PDA follow a transition if the top stack symbol doesn't match? Does a PDA only move states when both the input symbol matches and the symbol on the top of the stack matches?

In other words, is it possible to have two different transitions that both take the same input character but pop different stack symbols?

For example if we have a state Q0 with the two following transitions:

a, a -> b
 a, b -> a

I know that a PDA will transition in regards to the input symbol but how does it handle the stack symbol that it is trying to pop?

For some reason I can not find the answer to this simple question for the life of me. I have searched and searched in my textbook and online.

TL;DR: No, it does not.

I would guess that your notation a, a -> b means the syntax in a PDA transition such that if we read a character a from the input and we pop a character a from the stack, then we put a character b on top of the stack.

The notation of that transition that I'm used of is written as $$q\xrightarrow{\text{e,d;u}}r,$$

where the left side of the semicolon is what we read, i.e. character e from the input and character (or symbol) d from the stack. Right side of the semicolon is what we put onto the stack: u.

In order for your PDA to follow a transition, it has to match both of the conditions on the left side of the above notation. So, your PDA won't follow that particular transition if the stack symbol doesn't match.

What comes to your second question about having two different transitions with same input but different stack symbol, yes, that is possible based on nondeterminism, but your PDA still has to meet both conditions in the left side of the notation in order to move anywhere.

Hope this had any help!


Algorithm Complexity Analysis on functional programming language implementations I've learned today that algorithm analysis differs based on computational model. It is something I've never thought about or heard of.

An example given to me, that illustrated it further, by User @chi was:

  E.g. consider the task: given $(i,x_1 ,…,x_n )$
   return
  $x_i$
  . In RAM this can be solved in $O(1)$
   since array access is constant-time. Using TMs, we need to scan the whole input, so it's $O(n)$

This makes me wonder about functional languages; From my understanding, "Functional languages are intimately related to the lambda calculus" (from a comment by Yuval Filmus on here). So, if functional languages are based on lambda calculus, but they run on RAM based machines, what is the proper way to perform complexity analysis on algorithms implemented using purely functional data structures and languages?

I have not had the opportunity to read Purely Functional Data Structures but I have looked at the Wikipedia page for the subject, and it seems that some of the data structures do replace traditional arrays with:

  "Arrays can be replaced by map or random access list, which admits purely functional implementation, but the access and update time is logarithmic."

In that case, the computational model would be different, correct?

It depends on the semantics of your functional language. You can't do algorithm analysis on programming languages in isolation, because you don't know what the statements actually mean. The specification for your language needs to provide sufficiently detailed semantics. If your language specifies everything in terms of lambda calculus you need some cost measure for reductions (are they O(1) or do they depend on the size of the term you reduce?).

I think that most functional languages don't do it that way and instead provide more useful statements like "function calls are O(1), appending to the head of a list is O(1)", things like that.


What is the "formula" for "any cipher can be deciphered by a quantum computer"? There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.
P=NP BPP=NP in simple words means "any cipher can be deciphered by a classical computer". (Do I understand it correctly?)
So, what is the "formula" for "any cipher can be deciphered by a quantum computer"?

In general, if NP turns out to be the subset of any tractable class then that will be a black swan event for those who depend on cryptography as it exists today.  $NP \subseteq BQP$ is one such example. But it need not be a fatal blow to use of cryptography.  Quantum computers with a large number of qubits have yet to be built, and it is unknown whether they can be.  So increasing key lengths may well put tractable decryption out of reach of the machines that can be built.  And of course the polynomial exponent might turn out to be large enough to make polynomial-time "efficient" decryption infeasible in practice.  E.g. an $O(n^{13})$ algorithm for SAT, while a beautiful thing to behold, probably isn't going to break use of cryptography.


Binary tree node value maximization Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be included.

My intuition tells me dynamic programming (and possibly two-coloring) should be involved, but not sure where to start. Could you please offer me a hint?

This problem is known as Independent Set (and not two-coloring). Your intuition is quite correct though.

As a hint, I'd like to offer the following definitions:

Let $n$ be a node of the binary tree. Let $P(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may not be included. Similarly, let $Q(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may be included.


Analog computers and the Church-Turing thesis I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine):

  One class of challenges to the strong Church–Turing thesis comes from the field of
  analog computation. In the years since Turing, many different teams of researchers have
  noticed that certain types of analog computers can efficiently solve problems believed to
  have no efficient solution on a Turing machine. At first glance these analog computers
  appear to violate the strong form of the Church–Turing thesis. Unfortunately for analog
  computation, it turns out that when realistic assumptions about the presence of noise in
  analog computers are made, their power disappears in all known instances; they cannot
  efficiently solve problems which are not efficiently solvable on a Turing machine. This
  lesson – that the effects of realistic noise must be taken into account in evaluating the
  efficiency of a computational model – was one of the great early challenges of quantum
  computation and quantum information, a challenge successfully met by the development
  of a theory of quantum error-correcting codes and fault-tolerant quantum computation.
  Thus, unlike analog computation, quantum computation can in principle tolerate a finite
  amount of noise and still retain its computational advantages.

Is this a statement that noise scales faster than some power of the problem size, or can someone point me in the right direction so that I can find out more about whether these scaling limits are fundamental or merely an "engineering issue"?

To be clear, I am asking if analog computers cannot beat Turing machines in efficiency due to noise.

First of all, the authors seem to be confusing two different thesis: the Church–Turing thesis and the Cook–Karp thesis. The first concerns what is computable, and the second concerns what is computable efficiently.

According to the Cook–Karp thesis, all reasonable "strong" computational models are polynomially equivalent, in the sense that they all polynomially simulate each other. Equivalently, every reasonable computational model can be polynomially simulated by a Turing machine. Quantum computers are a counterexample to this thesis, since they appear to be exponentially more efficient than classical computers. However, they are not a counterexample to the Church–Turing thesis, that is, using quantum computers you can't compute anything that you can't already compute with a Turing machine. We can also formulate an updated Cook–Karp thesis, stating that all physically realizable computational models are polynomially simulated by quantum computers.

Several physical models of computations have been proposed as challenging these theses, but under scrutiny, they all seem to not violate the Church–Turing thesis, or not to be more powerful than quantum computation. Scott Aaronson proposes to consider this situation as a "law of nature". However, as far as I know there are no theoretical arguments supporting these theses other than the inductive argument that all models which have been proposed have been shown to conform to them.


Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content.

I recently had an university exam about Parallel Algorithms. One exercise asked me to write an algorithm to determine if the elements of an array, let's call it A, were repeated an equal number of times.

For example:

1) A = 1 8 8 1 8 1 1 8 : the answer is yes, every number is repeated 2 times.

2) A = 7 8 8 5 5 4 7 8 : the answer is no.

I had to write the algorithm for a particular model of parallel computing, a PRAM: the model required me to use some techniques to avoid read/write conflicts, and other problems, but this is not relevant. What I ended up with was a new array, let's call it B, which I can define as follow: Given the array A, B[i] contains the number of repetitions of the element A[i] within A.

For example:

1) A = 1 8 8 1 8 1 1 8

B = 4 4 4 4 4 4 4 4

2)A = 7 8 8 5 5 4 7 8

B = 2 3 3 2 2 1 2 3

As you might think and expect, the only thing left to do would be to check if every element of B is equal to the other, but.. it turns out I'm masochist, and the pressure of the exam (plus I had a bit temperature) led me to take another path. Moreover, comparing elements of an array is not immediate using this computing model.

So, to check if all the elements of B are the same, I summed all of them and divided the result by the number of elements of B: if the result was equal to an element of B (for example the first, B[0]) then the algorithm returned true (false otherwise).

Taking the example above:

1) sum = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 32 --> 32 / 8 = 4 = B[0] --> Yes.

2) sum = 2 + 3 + 3 + 2 + 2 + 1 + 2 + 3 = 18 --> 18 / 8 ≠ 2 = B[0] --> No.

I know it's absurd, but that's what I came up to.

I checked this approach with a lot of different combinations of arrays/numbers, and it seems to work. Thing is, I'm having an hard time in finding a (mathematical) proof that the algorithm is correct. Besides the result of the exam, which I still don't know yet, I'm very interested in knowing if there's some mathematical proof/explanation which states that this approach is correct or not, and that's why I need an help.

I hope I have posted the question in the right StackExchange site. If not, please redirect me to the right site.

Thank you in advance.

No, your algorithm doesn't work.  Consider if the array A is

A = [1 1 1 1 1 2 2 3 3 3 3 3 3].

Then the array B will be

B = [5 5 5 5 5 2 2 6 6 6 6 6 6].

The sum of B will be 65, and the length of B will be 13, so after division, we'll get the number 5.  This is equal to the first element of B, so your algorithm will output "Yes".  Nonetheless, not all elements of B are the same, and the correct answer is "No".  So, your algorithm gives the wrong output on this case.

Nice try, though!  Figuring out how to build B was probably the hardest part of this problem.

How I found this: I couldn't find a counterexample with two distinct numbers, so next I tried with three distinct numbers.  Let $u,v,w$ denote how often each of those numbers appear.  Then the array will have length $u+v+w$, and B will contain the value $u$ repeated $u$ times, the value $v$ repeated $v$ times, and $w$ repeated $w$ times, so the sum of elements of B is $u^2+v^2+w^2$.  We can find a counterexample if we can find a solution over the positive integers to the Diophantine equation

$${u^2 + v^2 + w^2 \over u+v+w} = u$$

such that $v\ne u$ or $w \ne u$.  This is equivalent to

$$u^2 + v^2 + w^2 = u(u+v+w),$$

where $u,v,w$ are positive integers and either $v\ne u$ or $w \ne u$.  I then picked a few small values of $u$ and tried solving this Diophantine equation using Wolfram Alpha.  The first solution I stumbled across was $u=5$, $v=2$, $w=6$, but there are many others as well.  In retrospect I guess I could have simplified further to

$$v^2 + w^2 = uv + uw$$

but I didn't notice and it turned out not to matter.


Is the reversal of a minimal DFA also minimal? The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $m$ states, where $m<n$?

The minimal DFA accepting the reversal of the language can be smaller. Consider the finite language
$$ L = (0+1)^22+(0+2)^21+(1+2)^20. $$
The words $\epsilon,0,1,2,00,01,02,11,12,22,000,001$ are inequivalent, so any DFA for $L$ requires at least 12 states; in fact there is a DFA with exactly 12 states. The reverse language
$$ L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2 $$
is accepted by a DFA with only 9 states: an initial state, states corresponding to initial $0,1,2$, states corresponding to initial $0(1+2),1(0+2),2(0+1)$, an accepting state and a fail state; this is also the optimal DFA, since $\epsilon,0,1,2,01,12,20,011,000$ are inequivalent.

Summarizing, the minimal DFA for $L$ requires 12 states, while the one for $L^R$ requires only 9 states.

As jmite mentions in their comment, for NFAs with multiple starting states this phenomenon can't happen, since if you flip the direction of all arrows in a NFA for $L$ then you get a valid NFA for $L^R$.


Having trouble proving a language is NP-complete I'm asked to prove that, if P=NP, that 0*1* is NP-complete, but I'm having trouble going about doing it. I know it's fairly easy to prove it's NP by creating a TM to verify an input (which can be done in O(n) time, and that's polynomial).

But then I now have to reduce an NP-complete problem to 0*1* in order to prove that 0*1* is NP-complete. I'm thinking reducing SAT to it, but I have no idea how to do that, since in SAT all you can use is and, or, and negate, and there's no way to tell if a 1 came before a 0 in an input by doing that (at least, as far as I can tell).

Thanks

Here is a more technical answer.  The "trick" is to put all the
work in the reduction function.

Assume $NP = P$, $L \in P$ and let $x_0, x_1$ be two instances, such
that $x_1 \in L$ and $x_0 \not\in L$.  We have to show that some
$NP$-complete problem $Q$ is poly-time reducible to $L$.  By
assumption, there is an algorithm $M$ deciding $Q$ in polynomial
time.

Define a function
$$
f(x) =
\begin{cases}
  x_1 & \mbox{if $M(x) = 1$} \\
  x_0 & \mbox{else}
\end{cases}\mbox{ ,}
$$
for all instances $x$ of $Q$.  Then clearly $f \in FP$ and $x \in Q
\Leftrightarrow f(x) \in L$.


Meaning of the Halting problem The Halting Problem is defined as:

$H_{TM} = \{ \langle M, w \rangle \mid \text{\(M\) halts on input \(w\)}\}$

I'm not sure what it means. Is $H_{TM}$ a collection of Turing Machines such that all of them accept/reject the word $w$? Is that a specific word? Or does that mean any word in their alphabet?

Thanks

We first choose an alphabet of symbols that our Turing machines can read and write on the tapes. Typically we have three symbols: $0$, $1$, and "empty". A word is a finite sequence of symbols.

If $u$ and $v$ are words we can form a new word $\langle u, v \rangle$ which represents the two words put together (this requires some coding so that we can tell where one words stops and the other begins).

A Turing machine can be be described by a word.

Like in all decidability problems, $H_{TM}$ is a set of words. More precisely, $H_{TM}$ contains all those words of the form $\langle M,w \rangle$ where $M$ is a Turing machine, $w$ is any word, and $M$ halts when we run it with input $w$.


Picking an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$ I've got the following problem:

Tommy has a toy consisting of wooden posts and in each move he can either hit one post (which decreases its height by 1) or pull out a post (which increases its height by one). Tommy wants to set all poles to the same height but he must do that using minimal ammount of moves. How many moves must be made?

An input is a list $[x_1,x_2,...,x_n]$ where $x_i$ is a starting height of pole number $i$.

Mathematically speaking we must find an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$ and then all we need to do is to calculate this sum. But how to find such an $m$? And if I have a candidate for $m$, how to prove that I am right?

Rearrange the numbers in sorted order so that you have $x_1\le x_2\le \dotsm \le x_n$. Now let $m$ be the median value, $x_{\lceil (n/2)\rceil}$, i.e., the value for which half of the elements are greater than or equal to $m$. This will minimize $\sum_{i=1}^n |x_i-m|$. (If $n$ is even, any value $m$ in the range $x_{\lceil (n/2)\rceil}\le m\le x_{\lceil (n/2)\rceil+1}$ will do for $m$).

For example, if $x_1=1, x_2=2, x_3=4, x_4=8, x_5=16$, the median value will be $m=x_3= 4$ and you'll have
$$\begin{array}{ccccccccc}
& |x_1-4| & + & |x_2-4| & + & |x_3-4| & + & |x_4-4| & + & |x_5-4|\\
=& |1-4| & + & |2-4| & + & |4-4| & + & |8-4| & + & |16-4|\\
=& 3 & + & 2 & + & 0 & + & 4 & + & 12\\
=& 21 &&&&&&&&
\end{array}$$

so the minimum value of the sum will be 21.

It's not too difficult to show that this algorithm is correct: inductive proofs for $n$ even and $n$ odd will do it. To see what's going on, try graphing something like $y=|x-1|+|x-3|$ and looking for the $x$ value(s) that minimize this function.


example for weakly fair v.s. strongly fair scheduling in concurrency I am having difficult time understanding the difference between weakly fair and strongly fair schedulers. Can someone provide an example and explain how they are different?

for reference, here are the definitions I have of each:

weakly fair: A condition becomes true and remains true at least until after the conditional atomic action has been executed.

strongly fair: If the condition is infinitely often true, a process will eventually see it as true and be able to proceed.

So I think I understand weakly fair, a conditional atomic action will execute when its condition is true, and the condition will remain true until the atomic action has ended.

But I don't see how strongly fair is different from this. for a conditional atomic action, once its condition is true it executes, and because it is atomic, the condition should remain true until it ends, right? this is the same as weakly fair isn't it?

If you are familiar with temporal logic, the difference is quite easy to demonstrate:

Weak fairness is $FGp\to Fq$. That is, if $p$ holds from some point and on, then $q$ will hold eventually.

Strong fairness is $GFp\to Fq$ (or sometimes $GFp\to GFq$). That is, if $p$ holds infinitely often, then eventually $q$ will hold (or $q$ will hold infinitely often, in the second version).

Your description is slightly different from the above, in that your weak fairness has the "until" flavour, but it's the same idea.

To demonstrate the difference in the approaches, think of yourself as a process trying to gain access to some critical section. If you know that the system is weakly fair, then you need to raise a flag saying that you want access, and you have to keep this flag up all the time, until you get access. If the system has strong fairness, it is enough that you raise the flag every now and then, and you know that eventually you'll get access.

As an alternative example, children who want attention often go "mom" repeatedly until they are granted attention. This is similar to weak-fairness (of the mother), and as you can see, it prevents the child from doing anything else until granted attention. With a strongly-fair mother, it suffices for the child to say "mom" every few minutes, and go about doing other things in the mean time.

By the way, this question has an excellent answer by Cynthia Disenfeld at quora.


Stroke Width Transform: Gradient Direction Computation I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .

Having a simple image with random texts, that underwent gray scaling. Then I have produced two edge maps using two different algorithms for output comparison (for later) , Sobel and Canny (I'm also planning on Prewwit or other edge detection algorithms). I also have gradient maps x and y, using sobel.

on the segment of computing the gradient direction, given the equation:

theta = arctan( Gy / Gx )

where:

theta = is the resulting angle
Gx = is the X gradient component
Gy = is the Y gradient component
(both Gx and Gy are from the gradient maps)

I got a bit confused. If the value of Gx is 0 (zero), and we all know dividing by zero is undefined (some say it's infinity), so are we going to make theta infinity or just 0 (zero)?

If $Gx = 0$ and $Gy > 0$, then we use $Gy / 0 = + \infty$. Note that $\arctan +\infty = 1$.

If $Gx = 0$ and $Gy < 0$, then we use $Gy / 0 = -\infty$.  Note that $\arctan -\infty = -1$.


How to we prove if a right linear language is ambiguous? Considering the following language as an example:
$$\begin{align}
S &\rightarrow aS \mid bA \\
A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\
B &\rightarrow aB \mid \varepsilon \\
D &\rightarrow aD \mid \varepsilon
\end{align}$$
This has ambiguous transitions on the string $ba$, but how do we prove in general that a right linear language is ambiguous. Is there an algorithm for this?

For simplicity, let me assume that the only allowed rules are of the form $A \to aB$ and $A \to \epsilon$. Denote the set of nonterminals by $V$, where $S \in V$ is the starting symbol.
Construct a new right linear grammar with nonterminals $V \times V \times \{0,1\}$. The new grammar will simulate two different production sequences for each word, keeping track whether the two actually differ.
The starting symbol is $(S,S,0)$, and the rules are:

For every pair of original rules $A \to aB$ and $C \to aD$ we add the rule $(A,C,1) \to a(B,D,1)$. (Possibly some of $A,B,C,D$ are equal.)

For every pair of original rules $A \to aB$ and $A \to aC$ such that $B \neq C$ we add the rule $(A,A,0) \to a(B,C,1)$. (Possibly $A=B$ or $A=C$.)

For every pair of original rules $A \to \epsilon$ and $B \to \epsilon$ we add the rule $(A,B,1) \to \epsilon$. (Possibly $A=B$.)

A word $w$ has two different derivations in the original grammar iff it can be generated by the new one.
For example, in your sample grammar the word $ba$ has two different derivations, $S \to bA \to baB \to ba$ and $S \to bA \to baD \to ba$, and this is reflected in the following derivation in the new grammar:
$$
(S,S,0) \to b(A,A,0) \to ba(B,D,1) \to ba.
$$


How to cluster similar objects into fixed size groups? I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day.

eg - Suppose there are 3 people who are free on (M,T,W,Th,F), (M,W) and (W,Th,F) respectively. They can all be placed in the same group since all of them can meet on Wednesday.

Just model your problem with graph and use any of the widely known search algorithm to help traverse your graph. After doing that, if you have any problem, let us know.


Why is this true: “There are countably many Turing Machines” It is said that there are uncountably many languages but only countably many Turing Machines. Could someone make this clear to me?
And this doesn't mean that the set of TM is finite, yes?

A quick informal answer:

a Turing Machine (states, transitions, ecc.) can be encoded using a string of $0$'s and $1$'s;
so you can pick all the binary strings in lexicographic order (0,1,00,01,10,11,000,001,...) and enumerate the Turing machines (i.e. build a one to one corrispondence between natural numbers and Turing machines) repeating the following steps:

1) start with $i=1$, $m=1$
2) generate the next binary string $s_i$ in lexicographic order
3.1) if $s_i$ is a valid encoding of a Turing machine then output $s_i$ as the $m$-th Turing machine and set $m = m+1$;
3.2) if $s_i$ is not a valid encoding of a Turing machine then ignore it
4) set $i = i+1$ and goto step 2

In this way each natural number ($m= 1,2,3,...$) corresponds to a Turing machine, and each Turing machine has a corresponding $m$, because you scan all possible binary strings. So the set of Turing machines is countable.

On the other side consider all possible strings $S$ over alphabet $\{0,1\}$:
$S =\{0,1\}^* = \{\epsilon,0,1,00,01,10,11,000,001,...\}$

A language $L$ is a subset (possible infinite) of $S$: $L \subseteq S$.

So the set of all languages is exactly the power set of $S$:
$2^S = \{ \{\epsilon\}, \{0\}, \{1\}, \{0,1\}, ... \}$

But the power set of a countably infinite set is uncountable (it can be easily proved using the diagonalization method).

You can also apply the diagonalization method directly to the set of languages: suppose that the languages are countable, then we can arrange all of them in a table in which every (infinte) row $i$ represents the elements of the language $L_i$ and the columns represent the string over the alphabet $\{0,1\}$ ($(i,j)=1$ if and only if string $j$ is in $L_i$):

    0 1 00 01 10 11 ...
L1  0 0  1  0  1  0
L2  1 1  0  1  0  1
L3  0 1  0  0  1  0
...

Then define a new language changing the "membership flag" of the elements $(i,i)$:

    0  1 00 01 10 11 ...
L1 [1] 0  1  0  1  0
L2  1 [0] 0  1  0  1
L3  0  1 [1] 0  1  0
...

The new language $L_{new} = \{0,00,...\}$ built from the modified diagonal is different from every language $L_i$: $0 \notin L_1, 0 \in L_{new}$, $1 \in L_2, 1 \notin L_{new}$, $00 \notin L_3, 00 \in L_{new}$, .... But this is a contraddiction because by hypothesis the above table should be an enumeration of all languages.


Cubic Cycle is Np-Complete HAMCYCLE = {<"G"> : G is a simple undirected
graph that has a Hamiltonian cycle}

CUBIC CYCLE = {<"G"> :G is a simple undirected graph that contains
a simple cycle of length at least |V (G)|^1/3}
The reduction i figured out is :
G has a ham-cycle <==> G has a cubic cycle of a given length(V^1/3).
Prooving ==> part is simple as we have to show that if a cycle of V exists, then in G a cycle of V^1/3 exists.
But i got stuck in proving the other direction.
Any insights would be helpful.

The reduction that you suggested does not work. For example, consider a graph $G = (V, E)$ that consists of 9 disjoint triangles ( triangles that do not touch each other). $G$ has a triangle which a hamiltonian cycle of length $3 = 27^{\frac{1}{3}} = |V|^{\frac{1}{3}}$, yet $G$ has no hamiltonian cycle.
A simple correct reduction operates as follows. Given an undirected graph $G = (V, E)$, the reduction outputs $G$ with additional $|V|^3 - |V|$ isolated vertices. I leave the details to you.