What algorithm to use for training combinations I would be very glad if someone could help me with my machine learning task. I have palettes of 5 colors each (in RGB format), and would like to train the neural network so that I can input a color, and the model would give me 4 other colors that would go best with it.

My training set consists of 1500 palettes (1500 * 5 = 7500 examples - each color from palettes is combined with four other). I've trained the network with multi-label classifier: one color as input (3 variables RGB) and one-hot encoded vector as output (I've predefined 68 classes, so it looks like [1 0 0 ... 1 1 1]). So basically, I have two questions:

1) Very strange, but when I try to predict colors that go best with my color, I always get the same colors, just with different probabilities (with sigmoid activation function). Why could this possibly happen? Why my probabilities never reach over 30%?

2) This still doesn't solve my problem - I get only suggestions on different colors, but these colors may not match between them. I need an algorithm that would take into account all 5 colors at once. What kind of algorithm could possibly solve this problem? Maybe combine several?

Thank you for your time reading this!

Your current setup might not be the best one for this.  You need to think about the structure of the model, and the set of features you use.

Model

I would suggest a different approach: see if you can construct a model that captures how well a set of 5 colors match.  In particular, perhaps you can fit a model $f$, where $f(c_1,\dots,c_5)$ describes how well the five colors $c_1,\dots,c_5$ match each other (larger values of $f$ correspond to a better match).  For instance, one plausible model for $f$ is

$$f(c_1,\dots,c_5) = \prod_{i<j} g(c_i,c_j)$$

where $g$ is some function (that you try to fit to the data).  Then, given a training set that describes many different combinations of five colors and how well they match, you could try to fit a model to that (e.g., find $g$ such that $f$ matches the training set as closely as possible).  You can then consider some architecture for $g$, e.g., a small neural network with a few hidden layers, and use gradient descent to train the model.

Features

Constructing a model based solely on the RGB values might be a lot to ask.  I suspect you can do a lot better by choosing some features that are likely to be relevant to color matching.

Often it helps to have some domain knowledge.  Do you know anything about color matching?  Are there any properties of colors that are relevant or informative or affect whether they match?

I would suggest that you pick multiple plausible features, then let the model training process work out which ones are most relevant.  Here are some ideas for you to consider:

Consider adding other color space as additional features.  I would suggest you consider adding the CMYK, HSV, and CIELAB.
It appears that primary colors are best matched with primary colors, and secondary colors best matched with secondary colors, etc.  Therefore, when determining how well two colors $c_i,c_j$ match, perhaps the difference between their hues (modulo 360 degrees) might be relevant.  You could add this as an additional feature that is input to $g$.

Maybe your study of the art of what colors match will suggest other features you can try as well.


Does there always exist equivalent (M)(I)LPs with and without objective functions? For computing pure Nash equilibria (game theory), there exists a MILP method in literature (clicky).

In the proposed MILP, there is no objective function. A solution is a pure Nash equilibrium if it is a feasible solution of the MILP.

Should there, in theory, exist an equivalent MILP with an objective function so that a solution is a pure Nash equilibrium if the objective function is minimized/maximized (e.g. equal to 0). Such MILP would be useful in this context as to still have an approximation if there exists no feasible solution in the first 'objective function-less' MILP (i.e. there exists no pure Nash equilibrium).

I gave context to the question but the question is general: for a (M)(I)LP without an objective function, is there always a reduction from and to a (equivalent) (M)(I)LP with an objective function? Can such reduction be done in polynomial time?

Yes (assuming you truly did mean "if" rather than "if and only if").

Add any objective function you want (e.g., 1, or the sum of the variables, or anything), then feed it to a MILP solver and see whether it returns 'Feasible' or 'Infeasible'.  Then the resulting MILP is feasible if and only if the original MILP was feasible.  Any optimal solution to the resulting MILP is feasible and thus also a feasible solution to the original MILP problem, and consequently represents a valid pure Nash equilibrium.


Oracle that can only definitively say if an instance is unsatisfiable Assuming I have an Oracle that takes as input a strictly 3SAT Boolean instance and states whether the instance is satisfiable or not. If it says instance is unsatisfiable then the instance is unsatisfiable. If it says instance is satisfiable there is a 57% chance the instance is satisfiable and a 43% chance that is unsatisfiable. The percentages are just an example, essentially oracle is reliable only one way.
Can I use such an Oracle to solve 3SAT instances? If so, how?

Edit: I wrongly read the question, therefore the following answer is incorrect. It would be correct if the oracle worked as followed: "if the instance is unsatisfiable, then the oracle always says it is unsatisfiable otherwise, there is a 57% chance the answer is that the instance is satisfiable, and a 43% chance that it is not".
The key here is to repeat the process of asking your oracle to improve the probability of getting the right answer. You know that the way it is constructed, if the oracle states that a formula is satisfiable, then IT IS satisfiable (since it never makes mistakes on non-satisfiable formulas).
For example, with your percentages, if you ask 6 times your oracle if a formula $\varphi$ is satisfiable, it will always give the right answer if $\varphi$ is not satisfiable, and there will be over 99% chance to say that $\varphi$ is satisfiable if $\varphi$ is satisfiable, because it has $0.43^6 < 1\%$ chances to say that $\varphi$ is not satisfiable even if it is.
You will never be able to guarantee 100% in both cases, but you can be as close as you want by repeating the question to the oracle.


Runtime of various versions of binary search I was given the following code and was told to find the best and worst case running times in big theta notation. (Below is in python)

def find(a, target):
    x = 0
    y = len(a)
    while x < y:
        m = (x+y)/2
        if a[m] < target:
            x = m+1
        elif a[m] > target:
            y = m
        else:
            return m
    return -1

I know that the running time of this code in the worst case is $O(\lg n)$. But the question I was given if the fifth line was changed from $m = \frac{x+y}{2}$ to $m=\frac{2x+y}{3}$, would the running time change?

My intuition is that the running time gets a little larger as it is no longer cutting the list in half like binary search should do which is less efficient, but I am not sure how to calculate what the asymptotic runtime would be at this point.

Instead of cutting the interval in half, it's cut in to a piece 1/3 of the length and it's cut in to a piece 2/3 of the length. If you are lucky enough that the item you're searching for is in the left half, then you've done a better job than regular binary search. If you're unlucky and it ends up in the right half, then you do slightly worse than regular binary search.

What happens if the algorithm has "bad luck" twice in a row. The interval gets cut to 2/3rds and then to 2/3rds again, meaning it gets cut to 4/9ths which means it is now slightly shorter than 1/2. This means that in the worst case (bad luck every time) this version of binary search will take only 2x more steps than regular binary search.

On the other hand, if the algorithm is lucky the interval is cut to 1/3rd. If we look at regular binary search, after two steps the algorithm has been cut in half two times, meaning it has been cut to 1/4th - slightly shorter than a 1/3rd. So in the best case, the algorithm takes at least half as many steps as regular binary search.


Regularity of a language constructed from a know regular language I'm working through so textbook questions on regular languages, and came across a problem that amounts to showing the following language is regular, given that $A$ is a regular language:
$$
\{x|\exists n \ge 0 \; \exists y \in A \; y = x^n\}
$$
I've attempted to show that this is regular by a contradiction using Myhill-Nerode, by assuming it has infinite index, and showing this means that $A$ must have infinite index. However, I cannot seem to get this proof to work, because taking representatives of each class lets me show an infinite number of pairs of elements in $A$ that are not in the same class, but these elements do not uniquely correspond to my representatives, so I cannot show that an element is not in the same class as infinitely many others.
However, the book seems to indicate that the solution should be construction.
I can also easily see the construction for a NFA if $n$ was fixed, but this doesn't seem to offer any help, as this makes the states depend on $n$ (by using tuples of states, and simultaneously moving states once).
If anyone could suggest how to go about constructing the required automata, that would be very helpful.

As you mention, if $n$ was fixed, then this is not too difficult to prove.
So, the idea would be to show that in fact, $n$ can be bounded a-priori, depending only on $A$, and not on $x$.
To this end, consider some word $x\in \Sigma^*$, and suppose $x^m\in A$ for some $m$.
Let $k$ be the number of states in some DFA $D$ for $A$ (e.g., minimal DFA). Suppose $m>k$, then there exist $0\le i<j\le m$ such that the run of $D$ on $x^i$ reaches the same state as on $x^j$. But this implies that $x^{m-{j-i}}$ is also accepted by $D$.
Thus, it's enough to consider $n\le k$. So you can rewrite your language as
$$\{x| \exists n\le k,\ x^n\in A\}$$
And this is regular.


Computation of iterated logarithm function I recently came across the iterated algorithm function denoted as $\lg^* n$.

But I am having a hard time understanding this statement:

$\lg^* n = \min \{i \ge 0: \lg^{(i)} n ≤ 1\}$

I could not understand what $\min$ set is used to signify.
Also, could someone please provide an example of how this works.
I also came across examples like:

$\lg^* 4= 2$

But could not understand the computation, specifically how did they take up the values of i?

Thank you.

$\lg^* n$ is just the minimum number of times you need to apply the $\lg$ function to $n$ in order to obtain a number that is smaller than or equal to $1$.

For example, assuming that you are working with base-2 logarithms and that $n=65536$ you have the following:

$\lg^{(0)} 65536  = 65536$,
$\lg^{(1)} 65536  = \lg 65536  = 16$,
$\lg^{(2)} 65536  = \lg 16  = 4$,
$\lg^{(3)} 65536  = \lg 4  = 2$,
$\lg^{(4)} 65536  = \lg 2  = 1$.

As you can see $4$ is the smallest integer value of $i \ge 0$ for which $\lg^{(i)} 65536 \le 1$. Therefore $\lg^* 65536 = 4$.


Is this unambiguous grammar equivalent? I have a simple context free grammar $(\{A\}, \{(,)\}, R, A)$, which consists of this one production rule:

$A \rightarrow AA\, \vert\, (A)\, \vert\, \epsilon$

I believe this is ambiguous! For example, I can represent "()" like this:

I'm sure there are an infinite number of these. I've attempted to make the grammar unambiguous whilst ensuring that the same language is accepted:

$A \rightarrow AA\, \vert\, B$
$B \rightarrow (C)$
$C \rightarrow \epsilon$

How can I be sure that this captures the same language and is no longer ambiguous?

Although determining whether grammars are ambiguous is undecidable, in the case where the  grammar has a rule of the form

$$T\to T\;T$$

