Understanding a binary classifier problem I'm trying to understand a problem that's more mathematical in nature that I'm accustomed to. Below I'll try to present the problem and what I have so far understood of it.

The problem

We have $X_1,..,X_n$ i.i.d. binary outcomes distributed according to Bernoulli distribution. The probability that $X_i = 1$ is given by $E[X_i] = p$. Hoeffding's inequality is somehow useful in solving the problem. It tells us that the total number of outcomes with value $1$ divided by $n$ is not too far from its expectation, which is $E[\frac{1}{n} \sum_{i=1}^n X_i] = \frac{1}{n} \sum_{i=1}^n E[X_i] = p$:

$Pr[|p-\frac{1}{n}\sum_{i=1}^n X_i| > \epsilon] \le 2exp(-2n\epsilon^2)$

Now I have to solve for the value $\epsilon$ for which the above probability equals $\alpha$. E.g. $n = 10$, $\alpha = 0.05$ this provides a bound that guarantees that with 95 % probability, the observed number of occurrences of $X_i = 1$ is within the interval $[n(p − \epsilon), n(p + \epsilon)]$. I must also evalute the width of this interval.

My understanding right now

The outcomes $X_1,..,X_n$ are something like coin tosses with a biased coin. We have some expectation $p$ for the coin toss to equal heads. The Hoeffding's inequality part says that if we take the sum of all of the expected values and multiply it with $\frac{1}{n}$ we get something close to $p$ (but why is it not $\frac{np}{n} = p$?) and the probability for it to be greater than $\epsilon$ is some (rather small?) number.

Now if we use the values of the example, the inequality would look like $0.05 \le 2^{-20\epsilon^2}$. I suppose I could solve that $\epsilon$ but the result is still an inequality and I think I need a concrete value to calculate $[10(p - \epsilon), 10(p + \epsilon)]$.

And if I'm correct the answer to the problem is some real valued range like $[5, 8]$ which says that there's a 95% possibility to get from 5 to 8 heads in 10 tosses, but I have no idea how to come up with the true range using that inequality.

I'm also not sure whether it's good to apply any real world scenarios in to this kind of abstract problems, or should I just try to learn to think on an abstract level and forget about the physical world? Especially if I'm to see a lot more problems like this.

Do you know of any materials that could possibly show me what's actually going on in that kind of equations? It's ok if I can't solve the problem but I would love to understand it on a level that doesn't make me want to scream and run away.

tl;dr

I'm having a hard time understanding probability distributions and inequalities with greek letters, but I would like to. Right now I'm stuck and I could use a pointer to the right direction.

I'll try to post updates as I go on.

Update

Ok so this is what I gathered:

So what the inequality is essentially saying is that when the amount of trials grows, the probability that we would deviate from our expected average by over some number $\epsilon$ decreases. And higher deviation also means smaller probability. It makes sense if I consider those coin tosses, because it's easy to see that during a large amount of trials the distribution should follow the the bias (if the coin has some).

Now if I estimate this $\alpha = 0.05$ for $100$ trials, I get that $2e^{-2*100*0.136^2} = 0.0494 \le 0.05$, which allows me to claim that in 95% of the cases I would deviate from the expected average by at most $0.136$.

How we arrive in to this conclusion without knowing anything about the initial probabilities is still beyond me. If I do not know them, the interval in the problem will take the form of $[100p-0.136, 100p+0.136]$ if I'm not mistaken?

Thanks for the explanation, I hope I understood it correctly and my apologies in advance if I didn't.

This kind of analysis could be confusing if you are new to it. I think you need some intuition about what's going on. I will assume you understood until this point

$$
Pr[|p - \frac{1}{n} \sum_{i = 1}^{n} X_i| > \epsilon] \leq 2 e^{-2n\epsilon^2}
$$

(If not, hold tight and ask in the comments, I will elaborate).

