About the definition of "differential privacy" in communication complexity In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense.

So the two parties $A$ and $B$ draw two strings $X$ and $Y$ from the set $S^n$ where $S$ is some finite set. Let $P$ be the protocol. Now if $z_1 = (X_1,Y_1)$ and $z_2 = (X_2,Y_2)$ are two instances drawn with a probability distribution $\mu$ over the set $S^n \times S^n$ then the protocol $P$ is called "$\epsilon$-differentially private" if the following holds:

$$e^{-2 \epsilon n}  \leq  \Pr[P(z_1) = p]  /  \Pr[P(z_2) = p]   \leq e^{2 \epsilon n}$$

Now why does this make sense? What's the intuition?
How is this related to the bounded derivative definition?

Your definition is wrong. The correct definition is as follows. A protocol $P$ is $\epsilon$-differentially private (for $\epsilon > 0$) if for any two inputs $Z_1,Z_2$ differing in a single coordinates and any $p$,
$$
e^{-\epsilon} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^\epsilon.
$$
For small $\epsilon>0$, $e^\epsilon \approx 1 + \epsilon$, and $e^{-\epsilon} \approx 1 - \epsilon$; the quantity $e^\epsilon$ is easier to work with compared to $1+\epsilon$, since $e^{\epsilon_1} e^{\epsilon_2} = e^{\epsilon_1+\epsilon_2}$, whereas $(1+\epsilon_1)(1+\epsilon_2) \approx 1 + \epsilon_1 + \epsilon_2$ holds only approximately.

Another small note: the upper bound implies the lower bound and vice versa.

The definition implies that for any two inputs $Z_1,Z_2$ that differ in at most $d$ places,
$$
e^{-\epsilon d} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon d}.
$$
In particular, if the inputs have length $m$, then for any $Z_1,Z_2$ we have
$$
e^{-\epsilon m} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^{\epsilon m}.
$$
In your case $m = 2n$.


What is the Big O time complexity of this algorithm? We are given $m$ arrays of $n$ elements each. For 90% of these arrays we run an $\mathcal O(n)$ algorithm and for the other 10% an $\mathcal O(n\log n)$ algorithm. What is the total time complexity? I think it is $\mathcal O(m n \log n)$ but I am not sure.

The O(n log n) eventually grows faster than the O(n) algorithm. We always take the fastest growing component of the algorithm when deciding the complexity, so you're right that the total complexity of the algorithm is O(m n log(n))


Importance of a person to another person in social network In social network (an unweighted indirect network), is there some measure of importance of a person A on another person B, denote as I(A,B), so that (approximately):

The smaller the shortest distance between A, B in the the network, the higher the I(A,B) (closeness)
If A_1 is 1 of the 100 friends of B_1,  A_2 is 1 of the 2 friends of B_2, then I(A_1,B_1) < I(A_2,B_2) (the more friends I have, the less importance of each one)
Some other reasonable properties that resemble the importance of a friend to another friend in real society.

yes, social networks have a simple (graph) connectivity property in many or most cases/ situations/ contexts (such as "friend" connections on a social network like Facebook etc), but also a weighted property of the graph in various other situations. a common aspect of this now measured is widely/ generally referred to as the influence of the "friendship". two users may be connected, but influence measures other aspects.

one aspect of high interest to marketers and driving a lot of research is how much "friends" influence each others purchasing decisions ie if person A buys x, does that influence friend B to buy x also, or a y similar to x. here are a few papers/ refs on this subject. there are different ways to attempt to measure influence and in some cases it may be derived/ estimated that some users have more friends and are more thus influential on those friends, in other ways it can be determined from additional data such as looking at buying patterns of A, B if A, B are connected etc.

buying influence is just one of the major/ dominating areas of weighting under study, but there are various others. another key aspect coming up in 2016 in the US is voting influence that is under some study also, ie tendency of connected users to vote in similar ways.

Determining Influential Users in Internet
Social Networks / Trusov, Bodapati, Bucklin
Do Friends Influence Purchases in a Social Network? / Iyengar, Han, Gupta
HOW FRIENDS INFLUENCE US ON SOCIAL MEDIA (AND WHAT THAT MEANS FOR MARKETERS) / fast company


How to state a recurrence that expresses the worst case for good pivots? The Problem
Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $\frac{3n}{4}$(a good pivot). Also with probability $\frac12$ the pivot selected will be between 1 and $\frac{n}{4}$ or between $\frac{3n}{4}$ and $n$(i.e.  a bad pivot)

1.State a recurrence that expresses the worst case for bad pivots.
2.State a recurrence that expresses the worst case for good pivots.

My Work:
I understand the overall idea of quicksort - pivot all the elements around the pivot(less-> to the left, right -> to the right) and repeat the process for the elements to left of the pivot and for the elements to the right of the pivot
Here is the recurrence I came up with for 1 -$ T(n) =
\begin{cases}
c  & \text{if $n$ is 1} \\
T(n-1) + n, & \text{if $n$ is > 1}
\end{cases}$
I was able to work out this recurrence by reasoning that if I just chose the worst possible pivot(either greatest or least), I would have to traverse through all the elements(the $n$) and then repeat this process for the rest of the elements(n-1)

I am having trouble with coming up with a recurrence that expresses the worst case for good pivots. The two I came up with is if you choose a pivot of $\frac{n}{2}$ and if you choose a pivot of  $\frac{n}{4}$

The recurrence for a pivot of $\frac{n}{2}$ would be  $ T(n) =
\begin{cases}
c  & \text{if $n$ is 1} \\
2T(\lfloor(n/2)\rfloor) + n, & \text{if $n$ is > 1}
\end{cases}$
I wasable to reason this out because if you had a pivot of $\frac{n}{2}$, you have to evaluate all the elements with regards to the pivot(the $n$) and then partition the equal proportions to the left and to the right of the pivot.

The recurrence for a pivot of $\frac{n}{4}$ would be $ T(n) =
\begin{cases}
c  & \text{if $n$ is 1} \\
T(\lfloor(3n/4)\rfloor) + T(\lfloor(n/4)\rfloor) + n, & \text{if $n$ is > 1}
\end{cases}$

Which one of these would express the worst case for good pivots?

The worst case for the good pivot is one where you split in 3n/4 and n/4. Splitting into two equal parts of size n/2 is the best possible case you can have. On the other hand, for the good pivots, 3n/4 leaves you with the largest subproblem possible.


In Bankers Algorithm, with three processes, in the question of need <= work(aka available). Is the need of 1 0 1 <= 0 0 2 work? Three processes A B C.  When conducting the safety algorithm, no explanation that I've been able to find answers the question of how the processes are being compared. Is it the total processes added up, or every process individually must pass the '<=' operator, or is it like regular integers where Process A would be the most significant comparison?

https://www.youtube.com/watch?v=2V2FfP_olaA

TLDR Answer: It's individual based. Each process work/available item in the matrix, must satisfy each need.

In Banker's Algorithm,

Every processes are compared individually.

So, In your question

If the Need is 1 0 1 and available matrix is 0 0 2, then this need can't be satisfied. Because there is no resource available for Process A.


Dynamic Learning (Machine Learning) I have been given a task to dynamically learn the optimum value of a parameter in a Heuristics Filtering Algorithm used in a tool.

The accuracy of the tool increase as the value of K in the heuristics filtering algorithm increases. How ever a lower K leads the tool towards a low resource consumption (memory, time and temporary storage).

How can I dynamically learning the optimum value of K using Machine Learning techniques so that the tool can dynamically generate an optimal value of K.