then either the grammar is ambiguous or the rule is useless. (Because $T\;T\;T$ can be reduced in two ways.)
Determining the equivalence of two CFGs is also undecidable so there is no general solution to the equivalence question. But you could try to prove that both grammars generate the Dyck language.
A simple deterministic grammar for that language is

$$S\to \epsilon\mid(\;S\;)\;S$$


Why is backtracking a necessary step in the Maze problem? The problem I am working on is specifically this:

A Maze is given as N*N binary matrix of blocks where source block is
the upper left most block i.e., maze[0][0] and destination block is
lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source
and has to reach the destination. The rat can move only in two
directions: forward and down.

The question essentially asks to find and print the path that exists through a given maze from the top left to the bottom right of the maze. The details of the problem can be found here.
The core of the C/C++ code for this problem's solution is this:
/* A utility function to check if x,
y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
    // if (x, y outside maze) return false
    if (
        x >= 0 && x < N && y >= 0
        && y < N && maze[x][y] == 1)
        return true;

    return false;
}

/* This function solves the Maze problem
using Backtracking. It mainly uses
solveMazeUtil() to solve the problem.
It returns false if no path is possible,
otherwise return true and prints the path
in the form of 1s. Please note that there
may be more than one solutions, this
function prints one of the feasible
solutions.*/
bool solveMaze(int maze[N][N])
{
    int sol[N][N] = { { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 } };

    if (solveMazeUtil(
            maze, 0, 0, sol)
        == false) {
        printf("Solution doesn't exist");
        return false;
    }

    printSolution(sol);
    return true;
}

/* A recursive utility function
to solve Maze problem */
bool solveMazeUtil(
    int maze[N][N], int x,
    int y, int sol[N][N])
{
    // if (x, y is goal) return true
    if (
        x == N - 1 && y == N - 1
        && maze[x][y] == 1) {
        sol[x][y] = 1;
        return true;
    }

    // Check if maze[x][y] is valid
    if (isSafe(maze, x, y) == true) {
        // mark x, y as part of solution path
        sol[x][y] = 1;

        /* Move forward in x direction */
        if (solveMazeUtil(
                maze, x + 1, y, sol)
            == true)
            return true;

        /* If moving in x direction
           doesn't give solution then
           Move down in y direction  */
        if (solveMazeUtil(
                maze, x, y + 1, sol)
            == true)
            return true;

        /* If none of the above movements
           work then BACKTRACK: unmark
           x, y as part of solution path */
        sol[x][y] = 0;
        return false;
    }

    return false;
}

I am confused about the following part of the solution in the function solveMazeUtil:
/* If none of the above movements
               work then BACKTRACK: unmark
               x, y as part of solution path */
            sol[x][y] = 0;
            return false;

What is the need to reset the value of the cell located at x,y in the solution matrix? The value of sol[x][y] was set to 1 only because it was a valid cell to go to. I don't understand why sol[x][y] has to be reset just because its neighboring cells are invalid?
EDIT:
I thought about this problem a little more and I realized the cell is only reset to zero when the program runs into a dead-end (0s in the maze, in this case) on its right side AND below it. If this cell is reset, the cell is available to be explored again.
What purpose does it serve? If the program encounters this reset cell again, it will perform the same computations for this cell again and encounter the same dead-ends as before.

Your question title doesn't match your question details.
You're not asking why backtracking is necessary, but you're asking why a cell marked in the matrix needs to be unmarked when backtracking.
A general technique for solving questions like this is as follows.
We'll investigate statements about the state of the program. In this case, statements about the contents of the matrix.
We start by looking at the intended outcome: the required postcondition. A postcondition is a statement that must always hold after the program terminates. In this case: what is the matrix supposed to contain after the program terminates?
The answer: the cells of the matrix must mark a path found from start to finish, if such a path exists. All cells marked 0 must be off that path, and all cells marked 1 must be on it.
Then, we figure out which invariant the program maintains in order to achieve the required postcondition. An invariant is a property that always holds: before, while, and after the program runs. In this case: which cells are supposed to be marked 1 while the program is in progress?
The answer: they are exactly the cells of the path found from the starting point to the current cell. If the program always successfully maintains this invariant, the required postcondition will always be met.
To maintain the invariant, when you add a cell to the path, it must be marked;
and when you retrace a step, removing the last cell from the current path, that cell must be unmarked.
What if we don't unmark it? Then, the program will maintain a different invariant: namely, the matrix will mark exactly those cells that have ever been visited, whether they are on the current path or not. This is the invariant Hansel was trying to maintain with his breadcrumbs.
If you follow Hansel, after the program terminates, all cells ever visited will be marked, even those that aren't on the path that was eventually found (and such cells will exist if any backtracking occurred). The requirement was for only the cells on the path to be marked. Backtracking can actually occur, so the program will no longer always be doing what it's supposed to do: it will no longer meet its required postcondition.


Byte/word addressing in cache When dealing with caches, the address is split in three parts - offset, index and tag. Question is: if we are given a word address, do we first have to shift left by 2 bits by adding 00 at the end of address?

Suppose cache block size is 4 . block offset is 2 LSBs of the address. If we were to add 00 at end of every memory address, then block offset would always be 00. That means, we could never have access to any other byte rather than one at position 00 in our block?

Huh? Let's modernise what you are saying a bit. Typical cache size nowadays is 64 bytes. So here is what a processor will typically do for such a cache:

Step 1a: Take the number of bytes accessed by the instruction, and the lowest six bits of the address, and determine whether the data is all within one cache line or straddles over two cache lines. (For example two consecutive bytes will in most cases be in one cache line, except if the lowest six bits are equal to 63. 16 consecutive bytes will often be in one cache line, except if the lowest six bits are greater than 48).

Step 1b: Use the other bits to determine the cache line where the data might be stored. If the cache has more than one way (say four way cache) this actually determines four possible cache lines.

Step 1c: Take the whole of the address to determine which of the possible ways contains the data. Also detect if the data is in the cache at all, and if not, start loading the data into cache which is much too complicated to explain here. When done, start all over again.

Steps 1a to 1c are performed in parallel if at all possible. Once the cache line containing the data, or the first part of the data is found, take the lowest six bits of the address, combine with the data size, and transfer as many bytes as needed and available.

If not all bytes needed are in the same cache line, repeat everything to get the remaining bytes.

Where your ideas went wrong: We don't set any bits of the address to zero, and we don't shift anything. We just take the parts of the address that are needed for every operation. To determine the cache line, you don't shift the address, you just take the address bits that are needed and you don't take the bits that are not needed. Since the lowest two bits are never zeroed, there is no problem accessing a byte anywhere in a cache line.


Does it make sense to say Big Theta of 1? Or should we just use Big O? Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$?

Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying Big Theta over Big O in this case.

Remember your definitions! As $n \to \infty$ (the use in CS, almost always) $O(\cdot)$ is an upper bound (within a constant multiple, for large $n$), $\Omega(\cdot)$ is a lower bound (within a constant multiple, for large $n$), and $\Theta(\cdot)$ both of the previous. To see the difference, as $n \to \infty$ you have:

$\begin{align*}
  1 + \lvert \sin n \rvert
    &= O(1) \\
  1 + \lvert \sin n \rvert
    &= \Omega(1) \\
  1 + \lvert \sin n \rvert
    &= \Theta(1) \\
  e^{-n}
    &= O(1) \\
  e^{-n}
    &\ne \Omega(1) \\
  e^{-n}
    &\ne \Theta(1)
\end{align*}$

For the first three, as $\sin x$ moves between -1 and 1, the expression fluctuates between 1 and 2.

To see why $e^{-n} \ne \Omega(1)$ (and so $e^{-n} \ne \Theta(1)$), note that we are looking for a constant $c > 0$ and an $N_0$ so that for all $n \ge N_0$ we have $e^{-n} \ge c \cdot 1$. For any $c$ you pick, you'll find that taking $n > \ln 1 / c$ makes this false. So no $c$ works.


Master Theorem on a*T(n/b) + c? The recurrence equations solved by the Master Theorem are in the following format :

$ T(n) = a T(\frac{n}{b}) + f(n)  $

but is it possible to use it on :

$ T(n) = a T(\frac{n}{b}) + c  $

?

Yes. The constant function $c$ plays the part of $f(n)$. Stated differently, you can use the function $f(n) = c$ to apply the master theorem.

A perhaps simpler way is to find a shift $d$ such that $S(n) := T(n) + d$ satisfies a nicer recurrence. We have
$$
S(n) = T(n) + d = aT(n/b) + c + d = a(S(n/b)-d)+c+d = aS(n/b) +c+d-ad.
$$
If $c+d-ad = 0$, then we get the simple recurrence $S(n) = aS(n/b)$, whose solution is $S(n) = n^{\log_b a} S(1)$ (for powers of $b$). This happens when $d = c/(a-1)$. We conclude that $T(n) = n^{\log_b a}(T(1) + c/(a-1)) - c/(a-1)$ (for powers of $b$).


Monad in Haskell programming vs. Monad in category theory I have a question about concept of monad used in Haskell programming
and category theory in math.
Recall in Haskell a monad consists of following components:

A type constructor that defines for each underlying type how the
corresponding monad type is to be obtained. The name of this type
constructor is often used synonymously with the whole monad. If $M$
is the name of the monad and $t$ is arbitrary fixed data type,
then $M t$ is the corresponding monadic type

A unit function that maps a value of the underlying type to the value of
the corresponding monad type. The result is the "simplest" value in the
corresponding type that can be obtained from the original value.
In Haskell this function is called return. The unit function has
the polymorphic type $t → M t$

At least one further operation, which describes the combination of
monadic operations.

On the other hand in category theory a monad is a triple $(T, \eta, \mu)$
of a category $C$ where

$T: C \to C$ is a functor

$\eta: 1_K \to T$ a natural transformation in sense of category theory

$\mu: T^2 \to T$ a natural transformation

and these objects should
satisfy following diagrams:
https://en.wikipedia.org/wiki/Monad_(category_theory)
Question: How are these monads from Haskell and abstract category theory
related? Does the monad structure in Haskell have natural
"monad structure" in sense of category theory, ie we can canonically associate to $M$ a canonical triple as described above?

A monad in Haskell is intended to be a monad on the category of types, when the category theory is done internally to the type theory. The capabilities of Haskell and similar languages are somewhat limited, so there are a lot of basic constructions in category theory that cannot be done, but there are plenty of structures that can be encoded reasonably.

M :: * → * is the object mapping of the functor, which you have instead named $T$ later.
The arrow mapping part of the functor is given by fmap
$η$ is the unit function, which Haskell calls return (or pure, which is a little more general)
$μ$ is given by join.