So this inequality tells you this. You should be expecting the average value to be around the expected value of the average (that's why they call it expected value), and larger and larger deviations should be less and less likely. So if you ask what is the probability the average is at least $0.01$ away from the expected value, you plug-in $\epsilon = 0.01$ in the right hand side and get an upper bound on the probability that this happens.

Notice that as $\epsilon$ gets larger the probability gets smaller and smaller. Also notice that as $n$ gets larger, the probability gets smaller. These reason behind these two statements should be clear to you. (If not, pause and think about it).

Now you ask the inverse question. If I want to be 95% sure that the average is within $\epsilon$ from the expected, how big must epsilon be. Notice that the answer to this question must necessarily be a lower bound on $\epsilon$. Since if you are 95% sure that the average is within $\epsilon$ from the expected value, then with even bigger probability you are sure that it is within a bigger range from expected.

So what you want to do is assert that $Pr[\dots > \epsilon] \leq 0.05$, that is the probability that the average is farther away than $\epsilon$ be at most 5%. You cannot calculate the probability exactly, but you do have an upper bound on how big it can be (given by your inequality above). So if you want to be certain the probability is less than 5%, you can assert that the upperbound on the probability is less than 5%. That is, you want to solve:

$$
2 e^{-2n\epsilon^2} \leq \alpha = 0.05
$$

Note, that solving this will give you something like $\epsilon \geq \dots$ That means as long as you choose $\epsilon$ to be at least this, you are sure that the probability of deviating from the expected value by at least $\epsilon$ is at most 0.05.

Of course you can do the entire analysis for a variable $\alpha$ instead of 0.05.


Is it "valid" for semantic functions to query outside of the grammar in attribute grammars? Is it valid (in the sense of formal grammars or formal language theory) to refer to outside of the grammar in attribute grammars?

What I mean is that since attribute grammars can contain semantic functions e.g.

  E1 → E2+T { E1.val := sum(E2.val, T.val) }

then could there (in the place of the sum function) be a function that does e.g. a SQL query?

Should add that this is technically feasible, but I want to know that if it's reasonable and in accord to the theory of attribute grammars and the practice of semantic analysis.

The sum function of your example itself is already stepping out of the strict scope of the grammar. Or you'd have to to explicitly include all the machinery used in your attributed grammar into it, in which case nothing forbids adding (some formalization of) SQL and a database to it.


Finding the Regular Expression of a language I'm trying to find a regular expression for the language
$$L = \{w\mid n_a(w)+n_b(w)\equiv 2\pmod3\}\,,$$
where $n_a(w)$ is the number of $a$s in $w$.

I can see that this would generate strings of length $3n-1$ and
I can write the expression for a string of whose length is a multiple of three: $(( a + b )^3)^*$. But that's not quite what I need.

The alphabet is $\{a,b\}$

It's better to think of $L$ as strings of length $3n+2$. You already have an expression for strings whose length is a multiple of 3, so use that and append all strings of length 2.


Removing and reinserting elements to minimally mimic a changeset Let's say that there is a tower of blocks labelled from top to bottom $1$ to $n$. Somebody comes along and removes a block and reinserts it somewhere in the tower (making space as needed). As they move these blocks one at a time, they write down in order which index they moved a block to (index starting at 1). For example, they take the block 5 from the 5th index and squeeze it into between the 6th and 7th making it the 7th index. They write down "block 5 to index 7". They can make as many moves as they like and move each block as many times as they like.

Note that the index "moved to" is the index of the block after the removal and insertion are complete.

Someone else finds the changeset the original person created. Knowing the size of the tower and having the list of changes, they must write another changeset that would have the same results as the first but with at most one move per block and the moves must take place in the order that the blocks were originally moved in without latter duplicates. This also means that only blocks of the original changeset can be moved.

I came up with one which is to repeat the steps in order excluding those where the block is moved again later. This seemed to work in some cases but not all.

Is there an algorithm to solve this problem?

Hint #1:

   Suppose you are only given the final configuration of the stack (not the changeset that led to it).  Could you find any sequence of moves that would lead to that configuration?  Could you find a sequence of moves that would lead to that configuration, and that makes at most one move per block?

Hint #2:

   Where does block 1 go to?  Where does block 2 go to?


What is dynamic programming about? Sorry in advance if this question sounds dumb...

As far as I know, building an algorithm using dynamic programming works this way:

express the problem as a recurrence relation;
implement the recurrence relation either via memoization or via a bottom up approach.

As far as I know, I have said everything about dynamic programming. I mean: dynamic programming does not give tools/rules/methods/theorems for expressing recurrence relations, nor for turning them into code.

So, what's special about dynamic programming? What does it give you, other than a vague method for approaching a certain kind of problems?

Dynamic programming gives you a way to think about algorithm design.  This is often very helpful.

Memoization and bottom-up methods give you a rule/method for turning recurrence relations into code.  Memoization is a relatively simple idea, but the best ideas often are!

Dynamic programming gives you a structured way to think about the running time of your algorithm.  The running time is basically determined by two numbers: the number of subproblems you have to solve, and the time it takes to solve each subproblem.  This provides a convenient easy way to think about the algorithm design problem.  When you have a candidate recurrence relation, you can look at it and very quickly get a sense of what the running time might be (for instance, you can often very quickly tell how many subproblems there will be, which is a lower bound on the running time; if there are exponentially many subproblems you have to solve, then the recurrence probably won't be a good approach).  This also helps you rule out candidate subproblem decompositions.  For instance, if we have a string $S[1..n]$, defining a subproblem by a prefix $S[1..i]$ or suffix $S[j..n]$ or substring $S[i..j]$ might be reasonable (the number of subproblems is polynomial in $n$), but defining a subproblem by a subsequence of $S$ is not likely to be a good approach (the number of subproblems is exponential in $n$).  This lets you prune the "search space" of possible recurrences.

Dynamic programming gives you a structured approach to look for candidate recurrence relations.  Empirically, this approach is often effective.  In particular, there are some heuristics/common patterns you can recognize for common ways to define subproblems, depending on the type of the input.  For instance:

If the input is a positive integer $n$, one candidate way to define a subproblem is by replacing $n$ with a smaller integer $n'$ (s.t. $0 \le n' \le n$).
If the input is a string $S[1..n]$, some candidate ways to define a subproblem include: replace $S[1..n]$ with a prefix $S[1..i]$; replace $S[1..n]$ with a suffix $S[j..n]$; replace $S[1..n]$ with a substring $S[i..j]$.  (Here the subproblem is determined by the choice of $i,j$.)
If the input is a list, do the same as you'd do for a string.
If the input is a tree $T$, one candidate way to define a subproblem is to replace $T$ with any subtree of $T$ (i.e., pick a node $x$ and replace $T$ with the subtree rooted at $x$; the subproblem is determined by the choice of $x$).
If the input is a pair $(x,y)$, then recursively look at the type of $x$ and the type of $y$ to identify a way to choose a subproblem for each.  In other words, one candidate way to define a subproblem is to replace $(x,y)$ by $(x',y')$ where $x'$ is a subproblem for $x$ and $y'$ is a subproblem for $y$.  (You can also consider subproblems of the form $(x,y')$ or $(x',y)$.)

And so on.  This gives you a very useful heuristic: just by looking at the type signature of the method, you can come up with a list of candidate ways to define subproblems.  In other words, just by looking at the problem statement -- looking only at the types of the inputs -- you can come up with a handful of candidate ways to define a subproblem.

This is often very helpful.  It doesn't tell you what the recurrence relation is, but when you have a particular choice for how to define the subproblem, often it's not too hard to work out a corresponding recurrence relation.  So, it often turns design of a dynamic programming algorithm into a structured experience.  You write down on scrap paper a list of candidate ways to define subproblems (using the heuristic above).  Then, for each candidate, you try to write down a recurrence relation, and evaluate its running time by counting the number of subproblems and the time spent per subproblem.  After trying each candidate, you keep the best one that you were able to find.  Providing some structure to the algorithm design process is a major help, as otherwise algorithm design can be intimidating (there's such a huge space of possible approaches, without some structure it can be unclear how to even get started).


Is my implementation of genetic algorithm correct? In genetic algorithms, we have a function called "mutation".  Before we call this function, we choose parents.
In my version of the algorithm, when i mutate the child, i don't change the bits which are the same as the given input.
By that, I mean :
Imagine we want to reach the string "ABCDE".
The algorithm first generates 5 strings randomly :
"ADDDE", "ABDIO", "MSDKO" , "POIUU" , "QWERT"
The fitness function says that the first two strings, have better quality to survive. So, we select them.
So we have "ADDDE","ABDIO" as parents.
Then we choose a random number between 0 & 4. Assume that 1 is chosen.
We take "AD" from the first string and "DIO" from the second one.
The child we made is : "ADDIO"

Now, The part which makes me confused :
When i mutate this child, I say "A" is in the same place of "ADDIO" as "ABCDE". So, I don't change "A". I mutate the other characters . For example i make "AQWERT","ARTYUI" , ...

Is this correct? Any idea? Any improvement ?

No, that does not make sense.

What you have there is a toy example. In any application, the algorithm will not know the goal -- otherwise you wouldn't need it! That is, you don't have any way of known whether a mutation is benefitial before executing it.

What's more, mutating away from the optimum is an essential part of the algorithm, and can be shown to be necessary for it to work well (otherwise you get stuck in local optima more easily).


What is meant by polynomially smaller I'm reading CLRS Section-4.5: The Master method for solving recurrences. There is a line saying

  $f(n)$ must be polynomially smaller than $n^{\log_b a}$.

What is meant by polynomially smaller? Can anybody explain it to me with an example?

In this context, the line means $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$.

More generally, there are a few possible interpretations. Under one interpretation, $f(n)$ is at least polynomially smaller than $g(n)$ if $f(n) = O(g(n)/n^\epsilon)$ for some $\epsilon > 0$; and $f(n)$ is at most polynomially smaller than $g(n)$ if $f(n) = \Omega(g(n)/n^\epsilon)$ for some $\epsilon > 0$.

A different interpretation has $f(n)$ at least polynomially smaller than $g(n)$ if $f(n) \leq g(n)^{1-\epsilon}$ for some $\epsilon > 0$, and at most polynomially smaller than $g(n)$ if $f(n) \geq g(n)^\epsilon$ for some $\epsilon > 0$.


Simplify $O(\min(m, n))$? I know that $O(\max(m, n)) = O(m + n)$, but is there a similar simplification for $O(\min(m, n))$? It could be $O(n) \cap O(m)$ but it does not simplify the notation that much…

Based on definition for non negative functions
$$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$
I prefer to consider your question as about $O(\min(f,g))$.
Now, if from one hand $O(f) \cap O(g) \subset O(\min(f,g))$: $\phi \leqslant C_1 \cdot f$ and $\phi \leqslant C_2 \cdot g$ we obtain $\phi \leqslant C \cdot \min(f,g)$. Reverse can be show in same way, so we can be sure that
$$O(f) \cap O(g) = O(\min(f,g))$$


How to calculate time complexity of a randomized search algorithm? Example: Finding an element from a sorted array

Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the array and performs the following operation:

if (value == A[randomIndex])
   // element found
else if (value < A[randomIndex])
   // check the left subarray of the randomIndex
else
   // check the right subarray of the randomIndex

This is similar to binary search but instead of selecting a mid index of the low and high index, we simply select a random index between low and high index.

Can anyone please provide the time complexity for this algorithm in worst, average and best case with a simple explanation for each?

Best case is $O(1)$, that is when you find the element in the first check.

Worst case is $O(n)$, and it happens when the element is in the first position, and in each check you get the last position, thus going through the whole array.

Average case is a little bit more tricky to get, since we need to solve a recurrence to get the expected value.
Let $T(n)$ be the expected time for an array of size n. The pivot is chosen randomly, so each posible pivot has a probability $p = \frac{1}{n}$. So, we have this:

$T(n) = T(1)/n + T(2)/n + ... + T(n-1)/n + 1$

We add that 1 at the end, because that's the constant time we have for checking at each step. Now we multiply each side by n:

$nT(n) = T(1) + T(2) + ... + T(n-1) + n$

Which also gives:

$(n-1)*T(n-1) = T(1) + T(2) + ... + T(n-2) + (n-1)$

So we can subtract those equations and we get

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

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

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

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

And "unrolling" this equation, we have:

$T(n) = 1 + 1/2 + 1/3 + ... + 1/n$

And the right side of the equation is the nth harmonic number. We can show that the nth harmonic number is $\Theta(\log n)$
So we have that the average time for the algorithm is $\Theta(\log n)$


Find every edge for which every s,t-path in a DAG goes through that edge Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-path contains $e$. I don't actually know the real name for this notion; so I'm calling it the "bottleneck set", but when I google that I get unrelated concepts.
An obvious solution is for each edge $e \in E$, run DFS on $G$ to get all $s$,$t$-paths, and check each one for whether it contains $e$. If all of them do, then $e$ is part of $\mathsf{Bottleneck}(G)$. However, this has runtime $O(E(V + E))$. Is there a faster way?

Compute the dominator tree of the flow graph $(G,s)$, i.e., the graph $G$ with source node $s$.  Let $s=v_0,v_1,\dots,v_{k-1},v_k=t$ be the sequence of nodes in the path from $s$ to $t$ in the dominator tree.  Check each pair $(v_i,v_{i+1})$ of consecutive nodes in this sequence; if it is an edge of $G$, it is visited on every $s,t$-path, so output it.  It is possible to see that this enumerates all such edges.
The running time is nearly linear time.  It is possible to compute the dominator tree in nearly linear time, and then the rest of the algorithm clearly runs in linear time.  In particular, the Lengauer-Tarjan algorithm computes the dominator tree in $O(E \alpha(E,V))$ time, where $\alpha(E,V$) is an inverse Ackerman's function -- thus nearly linear.  There is also an $O(V+E)$ time algorithm by Buchsbaum, Kaplan, Rogers, and Westbrook and by Georgiadis and Tarjan, but it is more complex to implement in practice.  If you are interested in ease of implementation, you might also be interested in work by Cooper, Harvey, and Kennedy.


What are handles in parsing? I have read a few algorithms for $LR(k)$ parser, in which there is a frequent mention of selecting a handle from the grammar given.
For example, one document said  - "the essence of LR parsing is identifying the handle on top of stack"

Please help me understand, what are handles in parsing?

Let's consider the following grammar:

  1: $S \to A b$
  2: $S \to B b$
  3: $A \to a a$
  4: $B \to a a a$

Obviously, this language is totally uninteresting: the only words in it are $aab$ and $aaab$. However, the grammar is not $LL(1)$ or $LL(2)$ (not sure if you know what that is, if you don't, then that's not a problem).

Let's try parsing the input $aaab$ by going through it one character at a time, while pretending we know absolutely nothing about the rest of the string, except the next token (essentially, we use 1 token of lookahead). We are allowed to use our knowledge of everything we've seen so far though.

Initially, we only know that the string starts with an $a$. This tells us absolutely nothing about whether we are in 'case 1' (production 1) or 'case 2' (production 2) of our grammar. Luckily, we don't really care at this point.

Let's skip over the $a$ and go to the next point. We remember the $a$ and look at the next token. This is another $a$. Note that by now, we've seen $aa$, which means that we might be in case 1: it might be the case that these first two $a$s constitute an instance of $A$! We'll just leave it at this for the moment, and first 'read' the $a$ officially.

We now look at our third token and find it is again an $a$. We now want to decide whether those two $a$s we saw earlier really constitute an $A$ ($LR(k)$ algorithms never delay this decision). As an $A$ is always followed by a $b$, we decide this is not the case: our next token is an $a$.

Reading the $a$, we know we're definitely in case 1 (assuming our input is correct). Our lookahead becomes a $b$, which is precisely what we expect. We therefore decide that the three $a$s we've seen so far are in fact a $B$. Note that at this point, we no longer need to 'remember' that we've seen three $a$s: all we need to know is that we've seen a $B$. This is effectively the same situation we'd be in if we would have had $Bb$ as input, and we'd have read $B$, and as this makes everything easier to remember, we'll do precisely that (this corresponds to a reduce action of an $LR(k)$ parser).

Finishing up, we read the $b$, find that we are at the end of the input, decide that the left part must be an $S$ and decide that the input was correct.

The $LR(k)$ algorithm works pretty much as described above. It remembers what it has seen so far and decides based on this information and the next token whether the last bit of what it has seen so far is 'actually' a nonterminal. It then replaces this by the nonterminal, shuffles some information around and continues as if the replacement had taken place in the input.

The crucial bit is finding out when what we've seen so far, or to be more precise the last bit of what we've seen so far, is actually an instance of a nonterminal, so an expansion of a production. In our example, if we had transformed the two $a$s at the start into an $A$, then everything would have went wrong. We say that $aa$ is not a handle at this point. However, $aaa$ was a handle, as we correctly replaced it by a $B$. A grammar is $LR(k)$ if we can always make correct decisions about what is a handle using $k$ tokens of lookahead and everything we've seen so far.


Shifting deletion algorithm for linear-probing hash table I'm looking for the algorithm for deleting an element from a linear-probing hash table that does a delete-and-shift instead of just using tombstone elements.

The basic idea is quite simple - but I keep getting caught up in corner cases (notably, w.r.t. "wraparound", where an element hashes to a high slot but all the end slots are full so the index it is actually inserted at is low.)

Basic idea:

When you delete an element, keep track of the slot and start scanning forwards. If you hit an element that's null (read: not present), you're done. Otherwise, if you hit an element that hashes to a slot <= the slot kept track of, move that element to the kept-track-of slot, and keep track of the current slot instead.

Or in pseudocode:

func del(item i):
    slot s = get_slot_of(i)
    table[s] = null
    fixup(s)
func fixup(slot s):
    assert table[s] == null
    slot t = s
    while table[++t] != null:
        if get_slot_of(table[t]) <= s:
            table[s] = table[t]
            table[t] = null
            s = t

In simple cases, this works. But as soon as you include the modulo behavior, it falls flat on its face.

So how would I go about fixing this up such that it doesn't fall flat on its face in such cases? I looked around, but couldn't find this algorithm implemented anywhere - it seems like most places that use linear probing just use tombstone elements instead.

There are two main approaches to cover the "wraparound" case:

"Triple condition", e. g. see java.util.IdentityHashMap source, or with more clarifying comments here
Second approach is based on counting the distance to the empty slot and comparing it with the distance between the slot where the "candidate for shift" is observed and where it should have been inserted if the hash table is empty, which could be obtained (covering the wraparound case) by substracting the index of the slot where the key should have been isnerted from the index of the current slot in the table, modulo table size (binary & (tableSize - 1) if the table size is a power of two). Example imlementation of this approach could be found here.


Can you solve 3D Tic Tac Toe with Minimax? I have implemented a 3d Tic Tac Toe game with AI, where the computer is unbeatable.

The only thing is that the board looks like this:

_ _ _
 _ _
_ _ _

rather than this:

_ _ _
_ _ _
_ _ _

There are a total of 3 boards stacked on top of each other, and any lines of 3 x's or o's grant a point. When the board is full, all points are tallied and the winner is announced.

I used the minimax algorithm with alpha-beta pruning.

But my algorithm is only able to get the optimal move if the board is full to a certain degree. When there are less moves, it takes a really, really long time to find the optimal move.

Is there some way to speed up my minimax? I have already researched ways to speed up minimax, but I need an answer specifically related to my situation.

Is it possible to solve to optimal move quickly using minimax? Or do I have to use a different algorithm?

EDIT: Please note that the game uses gravity, like in the connect-four game. I.e. the x's and y's stack.

You could precompute the optimal move for all possible configurations, and store that in a lookup table.  Once that's done (and it only needs to be done once), it would make your program extremely fast at runtime.

Your board has a total of 24 cells (8 cells at each level, times 3 levels), so there are at most a total of $3^{24}$ possible calculations.  Therefore, as a naive upper bound, your table will need to have at most $3^{24}$ entries.

In fact, due to gravity plus the fact that you don't need to store configurations where one player has already won, there will be many fewer configurations that you need to store in your table.  Call a configuration relevant if no one has won yet, and it is a reachable configuration (i.e., it doesn't violate the gravity rules).  Then your table can be stored as a dictionary/map: for each relevant configuration, it stores the optimal move when in that configuration and which player will win assuming optimal play (first-player win, second-player win, tie).  Now your job is to precompute that dictionary, with one element per relevant configuration.

It is possible to show that the number of relevant configurations is at most $13^8 \approx 2^{29.6}$: in particular, the number of configurations that satisfies gravity and has no vertical win is $13^8$.  This is only an upper bound; the true number of relevant configurations is even smaller still, as this estimate doesn't take into account that there's no need to store any configuration containing a horizontal or diagonal win.

To speed up the precomputation, you can avoid repeating effort (i.e., use "dynamic programming").  For instance, one approach would be to start by enumerating all relevant configurations containing 23 full cells and compute the optimal move for each; then enumerate all relevant configurations containing 22 full cells and compute the optimal move for each; and so on.  At each stage, when you compute the optimal move, you add it to the table along with who ultimately wins.  Notice that this makes it very easy to compute the optimal move at each stage, since you only need to search at depth 1 and then you can immediately look up what will happen thereafter in the table.

The running time of the precomputation will be some small constant times $N$, where $N$ is the number of relevant configurations.  We know that $N$ is smaller than $2^{29.6}$, and probably substantially smaller.  Therefore, I expect this precomputation to be something you could run within a few days on a modern PC, and store on the filesystem in a reasonable amount of space.

As a further optimization, you can use symmetry to further reduce the number of configurations you need to compute or store.  In particular, given any  configuration, you can find a bunch of other equivalent configurations through symmetry (flip horizontally, flip vertically, rotate).  For each set of equivalent configurations, you only need to consider and store one.  In particular, given a configuration, the first thing you'd do is map it to a canonical equivalent configuration (so that all equivalent configurations map to the same canonical); then you only need to compute or store canonical configurations in the lookup table.  I suspect this will reduce $N$ by a factor of 8 or so.


Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm? I was going through the text Introduction to Algorithm by Cormen et. al. where I came across an excerpt which I felt required a bit of clarification.
Now as far as I have learned that that while the Best Case and Worst Case time complexities of an algorithm arise for a certain physical input to the algorithm (say an input $A$ causes the worst case run time for an algorithm or say an input $B$ causes the best case run time of an algorithm , asymptotically), but there is no such physical input which causes the average case runtime of an algorithm as the average case run time of an algorithm is by it's definition the runtime of the algorithm averaged over all possible inputs. It is something I hope which only exists mathematically.
But on the other hand inputs to an algorithm which are neither the best case input nor the worst case input is supposed to be somewhere in between both the extremes and the performance of our algorithm is measured on them  by none other than the average case time complexity as the average case time complexity of the algorithm is in between the worst and best case complexities just as our input between the two extremes.
Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?
The excerpt from the text which made me ask such a question is as follows:

In context of the analysis of quicksort,
In the average case, PARTITION produces a mix of “good” and “bad” splits. In a recursion tree for an average-case execution of PARTITION, the good and bad splits are distributed randomly throughout the tree. Suppose, for the sake of intuition, that the good and bad splits alternate levels in the tree, and that the good splits are best-case splits and the bad splits are worst-case splits. Figure(a) shows the splits at two consecutive levels in the recursion tree. At the root of the tree, the cost is $n$ for partitioning, and the subarrays produced have sizes $n- 1$ and $0$: the worst case. At the next level, the subarray of size $n- 1$ undergoes best-case partitioning into subarrays of size $(n-1)/2 - 1$ and $(n-1)/2$ Let’s assume that the boundary-condition cost is $1$ for the subarray of size $0$.
The combination of the bad split followed by the good split produces three sub- arrays of sizes $0$, $(n-1)/2 - 1$ and $(n-1)/2$ at a combined partitioning cost of $\Theta(n)+\Theta(n-1)=\Theta(n)$. Certainly, this situation is no worse than that in Figure(b), namely a single level of partitioning that produces two subarrays of size $(n-1)/2$, at a cost of $\Theta(n)$. Yet this latter situation is balanced!

The average-case running time of an algorithm with respect to some distribution $D$ is, by definition, the expected running time of the algorithm when run on an input sampled according to $D$.
This should be contrasted with worst-case running time, which is the maximum running time on any input of a given length, and best-case running time, which is the minimum running time on any input of given length.
Since worst-case and best-case running time are defined as maximum and minimum, there are inputs attaining them. Average-case running time is an expectation, and so it is meaningless to talk about an input attaining them.
If you throw a die, the expected number you get is 3.5. This is not attained by any particular throw. If the die had 5 sides, the expected number is 3, which does correspond to some throw, but that doesn't mean that the throw is "average case".

What sometimes happens is that you can isolate a class of inputs $X$ such that when run on an input from $X$, the running time of the algorithm is within a constant factor of the average-case running time (for this to make sense, $X$ should actually corresponds to a sequence $X_n$ of inputs of every length, or at least infinitely many length). You can say that $X$  "achieves" the expected running time of the algorithm.


Proof language A= { 0^i 1^j where j>(i mod 3), j ≥0 , i≥0} is regular language $A = \{0^i1^j \text{ where }j>(i \text{ mod }3), i \geqslant 0, j \geqslant 0\} $

I know that A is a regular language, since we can construct the DFA or the NFA, but i dont know how to construct it, Can somebody help me please? Thank you

$A$ is regular since it's the union of the following $3$ regular languages:

$\{0^i 1^j : i \bmod{3} = 0, j > 0 \}$ for which a regular expression is $(000)^*11^*$.
$\{0^i 1^j : i \bmod{3} = 1, j > 1 \}$ for which a regular expression is $(000)^*0111^*$.
$\{0^i 1^j : i \bmod{3} = 2, j > 2 \}$ for which a regular expression is $(000)^*001111^*$.

A reguar expression for $A$ is then $E = (000)^*(1 + 011 + 00111)1^*$. You can now easily construct a NFA from $E$.


How does one show $(\lambda x . (\lambda y.x))yx \equiv_{\beta} y$ in lambda calculus? I wanted to show:

$$ (\lambda x . (\lambda y.x))yx \equiv_{\beta} y $$

the definition of beta equivalence is on page 17 of these notes.

I did a few attempts but got different things like $x$. I think my main confusion is how to interpret:

$$ yx $$

at the end. Does that mean we are applying $x$ to $y$ or that we are applying $yx$ to the lambda function $(\lambda x . (\lambda y.x))$? I tried both interpretations and didn't get anything that made sense.

I think I understand what $\beta$ conversion means (cuz I could follow the example he gave) but then when I tried doing it myself on this weird example I got non-sense.

I will make my answer more sophisticated by using parentheses. The first thing to realize is that $(\lambda x . (\lambda y . x)) y x$ is the same thing as $((\lambda x . (\lambda y . x)) y) x$ because in $\lambda$-calculus application associates to the left, which means that $A B C = (A B) C$. As you can see, $x y$ does not even appear in your expression.

After that, I would follow Yuval's observation that it is impolite to use the same variable for two different purposes: the $x$ and $y$ inside $\lambda$'s are not the same as the outer $x$ and $y$. We should rename bound variables to get
$$((\lambda a . (\lambda b . a)) y) x$$
Can you do it from here?

P.S. Please stop pelting us with questions about $\lambda$-calculus that all look alike. Take them one at a time, wait for the answers, and think about them. It is likely subsequent questions will become redundant.


How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar? Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$.  Is it possible to convert $G$ into an unambiguous grammar which also generates $L$?  If so, how would I go about doing this?  One starting approach I see is to have rules of the form $S \longrightarrow w $ in the new grammar, where $w$ is a string that was ambiguous in the original grammar.  I'm not sure; however, how I'd go about modifying the original grammar to a further extent.  Of course, we'd like to keep much of $G$ for our new grammar, insofar as $G$ unambiguously generates strings of sufficient length.

Here is the skeleton of the proof. I leave it to you to fill in the
details.

Let $R$ be a FSA recognizing the set $A$ of ambiguous strings of $G$
(yes, I am generalizing a bit the problem to regular sets of ambiguous words, since it is no harder). Let
$\bar R$ be a DFA recognizing the complement $\bar A$ of $A$: $\bar
A=\Sigma^*-A$.

We can use the cross-product construction for intersection of the
languages of a CF-grammar and a FSA, applying it to $G$ and $\bar R$
to get a CF grammar $G'$ that recognnizes $L'=L-A$. This grammar $G'$ is
not ambiguous, since it has exactly the same parse trees as $G$, up to
renaming of non-terminals (and the ambiguous words have been removed).
The FSA $\bar R$ has been chosen deterministic to make sure it has at most one accepting computation on any input, and thus does not introduce new ambiguities.

Then, Since the language $A$ is regular, it is easy to produce a
non-ambiguous CF (or regular) grammar $F$ that recognizes $A$.

Then, given the two non-ambiguous grammars $G'$ and $F$, generating
respectively $L'=L-A$ and $A$ which have an empty intersection, it is
easy, with one extra production rule, to produce a non-ambiguous grammar $G''$ that
recognizes the union $L'\cup A=(L-A)\cup A=L$.

So the non-ambiguous grammar $G''$ generates the language $L$. QED

That is all very nice, but given some CF grammar G you may not be able
to do all this, even when it is actually possible.


Base of logarithm in runtime of Prim's and Kruskal's algorithms For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|))$ and Kruskals's algorithm has runtime $O(|E|\cdot \log(|V|))$.