I have been looking into Reinforcement Learning and learning from online resources. First, the problem has to be modeled as a Markov Decision Process (s, a, r, s'). I got stuck at what my State Space s should be. My set of actions a (they represent the value that k should be) are {10,20,30...,100}. Is Reinforcement Learning the way to go in the first place? If not, what other machine learning techniques do you suggest? I'm not into AI but I enjoy solving problems

First some questions:

Can $k$ only take on 10 possible values?
From what you've said above, the measure of the 'quality' of a given value for $k$ would be an n-tuple e.g. $(accuracy,memory, time, storage)$, right?

So 'dynamically learning a value for $k$' involves learning a good choice based on $L$, the list of n-tuples for previous values of $k$.

Here are two very simple schemes:

If your problem is genuinely multi-objective, then you can always just pick the associated $k$ at random from the Pareto-front of $L$.

If your multiple objectives can be combined into a single quality value, then fit a differentiable curve (e.g. a polynomial) to these values, then symbolically determine the optimum of that curve and the associated value of $k$. Most computer algebra packages support the functionality for this, as does the Apache Commons Math library for Java.


Data structure or algorithm for quickly finding differences between strings I have an array of 100,000 strings, all of length $k$.  I want to compare each string to every other string to see if any two strings differ by 1 character.  Right now, as I add each string to the array, I'm checking it against every string already in the array, which has a time complexity of $\frac{n(n-1)}{2}  k$.

Is there a data structure or algorithm that can compare strings to each other faster than what I'm already doing?

Some additional information:

Order matters: abcde and xbcde differ by 1 character, while abcde and edcba differ by 4 characters.
For each pair of strings that differ by one character, I will be removing one of those strings from the array.
Right now, I'm looking for strings that differ by only 1 character, but it would be nice if that 1 character difference could be increased to, say, 2, 3, or 4 characters.  However, in this case, I think efficiency is more important than the ability to increase the character-difference limit.
$k$ is usually in the range of 20-40.

My solution is similar to j_random_hacker's but uses only a single hash set.

I would create a hash set of strings.
For each string in the input, add to the set $k$ strings.
In each of these strings replace one of the letters with a special character, not found in any of the strings.
While you add them, check that they are not already in the set. If they are then you have two strings that only differ by (at most) one character.

An example with strings 'abc', 'adc'

For abc we add '*bc', 'a*c' and 'ab*'

For adc we add '*dc', 'a*c' and 'ad*'

When we add 'a*c' the second time we notice it is already in the set, so we know that there are two strings that only differ by one letter.

The total running time of this algorithm is $O(n*k^2)$.
This is because we create $k$ new strings for all $n$ strings in the input. For each of those strings we need to calculate the hash, which typically takes $O(k)$ time.

Storing all the strings takes $O(n*k^2)$ space.

Further improvements

We can improve the algorithm further by not storing the modified strings directly but instead storing an object with a reference to the original string and the index of the character that is masked. This way we do not need to create all of the strings and we only need $O(n*k)$ space to store all of the objects.

You will need to implement a custom hash function for the objects. We can take the Java implementation as an example, see the java documentation. The java hashCode multiplies the unicode value of each character with $31^{k-i}$ (with $k$ the string length and $i$ the one-based index of the character. Note that each altered string only differs by one character from the original. We can easily compute the contribution of that character to the hash code. We can subtract that and add our masking character instead. This takes $O(1)$ to compute. This allows us to bring the total running time down to $O(n*k)$


Bounded bin covering problem This all seems fairly related to the knapsack problem, bin packing and the subset sum problem, but I can't find the appropriate problem name.

I have a multiset $S$ of $n$ (not necessarily unique) integers in the range $\{1,2,\dots,k-1\}$.

The problem is to partition this multiset in submultisets such that each submultiset has a sum of at least $s$ and the number of submultisets is maximized.

For example $k=20 \wedge s=40 \wedge S= \{14, 19, 12, 19, 3,15\} \Rightarrow \{\{19, 19, 3\}, \{12, 14, 15\}\}$.

Is this a known problem? What is its complexity, considering $s, k$ are bounded small integers?

When $k,s$ are upper-bounded by a constant, the problem can be solved in polynomial time.

Call a multiset $T$ good if its sum is at least $s$, and if removing any one element causes the sum to fall strictly below $s$, and if all elements are in the set $\{1,2,\dots,k-1\}$.  How many good multisets are there?  Well, since $k$ and $s$ are constants, the number of such multisets is also a constant.  (A very crude upper bound is $k^s$, which is a constant.)

Let's write down an integer linear program that is equivalent to your problem.  We'll have an integer variable $x_T$ for each good multiset $M$, constrained so that $x_T \ge 0$.  The idea is that $x_T$ will count the number of times $T$ appears in the partition that constitutes the solution to your problem.  We obtain $k-1$ linear equations of the form

$$\sum_T m_T(i) x_T = m_S(i)$$

for each $i \in \{1,2,\dots,k-1\}$, where $m_T(i)$ denotes the multiplicity of $i$ in $T$.  Now our goal is to maximize $\sum_T x_T$, the number of multisets in the resulting partition.

Thus, we obtain an integer linear program in constant dimension: i.e., it has (at most) a constant number of variables and (at most) a constant number of linear inequalities.  It is known that integer linear programming in constant dimension can solved in polynomial time.  Therefore, your problem can be solved in polynomial time, too.

Of course, this doesn't necessarily mean the algorithm will be efficient in practice.  The constants that are hidden by asymptotic analysis are potentially huge.

As a side note, if $k,s$ are part of the input (not fixed) and all integers are provided in binary, the problem is NP-hard.  The special case where $s = \frac12 \sum_{i \in S} i$ is equivalent to the partition problem, which is NP-complete so your problem is NP-hard as well, assuming $k$ is part of the input.  So your promise that $k,s$ are upper-bounded by a constant makes a crucial difference to the complexity of your problem.


Costs of updating arrays to contain only zeroes To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also?

And in that case, setting an $n$-array to zero inside a loop with $n$ iterations should be $O(n^2)$, right? I am asking because I have written some code that does this, but the runtime only increases linearly when I increase $n$, not quadratically as I would have expected, so I don't quite understand. Is it perhaps to do with the compiler?

To initialize an array of length n has complexity O(n), as far as I understand. If I set every element to zero (with one code line), does that have time complexity O(n) also?

The answers to both questions depend on the machine model. In common ones, like e.g. the RAM model, writing every memory cell take a constant amount of time $c$. Hence, intializing an array of length $n$ takes time $cn + d \in \Theta(n)$, with $d$ being some constant overhead.

Now, doing

arr = new array[n]
for i = 0 to n-1
  arr[i] = some_value
end

incurs both the cost for initializing arr plus the cost for the for-loop, which is not too hard to analyse. It has, in fact, linear runtime cost (with common RAM-model assumptions).

  setting an n-array to zero inside a loop with n iterations should be O(n²), right?

I don't understand your algorithm perfectly, but if you mean above code with some_value = 0 then no. The total running-time cost is linear since costs add up.

If you mean something like

arr = new array[n]
for i = 0 to n-1
  setAllToZero(arr)
end

then it depends on how set_all_to_zero is implemented. If it contains an explicit loop, then we'd expect quadratic runtime cost. If there are machine-level instructions to set a whole stretch of memory to zero, it may be faster.

The same holds for array initialization, by the way: if the machine (model) does not guarantee any specific value after array intialization, or has some nifty way to ensure zeroes everywhere without extra cost, array initialization may only take constant time.


Is the language $\{ 0^m 0^n : 0 \leq m \leq n\}$ regular? Is the following language regular?
  $$ \{ 0^m0^n : 0\le m\le n \}. $$

According to me, it is not regular. However, some of my friends are arguing that every string in $0^*$ can be divided into $0^m0^n$ satisfying the constrains between $m$ and $n$, hence it is regular.

Although I am absolutely sure that their reasoning is false, they are thinking in reverse, I would like a third opinion.

Here is my proof of non-regularity:

Let us take $0^p0^{p+1}$ as a string.

Applying the pumping lemma, we find that the part with $0^p$ needs to be pumped. So, even if it is pumped by one 0 at a time, we will soon get $0^{p+2}0^{p+1}$, which violates the constraints between $m$ and $n$.

Some people can be absolutely sure, and at the same time absolutely wrong. In this case, you are one of those people.

A language is a set of strings. A language is not the rules that were used to express the language. $0^*$ and $\{0^m 0^n: 0 ≤ m ≤ n\}$ are the same language, even when that language is expressed in two different ways. And $0^*$ and $\{0^m 0^n: m ≥ n ≥ 0\}$ is again the exact same language, just expressed differently.

Your attempted "pumping lemma" proof fails for the same reason: For example, $0^5 0^4$ is in the language, because it is exactly the same string as $000000000$, which is again the exact same string as $0^0 0^9$.


Can the Euclidean distance function be computed using only XOR's The Eulidean distance function $d$ of $x$ and $y$ is given by:

$
d(x,y)=\sqrt{x^2-y^2}
$

Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. We could even assume that $x,y$ have precision $n$ decimal digits. Any facilitating representations of rational or real values $x,y$ that carries "enough" information is good. $x,y$ could also be assumed to be only positive.

Can the Euclidean distance function be computed using only XOR's? If this cannot be achieved, what other boolean functions would be needed?

No.  It's not possible.  Any function that can be computed using just XOR's is affine over $GF(2)$.  However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it with just XOR's.

Recall that $GF(2)$ denotes the finite field with two elements; you might also see it indicated by $\mathbb{F}_2$, and it is the field $(\{0,1\},\oplus,\times)$, where $\oplus$ represents the XOR operation (i.e., addition modulo two) and $\times$ represents the AND operation (i.e., multiplication modulo two).

Recall that a function $f$ is linear if it can be expressed as a linear map, i.e., $f(x+y)=f(x)+f(y)$ holds.  More specifically, suppose we have a function $f:GF(2)^n \to GF(2)^m$ that maps from a vector space over $GF(2)$ to a vector space over $GF(2)$.  Then $f$ is linear if $f(x \oplus y)=f(x) \oplus f(y)$ for all $x,y$, where $\oplus$ denotes element-wise XOR.  Equivalently, $f$ is linear if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1), such that $f(x) = Mx$.

A function $g$ is affine if it is of the form $g(x)=f(x)+c$, where $f$ is linear and $c$ is an arbitrary constant.  In our case, $g$ is affine if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1) and a constant $c \in GF(2)^n$, such that $g(x) = Mx+c$.  See, e.g., this Wikipedia article for more.

The XOR operation is linear.  Also, because the set of $GF(2)$-affine transformations is closed under composition (this follows because $(\{0,1\},\oplus)$ is a group), it is easy to see that any circuit built solely out of XOR's must be $GF(2)$-affine.  (Why affine, rather than linear?  Because a circuit can contain constants: it can take an input and XOR it with the constant 1.  That makes it affine, rather than linear.)

Now it is easy to verify that the Euclidean distance is not $GF(2)$-affine, just by looking at a few values: e.g., you can look at $d(0,0)$, $d(0,1)$, $d(1,0)$, $d(1,1)$.  If $d$ were affine, we would have the relationship

$$d(0,0) \oplus d(0,1) \oplus d(1,0) \oplus d(1,1) = 0.$$

Since this relationship does not in fact hold, $d$ is not $GF(2)$-affine.

And since $d$ is not an affine function of its inputs, this means it cannot be expressed using only XORs.

Certainly NAND gates would be sufficient, as they are universal. It could also be expressed using just XORs and ANDs, as those two are also universal.  There are many other options.


Why does the square root of n! grow exponentially faster than exponential functions? I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.

In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the probabilities of sampling all irreps, $|p - q|_1$ of a subgroup inside the symmetric group $S_n$.

$$
\begin{align}
|p - q|_1 &=  \Sigma_{\rho} \mid p_{\rho} - q_{\rho} \mid \\
          &\le \Sigma_{\rho} \frac{d_{\rho}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\
          &\le \Sigma_{\rho} \frac{\sqrt{n!}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\
          &\le \frac{2^{O(n)} \sqrt{n}^{n/2}}{\sqrt{n!}} \\
          &= 2^{O(n)} \frac{\sqrt{\sqrt{n}^n}} {\sqrt{n!}} \\
          &\le 2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)}
\end{align}
$$

How is $2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)}$?