The requirements expected of Monad instances are equivalent to the ones to be a monad in category theory.
Essentially, this is not much different than speaking specifically about monads on the category $\mathsf{Set}$, aside from the earlier mention of Haskell/etc. missing some constructions that set theory has (there are things that act enough like (co)products, but not like pullbacks/pushouts). You could do a lot only thinking about monads on $\mathsf{Set}$, because many structures in abstract/universal algebra give rise to one, and are presentable that way.
One might quibble that types in various programming languages do not technically form a category with good properties/structure, but you could instead imagine that you are using them as a means to talk about something better behaved, like System $F_ω$, and it wouldn't really change the answer in an interesting way.


Not able to devise a concrete solution for the given graph query I was trying to solve the following problem:

You are given a grid of size N×N that has the following specifications:

Each cell in the grid contains either a policeman or a thief.

A policeman can only catch a thief if both of them are in the same row. Each policeman can only catch one thief.

A policeman cannot catch a thief who is more than K units away from the policeman.

Write a program to find the maximum number of thieves that can be caught in the grid.

example:

N=3,K=1

P T P

T T P

T P T

Answer:3

I tried a simple BFS solution but my code if failing in which there are alternative P and T,am not able to handle this case with BFS.

My solution:solution(Its a bit lengthy,so didn't paste it here.)

It would be really helpful and highly appreciating if someone could suggest some algorithm or pseudo code for this problem statement.

PS:This was the question of this test.It was a timed test, couldn't solve it.

Thanks.

Your problem is very similar to interval scheduling, and it seems it can be solved similarly using a greedy approach. Note first that you can solve each row separately. For each row, you scan the row from left to right. Assign each policeman to the leftmost thief that he can capture and isn't already taken (if any). Intuitively, this should work, and you can try proving that it does using the standard proof method of comparing the greedy solution to an optimal one.


is the problem of parallelising any program, NP-complete? Consider a program written in a common language such as C.  Assume that it does not have any explicit parallel constructs.  Then, once it is compiled to an executable program, it will be run serially, even if the machine has multiple processors.

Now, suppose we wanted theoretically to write a "parallel compiler", which would analyze such a program and figure out what operations are safe to execute concurrently, and output an executable which would run in parallel on multiple processors, so that, no matter the timing between these threads, the program in the end will come up with the same results as with "serial compiler".

I am guessing that such a compiler, if possible, would need a very long time to calculate - I am guessing that the problem "parallelize an arbitrary program" must be at least NP-complete (possibly exp).  Is that known, and if so, is that true, and if so, can you point me to a published argument?

Let me try and formalize the problem better.  Assuming each instruction emitted by the compiler executes in unit time, then for a given number of processors, and assuming the processors communicate and access memory instantly, given that some instructions will depend on others, there is theoretically the shortest possible time to complete the program.

Let's say we want our compiler, maybe not reach this theoretical limit, but come up with instructions that will take up to 2x the theoretical limit.

It is not clear what exactly you want of that compiler, so let me explore several possibilities.

Optimize the parallelism

This is impossible. Optimizing even sequential runtime is not computable, and a similar proof shows the same for parallel runtime. The proof also extends to any notion of "almost optimal" like within a constant factor or something similar.

Thus, any notion of parallelization in this direction is not even in NP, and it's not even close.

Get some parallelism

Without defining exactly what "some" means we can not classify the problem in terms of complexity. There are certainly things that modern compilers can do, for instance vectorize suitable for-loops -- but all of these are certainly not NP-hard to detect (or they wouldn't do them).

I'm certain that you can carefully define some parallelization feature that is NP-complete to detect. I'd especially look towards coarse-grained parallelism, though exploiting that requires serious rewrites of code.

Do anything

That's trivial and hence boring. For instance, standard data-flow analyses will identify (sub)sequences of statements that are independent and can thus be reordered or, in principle, be executed in parallel. This will get you some very fine-grained parallelism that may not even gain you a speed-up, and will certainly not scale to many processors, but well.

Some language have features to tell the compiler that two things are independent, e.g. method calls, and that way lies potential gain. Then it's easy for the compiler again, though.


Linear Programming: algorithm to check if ratios can be combined with n bottles to equal a given ratio Say you have n bottles. each with a ratio of $(a_i: b_i: c_i)$.
($a_i/(a_i+b_i+c_i),\cdots$ swap out the numerator for $b_i$ and $c_i$ respectively).

Now you are given a ratio of $(a:b:c)$. Use Linear programming to find an efficient algorithm to this problem. If it's yes, you can output the parts of bottles that gave you the answer. (e.g. 2 parts from one bottle, 1 part from another bottles.)

So it's not clear how to do this. One of my first thoughts was to make a variable $z = \sum(\alpha_i*(a_i,b_i,c_i)) - (a,b,c)$. This, I'm thinking could be the objective function we minimize.

Not sure if this works. Or if it does, where to go from here. Also, I'm not sure if I can have the alphas in the thing I'm trying to minimize. What am I supposed to do with these alphas.

Not sure what it means by algorithm either. That is, even if I could set up the problem as a linear problem, not sure what the algorithm would be.

I don't know what class this is for, and how much linear programming you are learning in it, so I don't really know what you need.

One way to do it: assuming $a_i + b_i + c_i = 1, \ \forall i$, use the linear program:

$$ \max x$$

such that

$$\eqalign{
\sum_i  a_i \lambda_i &= a,\\
\sum_i  b_i \lambda_i &= b,\\
\sum_i  c_i \lambda_i &= c, \\
\lambda _i -x &\geq 0 \quad \forall i.
}$$

If there is a solution with $x \geq 0$, then you're done. Why? If $x \geq 0$, then there is a set of positive $\lambda_i$ satisfying the first three equations above: $\sum_i a_i \lambda_i = a$. The $\lambda_i$ give you the proportions with which to mix the bottles.  If one of the $\lambda_i$ were less than $0$, then this would tell you to add a negative amount from that bottle, yielding an unphysical "solution". If there is no solution of the linear program with $x \geq 0$, then no combination will give the proportions $a:b:c$, as that would give a solution to the linear program with $x \geq 0$.


Computer Architecture, cache hit and misses I am currently enrolled in a computer organization and design class, which I am struggling mightily with, and I have a final homework in my class that I need to get a perfect score on. One of the questions covers cache hit-misses, and the lecture we had on the subject was relatively brief. The question I have having issues with is:

A processor has a CPI of 1.4 with level 1 caches with a 100% hit rate. When running benchmarks, the level 1 instruction cache has a 1% miss rate and the level 1 data cache has a 3% miss rate. 30% of the instructions access memory through load and store operations. Main memory has a 50 nano second access time and the clock is running at 2.5 GHz.

What is the actual CPI of the processor with just the level 1 caches?

A level 2 cache is added to the processor.  The hit time of this cache is 1.5 nanoseconds, and it has a global miss rate of 0.5%.  Compute the actual CPI of the processor after the addition of the level 2 cache.

What is the speedup achieved by adding the level 2 cache?

So my first attempt is this:

I-cache miss rate = 1%
D-cache miss rate = 3%
Miss penalty to main memory = main memory access time / clock time
50 ns / .4 ns per clock cycle = 125 clock cycles
Base CPI = 1.4
Load and store = 30% of instructions
Main memory access time = 50 ns
Processor clock = 2.5 GHz

What is the actual CPI of the processor with just the level 1 caches?

Instruction miss cycles = I x 1% x 125 = 1.25 x I
Data miss cycles = I x 30% x 3% x 125 = 1.125 x I
Total number of memory-stall cycles is 2.375 I
Total CPI including memory stalls is 1.4 + 2.375 = 3.775

A level 2 cache is added to the processor.  The hit time of this cache is 1.5 ns and it has a global miss rate of 0.5%.  Compute the actual CPI of the processor after the addition of the level 2 cache.

Secondary cache access time = 1.5ns
Processor clock = 2.5 GHz
Miss penalty for an access to second-level cache = 1.5ns / .4 ns per clock cycle = 3.75 clock cycles
For a two level cache, total CPI is the sum of the stall cycles from both levels of cache and the base CPI
1.4 + (.005 x 125) + (.005 x .3 x 125) + (.01 x 3.75) + (.01 x .3 x 3.75) = 2.26125
*****This is where I'm most unsure. The "global miss rate of 0.5%" is throwing me off, and I'm not sure I performed this calculation correctly.**

What is the speedup achieved by adding the level 2 cache?
3.775 / 2.26125 = 1.67
***This answer is dependent on the result from the calculation above. If I did that wrong, this answer will be different.

You may wish to ask your TA/Prof. what they mean by "0.5% global miss rate". The way I read it is the following:

  Out of $x$ accesses to the L2 cache, $0.005x$ accesses are a miss.

This interpretation makes more sense than assuming the miss rate is out of all the store/load instruction.

So each miss of the L1 cache becomes an access to the L2 cache, and out of these, 0.5% are a miss at the L2 cache. From here, it seems you can fill out the details by yourself, building on your own attempts.


Rearranging function in 'Theorems for free' I'm reading Wadler's 'Theorems for free'. In section 3.5 he states that $m_{AA}(I_A)$ is a rearranging (i. e. injective) function. $I_A$ is the identity function on the type A.
$$m : \forall X.\forall Y. (X \rightarrow Y) \rightarrow (X^* \rightarrow Y^*)$$
How does he use section 3.4 to prove this without any $\forall^{(=)}X$-types? Why can't $m_{AA}(I_A)$ e. g. drop a few elements in the list?

It can, as good evidence for it define m as something like

m f = map f . drop 2

And everything still typechecks. Here "rearranging" is supposed to refer to structural operation on the list without regards to the specific values of each element. This is captured by the free theorem at this type,

m (\x -> x) . map f = map f . m (\x -> x)

m (\x -> x) performs all the structural changes to the list and map f actually alters this element. This theorem implies that they are independent of each other.


Turning a simple polygon with holes into exterior-bounded only I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior boundary only. To overcome this restriction, I plan to “cut through the body of the shape” — joining a pair of nodes of exterior and interior boundary (see figure, left), thus creating a zero-width way into the shape's former interior space that will then technically become exterior (see figure, right).

So the question is: which nodes to join? (Not that it's unacceptable to create new nodes in suitable locations, but undesirable.) An obvious and ideal choice would be the two nodes most close to each other; moreover, I suppose that those would automatically constitute a valid solution — i. e. the new segments won't intersect any existing one. Consequently, the question becomes: how to find the closest node pair?
Googling on this topic yields many results for similar questions which vary in degree of “similarity”, complexity of understanding the algorithm and computational complexity. But most importantly, as far as I noticed, they vary in applicability to input data, — that is, some are designed for convex polygons only, others fail on “overlapping” polygons (I suppose that includes my case, too). So I decided to ask: which algorithms are optimal or at least suitable for my particular task?

The closest vertices between the inner and outer polygons do not necessarily produce a valid solution as shown in the following figure:

You just need to find a pair of vertices between the inner and outer polygons whose corresponding edge does not intersect either polygon.
Search for vertices $u$ and $v$ from the inner and outer polygons such that the edge $(u,v)$ does not cross any other edge (some care needs to be taken that you don't
slip between two edges as shown on the right above -- choosing the closer vertex avoids this problem).

A straight forward approach would scan all such $u,$ $v,$ and all edges
resulting in $O(n^3)$ time in the worst case -- in practice you'll find a solution fairly quickly. This can be sped up by placing all the vertices in a BSP tree whose half-spaces are defined by the polygon edges -- then you only considering vertices $v$ in the same half-space as $u.$


Why use SIMD if we have GPGPU? I thought this question is better served in the CS part of Stack Exchange. Now that we have GPGPUs with languages like CUDA and OpenCL, do the multimedia SIMD extensions (SSE/AVX/NEON) still serve a purpose?

I read an article recently about how SSE instructions could be used to accelerate sorting networks. I thought this was pretty neat but when I told my comp arch professor he laughed and said that running similar code on a GPU would destroy the SIMD version. I don't doubt this because SSE is very simple and GPUs are large highly-complex accelerators with a lot more parallelism, but it got me thinking, are there many scenarios where the multimedia SIMD extensions are more useful than using a GPU?

If GPGPUs make SIMD redundant, why would Intel be increasing their SIMD support? SSE was 128 bits, now it's 256 bits with AVX and next year it will be 512 bits. If GPGPUs are better processing code with data parallelism why is Intel pushing these SIMD extensions? They might be able to put the equivalent resources (research and area) into a larger cache and branch predictor thus improving serial performance.

Why use SIMD instead of GPGPUs?

Nothing is free.  GPGPUs are SIMD.  The SIMD instructions on GPGPUs tend to be wider than the SIMD instructions on CPUs.  GPGPUs tend to be fine-grained multi-threaded (and have many more hardware contexts than CPUs).  GPGPUs are optimized for streaming.  They tend to devote a greater percentage of area to floating point units, a lower percentage of area to cache, and a lower percentage of area to integer performance.

Let's do a comparison.  Intel's core i7-5960x has 8 cores, each with 4-wide (double precision) SIMD, running at 3 GHz (3.5GHz turbo), a 20M L3 cache, consumes 356mm^2 and 140W and costs \$1000.  So 8*4*3*4 = 384 double precision GFlops.  (The extra 4x is because you can do two fused-multiply-adds per vector lane per cycle.)  It can do 768 single precision GFlops.  That's about 1.08 DP GFlops/mm^2 and  2.75 DP GFlops/Watt.  There's also about 57.5 KB/mm^2 of on-chip cache.

NVidia's GeForce GTX Titan Black has 15 SMXs, each with 32-wide double precision SIMD, running at 890MHz (980MHz turbo), 3.5M of L1+L2 cache, consumes 561mm^2, 250W and costs \$1000.  So 15*32*.89*4 = 1709 double precision GFlops.  (Same 4x from two fused-multiply-adds per vector lane per cycle.)  It can do 5126 single precision GFlops.  That's about 3.05 DP GFlops/mm^2 and 6.8 DP GFlops/Watt.  So 3x the DP floating point density per unit area and 3x the DP floating point power efficiency.  And the tradeoff? 6.4 KB/mm^2 of on-chip cache. About 9x less dense than the CPU.

So the main difference is that the GPU has chosen an area balance that strongly favors floating point (and especially single-precision floating point) over cache.  Even ignoring the fact that you need to copy stuff back and forth between the CPU and GPU to do I/O, how well the GPU is going to do compared to the CPU depends on the program you are running.

If you have a data parallel floating point program with very little control divergence (all the vector lanes are doing the same thing at the same time) and your program is streaming (can not benefit from caching), then the GPU is going to be about 3x more efficient per unit area or per Watt.  But if you have any significant amount of divergent control, non-data-parallel work to do, or could benefit from large read-many-times data structures, the CPU will probably do better.


NFA and DFA storage cost In some paper I read,

  A theoretical worst case study shows that a single regular
  expression of length $n$ can be expressed as an NFA with $O(n)$
  states. When the NFA is converted into a DFA, it may generate
  O($\Sigma^n$) states. The processing complexity for each character in the inpuyt it $O(1)$ in a DFA, but is $O(n^2)$ for an NFA when all $n$ states are active at the same time.

Please explain how NFA has at its maximum just $n$ states and its equivalent DFA has at most $O(\Sigma^n)$ states?

Consider the construction of an NFA from a regular expression $r$. The construction is by induction over the generating sequence of $r$. If you examine the different operations (union, Kleene star, and concatenation), you will see that each operation increases the size of the NFA by a linear blowup.

For example, an NFA for $r_1\cup r_2$ is obtained by nondeterministically starting in an NFA for $r_1$ or an NFA for $r_2$, so the size of the NFA is (by induction) at most $|r_1|+|r_2|$.

Now, determinizing an NFA with $k$ states may involve a blowup of up to $2^k$ states. However, the NFA you obtained from the construction has $k=O(n)$ states, so the blowup is $2^{O(n)}$. The paper you read shows that the $O(n)$ factor is in fact $n\cdot O(\log|\Sigma|)$, thus making the total size $O(|\Sigma|^n)$.


What happens internally when you remove an object from a treemap I am wondering what happens if you remove an object in the middle of a treemap.
If the treemap would look something like this:

So what would happen if you remove the number 30? Because 27 and 34 will disconnect from the tree.

I think there are two cases here

Java Collections implementation :
 In this case Java uses red black tree to keep the tree balanced and to maintain the order. Thus if you are removing a node in such a tree it will adjust itself without breaking anything and will form a perfect BST even after removal. Red black trees are self balancing trees so it will also arrange itself to maintain log(n) height where n is the number of nodes. Thus for sure you will not lose any data here.
Your custom implementation :
In this case you have to do all the painful things which I have explained above. However you have an option to maintain the order or to rebalance the tree as per your requirements.


Are link-cut trees ever used in practice, for max flow computation or other applications? Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-cut trees).

Push relabel runs in $O(V^2E)$ or $O(V^3)$ or $O(V^2\sqrt{E})$ normally, but with dynamic trees $O(VE \log(V^2/E))$
Dinic's algorithm runs in $O(V^2E)$, but with dynamic trees $O(VE\log(V))$

However, practical implementations of max-flow algorithms in most libraries don't seem to make use of this data structure.  Are dynamic trees ever used in practice for max flow computation? Or do they carry too much overhead to be useful for real world problem sizes?

Are there any other problem domains where link cut trees are used?

This question is related to a question that I asked on cstheory: Are any of the state of the art Maximum Flow algorithms practical?

There is a paper titled "Dynamic Trees in Practice" which reviews the practical implementation.

The other categories that Link-Cut tree could be used efficiently is in Database Indexing.
You can find this in the book "Database Index Techniques".


Ford-Fulkerson Running Time This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them!

In the analysis of Ford-Fulkerson I understand why the while loop runs no more than $val(f^*)$ times but I don't see why it only takes $O(E)$ time to find an augmenting path. Using a BFS or DFS would give $O(V+E)$ no? The running time I see everywhere says $O(E\cdot val(f^*))$

Also, given $C$, the maximum capacity of any edge in the network, I see a lot of people stating the bound $val(f^*)\leq nC$ where $n$ seems to be $|V|$. However it isn't clear why this relation holds. $val(f^*)\leq C|E|$ makes more sense to me but never seems to be used...

There might be some more clever trick in the analysis to get rid of the $V$, but at the very least, I can provide some intuition as to why you can get rid of it.

With Ford-Fulkerson, it is generally assumed that you are working with connected graphs.

For any connected graph with $V$ nodes, there are at least $V-1$ edges, since each node needs at least one edge (except the "last" one in a sense) to be connected.

This means that, either there are $O(V)$ edges, in which case $O(V + E) = O(E)$, or the number of edges dominates the number of vertices (for example, when there are $O(V^2)$ edges), in which case the $V$ gets dominated and we can just write $O(E)$.

When you learn breadth-first search and depth-first search, one of the main applications is testing for connectedness and finding connected components. Here, you could be dealing with a graph with thousands of components, so it makes sense to not assume that there is one component.


2's complement substraction I need to perform 2's complement operations on -50 - -48
From a mathematical point of view the following would be true.
-50 + 48 = -2
If I would follow the steps I would have:
I got to this result by getting the bite for 50 and 48 and then reversing
-50 = 11001101
-48 = 11001111

In 2's complement:
the bite result for 11001101 - 11001111 is - 00000010 which is 2
the decimal result for 11001101 - 11001111 is -2.

Is my logic correct?
I think I am missing something.

In two's complement, we compute $a-b$ by adding $a$ and $-b$. To compute $-b$ in two's complement, we invert all bits in $b$, and increment the result by $1$.
Let's see how it works in your example. You haven't specified the bit length, but it appears to be $8$. We have $50 = 00110010$, and so $-50 = 11001101+1 = 11001110$. Similarly, $48 = 00110000$, and so $-48 = 11001111+1 = 11010000$. In order to subtract $-48$ from $-50$, we first negate $-48$: $-(-48) = 00101111+1 = 00110000$. Now we add $-50$ and $-(-48)$: $11001110+00110000 = 11111110$. Since the MSB is $1$, we know that this is a negative number. To find out negative what, we invert it: $-(11111110) = 00000001+1=00000010$, which is $2$. Therefore $-50-(-48)=-2$.


Running time with while loop What's the running time of:

foo(n)
if(n==1) return;
int i=1;
while(i<n)
{
    i=i+2
}
foo(n-2)

There are $n/2$ recursive calls to foo but how to add to the calculation the while loop

The number of the iterations of the while loop is

$$n/2+(n-2)/2 + (n-4)/2 + \dots +1$$

which is $O(n^2)$.


Pierce's Types and Programming Languages : circular definition of terms? In Pierce's book, on page 26-27 it is given a definition of terms for a simple language using inference rules.

In the picture below it is marked by red highlighting the problematic part.

What is Pierce referring to exactly by the red-highlighted word term in this context?

Is he referring to the terms given by the grammar on page 24 ?

In that case I see no point in defining the terms using the inference rules given in the Definition 3.2.2 because he is using the definition of terms already defined by the grammar on page 24, so there is no point in defining it again.

How should one really understand what the red-highlighted word term refers to on page 27, so that the definition 3.2.2 makes sense ?

The only way the last sentence would make sense to me if it would be changed to something like this: ... replacing each t by every possible term that has been generated inductively so far., meaning that the highlighted word term does not refer to the terms defined on page 24 but to the terms which already have been generated inductively by the inference rules given in Def 3.2.2.

What do you think ?

The grammar from page 24:

t ::=                                   terms:
      true                       constant true
      false                     constant false
      if t then t else t           conditional
      0                          constant zero
      succ t                         successor
      pred t                       predecessor
      iszero t                       zero test

From page 26:

  3.2.2. DEFINITION [TERMS, BY INFERENCE RULES]: The set of terms is defined by the following rules

  $$\begin{gather}
    \texttt{true}\in\mathcal{T} \qquad\qquad
    \texttt{false}\in\mathcal{T} \qquad\qquad
    0\in\mathcal{T}\\\\
    \frac{\texttt{t}_1\in\mathcal{T}}{\texttt{succ t}_1\in\mathcal{T}} \qquad
    \frac{\texttt{t}_1\in\mathcal{T}}{\texttt{pred t}_1\in\mathcal{T}} \qquad
    \frac{\texttt{t}_1\in\mathcal{T}}{\texttt{iszero t}_1\in\mathcal{T}}\\\\
    \frac{\texttt{t}_1\in\mathcal{T} \qquad \texttt{t}_2\in\mathcal{T} \qquad \texttt{t}_3\in\mathcal{T}}{\texttt{if t}_1\texttt{ then t}_2\texttt{ else t}_3\in\mathcal{T}}
\end{gather}$$

From page 27:

Part of your intuition is correct: "terms" really means "the collection of terms generated thus far". I think you will also find in Pierce a definition that makes this explicit on the next page (Definition 3.2.3).

What Pierce is actually doing is giving three equivalent and common ways of presenting syntax. In fact, the first one (page 24) is what you often see in papers and programming language specifications. Definition 3.2.2 is a way of understanding this as an inductive set of rules. And Definition 3.2.3 is a way of understanding the inductive set of rules by explicitly building larger terms from smaller terms.


Run Time of Nested Loop In the following loop

for i = 1 to n
    doSomething O(1)
    for j = 1 to k
        doSomething O(1)

Is the runtime still $O(nk)$ even with the expression in the outer loop? Because if I change the order of the loops and $n \neq k$ then doSomething is executed a different amount of times.

The running time is $O(n+nk) = O(nk)$, where we are making the implicit assumption that $n,k \geq 1$. This is usually a reasonable assumption.

If we do allow $n$ and $k$ to be zero then the running time becomes $O(nk + n + 1)$.

Let me comment that there are several different definitions of big O, which are usually but not always equivalent. Here I am using the following definition: $f(x_1,\ldots,x_m) = O(g(x_1,\ldots,x_m))$ if there exists a constant $C>0$ such that for all integers $x_1,\ldots,x_m \geq 0$, it holds that $0 \leq f(x_1,\ldots,x_m) \leq C g(x_1,\ldots,x_m)$.


Can this question be solved without knowing the Page Table Entry? I'm preparing for the exams and this question came up -

  Consider a machine with $64MB$ physical memory and a $32$-bit virtual address space. If the page size is $4KB$, what is the approximate size of the page table?
  (A) 16MB
  (B) 8MB
  (C) 2MB
  (D) 24MB

The way I've solved it -
Physical Address Space = $64MB = 2^{26}B$
Virtual Address = $32$-bits, $\therefore$ Virtual Address Space = $2^{32}B$
Page Size = $4KB=2^{12}B$
Number of pages =$\,\Large\frac{2^{32}}{2^{12}}$$=2^{20}$ pages.
Number of frames =$\,\Large\frac{2^{26}}{2^{12}}$$=2^{14}$ frames.
$\therefore$ Page Table Size = $2^{20}\times 14\,bits \approx 2^{20}\times 16\,bits\approx 2^{20}\times 2B= 2MB.$

Some books claim the answer to be $8MB$ and I don't see why, but that confuses me.
Is this the correct way to solve it? Is the answer correct?

Your answer and calculation is correct, if we used a one-level page table.

However, a one-level page table is probably not a very likely implementation strategy, so it's more interesting to analyze the space consumption for a more plausible implementation strategy and work out what this would look like.

A two-level page table is probably a more likely implementation strategy.  The first 9 bits of the virtual address will be used as an index into the first-level table; they yield the entry in the second level.  The next 11 bits of the virtual address will be used as an index into the second-level table.

With this strategy, the size of the entire page table is $1+k$ pages, or $(1+k) \times 2^{12}$ bytes, where $k$ is the number of second-level table entries.  The worst case is $k=2^9$, in which case the entire page table takes up approximately $2^9 \times 2^{12} = 2^{21}$ bytes, i.e., 2 MB.  In other words, the worst case for a two-level page table is approximately the same as the size of a one-level page table.  However, the best case is much less.

I don't know how the books got 8 KB, but that seems clearly wrong, absent further assumptions; that would only allow 4096 entries in the entire page table, which clearly isn't enough to maintain a virtual-to-physical mapping for all of virtual memory.


Find candidate keys given functional dependencies In my database class we practiced how to find the candidate keys, given the functional dependencies. However they were easy examples, based on a single attribute being functionally dependent on a single attribute but in our book it gives the following example of more complex functional dependencies. Let's say that I have the following relationship:

$$R(A,B,C,D,E,F)$$

with the following functional dependencies:

$$f_1: \{A,B,C\} \to \{D,F\}$$
$$f_2: \{D,E,F\} \to \{A,C,E\}$$
$$f_3: \{D\} \to \{B\}$$

and I need to find all the candidate keys. Because we need at least $3$ of the attributes to make candidate keys. Through writing out each of the tuples made up of $3$ or more attributes, I found that $\{A, D,E,F\}$, $\{A,B,C,E\}$, $\{D,E,F\}$ and $\{A,C,D,E\}$ are all candidate keys. However the catch is that either $\{A, D,E,F\}$, $\{A,B,C,E\}$ or $\{D,E,F\}$,$\{A,C,D,E\}$, $\{A,B,C,E\}$ are the candidate keys.

I think that because the definition of a candidate key is that there can't be a subset of it that's also a candidate key. Using this logic, $\{A, D,E,F\}$ would also not be candidate key as $\{D,E,F\}$ is already a candidate key. Therefore, the final candidate keys would be:

$$\{D,E,F\},\{A,C,D,E\}, \{A,B,C,E\}$$

Is my understanding of the topic correct or have I gone of the rails?

Assuming that the three dependencies are a cover of the dependencies of the relation schema R, to find all the candidate keys we could start from a canonical cover of the FDs, for instance the following one:

{ A B C → D
  A B C → F
  D E F → A
  D E F → C
  D → B }

From these dependencies we can see that E must belong to all the candidate keys, since it does not appear in any right part.

We can start now from the left hand parts of the dependencies to see if their closure contains all the attributes:

ABC+ = ABCDF

by adding E (that must be present in every candidate key) we discover the first candidate key, since ABCE+ = ABCDEF.

Then from DEF:

DEF+ = ACBDEF

so this is already a candidate key.

Finally, starting from  D we found that:

D+ = DB

trying again to add E, we find:

DE+ = BDE

we can now try to add A:

ADE+ = ABDE

which is still not a candidate key, and finally adding C we find the last candidate key:

ACDE+ = ABCDEF


Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts? BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running it for BB(n) steps.

So given some n-state TM, can we construct an m-state TM, where m>n, to calculate BB(n) and thus decides if it halts?

Now some might say that this is equivalent to solving the halting problem, but I don't think so. Because given an arbitrary TM, we don't in fact know how many states it has. And if we don't know n, we certainly can't find m.

If the answer is in the negative, then how is it that we can in fact find out the values of BB(n) for small n? What's the connection between incomputability and unknowability?

For a particular $n$, there are at most $2^{O(n)}$ different TMs with $n$ states, and we can have a list for all of them: 1 is the TM halts, and 0 otherwise. A TM that has this "list" in its memory can decide the problem you give in your question. Not only this language is decidable - it is even regular!

The "halting problem" states though, that there is no TM that works for all possible $n$'s.


The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)

I am purposefully not going though all the steps required to solve the exercise (comment if you need more help).

You might want to have a look at pumping lemma for regular languages
.

It gives you a property that all regular languages must satisfy. If you want to show that a language  $L$ is not regular, you can show that this property cannot hold. In practice, the proof usually follows these steps:

assume towards a contradiction that $L$ is regular
choose a suitable word $w \in L$
apply the pumping lemma on $w$ to conclude that a new word $w'$ must belong to $L$
Use the language definition to show that $w'$ does not belong to $L$ (hence the contradiction).

Hint:

   Here is a string $w$ that belongs to your language: $a^n b^n$, for a sufficiently large integer $n>0$.


Applying the Master Theorem on Merge sort I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into calls which aren't natural numbers, but how do I present this argument formally?

The proof:

The recursion splits the problem into two sub problems, each with at most $\lceil \frac{n}{2} \rceil$ elements. Therefore, we can apply the Master Theorem with $a = b = 2$. So, $\log_b{a}$ = 1. The cost of splitting is $0$ comparisons, and that of combining is at most $n−1$ comparisons. Hence the cost of split/combine is $\Theta(n) = \Theta(n\log_b{a})$, so we are in the second case of the Master Theorem, and therefore the total cost is $\Theta(n\log n)$.

You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you can split it into two arrays of length at most 2.5. But you are able to split it into two arrays of length at most $\lceil 2.5 \rceil = 3$.

Note that the textbook estimates the time it takes to sort an array with at most $n$ elements (rather than the time it takes to sort an array with exactly $n$ elements).


What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle? Typing out negative weight cycle again and again is kind of annoying, so for the rest of the question I'm going to abbreviate it to NWC.

I'm writing an optimized version of Bellman-Ford's Shortest Path Algorithm on a directed, weighted graph. When I give it a regular graph with no NWC's, it works fine, and finds the answer correctly. But when I give it a NWC, it loops forever. So, I put a system into the implementation where it finds out if there is a NWC, which it does correctly, but now I'm stuck on what to do once I find it.

My first thought was to just go on regularly while setting every vertex in the cycle to negative infinity, but every single vertex after that becomes negative infinity too, and soon enough, a huge chunk of the graph becomes negative infinity and I'm getting bugs left and right because I'm subtracting to negative infinity, adding to negative infinity, while also setting the distance to negative infinity. I technically could fix all the bugs, but then lot's of valuable information on the other vertices is lost because of one little NWC.

My next thought was to just terminate the program, but then again lot's of information is lost on the other vertices.

So,  what is the correct action to be taken when you find a NWC?

You say that your implementation of Bellman-Ford loops forever.
This leads me to believe that you are only stopping when no computed distance changes in one iteration.

You can always stop at the $(n-1)$-th iteration since, in the $i$-th iteration, all finite distances towards the vertices at hop-distance at most $i+1$ from the source must have correctly been computed.

Then, you can perform a single additional iteration. If a distance to a vertex $v$  changes during this iteration, then $v$ must be part of negative weight cycle (and you will find at least one such vertex $v$ per cycle).
If $V$ is the set of these vertices $v$, you can mark all vertices reachable by those in $V$ has having "negative infinity" distance (you can do this in linear time w.r.t. the size of the graph by performing any graph visit).


Are there algorithms for which we cannot determine if they ever halt? My understanding of the halting problem in layman's terms is that there is no algorithm which will accept an arbitrary program as input and return true if it halts and false if it does not.

For a Turing machine does the question, "Does this Turing machine halt for all inputs?" always have an answer in the first place?

E.g. the algorithm "If this machine halts, then loop. Otherwise halt." seems to suggest that the answer is no. Is there something wrong with this example? Is there a canonical example?

As you point out, the general problem of deciding if a TM stops on any given initial tape content is undecidable. In this answer I'll assume you are talking about the concrete existence (to the point of being possible to indicate, not just demonstrate) of one such machine.

As it happens, the (hypothetical) problem of deciding if a particular TM always halts gets arbitrarily complex as the machines themselves get more complex. It is quite impressive how problems involving even very small machines exist that defy our current understanding. It is possible to conjecture that, for any given limited set of resources, there will be some relatively small machine that is "out of reach", whose behaviour is impossible for us to determine.

Your formula does not add significantly to this idealized scenario.


Collectively pay the bill problem There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars.

Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm.

  First, everyone puts some of their money on the table. Then each individual takes back the money they overpaid.

The bills have a fixed set of denominations (not part of the input).

An example:
Suppose there are two people, Alice and Bob.  Alice owes \$5 and has five \$1 bills.  Bob owes \$2 and has one \$5 bill.  After Alice and Bob put all their money on the table, Bob takes back \$3, and everyone is happy.

Of course, there are times where one doesn't have to put all his money on the table. For example, if Alice had a thousand \$1 bills, it's not necessary for her to put them all on the table and then take most of them back.

I want to find an algorithm with the following properties:

The input specifies the number of people, how much each person owes and how many bills of each denomination each person has.
The algorithm tells each person which bills to put on the table in the first round.
The algorithm tells each person which bills to remove from the table in the second round.
The number of bills put on the table + the number of bills removed from the table is minimized.

If there is no feasible solution, the algorithm just return an error.

If you restate the problem in a slightly different (but equivalent) way, an algorithm becomes more obvious:

There are $n$ parties involved: $n-1$ persons, and one restauarant.  Let $p_i$ be the amount of money party $i$ should have after the meal is finished and paid for.  For example, if Alice has \$36 and owes \$25, Bob has \$12 and owes \$11, and Carl has \$30 and owes \$25, we say that $p_0$ is the restaurant and have:

$p = (61, 11, 1, 5)$

That is, when the meal is over the restaurant should have \$61, Alice should have \$11, Bob should have \$1 and Carl should have \$5.

Now let $b$ enumerate all of the $m$ bills involved.  For example:

$b = (1, 5, 10, 20, 1, 1, 5, 5, 10, 20)$

The denominations of the bills do not matter, but I have chosen denominations of paper US currency for this example because they are familiar.

We are seeking to minimize the number of bills that change hands, so we associate a "cost" with person $i$ leaving with bill $j$ by using a $\{0,1\}$ matrix $C$.  Entries of 0 in this matrix indicate which bills each party starts with ($C_{0,j} = 0$ for all $j$ because the restaurant starts with no bills).

Continuing our example:

$$
C = \left[ \begin{array}{cccccccccc}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
\end{array}
\right]
$$

indicates that Alice started with \$1, \$5, \$10, \$20, Bob started with \$1, \$1, \$5, \$5, and Carl started with \$10 and \$20.

Again, the goal is to minimize the number of bills that change hands.  In other words:

$$
\begin{align}
\text{Minimize:} & \sum_{i=0}^{n-1}{\sum_{j=0}^{m-1}{C_{i,j} x_{i,j}}} \\
\text{subject to:} & \sum_{i=0}^{n-1}{x_{i,j}} = 1  \text{ for } 0 \le j \lt m, \\
& \sum_{j=0}^{m-1}{x_{i,j}b_j = p_i} \text{ for } 0 \le i \lt n, \\
\text{and} & x_{i,j} \ge 0
\end{align}
$$

The first constraint says that the solution can only assign a particular bill to one party, and the second ensures that everyone pays the appropriate amount.

This is the 0,1 INTEGER PROGRAMMING problem and is NP-complete (see [Karp 1972]).  The Wikipedia page about linear programming has information on different algorithms that can be used for these types of problems.

There are potentially multiple optimal solutions; by hand the first solution to the example I came up with was:

$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
\end{array}
\right]
$$