What is the base of the $\log$?

To expand on what David Eppstein said, you can assume it's in any base.

If the log were initially in base $b$, it is asymptotically the same as if it were in base $k$:

$$O(\log_b n) = O\left(\frac{\log_k n}{\log_k b}\right) = O(\log_k n)$$

because $k$ and $b$ are both constants; $\log_k b = O(1)$.

The logs in any two bases are the same in big-O notation.


How are codes like 5421 and 2421 unique? For the number 6, if I need to represent it in 5421 code form, should I code it as
1001 or 0110? Why should I choose the one over the other?

Similarly for the number 5 in 2421, is it 1011 or 0101?

Edit 1:

In a weighted binary code, the name of the code indicates the weight assigned to each place.

So if the code is 8421, the number 9 would be written as 1001 (8*1 + 4*0 + 2*0 + 1*1=9). And the number 5 would be 0101 (8*0 +4*1 +2*0 +1*1=5). In each case, no other combination of weights add up to the values (9 and 5).

Edit 2:

But for 5421, can the number 5 be represented as 1000 (5*1+4*0+2*0+1*0=5) as well as 0101(5*0 + 4*1 + 2*0 + 1*1 = 5)? Which one should be chosen? Similarly for 2421, which one to choose between 1011 (2*1 + 4*0 + 2*1 + 1*1 = 5) and 0101 (2*0 + 4*1 + 2*0 + 1*1 = 5)?