$\log(n!)=\Theta(n\log n)$, (see Stirling's approximation), hence

$\frac{2^{O(n)}}{\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\log\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\Theta(n\log n)}=2^{-\left(\Theta(n\log n)-O(n)\right)}=2^{-\Omega(n)}$.


If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case? According to this source,

  If A is reduced to B and A ∈ class X, then B cannot be easier than X.  This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to the given problem. This reduction thus gives a lower bound for the complexity of B.

Now consider the following scenario: X is an NP-hard problem. It is polynomial-time many-one reducible to problem Y. This makes Y NP-hard. My question is, it could be possible that X has a better solution like NP or P, which we could not find. Then why should Y be NP-hard? It could be NP or P. If Y turns out to be P (assume) then X becomes P.

All NP-complete problems are "equally hard", in the sense that if one of them is in P, then all of them are in P. Similarly, if one NP-complete problem can be solved in quasipolynomial time (that is, time $e^{O(\log^C n)}$ for some constant $C$) then all of them can be solved in quasipolynomial time.

Some NP-hard problems are harder than others, but all of them are at least as hard as all NP-complete problem. That is, if some NP-hard problem is in P, then all NP-complete problems are in P. Similarly, if some NP-hard problem can be solved in quasipolynomial time, then the same holds for all NP-complete problems.

However, some NP-hard problems are provably harder than others. For example, the halting problem is NP-hard, but in contrast to all NP-complete problems, it cannot be solved in exponential time; in fact, it cannot be decided at all!

  My question is, it could be possible that X has a better solution like NP or P, which we could not find.

There are two problems with this statement. The first is the assumption that NP is a better complexity class than NP-hard. In fact, all NP-complete problems are both NP-hard and in NP (that's the definition of NP-completeness), so it's in fact common for problems to be both. NP-hardness is a lower bound on complexity, whereas being in NP is an upper bound. The two are not contradictory in any way.

The second problem is the assumption that it could be possible that X is in P. As explained above, that would imply that P=NP, which most people consider unlikely. An NP-hard problem cannot be "easy" – it's at least as hard as any problem in NP, and in particular at least as hard an any NP-complete problem.

  Then why should Y be NP-hard?

You can prove that Y is NP-hard if you can reduce, in polynomial time, another NP-hard problem X to it. I won't repeat the proof here, since it can be found in textbooks, lecture notes, and even here on Computer Science.

  If Y turns out to be P (assume) then X becomes P.

That's correct, but there is no contradiction here. This is actually the point of NP-hardness. We don't believe that Y is in P, since that would imply that X, as well as many other problems, are also in P.


Algorithm for matching people I work at a summer camp where one of the activities is called Speed Dating. It's a game where participants talk with each other for a fixed amount of time. At the end everyone has to list three people they liked the most.

I'm looking for an algorithm that would match participants based on their preferences. It seems like it's the Stable marriage problem that could be solved using Gale-Shapley algorithm. However every implementation of this algorithm I've seen assumes that the number of men and women is equal and every person has to rank everyone from the opposing gender.

So my question is:

How can I ensure that all "marriages" are stable given that:

Participants are divided into two groups unequal in size
Every participant provides a ranked list of only three people from the opposing group they like the most
Some of the participants might list no people
Not everyone has to be matched
A "marriage" is stable only when two people have picked each other (regardless of their ranks)

This is the problem of finding a matching in a bipartite graph.  Each person is represented as a vertex in the graph, and you draw an edge between two people if they both have included each other on their rankings.  Then any matching corresponds to a way to match people.  There are standard algorithms that can find a maximum matching in a bipartite graph efficiently, so you'll even be able to find a pairing that maximizes the number of stable pairs created.


Finding a minimal width strip which encloses a set of points in the plane Problem: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points?

Definitions: A strip is defined by two parallel lines and the vertical distance is defined as the distance between their intersection points with the $y$ axis.

3 variables solution: In the plane itself, this could be solved using a linear program of three variables, $m$, $a$ and $b$ where we look for $y=m\cdot x+a$ and $y=m\cdot x+b$.

Duality: If we move to the dual plane, we get a set on $n$ lines which can be transformed to $n$ upper half-planes or $n$ bottom half-planes. Denote $C_1$ to be the intersection of all upper half-planes intersection and $C_2$ of the bottom ones. The strip in the dual problem is represented by the two ends of the shortest vertical segment crossing the $C_1$ and $C_2$.

My question is - can we express the problem in the dual plane using a linear program of two variables?

Take the convex hull of your set of points. Then use "rotating calipers" to
find the optimal strip.
What is needed here to make this work is a lemma that characterizes a
potentially optimal solution: Could the optimum occur without one supporting line
through two points ("flush" to the hull)?

Added. Yes, that flush-lemma holds, because more-horizontal strips are preferred. So: for each edge $e$ of the convex hull $H$,
extend $e$ to a line $L_1$, and let $L_2$ be
the parallel line supporting $H$ on the other side. Compute the vertical distance between $L_1$ and $L_2$.
Select the shortest distance among all alternatives.


I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem? There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable asking the girl out [Ai, Bi] (inclusive). A boy will not ask someone out who is below Ai or above Bi.

I need to pair as many of them as I can for a single dance in O(n*logn) time.

I tried building some kind of a tree in O(n) and then using that three in O(logn) repeatedly against the whole list. I've spent some solid 3 hours on this problem and I'm really not getting anywhere. I've tried to build a dependency tree, I've treed weighted priority queues. I considered some constraint satisfaction algorithms, but as far as I recall they are all nowhere near  O(n*logn).

Nothing seems to work. But I do clearly see that this has to be reduced to some other standard computer science problem.

However I've had no luck looking up "load balancing" or "pair assignment". I've no idea what are the right keywords.

This seems the be the kind of problem data centers have when assigning load to virtual machines. Or web requests over the world for large web sites. For example a server can sustain a load in [Ai, Bi] range (let's say RAM in GB's 4-8GB) and our target application needs 5GB. Now let's say we have n of both of these (target applications and servers). How to pair them so as much get paired? Thanks.

Algorithm: Pick girl #i where $P_i$ is as high as possible. Eligible boys are those with $A_j ≥ P_i ≥ B_j$. If there is no eligible boy then she is not matched, otherwise match her with eligible boy #j, where $B_j$ is as large as possible. Then match the remaining boys and girls in an optimal way.

If instead you match her with boy #k or with nobody, then you can just swap boy #j and boy #k, and you get a result either as good as promised.


Shortest path in divisors graph There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. Given two vertices u and v, I want to find the length of the shortest path between them. I think that the shortest path should pass through gcd(u, v) or lcm(u, v) (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct? If it is not correct, then how to solve this? It is not my homework.

Given two vertices $u$ and $v$, I want to find the length of the shortest path between them. I think that the shortest path should pass through $\gcd(u, v)$ or $lcm(u, v)$ (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct?

I think the claim is not strictly true as written, and I will provide a counter-example.

First a claim: For any two vertices in this graph, there is a shortest path between them which uses only edges whose weight is a prime.

Pf: If the weight is not a prime, it can be factored, and this yields a different path between the same two vertices. The sum of any sequence of positive numbers all at least 2 is less than or equal to their product (trivial, by induction), so that is a shorter path, which can be substituted into the original in place of the non-prime edge.

(Note that a slightly stronger thing we could say is "shortest paths can only contain edges whose weight is a prime or is 4", proof left to reader.)

Now take two arbitrary non-prime coprime numbers, say, 6 = 2 * 3, and 35 = 5 * 7.

Clearly, a shortest path using only prime edges has at least 4 steps.

Also, we can ignore the possibility of a shortest path using edges corresponding to primes which are not {2, 3, 5, 7} -- by commutativity of multiplication, any such edges can be reordered until the end, without changing the weights of any of the edges, and the total effect of any such edges for primes which were not originally involved must be a loop, so in fact they could be skipped.

It follows (from this argument) that the shortest paths from 6 to 35 are in bijection with orderings of {2, 3, 5, 7}. They all have the same cost, which is 2 + 3 + 5 + 7.

Some of them pass through the lcm or gcd, but some do not. For instance, 6 -> 2 -> 10 -> 70 -> 35.

I think you can prove that there is a shortest path passing through the gcd? And there is a shortest path passing through the lcm?

I think the idea to prove that would be, look at the edges in the path, and look at which ones make the number larger, and which ones make the number smaller. Then rearrange the edges using commutativity of multiplication as before. If you sort it so that those that make the number larger come first, and then are followed by those that make the number smaller, then in the middle I think you pass through the lcm. If you sort it so that those that make the number smaller come first, then I think you pass through the gcd.


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

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

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

I am assuming that you are given the flow on each edge which corresponds to the maximum flow for the graph $G$. So $f_e$ is the flow on edge $e$.

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

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

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


Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week.

For N number of meals per day, find permutation of recipes that comes the closest to satisfying these conditions:

Sum of meal calories ~= my defined daily calorie limit
Average recipe macros* (weighted by recipe calories) ~= my desired macros (i.e. (30/40/30))

(*: Macros are the ratio of carbs/protein/fats in a meal, and are usually found in a tuple form: (CC/PP/FF))

Each recipe can be assumed to be in the form:

'name': {
   'calories': a,
   'protein': b,
   'carbs': c,
   'fats': d
}

In other words:

Inputs: n_meals, max_cals, (cc,pp,ff) # <- macros
Output: [recipe_1, recipe_2, ..., recipe_n]

I have no formal training in algorithms, so I'm not really sure where to start. The naive approach would be to take every permutation of recipes in the list and use the permutation which satisfies the criterion the closest.

This is definitely a multi-dimensional optimization problem but that's the depth of my knowledge. Perhaps something like a breadth-first search algorithm would be most appropriate?

Thanks all.

You could formulate this as an instance of integer linear programming.  You use zero-or-one variables $x_{ij}$, with the intended meaning that $x_{ij}=1$ if you assign recipe $i$ on day $j$.  Then your restrictions can be expressed as linear inequalities (e.g., $\sum_i x_{ij}=3$ means you eat 3 meals per day, $\sum_j x_{ij}=1$ means that you eat each recipe once).  You introduce a variable $y$ that expresses how far off from the goals you're allowed to be; then the restrictions on calories and macronutrients are also linear.  Finally, you feed this to an off-the-shelf ILP solver to minimize $y$.

Or, assuming you have three meals per day, you could generate all possible ways to pick a single day's menu that meets the calory requirement for that day, then exhaustively explore all possible ways to combine those daily menus into a week's worth of menus.


Prove existence of different programs printing each other code How to prove that there exist two different programs A and B such that A printing code of B and B printing code of A without giving actual examples of such programs?

You maybe know the recursion theorem. It implies, that you can assume that you have a procedure called get_your_own_codeif your programming language is at least as powerful as a Turing machine.

Now do the following

Progr. A
w=get_your_own_code
print "print "+w

Note that some code is hidden in the subroutine of get_you_own_code. So we assume the complete source code is a string called source_code_of_A.

Progr. B
print source_code_of_A

Program A prints:

  print source_code_of_A

Program B prints

  source_code_of_A


Counting inversions in an array of 1 to N Is there a straightforward way to characterise the number of inversions in an array of length N having distinct elements, each element an integer from 1 to N?

It's for a constraint optimization problem, where the number of inversions needs to be minimized.

You can count inversions efficiently by adapting mergesort, but the most intuitive way is to just count all pairs:

$$\text{inv}(A) = \sum_{i=1}^{|A|}\sum_{j=i+1}^{|A|}[A_j<A_i]$$

Where $[A_j < A_i] = 1$ when $A_j < A_i$ and $0$ otherwise.


the meaning of heuristics in artificial intelligence I would like to know what 'heuristics' actually means in artificial intelligence. For example, I am reading a paper by Engelbrecht on the convergence analysis of the particles of the algorithm. The section where the author discusses the mathematical reasons why the particles behave the way they do was entitled 'heuristics'. Does it, in any way, mean ... the mathematical rigour, methodology, convergence, etc?

Your insights would be helpful.

Heuristics typically have very little to do with rigor. (But you can surely study them in a rigorous way). They are rule of a thumb methods for solving (usually computationally difficult) problems, and typically they perform quite well in practice. In other words, there might not be any formal guarantees on the solution quality you get by running a heuristic, but experience and empirical analysis shows they can be quite effective. Arguably, it is rarely the case we understand their behaviour well.

Sometimes, when heuristics are analyzed formally, they turn out be to approximation algorithms. That is, methods for solving a problem with a formal guarantee on the solution quality. For example, one might have observed a heuristic usually works well, and an analysis proves it will always give a solution which is at most twice the optimum.

Perhaps in your particular case, the section "Heuristics" contains explanations (more or less formal) as to why the heuristic behaves or is expected to behave in certain ways when run.


Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \} $ Turing recognizeable? I'm working on the following problem:

  Is the following language Turing recognizable (recursively enumerable)
  ?

  $$L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not
> accept}\ 010 \} $$

The way I see it: Suppose that a machine $M$ loops forever on $010$. If a $TM$ recognizes $L$, it should accept $M$ in that case. But that means that it should know if $M$ loops forever or not, which is not possible. So, $L$ is not Turing recognizable.

Is my proof correct, and can it be more formal?

You are presenting an argument which falls short of being a proof. In particular, it is not clear why a Turing machine recognizing $L$ should know whether $M$ loops forever or not; indeed, it is not so clear what do you mean by know in this context.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can decide whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.


Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.

More precisely, given a triplet $(i,j,k)$ with $i<j<k,$ it satisfies the question above if $A[i] \times A[j] \times A[k] = target$ and either ($j = i+1$ and $k > j+1$) or ($k = j+1$ and $i < j -1$.)

For example, if the list given is $A = [1,2,2,2,4]$ and target $= 8,$ then the answer is $2$ as $(0, 1, 4)$ and $(0, 3, 4)$ are the only triplets satisfying conditions above if we use $0$-based numbering.

I stucked at this question for 3 hours and not able to solve it.

Any hint is appreciated.

Let $n$ be the number of integers and $t$ be the target integer.
You can solve your problem in $O(n \log n)$ time as follows:

For every $i=0, \dots, n-1$, let $p = A[i] \cdot A[i+1]$ and compute, in $O(\log n)$ time, the number $\eta(t/p)$ of integers in $A$ that are equal to $t/p$ (more on that later).
Then the number $\gamma_i$ of triplets formed by $A[i]$, $A[i+1]$ and a non-adjacent element is $\gamma_i = \eta(t/p) -  |\{A[j]=t/p \, : \, i-1 \le j \le i+2 \}|$.

It follows that the number of triplets of interest is $\sum_{i=1}^{n-1} \gamma_i$.

To find the values  $\eta(\cdot)$ do a preprocessing in which you create a copy $B$ of $A$, sort $B$ in $O(n \log n)$ time, and append an element with value $+\infty$ to $B$ (this is just to avoid edge cases, $+\infty$ can actually be any integer greater than $t$).

If $x \not\in\mathbb{Z}$, $\eta(x)=0$. Otherwise $\eta(x)$ can be found in $O(\log n)$ time by binary searching for the smallest indices $i$ and $j$ in $B$ such that $B[i]\ge x$ and $B[j] > x$, respectively. Notice that $i$ and $j$ are always well defined and that $\eta(x) = j-i$.


Why is $NP \subseteq P \implies NP^A \subseteq P^A$ false? My question is about why does the result of Baker-Gill-Solovay not prove that $P \neq NP$. There have been several questions on this forum about this topic perhaps but I couldn't find my specific question amongst them.

Context: This is what I had in mind when I first saw the Baker-Gill-Solovay result (there exists an oracle $A$ such that $P^A \neq NP^A$): I will try to give a proof for $P \neq NP$. Suppose $P=NP$ then $P^A = NP^A$ for all oracles $A$. By Baker-Gill-Solovay result we arrive at a contradiction. When I asked my prof about this he said that the implication $P=NP \implies P^A = NP^A$ is wrong. So I wanted to check why (and where) does it fail.

I think it is correct that $P \subseteq NP \implies P^A \subseteq NP^A$ for all oracles $A$ because any poly-time TM with oracle access to $A$, is also a poly-time NDTM with oracle access to $A$.

My question is: Why (if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$) is false?

My reasoning would go as follows: $NP \subseteq P$ means that given any NDTM (which involves a guessing sequence, followed by a poly-time verification), I can replace the guessing sequence with some poly-time TM. But given a NDTM with oracle access to $A$, I cannot directly replace the guessing sequence with some poly-time TM (as per the hypothesis), because in this NDTM, the guessing sequence might involve the access to oracle $A$.

Following that, I want to argue why isn't it so, that given a NDTM with oracle access to $A$, I can move all these calls to oracle $A$, after the guessing sequence? That is to say - why couldn't I, using non-determinism, guess the answers to my oracle queries and in the final step, verify these particular guesses using actual oracle queries?

More precisely, can I not re-define the definition of $L \in NP^A$ as follows: there exists a poly-time TM $M$ and a polynomial $p$ such that $x \in L \iff \exists w$ such that $|w| \leq p(|x|)$ and $M^A(x,w) = 1$?

Apologies for being too vague in my arguments above but I have just started learning Complexity Theory.

Edit1: Changed the question from
given a oracle $A$, if $NP \subseteq P$ then $NP^A \subseteq P^A$ to if $NP \subseteq P$ then for any oracle $A$, $NP^A \subseteq P^A$

Edit2: My definitions are: $P^A$ is the set of languages decided by a poly-time TM with oracle access to $A$ and $NP^A$ is the set of languages decided by a poly-time NDTM with oracle access to $A$

Edit3: Added more context to the problem.

Your statement holds for all oracles $A$ iff $\mathsf{P} \neq \mathsf{NP}$. Indeed, if $\mathsf{P} \neq \mathsf{NP}$ then your statement vacuously holds. Conversely, if $\mathsf{P} = \mathsf{NP}$, then your statement fails for a random oracle $O$, since such an oracle satisfies $\mathsf{P}^O \neq \mathsf{NP}^O$ almost surely.

A similar argument shows that if $A$ is a $\mathsf{PSPACE}$-complete language then your statement holds, since in that case $\mathsf{P}^A = \mathsf{NP}^A$ is known to hold.

The proof that $\mathsf{P} \subseteq \mathsf{NP}$ relativizes, which means that it works even in the presence of an oracle. That is, the proof only uses arguments that keep holding even when the Turing machines are allowed access to an oracle. In all other cases, you cannot conclude from a statement of the form $\mathsf{A} \subseteq \mathsf{B}$ that $\mathsf{A}^O \subseteq \mathsf{B}^O$ for all oracles $O$. The two statements are about two different objects: the first one is about Turing machines without oracle access, and the second one is about Turing machines with oracle access to $O$.

This actually happens in practice, as mentioned in the comments: $\mathsf{IP}=\mathsf{PSPACE}$, but there are oracles $O$ relative to which $\mathsf{IP}^O \neq \mathsf{PSPACE}^O$.


Not respecting the 3rd rule of a LL(1) grammar I'm trying to build a grammar that violate only the 3rd rule. I'm trying to figure out what kind of grammar would not respect that.

I think the grammar has to be left-recursive to not respect it.

if $\beta \Rightarrow^* \epsilon$ then $\alpha$ does not derive any string beginning with a terminal in $\mathop {FOLLOW}(A)$. Where $A \to \alpha \mid \beta$

Am I right to think that?

Something like the following:

$\begin{align}
  S &\to A a \\
  A &\to a \mid \epsilon
\end{align}$


Converting Binary Search Tree into Decreasing Ordered Linked List Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the function should be toList(T, L), where T is the root of the tree and L is a linked list.
The only operation that allowed to use in the linked list is InsertFront.
My attempt:
toList(T , L){
   if (T == null) return
   toList(T.right , L)
   InsertFront(T)
   toList(T.left , L)
}

What do you think about that?
Any suggestions will be great!
Thanks a lot!

The idea seems alright, just a tiny bit of comments:

InsertFront(T) should instead be InsertFront(T.root) (or you will get a linked list of trees).
As is, your function takes two arguments: a tree T and a linked list L, and add the in-order of T in front of L, and returns nothing. If you want a function that returns the in-order, you could add:

inOrder(T){
   L <- empty linked list
   toList(T, L)
   return L
}


confusion with worst case for direct addressing In CLRS there is an exercise for direct address table

  Suppose that a dynamic set S is represented by a direct-address table
  T of length m. Describe a procedure that finds the maximum element
  of S. What is the worst-case performance of your procedure?

for this question i have seen a lot of websites indicating the worst case possibility is O(m) by starting and examining every non null slot up to end and then returning the maximum index,
but i think it can be done in a faster way than that.
 If direct addressing tables has m slots , then obviously the highest value should be in the end (i thought keys are treated as indexes in direct addressing,correct me if i am wrong) , so if we start iterating from the end then worst case would be O(m-n) where n is the number of elements examined by our iterator before reaching  non null value from end of the direct addressing table

is something wrong with my approach? Can any one clear this topic?

When iterating from start to end, you always need to examine $m$ items, which is $O(m)$.
When iterating from end to start, in the worst case you need to examine $m - |S|$ items, then the answer depends on the relationship between $|S|$ and $m$.

If $m - |S|$ is const., it takes $O(1)$ time.
Otherwise since $0 \leq |S| \leq m$, we have $m - |S| \leq m$, the upper bound is also $O(m)$.

Then in either cases, as long as $m - |S|$ is not const., both approaches have $O(m)$.


About randomness and minmax algorithm with alpha beta pruning Will choosing the child of a node randomly in the alpha beta algorithm have a better chance to get a cut off than choosing them in order?

Here's the pseudocode with my addition marked with ***.

function alphabeta(node, depth, α, β, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node
     arrange childs of node randomly ***
     if maximizingPlayer
         v := -∞
         for each child of node
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
             α := max(α, v)
             if β ≤ α
                 break (* β cut-off*)
         return v
     else
         v := ∞
         for each child of node
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break (* α cut-off*)
         return v

I ran a small sample with this on a connect four game and it does seem to run a little faster, but when I actually count the cutoffs with and without randomness, there are more cutoffs without randomness. That's a little odd.

Is it possible to prove that it's faster (or slower)?

It's neither faster nor slower, since it depends on your order. Your order might be the best possible order, in which case randomness hurts; or it might be the worst possible order, in which case randomness helps.

If you want to guarantee not hitting a worst case behavior, you can use randomness. But it might be better to choose the order heuristically using less than full randomness.


Given 3 disjoint Turing-recognizable languages prove that one of them is decidable Let $A$, $B$, $C$ be Turing-recognizable languages over an alphabet $\Sigma$. Assume that

$A\cup B\cup C = \Sigma^*$, and
$A\cap B = A\cap C = B\cap C = \emptyset$.

Prove that $A$ is Turing-decidable.

So far I've tried the following but it really hasn't gotten me anywhere.
Suppose $A$ is recognizable but not decidable then, $\overline{A} = B \cup C$ so $B$ or $C$ is undecidable, since decidable languages are closed under union.
In the case that only one is decidable you can show at least that its in $A$ or $B$ (or $A$ or $C$ in the other case). Then, ... ?
In the case that both are recognizable, ... ?

Let's call MA, MB and MC the Turing machines that recognize A, B and C, respectively. The 3-TM T (a Turing machine with 3 tapes) that decides A can be described as follows:

T: input x.

Copy x on 2nd and 3rd tapes.
T executes one step of MA on tape 1. If MA accepts x, T accepts x.
T executes one step of MB on tape 2. If MB accepts x, T rejects x.
T executes one step of MC on tape 3. If MC accepts x, T rejects x.

T halts for every string x in A U B U C, so T halts for every input in Σ*. Moreover, L(T) = A. So T is a TM that decides A, and A is Turing-decidable.


Is the union of 2 non context free languages always non context free? Let $L_1 = \{a^nb^nc^n\}$
and $L_2 = \{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\}$ (which I think is a non Context free but I am not sure)

So, $L_1 \cup L_2$ will give $L_3 = \{a^*b^*c^*\}$ which is a CFG.

Is this correct?

As you suspected, the union of two non context-free languages may be context-free.

For example, $\{a^nb^nc^n\mid n\ge0\}\cup\{a^nb^nc^m \mid  m,n\ge 0,m\ne n\,\} = \{a^nb^nc^m\mid m,n\ge0\}$.

For a simpler example, $\{a^{n^2}\mid n\ge 0\}\cup\{a^{m}\mid m \text { is not a square}\} = \{a^{n}\mid n\ge 0\}$.

In fact, by a counting argument on countably infinity, for almost all languages $L$, both $L$ and its complement $\overline L=\Sigma^*\setminus L$ are non context-free (and even non context-sensitive), where $\Sigma$ is the (nonempty) alphabet. Their union, $\Sigma^*$ is context-free (and, actually, regular).

Your example is not correct since $L_3\setminus L_1 = \{a^nb^mc^k\mid n,m,k\ge0, n\ne m\}\cup \{a^nb^mc^k\mid n,m,k\ge0, m\ne k\}$ is a union of two context-free languages, hence also context-free.


Upper bound for the time complexity of a TM in P on input x? I am trying to show that the following problem is P-complete with respect to LOGSPACE reductions: given a Turing machine $M^*$, an input $x$ for that machine, and a number $t$ in unary, does $M^*$ accept $x$ in $t$ steps?

To do that I want to compute an upper bound on the time complexity of some TM $M$ in P on input $x$. I tried to use the maximum number of configurations, but failed because I don't know the space complexity either - I only know that space and time complexities are polynomial.

The complexity class P is a set of languages, not a set of Turing machines. A language is in P if it is accepted by some Turing machine running in polynomial time. So for every language $L$ in P, there is a Turing machine $M$ that accepts $L$ and runs in time $p(n)$ for some polynomial $p$, where $n$ is the input length. This is exactly the time bound you're after — its existence is guaranteed by the definition of P.

To show that the problem you were given is P-complete, you need to show that every language in P reduces to your problem. In other words, you need to show that for all languages $L \in P$ there exists a polytime reduction from $L$ to your problem. The reduction accepts an instance of $L$, and can depend on $L$ arbitrarily.

What you seem to be trying to construct is a function with two inputs: a language $L \in P$ (given as a polytime Turing machine) and an instance $x$ of $L$. There is absolutely no need to construct such a function.


Complexity of Merge Sort that splits in a random position I got a question that I don't fully understand:
Given a new algorithm to merge sort (AKA mergesort2) that instead of splitting the list in the middle it splits the list in a random number between $1$ and $n-1$.
Also, we know the probability of getting $1$ is $2/n$ and to every other number $1/n$.

I have tried again and again and came up with the regular when doing the "average case" $\Theta \ (n \log n)$ and of the merge sort algorithm and "worst case" $O (n^2)$ but I'm not sure about it.

Pseudo-Code:

   MergeSort2(A,p,q)
     if(p=q) then return
     i = random number from (1...q-p)
     MergeSort2(A, p,   p+i-1)
     MergeSort2(A, p+i, q)
     Merge(A, p, p+i-1, q)

How I did the calculations of the $O (n^2)$ "worst case" when I split it to $1$ and to $n-1$ every time: (if it's correct)

$$T(n)= T(1)+T(n-1)+O(n)$$

When $T(1)$ is the single number, $T(n-1)$ is the rest list and $O(n)$ is the merge

$$\begin{align*}
T(n) &= (T(1)+T(n-2)+O(n)) + T(1)+O(n) & \text{second recursive call}\\
     &= (T(n-3)+T(1)+O(n)) +2T(1)+2O(n) & \text{third recursive call}\\
     & \vdots\\
T(n) &= T(n-k)+kT(1)+kO(n) & k^{th}\text{ recursive call}
\end{align*}$$

Now we know that $T(1) = O(1)$ as it doesn't do anything.

In order to get to our stop condition, we need the $T(n-k)$ will be $T(1)$.

So to do so we will take $k = n-1$.

Therefore we will get the following:

$$T(n) = T(1)+(n-1)O(1)+(n-1)O(n) \implies T(n) = O(n^2)$$

How do I calculate properly the complexity of the given algorithm?

For definiteness, let us suppose that the $T(1) = 1$ and that if the split is $k+(n-k)$ then the running time is $T(k) + T(n-k) + n$.
The recursion for the worst-case running time is therefore
$$
T(n) = \begin{cases} \max_{1 \leq k \leq n-1} T(k) + T(n-k) + n & \text{if } n > 1 \\ 1 & \text{if } n = 1. \end{cases}
$$

In order to calculate the worst-case complexity, we need both an upper bound and a lower bound. You already gave the lower bound:
$$
T(n) \geq T(1) + T(n-1) + n = T(n-1) + n+1.
$$
Iterating this easily yields $T(n) = \Omega(n^2)$.

In the other direction, let us prove that $T(n) \leq n^2$ for all $n$. The base case is clear. For the inductive case,
$$
T(k) + T(n-k) + n \leq k^2 + (n-k)^2 + n \leq 1 + (n-1)^2 + n = n^2 - n + 2 \leq n^2,
$$
since $n \geq 2$. It follows that $T(n) = \Theta(n^2)$.

(In fact, with some more work you should be able to show that $k=1$ is indeed (together with $k=n-1$) the worst choice.)

Let us now proceed to the average case running time (i.e., the expected running time), which satisfies the recurrence
$$
S(n) = \begin{cases} \frac{1}{n-1}\sum_{1 \leq k \leq n-1} [S(k) + S(n-k)] + n & \text{if } n > 1 \\ 1 & \text{if } n = 1. \end{cases}
$$
We can simplify the inductive case to
$$
S(n) = \frac{2}{n-1} \sum_{1 \leq k \leq n-1} S(k) + n.
$$
This implies that for $n \geq 2$,
$$
n S(n+1) = 2(S(1) + \cdots + S(n)) + (n+1)n, \\
(n-1) S(n) = 2(S(1) + \cdots + S(n-1)) + n(n-1).
$$
Subtracting gives
$$
nS(n+1) - (n-1)S(n) = 2S(n) + 2n \Longrightarrow nS(n+1) = (n+1)S(n) + 2n \Longrightarrow \\ \frac{S(n+1)}{n+1} = \frac{S(n)}{n} + \frac{2}{n+1}.
$$
This shows that
$$
\frac{S(n)}{n} = \frac{2}{n} + \frac{2}{n-1} + \cdots + \frac{2}{2} + \frac{S(1)}{1} = 2H_n - 1 = \Theta(\log n),
$$
and so $S(n) = \Theta(n\log n)$.


What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't I'm taking a graduate course on the theory of functional programming, based on Paul Taylor's "Practical Foundations of  Mathematics." I understand the statement of Tarski's theorem about how for any $\omega$-compelte poset $X$, and any $\omega$-continuous function $T:X\rightarrow X$, that $T$ has a fixed point which is the join of (The statement and proof can be found here).

What I want to know is, how is this applicable, other than being a proof that the Y-combinator exists? It just seems to me that it says "we can use recursion to build a function that is defined for all natural numbers", where we could use some other recursive type for numbers. Doesn't the existence of the Y-combinator show the same thing?

If by Tarski's fix point theorem you mean the Knaster–Tarski fixpoint theorem, then it's widely applicable and very general. All you need is a complete lattice and a monotone function on the lattice.  There are many rather different examples of those.
Tarski-Knaster is for example used in the coinductive definition of bisimilarity. Another application is to construct models of logical formulae (e.g. for logics with fixpoints, such as
the modal $\mu$-calculus and the various fixpoint logics that are used to characterise complexity classes). It is also used in set theory and in program analysis.

The Y-combinator on the other hand is a specific piece of syntax in the $\lambda$-calculus. You don't need to prove the existence of the Y-combinator.


PAC learning axis parallel rectangles I am trying to understand the proof that the axis parallel rectangles are PAC learnable in the realizable case. This means that given $\epsilon, \delta$ with enough data we can find a function $h$ such that $$\mathbb{P}\left[\text{error} > \epsilon\right] \leq \delta$$
Here error can be seen as the probability of making an error with our chosen function $h$.

Now, for axis parallel rectangles (in binary classification) the usual argument goes like this, let $R$ be the true rectangle and let $R'$ be the smallest rectangle containing the positive examples, clearly $R' \subseteq R$, we consider the four rectangular strips between $R'$ and $R$. Clearly if all of them have probability $\leq \epsilon/4$ then the probability of making an error is less than $\epsilon$, so we can assume that at least one have probability of making an error $\geq \epsilon/4$.

For such a strip the probability of correctly classifying all the $m$ training examples is at most $(1 - \epsilon/4)^m$, and thus taking aunion bound over all strips we get that the probability of correctly classifying everything is less than $4(1-\epsilon/4)^m \leq 4e^{-m/4}$, and with a bit of algebra this yields that the sample complexity is $m \geq (4/\epsilon)\ln(4/\delta)$.

Here is a pdf that explains in a bit more detail, with some pictures, I just had to condense the argument as much as I can to fit it in here.

My question is, why do we have to consider the four rectangular strips separatedly, why can't we just say that the probability of the region between $R'$ and $R$ has to be greater than $\epsilon$ (because otherwise we are done), and thus using the same argument we would arrive at the better bound $m \geq (1/\epsilon)\ln(1/\delta)$?

Sorry for the long question, and thanks in advance.

The question is a little vague, but it seems like what you want to argue is along the line of this: Let $R$ be the concept to learn, and take any $R^*\subset R$ be any rectangle covering a $(1-\epsilon)$-fraction of $R$.  Then with some probability $R'$ will contain $R^*$.

The problem with this is that the particular probability depends on the specific choice of $R^*$.  I think what you're confused about is that want $R'$ to perform well on unseen examples.  By construction $R'$ will correctly classify all the training data.  The bad event is actually that all of the training data is concentrated in too small a rectangle; this happens with probability at most that of the event that one of the strips is missed by all the training examples.


For which values of $m$ is $m$-partition hard? Consider the following reduction: $m$-colouring to $m$-partition.

Define an $m$-partition as: Given an undirected graph $G = (V, E)$ and an integer $j$. Does there exist a partition of the vertices into $m$ parts $\{V_1, V_2, \ldots , V_m\}$ such that at least $j$ of the edges have their endpoints in different parts of the partition?

I was able to come up with the reduction, but now I'm stuck at this question:

What I need to find is the values of $m$ where the reduction implies that $m$-Partition is NP-complete?

The $1$-partition problem is trivial, since there is only one possible partition.

The $2$-partition problem is the same as MAX-CUT, which is known to be NP-complete.

For $m > 2$, the $m$-partition problem is NP-complete by reduction from $m$-coloring, which is NP-complete for that range of $m$.


Can a Turing Machine (TM) decide whether the halting problem applies to all TMs? On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets.  This question is somewhat different.

It asks whether the fact the halting problem applies to all TMs can be decided by a TM. I believe the answer is no, and wish to check my reasoning.

Define the meta-halting language $L_{MH}$ as the language composed of TMs  that decide whether a TM halts.

$$L_{MH} = \{ M : \forall_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\}$$

$L_{MH}= \emptyset$ due to the halting problem.

Thus, the title question more precisely stated: is it decidable whether $L_{MH} = \emptyset$?

Per Rice's theorem, it is undecidable whether an r.e. language is empty.
In both cases, if $L_{MH}$ is or is not r.e., it is undecidable whether $L_{MH} = \emptyset$.
Therefore, it is undecidable whether $L_{MH} = \emptyset$.

This proves a TM cannot decide whether the halting problem applies to all TMs.

Is my understanding correct?

UPDATE:
I am trying to show that a TM cannot "prove the halting problem" for some definition of "prove" that seems intuitively correct.  Below is an illustration of why I think this is correct.

We can create a TM $M_{MH}$ that generates $L_{MH}$ in the following way.  The TM takes a tuple $(M_i,M_j,w_k,steps)$.  It simulates $M_i(M_j, w_k)$ for $steps$ iterations. If $M_i$ accepts all $(M_j, w_k)$ pairs that halt, and rejects all others then $M_{MH}$ accepts $M_i$.  Otherwise, it rejects $M_i$ if $M_i$ decides incorrectly or fails to halt.

$M_{MH}$ does not halt, because it must evaluate an infinite number of pairs for each $M_i$.  Additionally, all the $M_i$s will fail to halt.  $M_{MH}$ will be unable to accept or reject any $M_i$ as it will not know from the simulation that all $M_i$s will fail to halt.  Thus, the language it defines is not r.e. and not decidable.

$M_{MH}$ captures my intuition of what I think it means for a TM to prove the halting problem.  Other suggestions, such as $M_{MH}$ rejecting all $M_i$ or outputting a known proof give $M_{MH}$ prior knowledge that the halting problem applies to all $M_i$.  This cannot count as $M_{MH}$ proving something since the $M_{MH}$'s premise is the conclusion it is proving, and thus is circular.

The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO.

In other words, $\emptyset$ is decidable.

You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input $T$, decides whether $L(T) = \emptyset$.


Which of the following words is in the language of the grammar G? This is taken from a practice quiz by my university.
I ruled out that aabbbaab is not part of the grammar:
S → aSb → aaSbb... This shows that I can't make this word because it would have to have atleast two b's at the end in order for me to add more letters
Then I tried to see if abbaabb can be derived from the grammar and I experienced the same thing:
S → aSb → aaSbb... This shows that I can't make a word with two b's at the end without having at least two a's in the beginning
Finally, I tried to do aabaabbb:
S → aSb → aaSbb → aaSSbb → aaSaSbbb... I decided it can't be this one because even if I make aaSaSbbb into ϵ, I still need to find a way to make aaSaSbbb into ba so I can derive the word. It doesn't seem like I can do that.
So by elimination I thought the correct answer was aabaabb but I was wrong.
Please show me how to work out whether a word can be derived from a grammar.

This is what we have at our hand.
Now let us see what can be get from the second production in red.

From the production in Blue we have

And the parsing can be stopped using $S\rightarrow \epsilon$
So from the above two work outs we find that the $a$'s and $b$'s are properly nested. (and can be mapped to the problem of valid parenthesization )
That being said let us work the options out:

Alternatively, during the examination, it is hard to get this detailed thought in mind, so one can try to draw the parse tree for any one of the words, trying to do so, you shall get the intuition of the semantics of the language of the grammar.


Time-Complexity Verification: Code with two loops with an index halved at each iteration I have the following code in python and was asked to find the tightest upper-bound in terms of Big-O , I've done two attempts below and I don't know which one is right, can you help me verify as to which one is the right answer/approach?
def f1(L):
   n = len(L)
     while n > 0:
        n = n // 2
        for i in range(n):
          if i in L:
             L.append(i)
   return L

My attempts:
Approach 1:
While loop runs $ log(n) $ times. And at the $ith$ iteration the for-loop runs $ \frac{n}{2^i} $ times; inside the for-loop the conditional runs at most $ O(n) $ times ( because "in" has complexity of $ O(n) $ according to https://wiki.python.org/moin/TimeComplexity ). Thus, the time-complexity of the for-loop is $O(n^2) $. So  the time-complexity of total code is: $ \sum_{i=1}^{log(n)} O(\frac{n^2}{2^i}) = O(\sum_{i=1}^{log(n)} \frac{n^2}{2^i} ) = O( n^2 \cdot \frac{1-(1/2)^{1+log(n)}}{ 1-(1/2)^{log(n)} } ) = O(n^2)  $
Approach 2:
In the for-loop we have the conditional “if i in L” , the “in” costs $ O(n) $, thus time-complexity of for-loop is  $ \sum_{i=1}^{n} O(n) = O( \sum_{i=1}^{n} n  ) = O(n^2). $ Looking at the while loop  we see that “n” is halved at each iteration because of the statement “n=n//2” . Denote $ n_k = \lfloor \frac{n}{2^k} \rfloor  $ as the value of $n$ at the k-th iteration; Disregarding the floor function ( we won't care about $ \pm 1 $ for the value of $ n_k $ since we care about time-complexity ), we'll seek the smallest $ k $ ( we denote $ k $ as the iteration of the while loop ) where $ n_k = 1 \leq \frac{n}{2^k} \iff k \leq log(n) $. Hence the total time complexity of code is $ \sum_{i=1}^{log(n)} O(n^2) = O(log(n)) \cdot O(n^2) = O(n^2 \cdot log(n) ) $

As said above, both approaches are correct but in approach #2 I don't get a tight-bound. Since I want a tight-bound using the second approach I failed to notice what $ n $ actually is once inside the while loop. Let's look at the code above but formatted a bit in the following manner:
def f1(L):
   n_0 = len(L)
   n_k = n_0
     while n_k > 0:
        n_k = n_k // 2
        for i in range(n_k):
          if i in L:
             L.append(i)
   return L

Analysing the time-complexity of code using "inside-out" approach as I wanted:
The for-loop's complexity is $ \sum_{i=1}^{n_k} \cdot O(n_0) $ ( Complexity of "in" is $ O(n_0) $ ), i.e. $ O( n_k \cdot n_0 ) $. Thus since the while-loop runs $ log(n_0) $ times by my analysis, the total time-complexity of code is $ \sum_{k=1}^{log(n_0)}O(n_k \cdot n_0 ) $ , notice that $ n_k = \frac{n_0}{2^k} $ ( $ k $ is the k-th iteration of while loop ) hence   $ \sum_{k=1}^{log(n_0)}O(n_k \cdot n_0 ) = O(\sum_{k=1}^{log(n_0)}n_k \cdot n_0 ) = O(\sum_{k=1}^{log(n_0)} \frac{n_0}{2^k} \cdot n_0 ) = O(n_0^2) $. Denote $ n_0 $ as $ n $ and we have $ O(n^2) $ and we're finished.


Polynomial time solution for bipartite matching Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem:

  Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all items labelled alphabetically. Each item has a disallow list: there are certain boxes that item cannot be put into. Generate a mapping of items to boxes that does not violate any item's disallow list.

For bonus points, I would be interested in being able to generate all such mappings.

At first blush, the problem appears to be the inverse of the stable marriage problem, in that everyone has a strict list (rather than an ordinal ranking) of whom they don't want to get married to but will settle for anyone else (and strictly speaking the men/boxes have no preferences). Edit: it appears this problem is closer to bipartite matching.

A very naive solution is to simply generate all permutations and check which ones don't violate any disallow lists, but this grows as $O(n!)$. Are there any polynomial time solutions out there?

This actually has nothing to do with the stable marriage problem; it's an instance of bipartite matching.  (It's not related to stable marriage, becuase you don't have an ordering on the preferences of which box each item is matched to; you just have a list of what's allowed or disallowed.)

There are efficient algorithms: use the Hungarian algorithm, or any other algorithm for finding a maximum matching in a bipartite graph.  See https://en.wikipedia.org/wiki/Bipartite_matching#In_unweighted_bipartite_graphs, https://en.wikipedia.org/wiki/Hungarian_algorithm, and https://en.wikipedia.org/wiki/Assignment_problem.


Difference between normal-order and applicative-order evaluation The language I'm learning is Scheme and I'm working on an exercise that gives this:

(define (p) (p) )

(define (test x y) (if (= x 0)
                               0
                               y))

Then the question asks to evaluate the expression: (test 0 (p) ) and to comment on the behavior that would be observed under normal - order and applicative order evaluation.

These are my thoughts:

Under normal order, the program would evaluate the subexpressions before proceeding:

Thus ( test 0 (p) ) becomes:

(test 0 p)
( if (= x 0) 0 p))

Returning output 0

The only difference in applicative order would be that the program would run as:

( test 0 (p) ) becomes:

(test 0 (p))
( if (= x 0) 0 (p)))

Returning output 0

Thus (p) would never be evaluated as it won't be needed.

Is this correct? Please let me know as I have almost no experience programming.

What research have you done to answer that question? I just plugged it
as it is in Google, and got as second answer (the first may be as
good, I did not check) a reference to a section of a bible on your
topic: Hal Abelson's, Jerry Sussman's and Julie Sussman's Structure
and Interpretation of Computer Programs (MIT Press, 1984; ISBN
0-262-01077-1), aka the wizard book. The reference is to the section
"Normal Order and Applicative Order".

It states:

  Scheme is an applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed.

and adds that the latter is called lazy evaluation.

So you have your definitions wrong, and taking one for the other:

applicative order evaluates subexpressions  when, i.e. just before,
the procedure is applied.
normal order passes subexpressions as they are, without evaluation,
and proceeds with the evaluation only when the corresponding formal
parameter is actually to be itself evaluated. (there is a further
twist to it regarding environment issues ... but we better forget
that at this point).

Furthermore, you do not properly understand the call mechanism which
involves two things:

the parameter passing mechanism, which include proper processing of
actual arguments to the call, depending on the evaluation rule;
the "replacement" of the call to the function by the body of the
function (without the header).

In the case of applicative order evaluation of ( test 0 (p) ), you are
supposed to evaluate the argument subxpressions first. These are 0
and (p).

evaluation of a literal value like 0 yield that value.
the second argument however is a procedure call to a parameter-less
procedure called p. It has no parameter, so that we have no worry
about evaluation order. Then, in order to pursue evaluation, we
have to replace the call by the body of the procedure which follows
the list of arguments, and then evaluate that body. The body of
procedure p, as defined by the declaration (define (p) (p) ),
is (p), so that we are left with the evaluation of what we were
just trying to evaluate. In order words, the evaluation process is
caught in a loop, and will not terminate.

... and you never get to actually finish the call to the function test,
since evaluation of its arguments does not terminate. Your program
does not terminate.

This risk of non termination, even when the guilty argument will never
be used in the call, is one of the reasons to use instead normal
order evaluation, which may be a bit harder to implement, but may have
better termination properties.

Under normal order evaluation, you do not touch the argument
sub-expressions. What you do is replace the call ( test 0 (p) ) by
the body of the function test, i.e. (if (= x 0) 0 y), where the
names of the (formal) arguments x and y are replaced by the
corresponding actual arguments 0 and (p) (up to environment, or
renaming issues, that are important but would complicate the
explanation here, and are the main difference between the original Lisp and
the Scheme language).

Hence you replace the evaluation of ( test 0 (p) ) by the evaluation
of (if (= 0 0) 0 (p)).

Now the function if is a primitive function that usually always
evaluate its first argument, but evaluates its last 2 arguments in
normal order, evaluating only the useful one, depending on whether the
first evaluates to false or true (actually NIL or #f for
false, or some other value for true, in the case of Scheme - if my
memory does not fail me). Since (= 0 0) evaluates to true,
evaluation of the conditional amount to evaluating the yet unevaluated
second argument, which is 0, which unsurprisingly (except in old
Fortran) evaluates to 0.

Deep breath.


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

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

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

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


Flow of control when calling a function I am learning about embedded and operating systems. I would like to know the order of control flow that occurs when a user-space C application calls a function, for example, printf().
I am slightly confused as to which order is correct:
printf() -> User-space library -> system call -> kernel driver
printf() -> User-space library -> kernel driver -> system call
printf() -> System call -> user-space library -> kernel driver
printf() -> Kernel driver -> system call -> user-space library

There is no such thing as a C application. Code written in C is compiled to a binary ELF file on Linux or a .exe file on Windows.
The answer to the question is it depends if the function requires a syscall or not. If it doesn't require a syscall (on Linux):

You launch the ELF executable
The ELF executable is interpreted and the code and data is placed in memory. A new process takes place. All code including the Linux kernel code that the process requires is placed into memory and linked against the user code (dynamic linking).
When the process calls a function, its arguments are placed on the stack, the function code runs and the function returns.

It is as simple as that for a situation when the kernel function doesn't require a syscall.
If it requires a syscall:

Steps 1 and 2 above.
The function is called as usual with its arguments on the stack.
When the kernel function requires to access hardware (like when using printf() to print to the screen), it uses system calls.
A system call is done using software interrupt 0x80 (the assembly instruction int 0x80).
The CPU is interrupted, looks in the IDT (https://wiki.osdev.org/Interrupt_Descriptor_Table), determines the address of the handler and jumps to the handler.
The interrupt handler for a system call contains a special instruction: SYSENTER (https://wiki.osdev.org/Sysenter). The SYSENTER instruction makes the processor switch from user mode to kernel mode. A special MSR register contains the address at which the processor will jump when executing a SYSENTER instruction. To write to this register, the OS uses the WRMSR special instruction at boot.
The CPU jumps to the address specified by the MSR register. It is now in kernel mode. It runs whatever code is needed to perform the requested operation (specified in EAX by the caller). It then returns the result to the caller by using certain registers depending on the system call. To return it calls SYSEXIT.
The request was fulfilled, so the user code can continue where it was.

Here is an example of Hello World app in assembly which does a syscall. Your printf() function will be compiled to something similar.
section .data
    hello:     db 'Hello world!',10    ; 'Hello world!' plus a linefeed character
    helloLen:  equ $-hello             ; Length of the 'Hello world!' string

section .text
    global _start

_start:
    mov eax,4            ; The system call for write (sys_write)
    mov ebx,1            ; File descriptor 1 - standard output
    mov ecx,hello        ; Put the offset of hello in ecx
    mov edx,helloLen     ; length of the string in edx

    int 80h              ; Call the kernel

    mov eax,1            ; The system call for exit (sys_exit)
    mov ebx,0            ; Exit with return code of 0 (no error)
    int 80h

The right answer would be
printf() -> User-space library -> system call -> kernel driver
The printf() function is placed in RAM alongside your code (and dynamically linked against it), the function is called, makes a system call which brings the processor in kernel mode using SYSENTER and then calls kernel drivers which do the required task like writing to the screen or writing to IO devices.


Is there an equivalent of van Emde Boas trees for ropes? Someone I know is planning on implementing a text editor in the near future, which prompted me to think about what kind of data structures are fast for a text editor. The most used structures are apparently ropes or gap buffers.

Van Emde Boas trees are just about the fastest priority queues around, if you don't mind an upper bound on the number of items you can put into it and a large initialization cost. My question is whether there exists some data structure that is just as fast as the van Emde Boas tree, but supports text editor operations.

We only need to support up to $m$ characters in our data structure (so if $\log m = 32$, then we support up to 4GB worth of ASCII characters). We are allowed $\sqrt{m}$ time to initialize a new data structure. We'd like to support the following operations:

Insert a character at position $i$ in $O(\log \log m)$ (and thereby increasing the position of every subsequent character by 1).
Delete a character at position $i$ in $O(\log \log m)$.
Return the character at position $i$ in $O(\log \log m)$.

So, insert(0,'a') followed by insert(0,'b') results in "ba".

Even better would be this:

Return a 'pointer' to some index $i$ in $O(\log \log m)$.
Given a 'pointer', return the character at this position in $O(1)$.
Given a 'pointer', remove the character at this position in $O(1)$.
Given a 'pointer', add a character at this position in $O(1)$ and return a pointer to the following position.
(optional) Given a 'pointer', return a 'pointer' to the next/previous character in $O(1)$.

Fredman and Saks show in "The cell probe complexity of dynamic data structures" that you cannot do better than $\Theta\left(\frac{\lg m}{\lg \lg m}\right)$ amortized time for the operations you are looking for. They call this problem "list representation".

Dietz presented a data structure in "Optimal Algorithms for List Indexing
and Subset Rank" that achieves this bound.


Efficient Implementation of Boolean Lattice-Esque Operation Let $X = \{1,2,\dots n\}$, and $Y_i= \{T \in \mathcal{P}(X): |T| \le i\}$. I am interested in "avoidance sets" $A \subset Y_n$. We say a subset $S \subset X$ is valid with respect to an avoidance set $A$ if $T \not \subseteq S$ for all $T \in A$.
We let $f(A)$ denote the set of $S\subset X$ that are valid with $A$. It may be helpful to note that $f(A' \cup A'') = f(A')\cap f(A'')$.
Given a list of avoidance sets $A_1,A_2,\dots A_k \in Y_2$, I want to return an avoidance set $A' \in Y_2$ such $$\bigcup_{1 \le i \le k} f(A_i) \subseteq f(A')\tag{1}$$ and for any other $A'' \in Y_2$ satisfying (1), we do not have $f(A'') \subsetneq f(A')$.
Can this be done in time linear to $\sum_{1\le i \le k} |A_i|$? (you may assume that all the sets $A_i$ are simplified, i.e. if $\{a\}\in A_i$ and $\{b\}\in A_i$ then $\{a,b\} \not \in A_i$)
Context:
The physical motivation behind my question is that I am trying to "roughly" keep track of events which must be avoided.
An element $x \in X$ corresponds to an "event" occurring in a probability space. A subset $S \subset X$ correspond to the intersection all the events $x_1,x_2 \dots x_k \in S$ occurring at once.
An avoidance set $A$ is supposed to express certain events which have probability zero of occurring. (so $S \subset X$ is not valid with $A$ if the event corresponding to $S$ has zero probability) To keep the cost of space low, I have decided to concern myself with only working with avoidance sets in $Y_2$. (thus this is a heuristic representation)
Now, let's say I am keeping track of avoidance sets $A_i$ where $S$ is invalid with $A_i$ represents that $S$ has probability zero given event $i$ happens. Now, if I know at least one of the events $A_1,\dots A_k$ occurs, then I am interested in finding $A'$.

I believe the desired $A'$ is given by
$$A' = \{T : \forall T' . T \subseteq T' \implies T' \notin \cup_i f(A_i)\}.$$
Here is how to compute $A'$ in linear time from the $A_i$'s.  Basically, we want to include the set $T$ if: (1) for all $i$, there exists $T_i \in A_i$ such that $T_i \subseteq T$ and (2) there exists $j$ such that $T \in A_j$.  You can find those sets as follows:

For each $T \in A_1 \cup \cdots \cup A_k$:

Set flag := true.
For each $i := 1,2, \dots, k$:

If $\not\exists T_i \in A_i$ such that $T_i \subseteq T$, set flag := false.

If flag := true, output $T$.

Naively, this seems likely to take quadratic time or more.  However, since you're working in $Y_2$, there is a more efficient algorithm.  For each $i$, build a hashtable (an index) that, given $T$, lets you check whether $T \in A_i$.  Then, you can implement the algorithm above as:

For each $T \in A_1 \cup \cdots \cup A_k$:

Set flag := true.
For each $i := 1,2, \dots, k$:

If $|T|=2$: suppose $T=\{u,v\}$; if $T \notin A_i$ and $\{u\} \notin A_i$ and $\{v\} \notin A_i$, then set flag := false.
Otherwise if $|T|=1$: if $T \notin A_i$, then set flag := false.

If flag := true, output $T$.

This can now be implemented in time proportional to $k \sum_i |A_i|$.  I don't know whether this is efficient enough for you.
I think for this to work corretly in all cases, you might need to first convert each avoidance set $A_i$ into canonical form.  The canonical form of avoidance set $A$ is an avoidance set $A^*$ with the smallest number of sets such that $f(A^*)=f(A)$.  When working in $Y_2$ you can compute the canonical form with the following rules:

Rule 1: If $\{u,v\} \in A$ and $\{u\} \in A$ or $\{v\} \in A$, delete $\{u,v\}$ from $A$.

Rule 2: If $\{x,u\} \in A$ for each $x \in \{1,\dots,n\}\setminus\{u\}$, then add $\{x\}$ to $A$ and remove all $\{x,u\}$ from $A$.

You can enforce Rule 1 with a linear scan over $A$; and then you can enforce Rule 2 with a simple linear-time graph algorithm (build the undirected graph with an edge for each $\{u,v\} \in A$; check the degree of each vertex; apply Rule 2 to each vertex with degree $n-1$).  So, at least when working in $Y_2$, you can convert an avoidance set to canonical form in linear time.  I haven't tried to think about a generalization to arbitrary $Y_i$.


Explanation of Summations for Algorithm Analysis I do not have a background in Computer Science, work as a Software Engineer, and am attending college for my Master's degree in Computer Science. I have a data structures and algorithms course that I am taking currently with the "Introduction to Algorithms" text book by Cormen, Leiserson, Rivest, and Stein (CLRS). This is not one of my homework problems, but rather extra effort for me to try and understand algorithm analysis as it relates to using summations.

For instance, consider the example of $T(n) = T(n-2) + n^2$. An answer I saw floating around had $\sum\limits_{i=0}^{n/2} (n-2i)^2$.  I can understand how to get the $(n-2i)^2$ part, but am not sure how to get the upper and lower boundary conditions, as well as what to do after this point. I guess the total answer for this is $\Theta(n^3)$, but am not making the connection between the summation and the final answer.

I have had calculus in the past, and do remember some of the series chapter that dealt with harmonic, Taylor, geometric, telescoping, and power series. But as it relates to CS, I'm not quite sure where it is going.

So, my questions are:

Why are the lower and upper bounds 0 and n/2, respectively?
What do I do with the summation notation to get a final answer?

I'm sure this is easily answered and that I'm just overlooking something.  I know that a series that looks like the harmonic series, which is $\sum_{i=1}^n (1/i)$, will give $\ln(n) + O(1)$. But most of it I don't understand how to get the values associated with Big-O, Omega, or Theta.

I appreciate the help, guidance, and any examples/tutorials you can point me to.

I will answer each of your questions as follows

Why are the lower and upper bounds 0 and n/2, respectively?

For the lower bound: we can see that at the first recursive call, the running time is $n^2$ so $n^2 = (n - 2i)^2$ when $i = 0$
For the upper bound: we can see that when a base case is given say $T(1) = a$, ($a$ can be some constant that for the purpose of calculating the upper bound, we don't really care) then to reach to the base case, you will need to apply the recurrence formula $x$ times which means you need to solve for $x$ the equation $((n - 2) - 2) .. -2) = 1$. This equation is $n - 2x = 1$ which will give you $x = \frac{n-1}{2}$. To make things easier for readers, someone might consider the base case is $T(0)$. In this case you will instead
solve $n-2x=0$ giving $x=\frac{n}{2}$. This is your convenient upper bound $\frac{n}{2}$.

What do I do with the summation notation to get a final answer?

A good way to solve summation like the one you give for the purpose of asymptotic bounding (such as $O$, $\Omega$, $\Theta$) is using integration. Let's look at the following graph, so you can easily visualize the approach and main idea.

Let's look at the interval where the terms in your summation are monotonic.
In your particular case, the terms in your summation decreases as $i$ increases in the interval of $[0, \frac{n}{2})$. This is because the each of the terms is a parabola on variable $i$, and this parabola has a single minima at $i = n/2$. As $i$ increases, the parabola decreases until $i$ reaches $n/2$ then the parabola start increasing.

Let's not worry too much about the actual value on the y-axis, but focus on the fact that your summation can be view as the summation of all the cyan blocks having width 1. As the terms monotonically decrease, you have $(n - 2i)^2 < (n - 2(i-1))^2$. Then you choose the function $f(x)$ using the right hand side replacing the variable $i$ with the variable $x$ which is the red line in the graph. $f(x)= (n - 2(x-1))^2$ thus you have $\sum\limits_{i=0}^{n/2} (n - 2i)^2 < \int\limits_{0}^{n/2} (n - 2(x-1))^2dx$

Now you solve the right hand side of the above inequality. This will give you $-\frac{1}{2}\frac{1}{3} (n - 2(x-1))^3 \Big|_{0}^{n/2} = -\frac{8}{6} - (- \frac{1}{2}\frac{1}{3}(n+2)^3) = \frac{(n+2)^3 - 8}{6} \in O(n^3)$. So you have $T(n) \in O(n^3)$

If you want to find the bound for $\Omega$, then you will do similarly. The difference now is that you choose $f(x) = (n - 2(x+1))^2$ because the terms in the summation are greater than the next term $(n - 2i)^2 > (n - 2(i+1))^2$. Your summation now can be seen as the bigger cyan plus blue (and purple) blocks. In other words, $\sum\limits_{i=0}^{n/2} (n - 2i)^2 > \int\limits_{0}^{\frac{n}{2}-1} (n - 2(x+1))^2dx$. Note that I have changed the upper bound on integration because getting over $\frac{n}{2}-1$ the terms change direction. But that is ok, because we still have the bound on $>$ sign

Solving the integration will give you a polynomial of degree 3 so you have $T(n) \in \Omega(n^3)$.

So now you can conclude that $T(n) \in \Theta(n^3)$

Extra: Back up image in case the graph above is no longer viewable:
Summation bound


How does a CPU differentiate between 1-operand instructions and 2-operand instructions? Suppose that we have 5 different instruction categories (1 OP, 2 OP, 0 OP, branch, and sub-routine instructions), how does a CPU manage to know which category is which whenever it reads an instruction from IR register using the least number of bits for each category? For instance, PDP-11 uses 4 bits (15 → 9) for two-operand instructions and 10 bits (15 → 8) for one-operand ones to denote the opcode of a particular instruction, how does it identify in the first place whether it's a two-operand or a one-operand instruction so that it would read the first 4 or 10 bits accordingly?

Normally the opcode encoding is designed to make it easy to tell.  The details of exactly how that works will depend on the particular architecture.  For instance, in your example, the first 4 bits might be enough to determine which category the instruction is in.  This decoding is performed by the instruction decoder.

As Ran G. explains,

  usually, either all instructions have the same length -- and then different OPCODEs signify different operations, or the instructions have variable length, and then there is some sort of prefix-coding that allows the CPU to determine which instruction it is (and what it length is) by its prefix.


Algorithm to fill a truck with pallets At work we build large machines, these get deconstructed, placed i crates and shipped away to the client.
Now we are just guessing how many trucks we need and how we lay the crates out to fit as many of them inside a truck.

For example:

We have a truck and want to load 8 crates of equal size into it. There are 2 possible "solutions" to this problem.

But here you can see that the second option is better in space used (all pallets fit).

Now the real question. Is there a algorithme out there that can do this, even with irregular crates (meaning diffrent in size). Or do i need to invent one myself?

EDIT: Some more details:

The crates can vary in dimensions. But are always rectacles or squares.

The crate dimensions voor in the form of an Excel file where width height and lenght are defined.

This already exists, but might not be what you are looking for.

While this might not be a problem for your application, notice that this is a more general problem than the (already NP-hard) bin packing problem, so for a large amount of crates finding the optimal solution will be hard.

On the other hand, for a small enough number of crates, brute force might be sufficient. For example, you could round all dimensions to multiples of 10cm and look at the trucks in terms of 10x10 tiles that crates can occupy, giving you a finite (hopefully small enough) number of potential solutions.


Easy infinite subclass of cubic graphs for Hamiltonian cycle problem I know that Hamiltonian cycle problem is $NP$-complete for 2-connected planar bipartite cubic graphs.

I'm interested in non-trivial infinite subclass of cubic graphs where the Hamiltonian cycle (path) problem is efficiently solvable. I tried the graph class database but could not find any such class graph.

  Is there any easy infinite subclass of 2-connected cubic graphs for Hamiltonian cycle problem?

Motivation: Barnette's conjecture states that every 3-connected planar bipartite cubic graphs is Hamiltonian which implies that HC is in $P$ (if it is true). However, Feder and Subi proved if there is any non-Hamiltonian 3-connected planar bipartite cubic graph then HC is $NP$-complete for this graph class.

Yes, there is an infinite class of 2-connected cubic graphs on which Hamilton Cycle has a polynomial-time algorithm. Further, there is a such a class that contains infinitely many Hamiltonian graphs and infinitely many non-Hamiltonian graphs, which I think is a decent definition of "non-trivial".

First, let $H_n$ be the union of a $2n$-cycle on vertices $\{1, \dots, 2n\}$ and the edges $\{(i, i+n)\mid 1\leq i\leq n\}$. $H_n$ is 3-regular, 2-connected and has an obvious Hamiltonian cycle.

Now, let $G$ be a 2-connected cubic graph that has no Hamiltonian cycle. Such a graph must exist, since the Hamiltonian Cycle problem is NP-complete on 2-connected cubic graphs, so must have both "yes" and "no" instances. Fix an edge $xx'\in G$. For any graph $H_n$ pick any edge $yy'\in H_n$ and let $H'_n$ be the graph made by taking $G\cup H_n$, deleting the edges $xx'$ and $yy'$ and adding edges $xy$ and $x'y'\!$.

$H'_n$ is 3-regular and 2-connected but I claim that it has no Hamiltonian cycle. Any Hamiltonian cycle $C$ in $H'_n$ must enter the copy of $G-xx'$ at $x$ and leave at $x'$ (or vice-versa). But then $C$ must contain a Hamiltonian path $P$ of $G-xx'$ that begins at $x$ and ends at $x'\!$. However, no such Hamiltonian path can exist, since $P\cup\{xx'\}$ would be a Hamiltonian cycle of $G$, but $G$ was chosen to have no Hamiltonian cycles.

So the desired class of graphs is $\mathcal{H} = \{H_n\mid n>1\}\cup\{H'_n\mid n>1\}$. It remains to show that the Hamiltonian Cycle problem can be solved in polynomial time for graphs in $\mathcal{H}$. Observe that, for every $n$, every edge of $H_n$ is on a 4-cycle (there are 4-cycles of the form $i$, $i+1$, $i+n+1$, $i+n$, $i$). However, the edges $xy$ and $x'y'$ are not on any 4-cycle of $H'_n$. We can test that every edge of a graph is in a 4-cycle in time $\mathcal{O}(n^4)$.

I edited to changed the construction slightly, with two benefits. First, the algorithm runs in time $\mathcal{O}(n^4)$ instead of $\mathcal{O}(n^{|V(G)|})$. Second, there's an actual correctness proof; the old algorithm relied on the assumption that $G-xx'$ is not a subgraph of any $H_n$, which was probably true but really needed to be proven.