which means Alice pays exactly \$5 and \$20, Bob pays exactly \$1, \$5 and \$5, and Carl overpays \$10 and \$20 and then removes a \$5 from the table.

I also used the Mixed Integer Linear Program module of the Sage Math system which has the ability to use different solver backends (GLPK, COIN, CPLEX, or Gurobi).  The first solution it gave was

$$
x = \left[ \begin{array}{cccccccccc}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
\end{array}
\right]
$$

which is almost the same except that Carl took the "other" $5 that Bob put on the table.

Formulating the problem in this way satisfies all the properties you list (you can extrapolate which bills end up where from $C$ and the solution matrix $x$).  The exception is perhaps #4 which was discussed in the comments of the question.  It is not clear to me what you would like to do in the situation that there is no feasible solution to the set of linear equations:

Identify a subset of people that can pay the reduced total?  Or perhaps a subset of people which could still pay the entire bill, i.e. they pay for their friend.

Your final statement makes it seem like you are interested in the case that the denominations of the bills are fixed, this doesn't change the problem however.

In any case, there is also an $O(1)$ solution in which every person pays with a credit card.


Isomorphism problem on bounded degree digraphs By Babai & Luks (1983), it was proved that graph isomorphism problem is tractable on bounded degree graphs. However, I could not find any result when the graph is edge directed.