Codes like 5421 and 2421 are not unique, and this is one of their advantages. For example, 2421 is self-complementing: computing the 9-complement of a digit is the same as negating its bits. In textbooks you can find tables in which the authors choose one possible code for each digit, but this choice is arbitrary, and you might find different choices in different textbooks.

Let me also mention that BCD has been gradually losing favor, and I expect only old hardware to use anything other than 8421 (if at all). Most of the interest in BCD is historical, since modern architectures don't use BCD. I suspect that material about BCD is there mostly because of inertia, though BCD might still be used in conservative industries such as banking.


Is regularity of the language accepted by a given Turing machine a semi-decidable property? Given is the definition of a general problem: $\{ \langle M,  S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of languages S?

I'm stuck with the following instance of that problem: $L = \{ \langle M \rangle \mid M \text{ is a } TM, L_M \in \mathrm{REG}\}$. I have found proof that it is undecidable, however I'm stuck at finding if it's recognizable (synonyms: Turing-acceptable, semidecidable, ...) or not.

The problem in words means: Given a TM M, does the TM decide a language that is an element of REG (the set of regular languages)?

To prove a language is not semi-decidable, I would try to prove that it's complement is semi-decidable and that the language is not decidable (which I did by reduction from the Halting-problem).

To prove it is semi-decidable, I would prove it by reduction to the $A_{TM}$, which is semi-decidable.

I have tried both for this problem, but I get stuck / lose my way of thinking at every try ... Some directions would be greatly appreciated!

You have a good idea for proving that $L$ is not semi-decidable but it's not going to work since neither $L$ nor $\overline{L}$ are semi-decidable. Intuitively, how can saying after finite time "this language is not regular" be easier than "this language is regular" -- you can only inspect finitely many inputs, and all finite languages are regular (thus we can not separate REG from other classes on finite samples).

So we are left with our basic device: reduction from a non-semi-decidable language. The canonical one is the complement of the halting problem, i.e.

$\qquad\displaystyle \overline{K} = \{ \langle M \rangle \mid M(\langle M \rangle) \text{ loops}\}$.

Now we have to define a function for every $M$ whose accepted language is (non-)regular depending on whether $M$ halts on itself in order to establish the contradiction.

So, for any fixed TM $M$, define the following function¹:

$\qquad\displaystyle
    f_M(w) = \begin{cases}
                1, & w = a^n b^n \land M(\langle M \rangle) \text{ terminates after at most $n$ steps} \\
                0, &\text{else}
             \end{cases}
$

The function $f_M$ is clearly computable for any $M$; just check the form of the input and simulate $M$ for $n = \frac{|w|}{2}$ steps if necessary.
Note furthermore that given $\langle M \rangle$, we can compute $\langle f_M \rangle$; such compilation is possible because we have (or can assume) a Gödel numbering.

Now we have what we always want when reducing, the equivalence of doom:

$\qquad\displaystyle \langle M \rangle \in \overline{K} \iff \mathcal{L}(f_M) = \emptyset \iff \mathcal{L}(f_M) \in \mathrm{REG}$,

since $\mathcal{L}(f_M) = \{a^n b^n \mid n \geq N \} \not\in \mathrm{REG}$ if $M(\langle M \rangle)$ halts after $N$ steps, i.e. $\langle M \rangle \in K$.

Thus, if we had a semi-decider for your $L$, we could semi-decide $\overline{K}$ which contradicts what we know.

For ease of notation I use strings as inputs; of course, we'd work on naturals using some computable bijection.


What cannot be proven at compile-time about a computer program? Is there a Turing-Complete-ish programming language without runtime errors? Like segmentation faults, memory leaks, race conditions, deadlock/livelock/starvation, etc.? With strongly typed languages, the compiler can detect null pointer exceptions and refuse to compile code. How much can we statically check? Everything, or are there some things impossible to check?

Are there any language projects that are trying to do this (especially with concurrent and networked applications)?

EDIT:

I guess there are two sorts of behavior that I'm looking to avoid: unwanted erroneous behavior (deadlocks, etc), and runtime exceptions (divide-by-zero, etc).

Taking the example of divide-by-zero, can we create some computation x/y so that, whenever such a computation is done, we require y to be of the type T nonzero where T is integer, floating-point, or whatever for that overloaded operator?

With deadlocks, and other concurrent scheduling hazards, is there a set of control structures which cannot create those hazards, or better yet, can detect those hazards at compile time (better because I think it might be more expressive)?

In the theory of programming languages there are the so-called safety theorems which tell us that programs "do not do bad things". A typical safety theorem says:

  Safety theorem: If a program $P$ has a type $T$, then it either runs forever or it terminates and yields a value of type $T$.

Not every language satisfies such a theorem, and in fact, it usually takes a bit of work to make sure that a language is safe. Once we have the theorem, the compiler can make a strong guarantee by checking that the program has a type.

The safety theorem guarantees that:

A program which has a type will never get stuck, i.e., it will not encounter an undefined state.
A program which has a type will not suddenly switch to doing something completely diffrerent, for instance, it will not return a string if its type is int.

What exactly this means in practice depends a lot on what sort of information is expressed by the types of the language. For example, since a well-typed program will not get stuck, we can be sure that it will not segfault, and it will not perform an invalid pointer dereference. This is quite useful to know. Many modern programming languages strive to provide this sort of guarantee, or actually have it in cases of programming languages that have formal definitions (SML).

There are other kinds of errors which we might try to prevent, for example division by zero. Since it is non-computable whether a particular operation will happen at runtime, we cannot expect that the compiler will simply figure out whether division by zero is possible. In order to recover the safety theorem in presence of division by zero we can introduce exceptions into the language and make sure that division by zero raises an exception (rather than encounters an undefined state). The safety theorem then says:

  Safety theorem (with expcetions): If a program $P$ has type $T$, then it runs forever or terminates by either returning a value of type $T$ or raising an exception.

This sounds like cheating but is the best we can do with this sort of language. It is also a very common solution, also because exceptions are a generally useful programming concept (they are not errors, but rather a flow control mechanism). We can do slightly better if we allow the types to contain information about exceptions. Java does this with the throws declaration. Note however, that types cannot describe runtime exceptions exactly because that would make type checking non-computable.

Another way to deal with division by zero is to design the language in such a way that it is impossible to divide by zero. This could be accomplished by having a construct

x / y orelse z

which divides x by y if y is not zero, or returns z otherwise. Most programmers would find this kind of solution impractical.

Deadlock and race conditions are problematic in the same way as division by zero. In the general case it is non-computable whether a deadlock, or a race condition will happen. There are two lines of attack (just as with division by zero):

We can have more expressive types which guarantee that deadlock does not happen. The danger is that the types will be so fancy that type checking becomes undecidable, or that programmers will find the types too complex to understand.
We can design the language so that deadlock is impossible. The danger is that we will impoverish the language by doing so.

Regarding the second point above: programmers and designers of programming languages both like to use loss of expressivity as an excuse for a non-safe design. A case in point is the null pointer/object/value, where it is often falsely claimed that not having null is impractical and results in slower code. Good design goes a long way, and sometimes requires change of habits, but brings many many advantages. (It used to be the case that "real programmers" disliked garbage collection, and never admitted to themsleves that their programs leaked memory because humans could not allocate and deallocate memory by hand correctly).

In general, by making types even fancier, we can make sure that the safety theorem precludes other kinds of bad behavior by specifying good behavior. For example, in a dependently typed langauge such as Idris you can specify that your program sorts lists, in which case it can't cause division by zero, nor can it run forever. (But now the compiler may possibly need a lot of help from the programmer in order to establish that the program really has the stated type.)

You might expect also that a compiler shold be able to guarantee that a well-typed program must terminate. However, this is non-computable (Halting Oracle), not to mention that there are many useful possibly non-terminating programs (such as the browser you're using right now, and the operating system). If you need termination guarantees, then instead of referring to a safety theorem, you can design the language so that it cannot express a non-terminating computation. An example of such a language is Agda, which is also dependently typed and it doubles as a proof assistant. Note however that there is an important theorem stating that a language with computable syntax in which all programs terminate is not Turing complete.


What is the machine epsilon and number of mantissa bits for TI-83? I am trying to determine how many bits the TI-83 Plus uses to store floating point numbers. I am using the algorithm for approximating the machine epsilon given in "Numerical Mathematics and Computing" by Cheney and Kincaid. In TI-BASIC, it looks like this:
: 1 -> E
: While (1+E) > 1
: E/2 -> E
: End
: Disp 2*E

The program returns 9.31322575E-10, which is equal to $2^{-30}$. This is an approximation within a factor of 2.
Here's where I get confused. In the textbook I mentioned above, they say that the number of binary digits used in the mantissa, $k$, is given by $u=2^{-k}$, where $u$ is the number we just found. This is easy to verify for things like IEEE-754 format, because the mantissa is stored as its base 2 representation, so k is the number of bits allocated to the mantissa. However, as far as I can tell from sources like this, the TI-83 does not use IEEE-754 floating point, but different floating point encoding scheme with 7 bytes of binary-coded decimal for the mantissa (that's 14 decimal digits). If that is true, then it seems to me like the machine epsilon should be $10^{-14}$. Furthermore, this means the number of mantissa bits is 56, rather than 30.
How can I rectify these two things?

the TI-83 does not use IEEE-754 floating point, but different floating point encoding scheme with 7 bytes of binary-coded decimal for the mantissa (that's 14 decimal digits).

Yes, and in order to deal with that, the program should take into account the base of 10:
1->E
While (1+E)>1
E/10->E
End
Disp 10*E

This results in $10^{-9}$, not $10^{-14}$ - though actually 14 digits would imply that $\epsilon = 10^{-13}$. There's still something missing to explain that result, and that thing is that the TI83+ sometimes rounds to 10 digits, for example for printing, but also for the purpose of comparisons. For the purpose of subtraction, that rounding is not performed. You can see the difference with a program like this, showing that there is more internal precision than 10 digits after all:
1->E
While (1+E)>1
E/10->E
End
10E->E
For(X,1,5
Disp 1+E-1
E/10->E
End

This program shows that evaluating $1+E-1$ for $E = 10^{-12}$ still does not yield zero, while for $E = 10^{-13}$ it does yield zero. We should be careful not to conclude that therefore $\epsilon = 10^{-12}$, it's more complicated. There seems to be a special rule the zeroes out small differences. That elusive 14th digit does exist though it's well hidden, for example this demo shows it:
1+8|E~13->X
Disp X*2-2

(this is SourceCoder syntax, |E is the small E made by pressing 2nd and ,, ~ is unary negation (-)).
This program doesn't print zero, so the 14th digit has to exist internally, even though the TI83+ tries very hard to deny it. Whether this means we should say that $\epsilon = 10^{-13}$ is not clear to me. $1 + 10^{-13}$ is technically different from $1$, but they compare equal and evaluating their difference yields zero.


Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium? The deferred acceptance algorithm solves the Stable Marriage Problem in a two-sided network, where each agent has complete preferences over each agent of the other side. There is always at least one stable matching but there can be several. Traditionally, the problem was solved by having men propose and women accept/reject a proposition, which leads to a stable matching that is male-optimal but at the same time female-pessimal. But it is also possible to switch roles and have women propose and men accept/reject, which leads to the female-optimal stable matching, which at the same time is the male-pessimal.

Now, imagine a network with more men than women. I observed that in this case the male-optimal matching and the female-optimal matching are (so far) always identical, as in this simple example:

    Women's preferences
        A   B   C   D
M   U   1   1   1   2
e   V   2   2   2   1
n   W   3   6   5   4
    X   6   3   4   5
    Y   5   4   3   6
    Z   4   5   6   3
Read: Woman A's 1st choice is Man U

    Men's preferences
        U   V   W   X   Y   Z
W   A   1   1   2   2   1   1
o   B   2   2   1   4   2   2
m   C   3   4   3   1   3   3
e   D   4   3   4   3   4   4
n
Read: Men W's 4th choice is Woman D

    M   F   pM  pF
    U   A   1   1
    V   B   2   2
    Y   C   3   3
    Z   D   4   3
    W   NA  0   NA
    X   NA  0   NA
    Read: Man Z is matched up with Woman D. She is his 4th choice, while he is her 3rd choice

Above example returns the stable matching consisting of four matches A<->U, B<->V, C<->Y and D<->Z (while men W and X did not find a match), regardless if I start with men proposing or women proposing.

Now, what are the consequences if there is only one stable matching? I would love to understand if my thoughts are correct:

First, I observed in my model always the same result, regardless if I used female-optimal algorithm or male-optimal. Since male-optimal solution = female-optimal solution, I claim there exists only one stable solution, which naturally is the optimal (and pessimal) solution for both genders.
Second, given this stable matching, I cannot improve anybody's position in a ranking without making another person's situation worse. The algorithm stops once there is no blocking pair. Therefore, this matching is pareto efficient.
Third, if only one stable matching exists, there is no possibility for any of the players to improve their situation by changing their strategy and creating a fake preference list (stating their actual preferences is their best strategy). I claim therefore that this is a Nash Equilibrium.

Example: In above example, U and A both have received their very first choice. They cannot be possibly happier. V and B would have liked A and A better than each other, but as U and A are already matched up with their ideal partner, V and B are the next best option. This continues until W and X, who both ended up without a match. However, no matter how they would have ranked their preferences, they always would have ended up without a match

First, while the Gale-Shapely algorithm guarantees that at least one stable matching exists, it need not be unique$^*$.

However, note that when the male-optimal and female-optimal matchings are the same, the stable matching is indeed unique, as shown in this answer.

As the male-optimal and female-optimal matchings coincide, both can be considered the 'optimal' side and therefore is Pareto optimal for both sides.

Your third argument however, is incorrect. While it is true the matching is unique, this is under the assumption that all preferences are true. As this is not the case, we cannot use this fact to conclude strategy-proofness on both sides.

However, we have the stronger property that the female and male optimal matchings coincide. This again means that the properties the algorithm assigns to the male side automatically apply to the female side and therefore the matching is strategy-proof for both sides.

(Another way to argue is that any manipulation cannot give the woman them a better result than switching sides with the men. But they already have the result they would get by switching! So they cannot improve by manipulation.)

*: Further conditions for uniqueness are explored in a paper by Jan Eeckhout:

The 'sufficient' condition for uniqueness (Theorem 1) basically says that if we order all men and women and if

All women of rank $i$ prefer the man of rank $i$ to any man of higher rank; and
All men of rank $i$ prefer the woman of rank $i$ to any woman of higher rank.

Furthermore, the paper mentions that if we match among a total of $4$ or $6$ persons, these conditions are also necessary for uniqueness.

If we want to talk about a Nash-Equilibrium, we have to phrase the matching process as a game. We can consider all men and women to be 'players' and their 'strategy' to be the preference profile they submit (which may differ from their actual preference, which determines the payoff). A set of strategies is said to be a Nash-Equilibrium if changing a single strategy of a single player cannot improve the results for that player. As we know that the current matching process is strategy-proof for all players involved, improving on 'everyone reports truthfully' is impossible. So, in this sense, the 'everyone reports truthfully' set of strategies is a Nash-Equilibrium.

In fact, we can say that strategy-proofness of our matching means precisely that the 'every reports truthfully' is a Nash-Equilibrium in the associated game we defined.


Algorithms online problems I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations.

As far as I can see, the sites that I found (CodeChef, Project Euler) seem to be more programming oriented, even if I like the format and their challenge. That is, even when speed is somehow important, you cannot not know the exact complexities values for the algorithm (the lovely greek letters), maybe some demonstration of the efficiency of the solution.

An online course or a book is acceptable if it is more problems oriented. In my opinion, these are the kind of questions that a development top company should ask anyway.

Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms (MIT Press, 3rd edition, 2009) is a good book for understanding and solving time complexity and correctness of
algorithms mathematically.


Providing Tight Example in Approximation Algorithm Analysis Let's say I found  a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight.

Do I now need to come up with an example of generic size $n$ or does it suffice to show that I   have an example of size $10$ for which the algorithm yields $2OPT$?

That depends on your definition of approximation ratio. Normally the approximation ratio is defined as the worst ratio between optimal solution and the one produced by your algorithm. If this is the case, all you need to show that the ratio is tight is come up with one bad example.

Sometimes, however, you prove something like $ALG \leq 2OPT + 1$. This means that your approximation ratio is really $2 + o(1)$. To show that this is tight, you will need an example for infinitely many sizes (but not necessarily for a generic size; perhaps all your examples have even size).


Total number of bits of storage for direct mapped cache I have a homework assignment dealing with caches. We are asked to compute the total number of bits of storage required for the cache, including tags and valid bits. Then compute the overhead for the cache incurred by the tags and valid bits.

Info given: Consider a direct-mapped cache with 16KBytes of storage and a block size of 16 bytes. Assume that the address size is 32 bits.

So I've done the calculation and get a total number of 32 bits required. We were given the following formula:

(bits/tag) + (bits/index) + (bits/block offset) = total number of bits

I am unsure about my number of sets.
I did this by:

16 byte blocks is 2^4, so 4 bits for block offset
2^32 / 16 bytes per frame gives us 2^28 blocks
2^28 blocks / 65536 sets gives us 2^12 blocks/set, so we need 2^12 unique tags
Add them together: 12 (bits/tag) + 16 (bits/index) + 4 (bits/block offset), which gives us 32 bits

I got my number of sets from 2^size, which is 2^16.

The second issue I'm running into is now calculating the overhead, given those numbers.

We were provided the formula

(Address size - bit offset - bit block offset) * number of frames = kbits of tags

When doing this, I get the following:

(32 - 16 - 4) * 65536 = 12 * 65536 = 786432bits
= 786432bits / 1024 = 768 KBits
= 768 * 0.125 = 96 Kbytes
= (96KBytes / 16KBytes)
= 600% overhead

Which obviously does not make sense.

I believe my issue is the number of sets, but from what I can gather from online and our lecture notes, the number of sets (in a direct-mapped cache) is equal to the size of the cache, so that would be 2^16, so 65536.

We have lecture notes that describe how to do this, but they were with 8byte blocks and we were told the number of sets (in the case of the notes, the size was 256, which is 2^8, which I can only presume is 2^block size).

Any insight will be of help!

I'll give these hints without actually solving it for you

1) You do not need to provide tags for all memory, only for the memory that is in the cache.

2) As the block (cache line) is 16 bytes, you only need one tag for each of these.

3) The valid bit are also only for the cached I guess.