Is isomorphism problem tractable (or GI-complete) on edge-directed graphs with bounded degree?

You can reduce graph isomorphism on directed graphs to graph isomorphism on undirected graphs.  I think it's possible to build a reduction that preserves the bounded-degree property.

For instance, I think the following should work.  Replace each directed edge u --> v with the following gadget:

u --- a --- c --- v
      |
      b

where a, b, and c are fresh new vertices (different ones for each edge).

Next, we'll add some edges to make sure that the isomorphism makes original vertices like u, v map to other original vertices (not to the new vertices).  Add a new vertex A (just one), and connect A to each of the a's; to do this in a way that preserves bounded edge degree, use a binary tree.  Finally, add a long path A --- A' --- A" --- A"' --- ... with n+3 new vertices, where n is the number of vertices in the original graph.  Add a new vertex B, connected to a path of n+2 new vertices, and connect it to the b-type vertices as above; and add a C, connected to a path of n+1 new vertices, connected to the c-type vertices.

Apply this transformation to both directed graphs, to get two undirected graphs.  Now I think any isomorphism of the resulting undirected graphs corresponds to an isomorphism of the original directed graphs.  In particular, the isomorphism must map the two n+1 paths to each other; so it must map the two A-type vertices to each other; so it must map a-type vertices to other a-type vertices; and similarly, b-type to b-type and c-type to c-type.  Thus vertices of the original directed graph must be mapped to vertices of the other original directed graph.  The mapping must preserve the direction of the edges, due to the asymmetry in the gadget above.


Using a point as an input for a perceptron Can a point be used as the input for a perceptron/neural net?

The relationship between the two numbers that make up a 2D point does not affect the output, but does this not matter when the satisfactory weights are found?

If I wanted to use a point $(x,y)$ as an input for my perceptron, would I simply have two input nodes, one for $x$ and one for $y$?

Yes, you can do that.  Nothing prevents it.  Yes, you'd have two inputs, one for $x$ and one for $y$.  You might want to normalize those values so they are in the range $[-1,1]$ or $[0,1]$.


The maximum number of nodes in a heap tree of degree d and depth k The maximum number of nodes in a binary tree of depth k is defined by $2^{(k+1)}-1$, but the same rule doesn't appear to work for heap trees of different degrees.
Let's say I have the following tree of degree 3
   1
 / | \
2  3  4

Here the depth of the tree is 1. So according to the formula, it will be $3^{(1+1)}-1=8$. But we have 4 nodes here. I am really struggling to adapt the binary tree formula to trees of other degrees.
Any thoughts?

A complete $d$-ary tree of depth $k$ has $d^\ell$ on level $\ell$ (where $0 \leq \ell \leq k$), so its total number of nodes is
$$
\sum_{\ell=0}^k d^\ell = \frac{d^{k+1}-1}{d-1}.
$$


Determine whether removing a node on a graph will disconnect the graph I have an undirected unweighted graph with a single component. I want to know if removing a given node will disconnect the graph. I know that I can remove the edges to the node and then use DFS to get the number of components, however this seems rather inefficient as I need to check all vertices in the graph for this. Is there a faster way to do this?

Yes, if we know something about the given graph. For example, if we know that graph is a tree or a cycle or a star graph. Or we might be able to terminate the algorithm early, for example, if we can determine the neighborhood of that node is still connected after that node is removed.

However, an algorithm to determine whether an arbitrary node is an articulation point or not in a general graph has to visit every node in the worse case.