Number of triangles in an undirected graph How do we count the numbers of traingles (i.e., different triads of vertex $u,v,w$ such that edges $u-v,v-w,w-u \in E$ ) in a given graph $G$?

It is obvious that it can be done in $O(N^2)$: is there anything better?

I'm assuming that the graph is given as an adjacency matrix. The trivial algorithm for counting triangles goes over all triples of vertices $u,v,w$ and checks whether $\{u,v,w\}$ is a triangle, for a total running time of $\Theta(N^3)$. This can be improved using matrix multiplication: if $A$ is the adjacency matrix, then the number of triangles can be extracted from $\operatorname{Tr} A^3$, taking into account the number of vertices and edges in the graph (details left to you). This takes time $O(n^\omega)$, where $\omega$ is the exponent of matrix multiplication.


cancel out parts of a formula in CNF (conjunctive normal form) In this image there is a given formula in DNF and CNF. When I check it on Wolfram Alpha I see that it cancel out (E or D) because of (not A or A) which is colored in red. My question is if it is allowed to cancel out (not A or D) because of (not E or E) which is colored in green instead. THX

It's probably useful to note that the resolution rule can be used to figure out exactly which literals (things like $\neg A\vee D$) may be deduced from the others.

In this case, the resolution rule applied to the clauses $\neg A\vee \neg E$ and $E\vee D$ results in the clause $\neg A\vee D$, which shows that that clause is redundant.


CFG for $\{a^ib^jc^k \mid i \neq j+k\}$ I am trying to design a context-free grammar for the language $L = \{a^ib^jc^k \mid i\neq j+k\}$ over the alphabet $\Sigma = \{a,b,c\}$.

I know that I can split this up into the union of two cfg's $S_1$ and $S_2$,
where $S_1$ is the case where $\#_a \lt \#_b + \#_c$,
and $S_2$ is the case where $\#_a \gt \#_b + \#_c$.

I keep producing the grammar that generates this language but not in the correct order, that is I am having a hard time keeping the $a$'s on the left, $b$'s in the middle, and $c$'s to the right. Is this even context free?

I would start by finding a CFG that generates the balanced version $\{a^ib^jc^k\mid i=j+k\}$ from nonterminal $C$.

   $C\rightarrow aCc\mid B \\ B\rightarrow aBb\mid\varepsilon$

Now, as you correctly note, there are two possibilities on how to get the unbalanced version; either there is $(a^+)$ to the left, or $(b^+\mid b^*c^+)$ on the right. To deal with the former possibility, you simply add the following rules.

$
S\rightarrow aL\\
L\rightarrow aL\mid C
$

You can deal with the other two possibilities in similar manner.

   $ S\rightarrow R_bb\mid R_cc\\R_c\rightarrow R_cc\mid R_b\mid C\\R_b\rightarrow R_bb\mid B$


Rules regarding Chomsky Normal Form (CNF) grammars I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions:

Can I use a single variable (a non-terminal) on the left-hand side of multiple rules?
Can I use a single variable (a non-terminal) twice on the right-hand side of a single rule?

For instance, is the following grammar properly in Chomsky Normal Form?  Is it OK that I have two rules with $S$ on the left-hand side?  Is it OK that I have $X$ twice on the right-hand side of the second rule?

$$S_0 \to S$$
$$S \to XX$$
$$S \to XZ$$
$$\vdots$$

The production

$$S_0 \to S$$

is not in CNF. CNF requires that nonterminals produce either two nonterminals or one terminal. Since the above line shows a nonterminal producing a single nonterminal, it does not fit. The CFG in CNF would be just:

$$S_0 \to XX$$
$$S_0 \to XZ$$
$$\vdots$$

To answer your original questions, though, yes, you can do the above in CNF. There are no stipulations about how many times a nonterminal may appear on the left or whether it can be duplicated on the right.


Would using the mean as pivot speed up quicksort? Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was:
'If we could consistently choose a pivot from the middle 50 percent, we would only have to split the list at most $\log_{4/3} n$.
The choice of the pivot seems to be one possible problem of quicksort that can lead to $O(n^2)$ behavior.

My idea was: If in each step one would use the mean of the partition as pivot, this could increase the speed significantly.
Especially after a few steps, when outliers are in their own division of the list, the mean and median should be very close to each other (once again, looking at large lists).
The additional time during each step to calculate the mean should be $n$. Therefore:

Quicksort estimated time: $nA\log_{4/3} n$

Quicksort_mean estimated time: $2nA\log_{5/3} n$

(5/3 is most likely a conservative estimation by me, could as well be closer to 2, as subsets should quickly be without outliers).
So, starting at around 10,000 entries Quicksort_mean would be (on average) faster than Quicksort. Furthermore, it would never risk to be $O(n^2)$, as it is bound to not take the minimal or maximal element of the stack.

My main question is: Did I miss anything? I have to admit, I never implemented quicksort myself, so I might miss out on other parts of the whole thing (storage, etc.)

Using the mean for your partition does not prevent the $\Omega(n^2)$ worst-case behavior. It occurs when the input list is exponentially increasing. Consider the input:

$1,n^2,n^3,\ldots,n^n$

The mean of this set is (asymptotically) $n^{n-1}$ so you obtain the worst partition possible. This is a bit of a cheat considering that storing the list takes $\Omega(n^2)$ space if the numbers are represented as integers. But if you are sorting floating-point numbers then this scenario is concievable.

However, it is possible to calculate the median of a set (or any other order statistic for that matter) in $O(n)$ time so if you really care about run time guarantees for quick sort you should use that rather than the mean.

However, in all practical scenarios the additional cost of computing the mean/median is so large that picking a random pivot almost always is faster.


Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm? I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and operations such as swap are ignored. Link to selection sort analysis. Please help me understand.

There are 2 major reasons:

For most algorithms the number of other operations can be bounded by a multiple of the number of comparisons (i.e. runtime in $\mathcal{O}(\#comparisons)$). This is because e.g. a swap does not occur without a prior comparison requiring this swap (depends on algorithm).
Using comparisons you can prove an $\mathcal{O}(n \log n)$ lower bound for any comparison based sorting algorithm on $n$ elements.


Can you say anything interesting about a language knowing only that it is prefix-closed? Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$).
Knowing only this, can you give any positive or negative decidability or complexity results about $L$?
Thanks! :)

If $P$ and $Q$ are languages closed under prefix, then
$P\cup Q$, $P\cap Q$, $P \cdot Q$, $P/Q$ are also closed under prefix. Also you can think of such a language $L$ as a directed tree. Define the graph/tree $G = (V,E)$ where $V = L$ and
$$E = \{(\mathit{prefix}(w),w) \mid w\in L \}$$
(the words are the nodes and the parent of every word is its prefix).
Note that I assume that $\mathit{prefix}(x) = \varepsilon$ for all $x\in\Sigma$, meaning that the prefix of a single symbol is the empty word. Thus the root of the tree constructed above is the empty word. The constructed tree can be easily transformed to a DFA recognizing the language (I think you can see how).


An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron? Suppose I have a set of points in 3D which are all co-planar, and which describe the vertices of a convex polygon. I know the coordinates of all of these vertices, I know the unit normal to the plane of the polygon, and I know the order (in a right-hand sense with respect to the normal) in which the vertices go around the polygon.

I also have a polyhedron, which is in general non-convex, and the surface of which is made of triangles. It is a triangle mesh like the one shown here. It describes a completely enclosed volume (no holes in the surface). I know the coordinates of all the vertices of all the triangles that make up the polyhedron. For a given vertex, I know the list of which triangles it is a vertex of.

One other thing I know, which may or may not be useful, is that the polygon lies "in the vicinity of" a particular pair of vertices of the polyhedron, say the ones with indices $i$ and $j$. So if there were to be some kind of a search of the surface of the polyhedron, that would be the place to start.

My task is to find the area of the intersection between the polygon and the polyhedron. I believe this is a well-defined quantity. I need an algorithm to calculate this, hopefully efficiently but at this point I'll take anything.

My thoughts:

I can classify each polygon vertex as either inside or outside the polyhedron. I've written a ray-casting algorithm that computes this fairly accurately and efficiently. That means that each edge of the polygon can be classified as either "both vertices inside", "both vertices outside", or "one in, one out." I can calculate the point of intersection between a given polygon edge and the polyhedron by checking a bunch of nearby triangles.

But that's not enough. For instance, just because both vertices of an edge are inside doesn't mean the whole edge is inside. A "finger" of the polyhedron might intersect an edge without touching either of its endpoints. Furthermore, the polyhedron might intersect the polygon in such a way that it doesn't touch any of the edges at all. Clearly, one must also calculate the intersections between the triangles' edges and the polygon as well.

It gets a bit too complicated for me at that point, and I'm wondering if there is some established algorithm for this?

Perhaps something like: Project the polyhedron onto the plane containing the polygon and then... I don't know.

You have a 2D convex polygon $G$, and a 3D polyhedron $H$.  Let $P_G$ denote the plane that the polygon is contained in.  The following should work:

Their intersection is a 2D polygon.  You can find the edges of the intersection as follows:

For each triangle of $H$:

If the triangle intersects $G$, output this intersection.

This procedure outputs the edges of a 2D polygon, and now you want to compute its area.  To do this, compute a triangulation of it (which apparently can be done in linear time), then sum up the area of the resulting triangles.