Suppose a clever algorithm claims a given node is an articulation point without visiting all nodes. Suppose node $\mathcal U$ is not visited. Well, it could happen that $\mathcal U$ is connected to every node. Or there might be an edge that connects $\mathcal U$ to a point in the other connected component. That is a contradiction.

To be slightly more precise, any such algorithm should visit every remaining edge in the worst case.

Any way, a DFS that goes through all edges runs in $O(|E|)$ time is pretty fast for graph without too many edges.  It should not be a big performance concern usually. If a series of node will be removed one by one and you want to determine the first one that disconnects the graph, it might help to do some precomputation to decompose the graph in certain way or other kinds of tricks to reduce the amortized cost. That is another story, though.


Why injection into sum type apparently leads to ambiguity? I have been reading Benjamin Pierce's Types and Programming Languages, plus a couple of course notes on type systems and typed $\lambda$-calculus, and there is one thing I don't get: it seems that everybody defines sum types in the same way, and they way the language is extended to accommodate this new type includes the following typing rules:

if $\sigma$ and $\tau$ are types, then $\sigma+\tau$ is a type
if $M$ is of type $\sigma$, then $\operatorname{inl} M$ is of type $\sigma+\tau$
symmetrically for $\operatorname{inr}$, if $M$ is of type $\tau$, then $\operatorname{inr} M$ is of type $\sigma+\tau$.

However, suppose I have two sum types, $\sigma+\tau$ and $\sigma+\phi$,
and also that $M$ is of type $\sigma$.
Then it is not clear what the type of $\operatorname{inl} M$ is.

Is there something I missed, or is this really how sum types work? Because it would be quite easy to actually "fix" the definition to allow one to immediately infer the type of $\operatorname{inl} M$ in the example above -- just include the sum type in the annotation:

$\operatorname{inl_{\sigma+\tau}} M$ is, of course, of type $\sigma+\tau$.

But this is not what is usually done. Why? (Or is it actually done, implicitly?)

I think the key point here is $\sigma$, $\tau$ and $\phi$ are type variables, and not specific types. So, what the typing rule for $\operatorname{inl}$ says is that $\operatorname{inl} M$ is of type $\sigma + \tau$ for any $\tau$. The names of type variables don't matter, what matters is where else are you using the same type variable.


Recurrence relation with a number value (not n) I'm learning how to use recursion trees to solve recurrence relations and while I know how to solve it for the form

$$T(n) = aT\big(\frac{n}{4}\big) + n$$

I'm stuck when the equation has a numerical term, like

$$T(n) = aT\big(\frac{n}{4}\big) + 3$$

Using a recursion tree, what gets multiplied at the first, second, third level? And what is the sum of the work done?

The recursion tree corresponds to repeated expansion of the recurrence:
$$
\begin{align*}
T(n) &= 3 + aT(n/4) \\ &=
3 + 3a + a^2T(n/16) \\ &=
3 + 3a + 3a^2 + a^3T(n/64) \\ &= \cdots \\ &=
3 + 3a + \cdots + 3a^{k-1} + a^kT(n/4^k) \\ &=
3\frac{a^k-1}{a-1} + a^kT(n/4^k).
\end{align*}
$$
This is the result if you stop the recursion after $k$ steps. If, for example, you define $T(1) = 3$ then for $n = 4^k$ you will get $T(n) = 3+3a+\cdots+3a^k = 3\frac{a^{k+1}-1}{a-1} = \Theta(a^{\log_4 n})$.


Does every NP problem have a poly-sized ILP formulation? Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem in NP.

But I've seen papers on specific NP problems where people write things like "this is the first poly-sized formulation" or "there is no known poly-sized formulation". That's why I'm puzzled.

This answer is mostly a recap of the comments on the question above.

If a problem is NP-complete, it can indeed be reduced to ILP, by using Karp's reductions (― Joe, andy). Claims of "polynomial sized formulations" from one problem to another, are likely meant as more direct formulations, as opposed to multiple reductions through SAT (― Kaveh).


Question about the definition of strings that GNFA's accept In Sipser's "Introduction to the Theory of Computation" it states "A GNFA accepts a string $w$ in $Σ^{*}$ if $w = w_1 w_2 · · · w_k$ , where each $w_i$ is in $Σ^{*}$".

However, wouldn't a more precise definition be "A GNFA accepts a string $w$ in $Σ^{*}$ if $w = w_1 w_2 · · · w_k$ , where each $w_i$ is in $Σ$" ?

If a GNFA $A$ reconizes $\Sigma^{*}$, then $\epsilon \in \Sigma^{*}$ must be accepted. However $\epsilon \not\in \Sigma $.


Deterministic Multi-tape Turing Machine construction I'm trying to construct a deterministic multi-tape turing machine for the following language in order to show that $L$ is in $DTIME(n)$:

$$L = \{ www \mid w \in \{a,b\}^+ \}$$

I'm not sure how to get started. Any hints would be appreciated.

You could copy the input to 3 tapes, then move the heads on tapes 2 and 3 until they point to the same substring and on tape 3, the end of substring matches the end of string.

The exact steps could be..

   1. copy input
 2. erase first symbol on tape two and first two symbols on tape three
 3. go forward on all tapes until...
 4. if one of the symbols is different than on other tapes, go back to the start of each tape and return to step 2
 5. if tape three reaches end of input, you are done


Amortized time of insertion into an Array list According to Amortized time cost of insertion into an Array list,

  A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

Can anyone kindly explain me the logic of this? If we consider the n(number of elements)=7 then we resize array at sizes 1,2,4 but according to above statement "1,2,4....7".

The question might be a little misleading.

  So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

This is only true if $n = 2^k$ for some $k \in \mathbb{N}$, because for a growth factor of 2, we only need to resize when $n$ is a power of 2.

So in your case we would only resize at 1, 2, 4. Not 7.

You should keep in mind this only applies to a growth factor of 2. We could change the growth factor however we wish. For example we set the growth factor to 3. Then we resize at powers of 3; $\{1, 3, 9, \dots 3^k\}$. You can still use the same analysis procedure to get a constant amortized time though.


N subsets with a given sum? How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?

¹⁾ Not as in $P$, I just want something smarter than $O(n^{|S|})$.

Ex. Let’s say we want $n=3$ subsets with the sum of $K=3$ chosen from $S=[1,1,1,2,2,2]$.

The correct solution is $[1,2], [1,2], [1,2]$.

Ex. Let’s say we want $n=2$ subsets with the sum of $K=5$ chosen from $S=[5,4,3,2,2,2,2,1]$.

One correct solution is $[5], [1,4]$.

Another one would be $[2,2,1], [2,3]$.

Etc. Just a correct solution, regardless of which one.

This problem is strongly NP-hard because it generalizes the 3-Partition problem. That means that it has no efficient (polynomial-time) algorithm, unless P=NP.


Effect of value of k in K-Nearest Neighbor In K-Nearest Neighbor the value of k decides the accuracy of classification. What are the pros and cons of choosing smaller value for k and larger value for k?

There is no simple answer.  The standard approach to choose $k$ is to try different values of $k$ and see which provides the best accuracy on your particular data set (using cross-validation or hold-out sets, i.e., a training-validation-test set split).

Intuitively, $k$-nearest neighbors tries to approximate a locally smooth function; larger values of $k$ provide more "smoothing", which or might not be desirable.


Finding optimal sequence of questions to minimize total student time Suppose there is a tutorial session at a university.
We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$
students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s_j$, let $Q_j \subseteq Q$ be
the set of questions that a student has a doubt it. Assume that
$\forall 1 \leq j \leq n: Q_j \neq \phi$ and
$\bigcup_{1\leq j\leq n}Q_j = Q$.

All students enter the tutorial session in the beginning (at $t = 0$). Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time
taken to discuss each question is equal, say 1 unit$^*$. Let $t_j$ be the
time spent by $s_j$ in the tutorial session. We want to find out an
optimal permutation $\sigma$ in which questions are discussed
$(q_{\sigma(1)} \ldots q_{\sigma(n)})$ such the the quantity $T_\sigma = \Sigma_{1\leq j \leq n}t_j$ is minimized.

I have not been able to design a polynomial time algorithm, or prove $\mathsf{NP}$-hardness.

We can define a decision version of the problem
$$ \mathsf{TUT} = \{\langle k, n, \mathcal{F}_Q, C \rangle \mid \exists \sigma : T_{\sigma} \leq C\} $$

where $\mathcal{F}_Q$ is the set of $Q_j$'s.

We can then find out the minimum
$T_\sigma$ using binary search on $C$ and find out the optimal $\sigma$ using partial assignments to $\sigma$ in polynomial time using an oracle for $\mathsf{TUT}$. Also, $\mathsf{TUT} \in \mathsf{NP}$ because the optimal $\sigma$ can be used as a certificate which we can verify easily in polynomial time.

My question: Is $\mathsf{TUT}$ $\mathsf{NP}$-complete or can we design a
polynomial time algorithm for it?

Sidenote: By the way, I thought of this question after an actual tutorial
session, in which the TA discussed the questions in the normal order $q_1 \ldots q_n$ because of which many students had to wait until the end.

Example
Let $k=3$ and $n=2$. $Q_1 = \{q_3\}$ and $Q_2 = \{q_1, q_2, q_3\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s_1$ leaves after $t_1 = 1$ and $s_2$ leaves after $t_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s_1$ and $s_2$ both have to wait till the end and $t_1 = t_2 = 3$, so sum is 6.

$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!

I suspect the problem $\mathsf{TUT}$ to be NP-hard. I will show how to transform the problem such that it is strongly related to a problem which is NP-hard. (Yes, this is all rather vague. I basically think my general approach is correct, but I am currently unable to proceed.)

First, note that the problem $\mathsf{TUT}$ can be reformulated as follows:

Given a set of questions $Q$ of size $k$, a set of $n$ subsets $\mathcal{F}_Q\subseteq \mathcal{P}(Q)$ and an integer $C$, does there exists a sequence $\Sigma : \langle S_1,\ldots, S_k\rangle$ such that, for all $i \in\{1,\ldots,k\}$:

$S_i\subseteq Q$ and $|S_i|=i$; and
$S_i \subset S_j$ for all $j>i$; and
$\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq C$ ?

Note that the set $S_i$ represent the first $i$ questions that will be explained. Conditions 1 and 2 ensure that the subsets are well formed according to this interpretation. Condition 3 counts the amount of students that haven't left at every moment in time, so it indeed sums up to the total waiting time among all students.

Now, we restrict the size of the subsets in $\mathcal{F}_Q$ to $2$, so we can represent these subsets as edges on a graph where the vertices are the elements from $Q$. (A hardness result for this special case is sufficient for hardness of the general problem)

Now, the problem of minimizing $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$ for a single $i$ (this is essentially ignoring condition 2) is equivalent to the following problem, which I dub '$\mathsf{\text{Double max $k$-vertex-cover}}$':

  Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$ has a size of at least $t$?

This problem is NP-hard, since $k$-clique is a special case of this problem, as this answer shows. However, this is not sufficient to prove $\mathsf{TUT}$ to be NP-hard, since we need to find the maximum for every $i$, while respecting condition 2. This conditions are not satisfied by every sequence $\Sigma$ that satisfies only condition 1 and 3: consider the graph on $7$ vertices with two disjoint cycles, one of size $4$, the other size $3$. For $i=3$, selecting all vertices in the $3$-cycle gives the maximum, while selecting all vertices of the $4$-cycle is optimal for $i=4$.

It seems that condition 2 makes the problem even harder and most certainly not easier, which means $\mathsf{TUT}$ should be NP-hard, but I haven't seen a method to formally prove this.

So, to summarize, I have reduced the question to the following:

Is it possible to include condition 2 to complete the hardness proof for $\mathsf{TUT}$?

Side note: The formulation I gave makes it tempting to try an iterative algorithm which finds $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$ under condition 2 from $i=1\ldots k$, by finding all maximum 'extenstions' of all found maximum sets for $i-1$. This does not lead to an efficient algorithm, as the amount of maximum sets at a single iteration may be exponential in $k$. Additionally, I have not seen a method to determine whether a subset for some $i$ would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.


When did "regular" start referring to Type 3 languages/grammars? In his 1959 paper, On Certain Formal Properties of Grammars, Chomsky defined a "regular" grammar as a specific form of a type 2 (context-free) grammar. (See Definition 8 of that paper.) He then goes on (in Section 6) to demonstrate that regular (type 2, context-free) grammars can generate more languages than type 3 (finite state) grammars.

However, in every other computer-science reference I've read, type 3 languages (those recognizable by a finite state machine) are called "regular". (For example, see the Wikipedia entry for Chomsky Hierarchy.)

My question is, when did "regular" shift from referring to type 2 languages to type 3 languages? And why? (Was it intentional, or did someone mis-quote Chomsky at some point and that stuck?)

I found an answer, at least a partial one, hinted at in Footnote 10 of Chomsky's paper where he refers to a 1956 paper by Kleene in which Kleene describes "regular events" -- a language recognized by finite state machines.
So it would seem the common usage of "regular language" today traces back to Kleene's "regular events" rather than to Chomsky's "regular grammar".
Furthermore, as renierpost pointed out in a comment, what Chomsky called a "regular" grammar in 1959 is now known as Chomsky normal form.
Edit: I asked Professor Chomsky via email whether he intended his "regular grammar" to have a connection to Kleene's "regular events". He replied: "Long time ago and I don't recall. I suppose just a coincidence."


What are these tree transformations called? I want to transform a general rooted, node-labeled tree into a related binary tree. I came up with four different schemes ("left shallow", "right shallow", "left deep" and "right deep" binarization) that are illustrated by an example in the diagram below. They all preserve certain aspects of the original structure. Children stay children or become grand- (or grand-grand or grand*-)children. Also, new nodes are introduced (depicted in blue), which is fine for my application.

Does any of these four schemes have a name? Or is it documented or studied somewhere?

I am aware of one documented "binarization" scheme, which is called Knuth transform (also in the diagram). It is also possible to recover the original tree from this and you don't even have to introduce new nodes while building the binary tree. However, I am not interested in this, since it brings former siblings into parent-child-relation, which I can't have in my application.

The Natural Language Toolkit (NLTK) offers binarization: nltk.treetransforms.chomsky_normal_form(). The algorithm in NLTK implements the standard, straight-forward transformation into Chomsky normal form. It assumes the tree was generated via an underlying (context-free) grammar. This results in the deep trees in the bottom row (diagram in the question post). By default, you will get the "right deep" variant, as a consequence of putting the artificial non-terminals on the right of the existing non-terminals ("right factorization") when transforming the production rules. You can change the default parameter factor="right" to factor="left", if you prefer the "left deep" variant.

However, this is not the only way to construct a grammar in Chomsky normal form, since it only requires to have production rules of the form $A\to BC$ (or $A\to a$). You could just as well decide to balance the two sets of children as well as possible and assign them to the artificial nodes on the left and right. Since children can come in odd numbers, you will have to decide to add one more to either side. If you put it on the left, you will get the "left shallow" variant, and the "right shallow" variant otherwise.

For this other algorithm to arrive at a Chomsky normal form (that produces the "shallow" variants) I could not find a term. This is likely because Chomsky normal form comes from the world of theoretical computer science and it is most useful as an existential fact ("there exists a certain normal form, s.t. ...") where the details matter little. I think "balanced factorization" would be an appropriate term for this transformation.

The library Discontinuous Data-Oriented Parsing offers more binarization schemes with a confusing set of options. This includes the algorithm from NLTK and approaches described in two papers. The library deals with natural language parsing via Linear Context-Free Rewriting Systems (LCFRS) (a generalization of Probabilistic Context-Free Grammars (PCFG)),  and a lot of options might related to this specific application. I was not able to get a "shallow"/"balanced" binarization from this library, but it might be possible.


Runtime of weighted interval scheduling dynamic programming algorithm Consider this implementation of a dynamic programming algorithm for weighted interval scheduling:

M-Compute-Opt(j)
    If j=0 then
        Return 0
    Else if M[j] is not empty then
        Return M[j]
    Else
        Define M[j] = max(v_j + M-Compute-Opt(p(j)), M-Compute-Opt(j − 1))
        Return M[j]
    Endif

Here we have a set of requests $\{1, 2, \ldots , j\}$. We're assuming they're ordered by finishing time in nondecreasing order. I.e., $j$ finishes last, $j-1$ second last, etc. $v_j$ is the weight assigned to interval $j$. Also, $p(j)$ is the interval to the left of $j$ that ends as close to the beginning of $j$ as possible without overlapping. We're assuming these were also computed beforehand.

The textbook I'm looking at says the runtime is $O(n)$ because a single call to M-Compute-Opt is $O(1)$ and we call it twice for every empty entry in array M. I almost buy it except it seems to me that we could end up calling it more often for some $i \in \{1, \ldots , j\}$ if the function $p$ maps lots of elements to that $i$. For example, if there is some interval $i$ where right after it ends a ton of intervals start, $p$ would map lots of intervals to it. And of course M-Compute-Opt wouldn't be called from within those instances since the value would be stored the first time, but it seems they would run nonetheless.

I guess in general I understand the argument given in the book, but I was wondering if there is a good one way to understand the linear time from a more intuitive standpoint. I'm not used to calculating runtimes and I feel like if I saw a different problem like this one I wouldn't come up with the "trick" used.

If I understand your concern correctly, you are right in that many $p(j)$ may give the same $i$. But that means that other $i$s don't get many $p(j)$s (the total of them is $n$).


Is this an example of Tail Recursion As I have read in this answer: What is tail recursion? tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call.

Here after the recursive call we just assign the result to another variable.
Can we consider this code as tail recursion?

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        if not head or not head.next:
            return head

        head_ = head
        head_next = head.next
        head_next_next = head.next.next

        head_next.next = head_

        head_.next = self.swapPairs(head_next_next)

        return head_next

It is considered tail recursion if there is no computation between the recursive call and the return.

In your example there is no computation, only an assignment.

It would depend  on the actual compiler if code for an optimised tail recursive call was made at this point, but yes some compilers could treat this as a tail recursive call.


Need help in a question regarding polynomial oracle reductions Prove the following:

If there is a polynomial oracle reduction from $S1$ to $S2$:

a. If $S2\in\ P$ so $S1\in\ P$

b. If $S2\notin\ P$ so $S1\notin\ P$

The way I see it - If there is a polynomial oracle reduction from $S1$ to $S2$, you can solve $S1$ with $n^k$ questions to $S2$. If $S2\in\ P$, and $S2$ is solved with $n^k$ actions, it means $S1$ can be solved in $n^{n^k}$ actions - $\in\ P?!$

(I translated the phrase 'polynomial oracle reduction' from hebrew, so ask me if you don't understand what I meant).

Hint: Since $S_1$ runs in polynomial time, say $O(n^a)$, every input to the oracle has polynomial length $O(n^a)$. If $S_2 \in \mathsf{P}$, say can be decided in polynomial times $O(n^b)$, then we can simulate all the oracle calls in $O(O(n^a)^b)$.


Thompson's construction, transforming a regular expression into an equivalent NFA There is this case of concatenation that says (from wikipedia):

  The initial state of N(s) is the initial state of the whole NFA. The final state of N(s) becomes the initial state of N(t). The final state of N(t) is the final state of the whole NFA.

My question is, does this mean that the final state of N(s) is linked to the initial state of N(t) with an edge labeled ε ?

You can do concatenation with an epsilon transition, but it is not necessary. Many implementations avoid it because concatenations are common and the epsilon transitions significantly increase the machine size.

There is some nice code in Russ Cox's famous essay on regular expressions, which implements a common strategy: fragment machines are built without any endpoint. Instead, the fragment descriptor contains a list of states in the fragment which would have a transition to the endpoint if there were one. In this way, two fragments can be concatenated by backpatching the second fragment's start state number as the head (target) of all outgoing transitions from the states in the first fragment's endpoint list.

You will find real code (in C) in the linked essay; search for the heading starting "Implementation"


If there's algorithm which returns true if Hamiltonian cycle exists in polynomial time then an algorithm to find the cycle in such time also exists? How can it be proved that if there's an algorithm which in polynomial time determines whether a graph has a Hamiltonian cycle then there's an algorithm which can find such Hamiltonian cycle in polynomial time as well?

Note: there's no need to devise the actual algorithm I just need to prove that one causes the other to hold.

I thought that perhaps the algorithm A which just determines whether the graph contains a Hamiltonian cycle has to perform the same amount of work as the algorithm B which has to find the actual cycle because each node has to be visited.

But I'm not sure how to actually prove this.

Input: A graph G = (V, E) for which the checker algorithm is true.

if you remove an edge $e\in E$ from The graph and run the algorithm then if it returns false the removed edge must be part of every hamiltonian cycle in the graph.

If the result is true then we can remove the edge and remove another edge we haven't checked yet and run the algorithm again.

Eventually the graph will only contain a hamiltonian cycle. in O(e) applications of the algorithm.