You can test whether a triangle intersects $G$ as follows: compute the intersection of the triangle with $P_G$; call the result $R$.  Typically, $R$ will be a point or line.  $R$ can be computed efficiently.  Then, compute the intersection of $R$ with $G$.  This is purely a 2D problem.  There are standard algorithms for solving this; see, e.g., https://en.wikipedia.org/wiki/Line_clipping or http://geomalgorithms.com/a13-_intersect-4.html.


Approximate probabilities of passing a NIST statistical test I am working with random number generation and testing, so I'm using NIST statistical tests to examine my random numbers. Now I want to compare my solution with other RNGs, but i can't find any probabilities of passing a NIST statistical test for them. So does anyone have that info? Info about both PRNGs and TRNGs would be appreciated.

Have a look at TestU01. It's another testing suite that has NIST built in. It also has implementations of most of the well-known RNGs, so you can compare. The documentation may have some results listed in it.


A variation of the halting problem Given an infinite set $S \subseteq \mathbb{N}$, define the language:
$L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $\epsilon$, or, $T_M \in S\}$
where $T_M$ is the number of steps that $M$ takes until it halts with the empty word $\epsilon$ as input (or $\infty$ if it doesn't halt).

What are the sets $S$ such that $L_S$ is decidable?

There are some more trivial cases, if $S = \{k,k+1,k+2, \dots \}$ for some $k \in \mathbb{N}$ then $L_S$ is clearly decidable, as we can simulate $M$ on $\epsilon$ for $k-1$ steps and accept if and only if $M$ didn't halt. though, if we take $S= \{k,k+2,k+4,\dots \}$ for some $k \in \mathbb{N}$, or even simply taking $S=\mathbb{N}_{even}$ or $S=\mathbb{N}_{odd}$ this becomes more of a problem, because there is no prevention from it being impossible to have a finite calculation for whether the number of steps until halting will be even in the cases where it halts. Although this seems undecidable I'm not sure how to prove this.
I generally suspect that $L_S$ is decidable if and only if $\mathbb{N} \setminus S$ is finite and $S$ is decidable

$L_S$ is undecidable if $S = \mathbb{N}_{odd}$:
The problem of whether a given TM accepts $\epsilon$ is undecidable. There is a simple reduction from this problem to the problem of membership in $L_S$ when $S = \mathbb{N}_{odd}$.  Given a TM $M$, we create a new TM $M'$ which on any input simulates $M$ on the same input, but for each step of $M$, it takes one (or any finite odd number of) extra redundant step(s). This basically makes sure that the number of steps taken by $M'$ on any input is always even.
Now, since $T_{M'} \notin S$, hence, $M'$ is in $L_S$ if and only if $M'$ doesn't halts on $\epsilon$, which in turn implies that $M$ doesn't halt on $\epsilon$. Hence, this language is undecidable.
A similar proof can be also given for $\mathbb{N}_{even}$.
[Undecidable $S$ with Oracle Machines]
$L_S$ is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.
Assuming that the set $S$ need not be decidable itself, and we are going to use it as an oracle and check for decidability using oracle machines.
We construct the set $S$ as follows: for each Turing Machine $M$, let it's binary encoding be $\langle M \rangle$, and let the length of the string $\langle M \rangle$ be $n$. If $M$ doesn't halt on $\epsilon$, then we add the number $10^{n}\langle M \rangle$ to our set $S$. By construction, this set doesn't contain infinite numbers.
Now, the decider will work as follows: On an input $M$, it will check whether the number $10^{n}\langle M \rangle$ is in $S$. It will accept $M$ if the number if found, else we can be sure that the machine $M$ will halt, and hence we simulate $M$ on $\epsilon$ until it halts while keeping the count of the number of steps taken by $M$. We finally accept or reject $M$ on the basis of whether this count is in $S$ or not.
Hence, this language is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.
[Decidable S]
When the set $S$ is decidable, it will be interesting to know whether the hypothesis that "$\mathbb{N} \setminus S$ is finite" holds. I suspect that the answer would be affirmative.
Let $S' = \mathbb{N} \setminus S$ be infinite set. If $S'$ has "simple" subsequence in it (say, an Arithmetic Progression), then we can prove that $L_S$ would be undecidable by a proof similar to the one in the case of $S = \mathbb{N}_{odd}$. The idea is simply to run a construct a TM $M'$ which simulates $M$, and if $M$ halts, then jump to the next hole in $S$. $M'$ will be in $L_S$ iff $M$ halts.
This idea doesn't seem to work when $S'$ is a difficult set; by which I mean that checking the membership is hard in terms of time complexity.


Is k -rainbow coloring of a hypergraph NP-complete or not? **A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Is k-rainbow coloring of a hypergraph is NP-complete or not? The problem is also called "polychromatic coloring" **

I looked at some reference papers such as "Hardness of Rainbow Coloring Hypergraphs by Venkatesan Guruswami and Rishi Sakety" and "Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs by Venkatesan Guruswami and Euiwoong Lee". But these are the only reference I found discuss the problem but the authors foucs on generating balance rainbow coloring for K-uniform hypergraph where each color has to appear the same number of times in the hypergraph. It has been proved that K-rainbow coloring for planer graph is P for K= 2 and NP complete for K=3,4 according to this reference "Polychromatic Colorings of Plane Graphs".

My question " Is k-rainbow coloring of a hypergraph NP-complete or not?" in general for any hypergraph. I think this problem is related to vertex cover problem.

Deciding if a hypergraph can be rainbow colored in $k$ colors is NP-complete for every $k \geq 2$. A proof is given in [1, Theorem 12].

For $k=2$, the result follows immediately by observing the problem is equivalent to set splitting (also known as hypergraph 2-coloring). For $k \geq 3$, the authors of [1] give a reduction from chromatic index on $k$-regular graphs.

[1] M. Koivisto, P. Laakkonen, and J. Lauri. "NP-completeness results for partitioning a graph into total dominating sets". In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON), volume 10392 of Lecture Notes in Computer Science, pages 333-345. Springer, 2017.


Clarification regarding definition: Two way non deterministic finite state Automata In two way non-deterministic finite state automata there is the concept of reject state.

Since an input is accepted if any one of the parallel branches in the Non Deterministic FSA reaches an accept state and the rest of the branches are then immaterial.

On a given Input even if one of the branches reaches the 'reject' state and the other reaches the accept state (after processing the last input symbol) what do we do ?
If one of the branch reaches the reject state before processing the complete input what do we do? Continue processing the other branches that might lead to accepting the input and terminate only the local branch? Or the input is rejected (similar to accept state)?

As you clearly state, an input is accepted, by definition, if one of the parallel branches accepts. This means that an input is accepted if and only if at least one of the parallel branches accepts. So if one brach accepts and another rejects, the input is accepted.

In non-deterministic automata, acceptance and rejection are not symmetric. An input is accepted iff there is some accepting computation path. An input is rejected iff all computation paths are rejecting.


Show that a language is decidable iff some enumerator enumerates the language in lexicographic order The proof is given in the below:

If $A$ is decidable, the enumerator operates by generating the strings in lexicographic order and testing each in turn for membership in $A$ using the decider. Those strings which are found to be in $A$ are printed.
If $A$ is enumerable in lexicographic order, we consider two cases. If $A$ is finite, it is decidable because all finite languages are decidable. If $A$ is infinite, a decider for $A$ operates as follows. On receiving input $w$, the decider enumerates all strings in $A$ in order until some string lexicographically after $w$ appears. That must occur eventually because $A$ is infinite. If $w$ has appeared in the enumeration already then accept, but if it hasn't appeared yet, it never will, so reject.
Note: Breaking into two cases is necessary to handle the possibility that the enumerator may loop without producing additional output when it is enumerating a finite language. As a result, we end up showing that the language is decidable but we do not (and cannot) algorithmically construct the decider for the language from the enumerator for the language. This subtle point is the reason for the star on the problem.

I could not understand the rejection case in the last line in the second paragraph. The author said "if it has not appeared yet, it never will". Why, could anyone explain it for me in a simpler way?

Also I could not understand the last paragraph at all, could anyone explain it to me in a simpler way?

It's easier to think of $A$ as a list of natural numbers. If $A$ is decidable, then we can list all numbers in $A$ in increasing order by just testing all of them in order – Is $0 \in A$? Is $1 \in A$? And so on.

Now let us show that if $A$ can be enumerated in increasing order, then we can decide $A$. Let us try to use the following algorithm:

  On input $n$, enumerate all integers in $A$ in increasing order until a number $m \geq n$ appears. If $n$ has appeared, then clearly $n \in A$. If $n$ has not appeared, then $n \notin A$.

To see why the last point holds, suppose that $n=5$, and the enumeration starts $2,3,6$. At the point when we see 6, we know that 5 is never going to appear.

There is one problem with this algorithm – if $A$ is a finite language, then a number $m \geq n$ might never appear. Indeed, suppose for example that $A = \{2,3,5\}$ and that $n=6$. We see $2,3,5$, and then wait forever for a larger number to appear. We fix this problem in the following way:

If $A$ is finite, it is clearly decidable.
If $A$ is infinite, then the algorithm described above always terminates (why?).

Unfortunately, given just an enumerator for $A$, we (provably) cannot know whether $A$ is infinite or not, and so we don't know which of the two cases to use. Fortunately, this does not matter for the proof. All we need to do is show that if $A$ has an enumerator, then it has a decider. There is no requirement to turn an enumerator for $A$ into a decider for $A$ in a uniform fashion.


Show $f(n)\log f(n)^c=O(g(n)\log g(n))$ You are given functions $f$ and $g$ such that $f(n)=O(g(n))$. Show that $f(n)\log_2(f(n)^c)=O(g(n)\log_2(g(n)))$. (Here $c$ is some positive constant.) You should assume that $f$ and $g$ are nondecreasing and always bigger than 1.

My solution: There exists $c_1$ such that $f \leq c_1 g$. Note that all $\log$ functions are base 2 throughout.

We have that $f \log(f^c) \le c_1 c g \log(c_1g) = c_1 c g \log(c_1) + c_1 c g \log(g)$.

Let expression $(*)$ be as follows:

$(*) \quad c_1 c g \log(c_1) + c_1 c g \log(g) \le c_2 g \log(g)$ for some $c_2 > 0$.

Then $(*)$ holds iff $c_1 c g \log(c_1) < 0$ iff $0 \leq c_1 \leq 1$.

Now put $c_2 = c_1 c$, then:

$c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$ iff $c_2 / c > 1$.

Therefore, we require than $c_2 > c$, which we cannot guarantee as we have already fixed $c_2 = c_1 c$.

What choice of $c_2$ would guarantee that $c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$?

I am looking for a formal argument.

An essential hint: "Assume that f and g are nondecreasing". That is essential. Without it the statement is false, for example $f (n) = 2$ and $g = 1 + 2^{-n}$, where log f (n) = 1 and log g (n) ≈ $2^{-n}$.

The problem here is showing that f (n) = O (g (n)) implies log f (n) = O (log (g (n)). So how does "g is non-decreasing" help? Well, if n ≥ N then 1 < g (N) ≤ g (n) and 0 < log g (N) ≤ log g (n).

f (n) = O (g (n)) means "there are $N, c > 0$ so that we have $f (n) ≤ c·g (n)$ for $n ≥ N$". So there are $N, c > 0$ so that $\log f (n) ≤ c + \log g (n)$ for $n ≥ N$. Now we need to somehow relate c and $\log g (n)$. We have $c = (c \div \log g (N)) · \log g (N) ≤ (c \div \log g (N)) · \log g (n)$, because $g (n)$ is not decreasing. Therefore $\log f (n) ≤ (c \div \log g (N) + 1) · \log g (n)$, so we found a constant c' = (c / log g (N) + 1) such that $\log f (n) ≤ c' · \log g (n)$ for n ≥ N and that means $\log f (n) = O (\log (g (n))$.


If a Ptime function loses x bits of data at every call, is it a one way function? If we have a computational function $f(x)=g(f(x-1)^2)$, where $g(y)$ is a floating point operation, mapped onto a given number of bits say 32 bits (thus leading to loss of a given number of precision bits every time), is the function a one-way function?

A one-way function is a function which is easy to compute but hard to invert. More accurate, it is a polytime function $f$ such that given a random $y$, it is hard to find a preimage $x$ satisfying $f(x) = y$. The exact sense of hardness isn't important here.

Your function is not one-way since it fails the first requirement: it is not easy to compute. If you use your recursive definition, computing $f(x)$ takes $x$ applications of the function $g$, which is exponential time.

It also fails the second requirement, since its range is finite. You can hardcode one preimage for each possible value in the image, and so invert the function efficiently.


Proof of the Stable Matching Problem Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem.

Theorem 1.2.3 - page 12:

  In a man-optimal version of stable matching, each woman has worst
  partner that she can have in any stable matching.

Proof:

  Suppose not. Let $M_0$ be the man-optimal stable matching, and
  suppose there is a stable matching $M’$ and a woman $w$ such
  that $w$ prefers $m = p_{M_0}(w)$ to $m' = p_{M'}(w)$ . But
  then $(m,w)$ blocks $M'$ unless $m$ prefers $p_{M'}(m)$ to
  $w = p_{M_0}(m)$, in contradiction of the fact that $m$ has no
  stable partner better than his partner in $M_0$.

I'm having trouble visualizing the definition of the problem and the proof (what is the contradiction?).

First, what is the question implying?  From what I read and the fact that in most stable matching examples, all the women do not end up with the completely last person on their list ... So I'm a bit confused.

In the proof, here is what I am getting: in $M'$ we suppose $w$ prefers $m$ to $m'$.  But then if there is a stable matching containing $(m,w)$ this would leave $w$ with her worst partner and that is a contradiction.  Is this correct?

In addition, if $m$ did prefer $w'$ it would contradict that it is not his first pick ?

I'm new to computer science concepts so any help is appreciated.

The claim is not that every woman ends with the last man on her list. Rather, consider all stable matchings, and all partners of some woman $w$ in these stable matchings. Among them, pick the worst one (according to her view) $m$. Then in the man-optimal matching, $w$ is matched to $m$.

Now that you understand what they're trying to prove, read the proof again. (It couldn't have made sense before, because the claim as you stated it just isn't true.)


Approximating maximal independent set with a minimal vertex cover approximation The minimal vertex cover problem has a 2-approximation algorithm.

We can reduce the maximal independent set problem to the minimal vertex cover problem as shown here.

Does this mean that I can use the $2$-approximation for minimal vertex cover to get a $1/2$-approximation for maximal independent set?

My approach:

// is this a 1/2-approximation algorithm?
approxAlgForMaxIS(Graph G) {
    minVC = computeMinVC(G);
    maxIS = G.V - minVC;   // remove all vertices in the minVC from G
    return maxIS
}

No, unfortunately this doesn't work. Denote by $\newcommand{\VC}{\mathrm{VC}}\VC$ the size of a minimum vertex cover and by $\newcommand{\IS}{\mathrm{IS}}\IS$ the size of a maximum independent set, so that $\VC+\IS=n$. The approximation algorithm for $\VC$ produces a vertex cover $C$ whose size satisfies $|C| \leq 2\VC$. The complement of $C$ is an independent set $I$ whose size satisfies
$$
|I| = n-|C| \geq n-2\VC.
$$
Unfortunately, $n-2\VC$ can be much smaller than $n-\VC$, and there's no constant lower bound on the ratio $$ \frac{n-2\VC}{n-\VC}. $$

As an example, let's see how the algorithm which picks a maximal matching fares on a graph consisting of a matching on $n$ vertices. The minimum vertex cover has size $n/2$, and so the maximum independent set has size $n/2$. The maximal matching algorithm picks all edges in the graph and then all vertices contained in them – in other words, it picks all vertices. It thus gives a vertex cover of size $n$, which corresponds to an independent set of size 0.

This difference between vertex cover and independent set is reflected in the fact that it is NP-hard to approximate independent set to within $n^{1-\epsilon}$, for any $\epsilon > 0$.


Valid actions of Reductions to NP-Completeness To my understanding, as long as we can find some polytime function $f$ such that $\forall x:x \in A \Longleftrightarrow f(x) \in B, x\notin A \Longleftrightarrow f(x) \notin B$, it follows that if $A$ is NP-complete and B is in NP, then B is also in NP-complete.

My question is about what sort of 'things' we can do to obtain reductions from NP-completeness. That is, I want to know if $f$ is allowed to do anything so long as it is still done in polytime and satisfies the above property? If not, then what sort of limitations are there?

Your understanding is correct.

The only restriction is the one you mention: the reduction must work in polynomial time. That is, there must be some algorithm and some polynomial function $t(n)$ (e.g. $t(n)=n^5+n^3+42$) such that, on all inputs $x$ of length $n$, the algorithm outputs $f(x)$ and the time it takes the algorithm to do that is less than or equal to $t(n)$.

To answer concretely what "things" you may do, I can't! Anything you can think of that takes polynomial time: perfect matching, integer multiplication, some variants of linear programming... graph isomorphism? Counting the number of solutions to the traveling salesman problem? If you can do it in polynomial time, then yes!

To read some posts on this site about NP Completeness, click here to search for posts about that topic.


Linear optimization or Constraint Satisfaction Problem with food I was hoping someone could point me in the right direction in terms of what type of problem I am describing here so I can research it.  My initial thought is that it is some form of Constraint Satisfaction Problem.

Say as an example I am working with food, and I would like to determine from a massive database of recipes which foods might sum up to equal a certain macro-nutrient profile.

For example, maybe I want to target a 410 calorie meal consisting of 30 grams of protein (4 cals per gram), 10 grams of fat (9 cals per gram) , and 50 grams of carbohydrates (4 cals per gram).

Would this be in the domain of CSP, or should I look elsewhere?

I suggest you use integer linear programming.

Suppose you have $n$ recipes.  Introduce zero-or-one variables $x_1,x_2,\dots,x_n$, with the idea that $x_i=1$ represents including the $i$th recipe and $x_i=0$ represents omitting it.  Now you can obtain a bunch of linear equations, one per macronutrient requirement.  For instance, in your example, we get something like $c_1 x_1 + \dots + c_n x_n = 30$, where $c_i$ is the number of grams of protein contributed by the $i$th recipe.  Feed this to an off-the-shelf ILP solver, and hopefully it will find a solution for you.

If you're willing to eat multiple servings of a single recipe, you can relax the constraint on each $x_i$ and require it to be an arbitrary non-negative integer ($x_i \ge 0$), instead of requiring that it be 0 or 1.

Your problem is basically a multi-dimensional subset sum problem.  That's a special case of the multi-dimensional knapsack problem, which is NP-hard.  There  have been people who have studied algorithms for the multi-dimensional knapsack problem, but my guess is that the pragmatic solution is to start by trying an off-the-shelf ILP solver, and studying the literature only if that doesn't work.

Related: 2 Dimensional Subset Sum: looking for information.  Also, your problem has been proved to be NP-hard if we allow the requirements to include large numbers: What algorithms exist for solving natural number linear systems?. (In technical terms, the problem is NP-hard when the macro-nutrient requirements and properties are provided in binary.  I don't know if it remains NP-hard when they're provided in unary -- and the latter seems more relevant for practical situations.)


Finding perfect matchings with as few database queries as possible I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows:

There are an equal number of men and women.
Each man has a perfect match with one and only one other woman.
No two men have a perfect match with the same woman.
A perfect matching is a set of matches where all matches are perfect (as above).
There exists a database that can determine how many matches are perfect in any set.  You can query the database with a set to learn how many matches are perfect in that set, but you don't learn which matches.

I'm looking for an algorithm that finds a perfect matching that matches all the men and women, while querying the database the least amount of times.

Is there an efficient algorithm for this problem?

A $O(n \log n)$ solution works as follows:

For each man $M$, we find the matching woman in $O(\log n)$ queries. We start by dividing the women into two sets of size $n/2$. Using one query, we can find out which of the two halves contains $M$'s match. We recurse on that half.


Determining a minimal-state regular language $A$ such that $A \cap B = C$ given regular languages $B$ and $C$ Suppose I have a regular language $B$ and a regular language $C$ such that $C \subseteq B$.

How do I find a regular language $A$ such that $A \cap B = C$, where $A$ is represented by a DFA with as few states as possible?

I don't really know where to start looking for research on this, so even pointers to some work in this area would be appreciated.

The motivating case for this general question is building state machines to recognize certain regular expressions within UTF-8 streams, where I can rely on the UTF-8 stream being well-formed. (Or rather, my engine need not return correct values for malformed UTF-8 streams)

This question is essentially answered here. You are asking for the smallest DFA such that its language contains all words from $C \cap B$ and no words from $C \setminus B$. This called a minimal separating DFA (for $C \cap B$ and $C \setminus B$) in answer number one of the linked other question, where also a link to a paper with an algorithm is given. The other answer in that thread gives a reference to a paper showing that the problem is at least NP-hard. Since the size of the separating automaton is bounded (by the product of the DFA sizes for $B$ and $C$), the (decision version of the) problem is NP-complete.