DP Knapsack Problem With Categorical Constraint so I'm working on a variation of the knapsack problem which includes a constraint on the number of each item from each category in addition to a weight. For instance, we have a number of books each given a genre (1 of 3  genres), and our goal is to maximize the total weight as well as include at least G books from each genre.

The recursion is found below, but when trying to convert this to a DP solution I'm having some issue. Note that the problem specifically deals with books, their categories, and maximizing an enjoyment factor up to some k. It's identical to the knapsack problem beyond the fact that the items are categorized and we need at least N items from each category.

private double S2(int W, int k, List<Book> books, int F, int SC, int C) {
    if(W == 0 || k == -1) {
        if(F <= 0 && SC <= 0 && C <= 0) {
            return 0.0;
        } else {
            return Double.NEGATIVE_INFINITY;
        }
    }

    Book b = books.get(k);
    int w = b.getWeight();
    if(W-w >= 0) {
        int newF = F;
        int newSC = SC;
        int newC = C;
        if(b.getGenre() == Book.Genre.FANTASY) {
            newF = F-1;
        }
        if(b.getGenre() == Book.Genre.SCIENCE_FICTION) {
            newSC = SC-1;
        }
        if(b.getGenre() == Book.Genre.CLASSICS) {
            newC = C-1;
        }
        return Math.max(b.enjoyment+S2(W-w, k-1, books, newF, newSC, newC), S2(W, k-1, books, F, SC, C));
    } else {
        return S2(W, k-1, books, F, SC, C);
    }
}

My DP solution involves a 5 dimensional array for W, k, F, SC, C and I'm just traversing it in 5 dimensions and filling in each value based on the recursion but it's way too slow--in fact, slower than the recursion for small n (even though it should run in polynomial time as opposed to exponential time). Is there some quicker way to traverse the subproblems in the DP solution, in some specific order?

I'm basically doing "tabular memoization" in 3 extra dimensions for the original Knapsack problem with only 1 constraint. Is my recursion wrong? Or is this to be expected?

An alternative approach you could try: solve a knapsack problem for each category separately, then combine those solutions.

You'll probably find it more rewarding to work out how to do that on your own, but if you want a more detailed hint:

   For each category and each total weight $w$ and each integer $t$, compute the maximum enjoyment you can have by using at most $t$ books from that category and where the total weight is at most $w$.

 For instance, for each $w,t$, you'll compute the maximum enjoyment you can have by selecting at most $t$ fantasy books (and no science fiction or classic books) of weight at most $w$.  Then do the same for science fiction, and the same for classic books.

 Then, combine these three results.  I'll let you work out how to combine them.


Assign unique integer keys to sets I am given a list of $n>1$ arrays, where each array has fairly small number of elements (rarely above $5$). Also $n$ is quite small in practice (around $6$).

My problem is that I would like to efficiently map each element product to unique integer. Also, I would like to efficiently compute the integer, when I change the order of the arrays in the list.

I was thinking something in the line of integer factorization.

Take first $n$ primes ($p_1, p_2, ..., p_n$) and remeber the index of the array in the original list with $ind: A \rightarrow \mathbb{N}$. So the initial function would be $ind(A_i)=i$.

Also we denote with $a_{i,j}$ the $j$-th element of the $i$-th array in the list. So the function $F:A_1 \times A_2 \times \ldots \times A_n \rightarrow \mathbb{N}$ would be:

$$F(a_{1,i_1}, a_{2,i_2}, \ldots, a_{n,i_n})=\prod_{j=1}^{j=n}p_{ind(A_i)}^{i_j}$$

In more common words, we initially assign a prime number $p_i$ to array $i$ and raise $p_i$ to the index of the element in array $i$.

This guarantees us the uniqueness and also if we change the order of the arrays in the list, we just need to change the $ind$ function. But the problem here is that these products are fairly large and will overflow soon enough (even with using doubles).

Do you have any better idea how to enumerate these products without the large number constraint? I am implementing this in Java and I really would not like to use BigInteger implementation.

Based on your description, I take it that an element product is taking one element from each array and multiplying?

You don't really need to multiply or use prime numbers which might overflow (but not too much for your constrains I suppose, and is a cute solution :-)).

Suppose the arrays were of fixed size $k$ (You can pad the arrays to achieve this, and based on your constraints, won't be too much of a problem).

Then you want to map all possible tuples $(x_1, x_2, \dots x_n)$ where $0 \le x_i \lt k$ to unique integers.

The mapping you need: Interpret the tuple as an integer in base-$k$.

If arrays are shuffled you can still change the $ind$ function and remap the digits according to that.

(or did you try that and didn't work for some reason?)


Origin of tFAW (Four Activation Window) in DRAM timing constraint In DRAM timing constraints, tFAW means length of a rolling window that allows up to four row activations in same Rank. This constraint is mainly due to power budget of each rank.

However, I am curious why 4 is the magic number？Would it be wrong if we use Eight Activation Window and double the value or use Two Activation Window and halve the value?

The magic number is just 4 since (within one rank) you have just 8 banks where you can spread your consecutive accesses. The problem lies with the bank activation current drained from the entire array (or bank) of single cells (transistor + capacitor) needed to prepare the memory location to be read. If the consecutive read operations are falling each time in a different ROW within each bank than you have the activation problem kicking in each time. In order to avert a high current drain from the arrays you need to limit the number of consecutive bank activation over a rolling window of time. The reason why you need to prevent the bank from high energy / current drain is because this may cause a Voltage Reference (VR) deterioration. The VR is the standard Voltage level against which earch data read from the bank is compared to verify if what you are reading is 1 or a 0. Risking to alter the VR level may mean that the reliability of what your read or write is compromised.

However these tFAW and tRRD parameters are usually overestimated and a memory tuner may increase system performances by slightly changing these parameters.


Optimal Partition of Book Chapters Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions:

by the end of each day, you cannot be in the middle of a chapter.
You must read the chapters in order.

You also want to minimize the maximum number of pages read in a single day.

Now let's consider the brute force algorithm: look at every possible way of dividing the chapters into $d$ days, and compute the maximum number of pages read in a single day. There are $\binom{n+d-1}{n}$ ways to divide the chapters up (using stars and bars) and you must check the number of pages read in each day, ultimately by doing $n$ operations. So this algorithm takes $O\left(n\binom{n+d-1}n\right)$ time, which is pretty bad, but I can't think of how to improve it.

Imagine an analogous decision problem:

  Given a book with $n$ chapters, is it possible to read it in $d$ days such that you never read more than $k$ pages in a single day without violating the restrictions?

The decision problem seems to have a really easy greedy solution: Each day, read as many chapters as you can without exceeding $k$ pages. If you're done with the book after $d$ days, the answer is yes. Otherwise, the answer is no. This takes $O(n)$ time.

It seems weird that the decision problem would have such a simple solution but the original one doesn't. Can anyone think of how to do better than the brute force algorithm for the original problem?

Your brute force solution is far from optimal. One improvement is to use dynamic programming. For every $i,j$, determine the minimal maximum number of pages per day when reading the first $i$ chapters in $j$ days. Implemented naively, this leads to an $O(n^2d)$ solution, though you might be able to improve this to $O(nd)$ using a smart implementation.

A perhaps better solution is to use binary search. You state that it is easy to determine whether a certain maximum number of pages can be achieved. To find the minimum number that can be achieved, use binary search with the decision algorithm as an oracle. The running time in principle depends on the total number of pages, but in fact there are only $n^2$ different possible answers, and this leads to an $O(n^2)$ algorithm, which can probably be improved to $O(n\log n)$ with some additional ideas.


Does the callback concept of programming have any basis in computer science? Although I seriously code with computer languages in general since 2010 and as an amateur programmer with programming languages in particular since 2015 (primarily Bash and JavaScript imperative scripts) and codes I wrote are scattered through my Stack Exchange accounts, as in my Code Review SE account,
I think I still misunderstand what a Callback is;
I feel that the term itself might be misleading, as I understand that callback functions doesn't "call back" anything, but rather "called back" as a reaction to a condition (event).
I understand the alternative term Callafter as significantly controversial between programmers, so I stay with "Callback" or its semantic siblings;
Any Stack Exchange session I read about "Callback" contained answers that I either recognized as contradicting or controversial by other programmers commenting in comments.

My question

Because the particular examples I read of this concept in Bash and JavaScript are not remembered to me as clear, I ask:

  Does the callback concept of programming have any basis in computer
  science?

That is to ask; is there, as part of a computer science theory, some logical formula that can simulate all possible "callback functions" (similarly to as a Turing machine can simulate all possible functions of a computer) that might help understanding the purpose of this concept?
An answer might help me understand what is the common denominator (if there is one) between different "callback" terms in programming.

(I might be wrong, but this is my understanding.)

Callbacks, especially as seen in JS, are analogous to a semantic model known as Continuation-passing style (CPS). In CPS, a program’s flow is modeled as a series of functions, each of which takes in a continuation, and calls the continuation with the function’s result when finished.

As stated, this is also a form of higher-order programming, where functions are used as values.


CFG for the language L ={a^n w | w \in {b,c}^*, n= count of b.c in w. } $L =\{a^nw \mid w \in \{b,c\}^*$, $n=$ #$_b$ + #$_c$$\}$

$\bullet $ #$_b$ denotes the number of $b$'s in $w$

$\bullet $ #$_c$ denotes the number of $c$'s in $w$

I have some trouble designing a CFG for the language above. How can I do this?

I believe the following CFG meets the requirements

$$
S \to aSB \mid \varepsilon\\
B \to b \mid c
$$


CFG - Ambiguous to Unambiguous Given the ambiguous CFG :
S → 01S1|SS|ϵ

I came up with the following CFG which I think is unambiguous:

S → 01X | 011X
X → 01X1 | ϵ

Is my CFG unambiguous and does it represent the same language?

Let $D$ be the grammar, $S \mapsto01S1\mid SS\mid\epsilon$.
Then each word $w$ generated by $D$ is a mixture of equal number of $01$'s and $1$'s such that in any prefix of $w$ there are at least as many 1's as 0's but at most twice as many 1's as 0's.

Let $H$ be your grammar, $S \mapsto01X\mid011X$ and $X\mapsto 01X1\mid ϵ$.
Then each word generated by $X$ is some number of 01's followed by the same number of 1's. So each word $w$ generated by $H$ starts with 01 or 011, followed by some number of 01's, followed by the same number of 1's.

Both $D$ and $H$ are CFGs. While $D$ is ambiguous as illustrated by $011\ \  011011=011011\ \ 011$, $H$ is unambiguous.

The word 010111011 is generated by $D$ but not by $H$. The word 01011 is generated by $H$ but not by $D$. Hence, the language generated by $D$ and the language generated by $H$ are not the same.

It should not be hard to prove the various claims in the above paragraphs. Yuval Filmus' idea to treat 01 as one symbol might be helpful.

Is the language generated by $D$ inherently ambiguous? Here is the spoiler.

   No. In fact, there is a deterministic grammar $S \mapsto \epsilon\mid 01S1S $. The language is actually isomorphic to the celebrated dyck language.


Average depth of a Binary Search Tree and AVL Tree My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary search trees and I don't think I am understanding the concept correctly. For example, if $n=4$ the tree is either going to have a node with a maximum depth of $3$ or node(s) with a maximum depth of $2$. In the case of where the maximum is $3$, then we would have nodes of $0$, $1$, $2$, and $3$ depths. This would give us an average depth of $1.5$ and $log(4)$ is $2$.

My professor also said that an AVL tree's nodes will ALWAYS have an average depth of $O(log(n))$, which makes even less sense to me, since with the example above of $n=4$ the closest we got to $log(4)$ was $1.5$ with a tree that had nodes of depth $0$, $1$, $2$, $3$ but in an AVL tree we couldn't have that tree.

The $O(log(n))$ stuff would kind of make sense if the root started with a depth of $1$, but I specifically asked the professor if that was the case and he said no.

Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, assuming it's not a balanced tree and the inputs are sorted, so the resultant tree ends up being a very deep linked list. In that case, the average depth of nodes in the tree can be $\frac{n}{2}$. But assuming the tree is balanced, or the input is randomized, the expected depth will be $O(\log n)$ because the number of nodes present at each depth in the tree grows exponentially with the depth of the tree. ($2^0$ nodes at depth 0, and $2^1$ nodes at depth 1, etc). This is of course, subject to the constraint that the count of all nodes is equal to $n$, so the height of the tree will be $O(\log n)$.

The average depth of all the nodes in the tree will of course grow as the depth of the tree increases, and since the number of nodes present at a particular depth increases exponentially with the depth, the larger the tree is, the denser the deeper layers of the tree will be, and the more the deeper layers will dominate the average. So the average depth of nodes in the tree will approach the height of the tree, which we know to be $O(\log n)$. So the average depth of nodes in the tree is also $O(\log n)$.

Your professor mentioned that AVL trees will always have an average depth of $O(\log n)$. This is because AVL trees are balanced, so everything mentioned above always applies to AVL trees. They cannot end up being linear.

This is just an intuitive argument, not a proof. If you need a proof, see CLRS (Cormen Leiserson Rivest Stein) Introduction to Algorithms Third Edition pg 300. They have 3 pages of algebra as a proof.


Time complexities of state-of-the-art SAT solvers with respect to length of the formula I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables.

If I am not mistaken, one of the reasons why most believe P does not equal to NP is that there exists no polynomial-time algorithm for SAT despite tremendous effort from mathematicians and computer scientists. However, the P vs NP problem only cares about the time complexity with respect to the length of the formula, not the number of variables.

If these state-of-the-art SAT solvers were run on 3CNF formulas, then a time complexity exponential to the number of variables implies a time complexity exponential to the length of the 3CNF.

However, if they were run on arbitrary CNFs, whose length can be exponential to the number of variables, then a time complexity exponential to the number of variables would not necessarily imply a time complexity exponential to the length of the CNF.

Thus, a related question is, are these SAT solvers run on 3CNF or CNF while measuring time complexity?

For 3SAT, the number of variables is polynomially related to the number of clauses. (See the end for the justification.)

Consequently, any algorithm for 3SAT whose running time is polynomial in the number of clauses would also be polynomial in the number of variables; and any algorithm for 3SAT whose running time is polynomial in the number of variables would also be polynomial in the number of clauses.

It is known that there is a polynomial-time algorithm for 3SAT, if and only if there is a polynomial-time algorithm for SAT, if and only if there is a polynomial-time algorithm for CircuitSAT (e.g., for formulas).  Also, despite decades of work on SAT solvers, no one knows any algorithm for 3SAT that runs in polynomial time (or indeed in less than exponential time in the worst case).  You could take this as evidence that there is no polynomial-time algorithm for 3SAT; which implies that there is no polynomial-time algorithm for SAT or CircuitSAT, either, and also implies that P != NP.

Justification: Let $n$ denote the number of variables and $m$ the number of clauses.  We have $n \le 3m$ (a variable that doesn't appear in any clause can be ignored) and $m \le 8n^3$ (each clause has three literals, and you can ignore repeated clauses).  It follows that $n/3 \le m \le 8n^3$ and $\sqrt[3]{m/8} \le n \le 3m$, i.e., each is polynomially related to the other.

I see that you revised your question.  That clarifies that I think you have a misconception.  You talk about "run[ning] [a SAT solver] on arbitrary Boolean formulas".  However, you can't run a SAT solver on an arbitrary Boolean formula.  SAT solvers only work on CNF formulas.

However, we do know that any Boolean formula can be converted to an equisatisfiable CNF formula of size at most polynomial in the size of the formula, and vice versa.  If you had an algorithm that could test satisfiability of arbitrary Boolean formulas in time polynomial in the size of the formula, then it would follow that you have an algorithm that could test satisfiability of 3CNF formulas in time polynomial in the size of the formula (every 3CNF formula is a Boolean formula), and thus an algorithm that could test satisfiability of 3CNF formulas in time polynomial in the number of variables -- which contradicts the available evidence.  So, if you believe that there is no algorithm to solve 3SAT in time polynomial in the number of variables, then you should also believe that there is no algorithm to test satisfiability of arbitrary Boolean formulas in time polynomial in the size of the formula.


Flipping accept states DFA vs. NFA I realized that if a language L is recognized by a DFA, then flipping its accept and reject states (aka switching all the accept to reject states and all the reject states to accept) works to recognize the complement of L (which wold be L^c).

I was curious if that worked also with NFAs (flipping the accept and reject states to go from L to L complement), but with their additional paths it doesn't seem like it would work..Definitely seems like it would have too many accept states that aren't correct.

Is this correct? Is there more to it?
Thank you!

Same thing does not hold for an NFA. Example

q0 -> 0 -> q1
q0 -> 0 -> q2

q0 is the start state, q1 is the final state.


Algorithm favours CPU bound or I/O bound processes Some scheduling algorithms favour CPU bound processes while others favour I/O bound processes.
Which algorithm favours which type of process?
My answers:

SJF favours I/O bound processes.Explanation: Short CPU burst processes(I/O bound processes) are given higher priority.
SRTF favours I/O bound processes.Explanation: Same as SJF
Round Robin?  Not able to decide categorically
LRTF favours CPU bound processes.Explanation: Large CPU burst processes(CPU bound) are given higher priority.
HRRN?  Not able to decide categorically
Multilevel feedback Queue favours I/O bound processes.Explanation: Short CPU burst processes(I/O bound processes) are given higher priority. While processes that have large CPU bursts(CPU bound) will slowly have decrement in priority. A process in lower priority queue can only execute when higher priority queues are empty. A process running in a lower priority queue is interrupted by a process arriving in a higher priority queue.
Multilevel Queue favours I/O bound processes.Explanation: Similar to multilevel feedback.
Priority Scheduling?  Not able to decide categorically
FCFS?  Not able to decide categorically

 Please verify above answers and explanations.
Correct me if I'm wrong somewhere and provide answers with explanation for the omitted ones.

First of all, let me clarify that the CPU Burst Time of a process has no relation with being a CPU or I/O bound process. A CPU bound process is one that spends most of its execution time at CPU and an I/O bound process is one that spends most of its execution time at an I/O device. Therefore, a process having small CPU burst time can also be a CPU bound process. Similarly, a process having very large CPU burst time can still be I/O bound.
For example, consider a process A having CPU burst time of 1ms and I/O burst time of 5 ms. It is clearly an I/O bound process. And a process B having CPU burst time of 10ms and I/O burst time of 5 ms is clearly a CPU bound process. But if we consider SJF or SRTF algorithms, they will definitely prefer the process A over B inspite of A being I/O bound and B being CPU bound because A has lower CPU burst time than that of B. Thus, it is incorrect to think that SJF favours I/O bound processes.
But, as I/O bound processes spend more time doing I/O than CPU, they will be sent to the waiting state more often.
(It has nothing to do with CPU scheduling as CPU scheduling is handled by Short Term Scheduler and waiting state is handle by Medium Term Scheduler). Once a process in waiting finishes its I/O, it now depends on the CPU Scheduler. Now, if any preemptive algorithm is being used, there are chances that this process will get execution (depending on the criteria). But if any non-preemptive algorithm is being used, this process won't get execution until currently executing process is finished. So, we can say that non-preemptive algorithms (kind of) favour CPU bound processes (as they spend more time at the CPU, so they have to face lower chances of waiting).


Showing that Bayes classifier is optimal Consider domain $X$, label set $ Y=\{0,1\}$ and the zero-one loss.

Given any probability distribution D over $ X\times \{0,1\} $, we've defined the Bayes classifier $ f_D $ to be-

$$ f_{D}(x)=
\begin{cases}
1 & \text{if }\mathbb{P}[y=1|x]\geq\tfrac{1}{2}\\
0 & \text{otherwise.}
\end{cases} $$

I wish to prove that, for any classifer $ g\colon X\rightarrow\{0,1\}$,
$ L_D(f_D)\leq L_D(g)$, which means that $ f_D$ is optimal.

$L_D(h) $ is defined to be the "true error" of the classifier $h$. That is,  $L_D(h)=D\{(x,y)\mid h(x)\not = y\}$.

I'm having some hard time proving this given the definitions above, and some hints/intuition will be appreciated.

The true error of a classifier $h$ is
$$
\begin{align*}
L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &=
\sideset{\mathbb{E}}{}{}_{x,y \sim D}
\begin{cases}
\Pr[y \neq 0|x] & \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] & \text{if } h(x) = 1.
\end{cases}
\end{align*}
$$
(All probabilities are with respect to $D$.)

The optimal classifier is thus the one that minimizes the loss function
$$
\phi(x) = \begin{cases}
\Pr[y \neq 0|x] & \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] & \text{if } h(x) = 1
\end{cases}
$$
for all $x$. We can rewrite the loss function as
$$
\phi(x) = \begin{cases}
\Pr[y = 1|x] & \text{if } h(x) = 0, \\
1-\Pr[y = 1|x] & \text{if } h(x) = 1
\end{cases}
$$
So if $\Pr[y=1|x] < 1-\Pr[y=1|x]$ we should choose $h(x) = 0$, and if $\Pr[y=1|x] > 1-\Pr[y=1|x]$ we should choose $h(x) = 1$; if $\Pr[y=1|x] = 1-\Pr[y=1|x]$ then the choice doesn't matter.

Finally, $\Pr[y=1|x] < 1-\Pr[y=1|x]$ is the same as $\Pr[y=1|x] < 1/2$, and this explains the formula for $f_D(x)$.


Best way to merge 2 max heaps into a min heap Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this?

The easiest way is to consider 2 max heaps an array with $2n$ elements and build a min heap with $O(n)$ complexity. Is there an algorithm with a complexity better than $O(n)$ ?

I guess you're thinking that there may be a faster way because if you want to merge two min heaps into a third min heap, is can be done in $O(\log n)$ by creating a $-\infty$ node in $O(1)$, making the roots of both heaps be children of that new node in $O(1)$, and extracting the min of the heap in $O(\log n)$.

But in your case, it can't be done. Clearly, building a min heap is harder than finding the minimum. But the minimum could be any of the leaves of the max heaps, so you have $O(n)$ elements of which you want to find the minimum. Clearly, you have to at least read all those elements and so you take at least $O(n)$ time. So it's $\Theta(n)$.

(Note that when merging two min heaps into a min heap, the minimum has to be one of the two roots, so it can be found in $O(1)$. But in the second case, there are too many nodes that could potentially be (i.e. are for some values of the heap) the minimum)


MST with degree constraints on some node While preparing for an algorithms exam I came across the following problem in a practice test:

Let $G = (V,E)$ be a connected, undirected graph with weighted edges (all weights are rational numbers but not necessarily all unique) and let $v$ be some node in $G$.

Design an algorithm that finds a minimum spanning tree of $G$ where $\deg(v)=2$ if one exists or indicates if there is no such tree.

Full credit will be given for solutions with the same time complexity as Prim's algorithm ($O(|E| + |V|\log |V|)$). Partial credit will be given for solutions whose time complexity is $|V|\cdot$Prim, and minimal credit will be given for solutions with greater time complexity.

The first step in any solution must be to use Prim or Kruskal's algorithm to find the target weight for such an MST. From there, though, I've tried a number of different methods of approaching this problem but all the successful ones require halting an existing MST algorithm before it's done, i.e. prioritizing all $v$'s edges, running Kruskal until $v$''s degree is two, then deprioritizing them and continuing the algorithm, etc.

The problem is that my professor flat-out refuses to accept answers that involve stopping an algorithm in the middle, insisting that this would require one to re-prove the correctness of the entire algorithm.

Does anyone have a solution? The problem has been eating at me for a few weeks now and I haven't been able to find an answer on the internet anywhere. The professor said she won't tell us the answer and I suspect she intends to put this question on this or future exams.

Thanks very much in advance for your time.

Here's an algorithm that just reduces to MST; no need to modify Prim's or some other algorithm. The idea is simple: remove $v$, compute the MSTs of the resulting components of the graph, and then stitch them together with $v$. The interesting case is when removing $v$ doesn't disconnect the graph.

I'll assume the input graph $G$ is connected, although it would not be difficult to generalize this idea to computing a minimum spanning forest. Also, obviously the degree of $v$ needs to be at least 2.

Algorithm

Start by removing $v$ and all incident edges; call this $G'$. Now compute the number of connected components in $G'$. This can be done with DFS or something similar.

More than 2 components:
If $G'$ has more than 2 connected components, no solution is possible.

Exactly 2 components: If $G'$ has exactly two connected components, then we can construct a solution by using $v$ as the "bridge" between the two components: just connect the MSTs of the components with the cheapest edges through $v$.

Exactly 1 component: If $G'$ has exactly one component, we can compute $T' = \text{MST}(G')$, and then we just need to stitch $v$ into $T'$ using two edges.

Find the cheapest edge incident on $v$ and add this to $T'$. Call this $T''$. Now we have a spanning tree, but not necessarily minimum.
Iterate over all other edges incident on $v$. For each of these, we will try to construct a MST where $d(v) = 2$. If we don't find one, then no solution is possible.

Consider some incident edge $(u,v)$ which is not the lightest edge on $v$.
Observe that if we added this edge to $T''$, it would create a cycle.
If $(u,v)$ is the heaviest edge on this cycle, then skip this edge, because no solution is possible using $(u,v)$.
Otherwise, we can take out the heaviest cycle edge and add $(u,v)$ instead. Now we have a spanning tree where $d(v) = 2$. If this spanning tree is minimum, we're done. (We can determine if a spanning tree is minimum just by computing any $\text{MST}(G)$ and comparing weights. This "reference" MST only needs to be computed once.)

It's not immediately obvious that this is within cost bounds, because for each of $O(|V|)$ edges incident on $v$, we have to compute the heaviest edge in the tree on the path between $v$ and some other vertex $u$. However, these "path queries" are well studied in the literature, and can be computed in $O(\log|V|)$ by preprocessing $T''$ into a balanced lookup structure. Some examples include binary lifting, Miller-Reif rake/compress tree contraction, and Sleator-Tarjan link/cut trees. The link/cut trees are actually far more general: they handle dynamic trees too! But here we only need to preprocess a static tree, i.e. $T''$.

Edit: My original idea was to do the following, which doesn't work (thank you @VladislavBezhentsev for pointing this out in the comments!). It doesn't work because, while we know that the cheaper of $e_1$ and $e_2$ is certainly in the MST (by the cut property), it's not necessarily true that the heavier of the two edges is!

  (Incorrect idea): Find the two cheapest edges $e_1$ and $e_2$ that are incident on $v$. Add $e_1$ and $e_2$ to $T'$: this creates a cycle. If the largest edge on this cycle is either $e_1$ or $e_2$, no solution is possible. Otherwise, remove the largest edge on the cycle.


Sort a list of points to form a non-self-intersecting polygon Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \rightarrow p_1 \rightarrow \ldots \rightarrow p_{n-1} \rightarrow p_n \rightarrow p_0$ would form a non-self-intersecting polygon?

Thanks to the advice of Rick Decker, I was able to create an algorithm based on the first half of the Grahm Scan convex hull algorithm, as detailed here.

The first step of the Grahm Scan is to sort the points in a set based on the angle  made with the X axis when drawing a line through the point and the lower-right point of the set. This seems to solve the problem for all point sets that I can think of, with a single addition...

If two or more points form the same angle with the X axis (i.e. are aligned with respect to the reference point) then those points should be sorted based on distance from the reference point.

Here is an implementation of the algorithm in JavaScript:

function sortPoints(points) {
    points = points.splice(0);
    var p0 = {};
    p0.y = Math.min.apply(null, points.map(p=>p.y));
    p0.x = Math.max.apply(null, points.filter(p=>p.y == p0.y).map(p=>p.x));
    points.sort((a,b)=>angleCompare(p0, a, b));
    return points;
};

function angleCompare(p0, a, b) {
    var left = isLeft(p0, a, b);
    if (left == 0) return distCompare(p0, a, b);
    return left;
}

function isLeft(p0, a, b) {
    return (a.x-p0.x)*(b.y-p0.y) - (b.x-p0.x)*(a.y-p0.y);
}

function distCompare(p0, a, b) {
    var distA = (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y);
    var distB = (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
    return distA - distB;
}


Where have I gone wrong in "proving" this big-O identity? (From CLRS -- 3-4,d)

Let $f(n)$ and $g(n)$ be asymptotically positive functions.

I tried to prove that $$f(n) = O(g(n)) \implies 2^{f(n)} = O\left(2^{g(n)}\right) .$$

I know that the above statement is false, so where have I gone wrong in my proof?:

  Suppose $f(n) = O(g(n)).$ Then there exist positive real numbers $c, n_0$ such that for all $n \geq n_0:$
  $$0 \leq f(n) \leq c g(n).$$ Raising all sides to the power of 2, we have:
  $$0 \leq 2^{f(n)} \leq 2^{cg(n)}$$ (we can do this because $2^n$ is an increasing function).

  From this, we can say that $$0 \leq 2^{f(n)} \leq \underbrace{2^c}_{\text{arbitrary constant}}\cdot 2^{g(n)}$$ so if $d = 2^c$, we can say that $2^{f(n)} = O(2^{g(n)})$.

(I now know that $f(n) = 2n, \ \ g(n) = n$ is an easy counterexample, but I'm still struggling to find the flaw in my "proof").

You should be able to work out the answer yourself.  Here's the general procedure:

Since you know of a counterexample to the original claim, plug those $f,g$ into each step of your proof and find the first step in your proof where the proof goes wrong.  In other words, find the first claim made in the proof that isn't correct for that choice of $f,g$.  That will help you pinpoint the step in your proof that is flawed, i.e., that makes a conclusion that doesn't follow logically from the previous steps.


How to perform local search on simple paths? I have a local search problem.
The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph.

The question is: given a current solution (an $S$-$T$-path), how can I generate a set of neighbour solutions?

To elaborate, I have an optimization (minimization) problem, on which I have to select the "best" path $S$-$T$ path. The evaluation function is complex and can't be evaluated until all the edges in the path are known. This plus the fact that the number of paths is exponential, lead me to draw on local search.

I know how to find an initial solution in polynomial time. The only piece missing in order to be able to use a local search algorithm (i.e. hill climbing) is to be able to generate a set of successors from the current path. I find this not to be trivial because simply switching one random node in the path for one not in it does not necessarily generate a still valid $S$-$T$ path.

Edit: I did not want to enter in the details of my specific problem because I think the question about how to define a relationship of neighbourhood in the space of path graphs is interesting in itself. But since you have asked, this is the evaluation function:
$$\mbox{length}(\mbox{path}) \times \sum_{i=1}^n \left ( p_i \times -\mbox{log}_2(p_i) \right )$$, where $p_i$ is the relative frequency of nodes in the path tagged with the number $i$ (every node in the graph is tagged with a number $1..n$.

I can't comment yet, so I'll post this as an answer:

Assuming you can find the S-T path with a pathfinding algorithm, why not use the same algorithm with an "antiheuristic" topology?

As you increase the "heat," the further away your found paths will be from your initial solution.

Additionally, you could add some grainy noise wavelets, or random hills and valleys, into the landscape to toss things up a little.

But still:

  The evaluation function is complex and can't be evaluated until all the edges in the path are known

This is always the case. It is usually better to try and find a proper heuristic/path abstraction than monte-carloing it. I recommend you post more info about your problem.


Complexity and hardness of undirected path Let $PATH = \{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$ on undirected graphs is and whether any hardness results for $PATH$ on undirected graphs are known?

The undirected version of PATH, usually known as USTCON, is in L due to Reingold's theorem.

USTCON is trivially complete for L with respect to logspace reductions. I don't know if it is L-complete with respect to weaker reductions such as $\mathsf{AC}^0$ reductions; see this question.


Markov Inequality in graph theory Fix an optimal solution G∗ to k-Cycle-Free Subgraph. Partition the vertex set V of G randomly into two subsets, A and B, each of size n/2, and remove edges internal to A or B. In expectation, the fraction of edges in G∗ that remain after this process is 1/2. With probability at least 2/3 the fraction of edges in G∗ that remain is at least 1/4; here we apply the Markov inequality on the fraction of edges inside A and B.

I know Markov inequality in context of probability theory I don't know what it means here.

APPROXIMATING SUBGRAPHS WITHOUT SHORT CYCLES

Let $X$ denote the fraction of remaining edges. We know that $0 \leq X \leq 1$ and $\mathbb{E}[X] = 1/2$. Let us define $Y = 1 - X$, which is the fraction of edges inside $A$ and $B$. This is a non-negative random variable whose expectation is $\mathbb{E}[Y] = 1/2$. According to Markov's inequality,
$$
\Pr[X < 1/4] = \Pr[Y > 3/4] = \Pr[Y > \tfrac{3}{2} \mathbb{E}[Y]] < \frac{2}{3}.
$$
Therefore $\Pr[X \geq 1/4] > 1/3$.

Let us show that the similar inequality $\Pr[X > 1/4] \geq 1/3$ is tight, that is, there exists a random variable satisfying $0 \leq X \leq 1$, $\mathbb{E}[X] = 1/2$, and $\Pr[X > 1/4] = 1/3$. Indeed, take $\Pr[X = 1/4] = 2/3$ and $\Pr[X = 1] = 1/3$, and notice that
$$
\mathbb{E}[X] = \frac{2}{3} \cdot \frac{1}{4} + \frac{1}{3} \cdot 1 = \frac{1}{6} + \frac{1}{3} = \frac{1}{2}.
$$
In a similar way, one can show that $\Pr[X \geq 1/4]$ can be arbitrarily close to $1/3$.


show that this decidable set $C$ exists I came across this problem which says that given disjoint sets $A$ and $B$ s.t $\bar{A}$ and $\bar{B}$ are both computably enumerable (c.e.), there exists a decidable set $C$ s.t. $A \subseteq C$ and $C \cap B = \emptyset$.

I think one way to construct $C$ is to show that $\bar{A}-\bar{B}$ is c.e., but is the set difference $\bar{A}-\bar{B}$ for this particular case c.e.?

No, it is not necessarily recursively enumerable.  There are languages that are recursively enumerable but not recursive.  Thus, their complement is not recursively enumerable.  From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).


Decidable languages kleene star closure - question on a proof I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the original decider of the language to approve the partition of each branch.

My question is, I can't understand how we can do this non-deterministic split on a word whose length we do not yet know. if the word is very big then there exist more partitions, thus more branches are needed.

So, i don't understand how this "non-deterministic split" can be materialized.

Also, if someone has another proof of this closure via turing machines it will be more than welcome!

It can be hard to grasp why we can just reason about an NTM to prove the Kleene star closure for decidable languages. The important fact is that any nondeterministic TM can be simulated by a deterministic TM. In some cases, it will just take a whole lot of time. When the topic is decidable languages, we are only concerned with whether something can be decided or not, regardless of how much time it will take to figure out. Therefore, an NTM will sometimes be more convenient to reason about, as we can abstract the "try all possible ways to do this", into "guess the right way to do this". However, the abstraction is only valid if we have a finite number of possibilities to try, of course.

So, for the Kleene star closure:

Assume that we have a decidable language $A$. Given that $A$ is decidable, there exists a decider for $A$, let us call it $M_A$. From this $M_A$, we can now construct a decider of $A^\ast$, let us call that decider $M_{A^\ast}$.

This is a description of how $M_{A^\ast}$ works:

On input $w$:

If $w = \varepsilon$ (the empty string), accept

For all possible splits of $w$ into $w_1,w_2,...,w_k$: if $M_A$ accepts all the strings $w_1, w_2, ..., w_k$, then accept

If all splits have been tried without success, reject.

Lets look at an example where $A = \{w \in \{a,b,c\}^\ast \; | \; w \; \text{starts with} \; ab \; \text{or ends with} \; c\}$

For instance, we have that $\{c, ab, ac, bc, cc, aac\} \subset A$, but $\{a, b, aa, ba, bb, ca\} \cap A = \emptyset$.

Now, let us look at how $M_{A^\ast}$ will determine whether or not the string $ccab$ is in $A^\ast$:

First, $M_{A^\ast}$ checks the trivial case. Since $w \neq \varepsilon$, it cannot accept right away. It now has to try all the 8 possible splits of $ccab$ listed here:

$S_1 = \{ccab\}$

$S_2 = \{cca, b\}$

$S_3 = \{cc, ab\}$

$S_4 = \{c, cab\}$

$S_5 = \{cc, a, b\}$

$S_6 = \{c, c, ab\}$

$S_7 = \{c, cab\}$

$S_8 = \{c, c, a, b\}$

You could argue that split $1$ is not a real split, but since it complies with our definition of a split, $M_A'$ has to check whether $A$ accepts all $w' \in S_1$, which is only $ccab$. $M_A$ rejects $ccab$ because it does not start with $ab$ or end with $c$.
In $S_2$, $cca$ is rejected by $M_A$, and hence $M_A'$ does not have to check $b$ and proceeds to split $S_3$.
In $S_3$, both strings are accepted by $M_A$. $cc$ is accepted because it ends with $c$, and $ab$ is accepted because it starts with $ab$. The machine $M_A'$ now accepts, and hence $ccab \in A^\ast$, simply because $cc \in A$ and $ab \in A$.


Verifying if a greedy solution is optimal for a specific instance (Set cover) Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution.

Is there an efficient way of verifying if, for that particular instance, the given solution is optimal?

Let me formalize your problem, in two different ways:

GREEDY-SET-COVER: Given a Set Cover instance, does the greedy algorithm always produce a set cover of minimal size?
GREEDY-SET-COVER2: Given a Set Cover instance, does the greedy algorithm always produce a set cover of non-minimal size?

The two problems might seem complementary, but in fact it is not the case: if at some step of the algorithm there are several sets covering the same number of uncovered elements, the greedy algorithm must make a choice. In GREEDY-SET-COVER, we are asking whether all such choices lead to an optimal solution. The complement of GREEDY-SET-COVER2 asks whether some such choice leads to an optimal solution.
I will show that GREEDY-SET-COVER is $\mathsf{coNP}$-complete, and that GREEDY-SET-COVER2 is $\mathsf{NP}$-hard (but not necessarily in $\mathsf{NP}$). In fact, the same reduction will work for both.
Let me start by showing that GREEDY-SET-COVER is in $\mathsf{coNP}$. Given an instance of GREEDY-SET-COVER, all we need to do in order to show that it is a No instance is to give a transcript of the greedy algorithm together with a set cover which is smaller than what the greedy algorithm output. Unfortunately the same kind of witness doesn't work for GREEDY-SET-COVER2, since we would have to list all possible runs of the greedy algorithm.
In order to show that GREEDY-SET-COVER is $\mathsf{coNP}$-hard, we reduce from SAT. Let $\varphi$ be an instance of SAT with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. We first check whether there is an assignment to some variable which satisfies at least $m-1$ clauses. If it satisfies all clauses, the instance is satisfiable. Otherwise, the instance is satisfiable unless the remaining clause consists of this variable with opposite polarity. In both cases, we output an appropriate fixed instance of GREEDY-SET-COVER.
Suppose now that every assignment to a variable satisfies at most $m-2$ clauses. We will construct a Set Cover instance over the universe $\{x_1,\ldots,x_n,C_1,\ldots,C_m\}$ having the following sets:

For each variable $x_i$ and each truth value $\tau$, there is a set $X_{i,\tau}$ which contains all clauses satisfied by this assignment to $\tau$, as well as the element $x_i$.
The set $Y = \{C_1,\ldots,C_m\}$.

If the SAT instance is satisfiable, there is a set cover of size $n$, consisting of the sets $X_{1,\tau(1)},\ldots,X_{n,\tau(n)}$, where $\tau$ is a satisfying assignment. Otherwise, the optimal set covers have size $n+1$. The greedy algorithm first takes the set $Y$ (since all other sets contain at most $(m-2)+1 = m-1$ elements), and then takes one set each from every pair $X_{i,T},X_{i,F}$, in total producing a set cover of size $n+1$. This set cover has minimal size if and only if the SAT instance is unsatisfiable.
The exact same reduction works for GREEDY-SET-COVER2, since every run of the greedy algorithm must start with the set $Y$, and eventually produces a set cover of size $n+1$.


Recursive factorial algorithm I'm struggling to understand this factorial algorithm.

Falling(n, m):
    if m = 0
        return 1
    if m = 1
        return n
    return Falling(n, floor(m/2))*
           Falling(n - floor(m/2), ceil(m/2))

The algorithm should compute $n!/(n-m)!$

I'm analyzing it in the case of n = m, i.e it returns n! Now I'm getting the correct results from my implementation of it in Java, but the correctness of it has shaking my head.

How should I approach this?

If you plug in the result in what is returned by the recursion, you get:
$$\frac{n!}{(n - \lfloor \frac{m}{2} \rfloor)!}
\frac{(n - \lfloor \frac{m}{2} \rfloor)!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!}
= \frac{n!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!}$$

You can see the right side is equal to $\frac{n!}{(n - m)!}$ because of the identity $m = \lfloor \frac{m}{2} \rfloor + \lceil \frac{m}{2} \rceil$ (if you are in doubt about this: check the cases $m$ even and $m$ odd separately).

For correctness, the only thing left to check then is the base cases $m=0$ and $m=1$ are correct (which is a trivial observation), that Falling is not invoked with incorrect parameters (this is the case if $m \le n$ holds) and that it terminates (also the case because the invoked instances have strictly smaller parameters).


Repeated String Match: need help to understand the maximum number of repeats needed to be looked at There's this question on LeetCode (link):

  Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution exists, return -1.

  For example, with A = "abcd" and B = "cdabcdab".

  Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

  Note:
  The length of A and B will be between 1 and 10000.

The brute force solution provided on the website is this:

  The question can be summarized as "What is the smallest k for which B
  is a substring of A * k?" We can simply try every k.

  Algorithm

  Imagine we wrote S = A+A+A+.... If B is to be a substring of S, we
  only need to check whether some S[0:], S[1:], ..., S[len(A) - 1:]
  starts with B, as S is long enough to contain B, and S has period at
  most len(A).

  Now, suppose q is the least number for which len(B) <= len(A * q). We
  only need to check whether B is a substring of A * q or A * (q+1). If
  we try k < q, then B has larger length than A * q and therefore can't
  be a substring. When k = q+1, A * k is already big enough to try all
  positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.

I understand this part:

  If we try k < q, then B has larger length than A * q and therefore can't
  be a substring.

But I don't follow how the writer has arrived at this other conclusion:

  When k = q+1, A * k is already big enough to try all
  positions for B; namely, A[i:i+len(B)] == B for i = 0, 1, ..., len(A) - 1.

Why can we stop at k = q+1? Why is it not necessary to try q+2 (and q+3, etc.)?

Here is a proof by example. We want to check whether $B$ is a substring of some power of $A$. Instead, let us check whether $B$ is a substring of $A^\omega$, that is, $A$ repeated infinitely many times. It suffices to test the following starting positions (why?):

abcdabcdabcdabcd...
cdabcdab

abcdabcdabcdabcd...
 cdabcdab

abcdabcdabcdabcd...
  cdabcdab

abcdabcdabcdabcd...
   cdabcdab

In order to perform these checks, we don't need to consider $A^\omega$; it suffices to consider the smallest power of $A$ which covers the very last case. This power is $q+1$ (or possibly just $q$).


Programmatically checking equivalence of statements So as part of a theorem-prover/checker, I'm using Prolog to try to determine the equivalence of statements that have been parsed into tree form, e.g. $x=2$ is represented as eq(x,2), or $x=2 \land y\leq z$ if and(eq(x,2),leq(y,z)), and I want to determine if these statements are equal.

The way I'm currently (attempting) to do this is by trying to convert statements to some normal form, e.g. converting all greater-than statements to less-than statements, or eq(x,x) simplifies to true, and then statements would be compared syntactically to determine equivalence. However, this feels like it might be a tad tricky/complicated, and to some extent I'm a bit uncomfortable simply using syntax rather than semantics to determine whether they are the same.

Is there some standard way of solving determining these equivalences algorithmically, or perhaps can anyone think of a better alternative?

Much appreciated.

So, there are two possibilities, depending on how complex your statements are.

If your statements are relatively simple, then there's a good chance they fit in what is decidable with Satisfiability Modulo Theories. It's basically a way of taking a SAT solver and integrating it with a solver for a specific theory, for example, theory of linear arithmetic. Here is a list of common theories.

If your statements are too complex, then reducing these equations to a normal form becomes undecidable. This is because there are ways to encode logic and computation in arithmetic, so determining the equivalence of some formulas can be equivalent to solving arbitrary logical equations.

The decidability of your problems depends heavily on whether you're using integers or reals, linear or non-linear arithmetic, etc. As was mentioned in the comments, if you can encode arbitrary Diophantine equations, then you're definitely undecidable.

Regardless of decidability, your problem is definitely $NP$-hard. Suppose we could efficiently check if the normal form of problems were syntactically the same. Then we could efficiently solve 3SAT by checking if a boolean formula is equivalent to False.


Average case analysis of linear search Based on CLRS question 2.2:

Consider linear search again. How many elements of the input
sequence need to be checked on the average, assuming that the element being
searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in $\theta$-notation? Justify your answers.

I have a question regarding the average case.

"assuming that the element being
searched for is equally likely to be any element in the array" - what does that exactly mean? Does it mean that the probability for each to happen is $\frac{1}{n}$?

Or could it also be that the element is not in the array at all - is that a case is this probability the same as the rest (and then they are all $\frac{1}{n+1}$)?

Does it matter for the average case how many duplicated are there? Are we assumming that there are no duplicates?

A good explanation about what exactly is the average case would be helpful.

Thanks a lot!!!

The phrase "the element being searched for is equally likely to be any element in the array" is ambiguous. It might mean two different things:

The element is at a uniformly random position in the array.
The element is chosen uniformly at random from the set of elements in the array.

This ambiguity suggests that the authors are making the hidden assumption that all elements are distinct, in which case both meanings coincide. Moreover, without this assumption it is impossible to determine the average-case complexity (consider what happens if all elements in the array are identical).


Unique-neighbor expander I want to solve Problem 4.10 from Randomness by Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225/spring15/PS3.pdf

Consider a bipartite expander $G$ with left degree $D$ so that every subset $S$ of the left vertices with at most $K$ vertices has at least $(1-\epsilon)D|S|$ neighbors. Then $G$ also has the property that it has $(1-2\epsilon)D|S|$ unique neighbors. Unique meaning that it has exactly one corresponding vertex from $S$.

I recognize that the new expansion factor is $(1-2\epsilon)D = 2\cdot(1-\epsilon)D -D$

Let $S$ be a subset of at most $K$ vertices. Let $a_d$ be the number of vertices on the right side which are connected to exactly $d$ vertices in $S$. Since the left degree is $D$,
$$
\sum_{d \geq 1} da_d = D|S|.
$$
Since $S$ has at least $(1-\epsilon)D|S|$ neighbors,
$$
\sum_{d \geq 1} a_d \geq (1-\epsilon)D|S|.
$$
Therefore
$$
\sum_{d \geq 2} a_d \leq \sum_{d \geq 1} (d-1) a_d = \sum_{d \geq 1} da_d - \sum_{d \geq 1} a_d \leq D|S| - (1-\epsilon)D|S| = \epsilon D|S|.
$$
It follows that
$$
a_1 = \sum_{d \geq 1} a_d - \sum_{d \geq 2} a_d \geq (1-\epsilon)D|S| - \epsilon D|S| = (1-2\epsilon)D|S|.
$$


Suppose G is simple graph with n vertices. Prove that G has twice as many edges as vertices only if $n\geq 5$ I just didn't understand the second part of the prove

"G has twice as many edges as vertices only "... what do I actually have to prove ?

I understand it like $n=2e$ , is it right ?

then isn't it's just similar to the degree equation ??

When $n \leq 4$, the possible number of edges is less than twice the number of vertices. For example, when $n = 4$, there are 4 vertices but only 6 edges. In contrast, the complete graph on 5 vertices contains 10 edges.


Color a graph using k colors, k>4, with the most equal distribution of colors Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors.

Let $k > 4$. Is there an algorithm to color the nodes with $k$ colors, so that the colors are distributed the most equally possible?

In other words:

Let's call $c_1, ..., c_k$ the colors. We define
$\forall c_k\in[1,k], f(c_k)=\textrm{number of nodes of color}c_k$. Obviously, $\sum f(c_k) = N$. Find an algorithm to color the $N$ node with the $k$ colors to maximize the value $\min f$, with 2 adjacent nodes having different colors.

You are perhaps looking for an equitable coloring, which is a proper coloring where the size of any two color classes differ by at most one. Finding an equitable 3-coloring is NP-complete for planar graphs.


Why doesn't decision tree work in case find minimum When we would like to prove lower bound comparison algorirthm, we often use decision tree, for example sorting by comparisons.
So let's consider find minimum in array $a[1..n]$  by comparison.  Lower bound for that problem is commonly known - $n-1$ comparisons.

However, how to use decison tree in order to prove lower bound ?
It seems that it might be (analogously to sorting problem):
$n$ - number of possible results (similiar to $n!$ in sorting).
So the number of comparison (minimal height of tree) is $\log_2(n) < n - 1$.

Believe me, I have tried to understand it, but I can't.

There is more than one technique to prove a lower bound on the depth of decision trees. One technique you have seen is bounding the depth of a decision tree by the logarithm of the number of its leaves. As you comment, this technique doesn't give the correct lower bound for the case of computing the minimum. However, we can lower bound the depth of a decision tree computing minimum directly.

Take any reachable leaf $\ell$ in a decision tree for minimum, and consider the entire path $p$ leading to it. Construct a graph whose vertices are the input elements $x_1,\ldots,x_n$, two elements $(x_i,x_j)$ being connected if they are compared in $p$. I claim that this graph must be connected, and I show this below. A connected graph on $n$ vertices must have at least $n-1$ edges, and this shows that the leaf must have depth at least $n-1$. In particular, the depth of the decision tree is at least $n-1$.

Now to the proof of the claim. Suppose that the graph contains more than one connected component, say it contains the components $C_1,\ldots,C_m$. Since the leaf $\ell$ is reachable, there is a linear ordering compatible with the results of the comparisons in each connected component $C_i$. We can put together these linear orderings into a linear ordering of all elements in $m!$ different ways. In particular, we can have $C_1 > C_2 > \cdots > C_m$, and we can have $C_1 < C_2 < \cdots < C_m$. This means that it is consistent with the comparisons in $p$ that the minimum is in $C_m$, and it is also consistent that the minimum is in $C_1$. Hence whatever the tree outputs at $\ell$ will be wrong in at least one linear ordering consistent with the comparisons in $p$, showing that the tree doesn't compute the minimum.


Finding one face in planar graph Given a planar graph (represented using adjacency lists) we want to find a set of vertices which are around one (random) face. We know that the graph contains at least one triangle.

How do we find such a face?

It depends. If you have a planar embedding, and you want to find faces on it, just pick an edge, and keep walking on the face that's on the 'left' side of the edge when looked at in the direction you were walking. If you want to find a cycle of nodes for which there exists a planar embedding in which those cycles are a face, that's even easier, because in planar graphs, every cycle is a face in some embedding.

Here's a simple algorithm for finding a cycle, but you can think of your own one. Suppose you have a graph that you know is planar, and you want to find a face. Start at some vertex $v$ and perform a breadth-first search. In iteration $k$, you find the vertices at distance $k$ from $v$ and for each vertex at distance $k$ that you add, you count how many nodes at distance $k-1$ were connected to that node. If there is just one, then continue. Otherwise, if two nodes at distance $k-1$ are connected to a node $w$ at distance $k$, then you have found a cycle in the graph (it is possible that you count three or more, in that case, select two). Node $w$ lies on a face in the graph, in some planar embedding of the graph. It may lie on the same face as $v$, but not necessarily, for example, you can have a cycle with a tail, and you accidentally started in the tail.

To find a face, backtrack from $w$ within the nodes that you explored so far with your breadth-first search: first, two nodes $x_1, x_2$ at distance $k-1$ (like I described above). Then, in each iteration, for $x_1$, find the node $x_1'$ which is connected to $x_1$ and is at distance $k-2$ from $v$ (why is there guaranteed to be only one? Because we identified $w$ as most nearby node with two paths leading to it from $v$), and repeat this until at some distance $d$ you find that your $x_1$ ancestor and your $x_2$ ancestor are the same node $y$.

You now have a face! That is, a cycle for which there is some planar embedding. The face has $w$ on one side, $y$ on the other side, and they are connected with two paths. One path is the series of $x_1$ nodes that you just found, and the other is the series of $x_2$ nodes. If you found $y=v$, then $v$ is on the face. You are not guaranteed to find a face with $v$ on it, but are other algorithms that find one if there is one. I can modify this algorithm to do that, and I'm sure you can too.


Given a bitonic sequence $a_1, a_2, \ldots, a_n$ , calculate the median in $O(\log n)$ This is a question in my textbook, it requires me to write an algorithm to find the median of a bitonic sequence in $O(\log n)$, where $n$ is the number of elements (a bitonic sequence is a sequence that is non-increasing first, and then it's non-decreasing after some point). How do I approach this? I feel like it has something to do with the medians of the 2 parts (the non-increasing and non-decreasing parts of the sequence), but I couldn't find a way to solve it from there.
Any help would be much appreciated. Thank you.

First you use an algorithm to find the bitonic point, that is the point where the sequence swaps from being non-increasing to non-decreasing. This is possible with this algorithm in $O(\log(n))$. Now you split the sequence apart at this point (virtually, you don't really make any copies since that would cost $O(n)$). You can now use this algorithm to find the median of two sorted sequences in $O(\log(\min(u,v)))$. $u+v = n$ in our case since we split the original sequence.
Beware that you need to adjust the given algorithms since the first one uses the opposite definition of bitonic (first increasing the decreasing) and the second one assumes that both arrays are sorted in the same direction (in our case one is in reverse).


How to evaluate all derivatives of a polynomial at a point with FFT? I found this problem:

  Evaluating all derivatives of a polynomial at a point

  Given a polynomial A(x) of degree-bound n, its tth derivative is
  defined by

  From the coefficient representation $(a_0, a_1, . . . , a_{n-1})$ of A(x) and
  a given point $x_0$, we wish to determine A(t) ($x_0$) for t = 0, 1, . . . ,
  n - 1.

I know the vector of the coefficients has to be used and I also know that the derivative of a term $ax^n$ is $a*n*x^{n-1}$, but where do I go from there?

I can only think of the naïve scheme to evaluate this: Find the first derivative ($O(n)$), evaluate it using Horner's method ($O(n)$). Repeat this for all deterivaties, giving $(O(n^2)$).

Hint: Taking the derivative has a certain, simple diagonal effect on the Fourier transform, that hopefully was covered in class. Hence if you compute the Fourier transform of the original function, you "know" the Fourier transform of all its derivatives as well. Given the Fourier transform, there is a formula for the value of the actual function. In your case, in order to compute the value of all derivatives of the function at a point, you multiply some matrix by the vector of Fourier coefficients. This matrix looks suspiciously similar to the DFT matrix, so hopefully you can compute the matrix-vector product in time $O(n\log n)$.


Building ideal skip lists I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list.

The definition of an “ideal skip list” is that in the first level we'll have all the elements, half of them in the next level, a quarter of them in the level after that, and so on.

I'm thinking about a $\mathcal{O}(n)$ run-time algorithm involving throwing a coin for each node in the original linked-list, to determine for any given node whether it should be placed in a higher or lower level, and create a duplicate node for the current node at a higher level. This algorithm should work in $\mathcal{O}(n)$; is there any better algorithm?

Following your idea, you can do this:

Iterate through the (sorted) list.
For every item, flip a coin until you get a $0$. The item's level is the number of $1$s you got; create the tower of pointers and link already created towers accordingly.

For every item, the expected level is $\frac{1}{p}$ with $p$ the probability of a $1$ (geometric distribution); therefore, every item causes constant runtime in expectation, resulting in a total expected runtime in $O(n)$ for creating the list. As the maximum level is $\log_{1/p} n$ in expectation and you only need to remember the last (dangling) pointer for every level, the algorithm requires only $O(\log_{1/p} n)$ additional memory in expectation.

Note that the resulting list is not stricly "ideal" but in expectation; the interesting operations have logarithmic expected runtime due to the resulting distribution. See William Pugh's Skip Lists: A Probabilistic Alternative to Balanced Trees (1990) and the work referenced there for details.

It is clear that there can be no algorithm that works in expected time $o(n)$; in expectation, there have to be $\frac{n}{2}$ items on level two so at least that many have to be investigated (in expectation).


Can a deterministic language be accepted by a deterministic Push Down Automaton? I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic language contains a PDA that is deterministic.

The language in question is: $L = \{w \in \{a,b\}^* : n_a(w) = n_b(w)\}$

Sure, a deterministic language can trivially be accepted by a nondeterministic PDA. Simplest way to see it is that a deterministic PDA is just a special case of the non-deterministic one. If that isn't enough, for some transition

$\begin{align}
   \delta(q, a, A) = \{(p, \alpha)\}
\end{align}$

you can add the following, without changing the language accepted
(the modified PDA isn't deterministic, it is enabled to do completely pointless $\epsilon$ moves):

$\begin{align}
   \delta(q, \epsilon, A) = \{(q, A)\}
\end{align}$


In general terms, how could the Thompson Hack be implemented in Microcode? In his lecture Reflections on Trusting Trust, Ken Thompson describes a virus that infects a compiler; the infected compiler installs backdoors into programs, but the key part is that the infected compiler also infects all compilers it compiles.

K. Thompson notes that if this was implemented at the Microcode level, it would be almost impossible to stop.

My question is this; in general terms (i.e. I'm not going to ask for details on how to create the most insidious trojan that has ever existed) how can you write microcode that would inject Thompson's trojan into every program compiled on a computer with that microcode.

As far as I can tell, the core of this question (i.e. the most important part, theoretically speaking) is:

  Can the code implementing machine code (such as microcode) detect when the machine code it is implementing is a compiler that is compiling (in order to inject trojans into the compiled program), and if so, how?

In general, it certainly can not; this follows from Rice's theorem. That is, if you want to restrict the set of functions that are compilers in a meaningful way (one might also say that every function is a compiler).

In practice, you can of course inspect the sources of popular compilers and include heuristics in your malicious code that detect gcc, javac or any other known compiler.


ODEs and Zeno Machines Disclaimer: I know nothing about differential equations, and I don't know if this belongs here...

Wikipedia states that a Zeno machine is a hypothetical machine able to compute infinite
steps in finite time, by making use of supertasks. Building such a machine is physically impossible. My question is this: Is the Zeno machine an example of an differential equation and if so, is my assumption correct that we can utilize a differential equation solver to solve the Zeno machine differential.equation, like in this paper, which shows a different but fundamentally the same concept?

No, they are not the same.

There are different equivalent representations for any problem (e.g. Turing machines, neural networks, differential equations, ...). But changing from one representation to another does not change whether the problem is fundamentally solvable - otherwise they would not constitute equivalent representations.

Zeno machines can be considered as Turing machines plus hypercomputation which, if it were possible, would permit solving certain previously undecidable problems.

Differential equations can be seen as extension of algebraic equations (or, conversely: an algebraic equation is a differential equation where no derivatives appear).

However, those two types of extensions are independent of each other:

There exist differential equations which are solvable by Turing machines.
There exist differential equations which are not solvable by Zeno machines.

If what made Zeno machines different from Turing machines was that only Zeno machines could represent differential equations, then there could be no Turing machines which can solve for differential equations.

But if you search for "differential equation solver" you get a lot of results: there exist programs which can solve certain differential equations. So a Zeno machine is not necessary for solving differential equations. Therefore Zeno machines and differential equations cannot be the same.

You can interpret the computations of a Zeno machine as a differential equation only insofar as you can already interpret the computations of a Turing machine as a differential equation. So neither do differential equations tell you anything about Zeno machines nor do Zeno machines tell you anything about differential equations.


Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing) Before the Question:
Greene, Parnas and Yao presented a scheme which, for binary data chosen uniformily a random,
 retrieves all points within Hamming distance r of a given point in time $O(d n^{r/d})$ using $O(d n^{1+r/d})$.
The scheme is based on Turán's graph and the complete description can be found
here.

I was reading this paper
Fast Exact Search in Hamming Space with Multi-Index Hashing.
and realised there is nothing written WHEN r=0, that is, how to find an EXACT MATCH using neighbour search.

The question is concerned with EXACT MATCH (r=0) of an exact k-NN search in Hamming Space using Multi-index Hashing.
I'm not interested in the first nearest element.
I would like a data structure that answer the existence of an element inside a set.
Is it possible to make such a data structure?

What is the complexity of the Yao's algorithm or Norouzi's algorithm when r=0?
I think it is not only make r=0 in the above complexities to get the answer...

You don't need sophisticated data structures or algorithms to handle this case.   Exact match (r=0) just means that you want to store a set $S$ of points in a way so that, given $x$, you can test whether $x$ is in $S$.  If you have a set $S$ and want to be able to query whether a point $x$ is in the set, then standard data structures suffice.  You don't need anything fancy: you can just store all the points of the set in a hashtable.  Queries just involve a lookup into the hashtable.  Or, you can use a balanced binary tree, or any other standard dictionary data structure.

The running time per query is basically expected $O(d)$ time or $O(d \lg n)$ time, where $d$ is the number of dimensions, if you choose the data structures appropriately.  This is essentially optimal, since even just reading the point takes $O(d)$ time.  In principle, you could get the running time down to expected $O(\lg n)$ time per query, if you cared, by taking a random projection onto a subset of $O(\lg n)$ coordinates, though I'm not sure whether it'll be significantly faster in practice.


Tag storage when using HBM as an L4 cache I'm reading through Computer Architecture: A Quantitative Approach, Sixth Edition, and I'm trying to understand the issues surrounding tag storage in using HBM as an L4 cache. The primary concern mentioned in the book is "where do the tags reside?", since the sheer capacity (1 GiB) of the HBM with a small block size (64B) results in a large amount of tag bits (96MiB).

The book first suggests that the tag data might live outside of HBM, in a higher level of the memory hierarchy - except there is not enough SRAM capacity to store them, even in a modern L3 cache. It then goes on to suggest that keeping the tags in HBM as a solution to this. However, in L1-L3 SRAM caches, don't the tags reside in each of the caches themselves? Why would HBM be any different? Is it because we're somehow unable to perform hit detection/tag comparison on the HBM DRAM chips themselves (as is done in SRAM caches), so they need to be processed outside of HBM?

Disclaimer: It's been a while since I last read that book. It was an edition that pre-dated HBM. So I can't really refer to the book to find out what it's saying.

The "level" of a cache refers to how many steps removed it is from the CPU's load/store hardware. It means nothing beyond that. You can't just say "L3" and assume that it refers to the same organisation.

In a modern machine, there is usually one L1 cache per core, split between instruction and data. It may be virtually addressed or physically addressed depending on the architecture.

L2 cache is typically unified, instructions and data. But is there one per core, or one per die?

And what does L3 cache mean? Is that the one shared between cores on a die? Is the GPU on the die, and the L3 is shared between the CPU cores and the GPU? Is the L3 cache off-chip? Or perhaps the tags are on-chip and the data is off-chip? Maybe this is a NUMA machine, and the L3 is shared between all processors on the same board?

I think the issue here may be that any signal that has to go off the chip is more expensive than one that stays entirely on the chip. It usually requires higher electrical currents, and more time since the tolerances of a circuit board aren't as tight as they are on a die. So if you can't fit an entire cache on a single chip or package, it can make sense to split the tags from the data.

If you are a CPU die, for example, and a different die invalidates a cache line (e.g. it changes state from Shared to Exclusive in the MESI model), then all levels of your cache need to be potentially invalidated. That is an operation that only requires accessing and modifying the tags, not the data. So keeping the tags on-chip and storing the data off-chip could make sense here. This was extremely common back when you couldn't pack quite so many transistors on a die.

I don't know if any of that helped.


Multiple-Choice Questions about decidability I'm working on old MC-Questions about decidability und don't have the answers to the following ones:

1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable

2.) For Turing-acceptable languages L is "L = $\emptyset$" a non-trivial property.

3.) There are context-free languages $L_1$ and $L_2$ so that $L_1 \cap L_2$ is not decidable.

4.) $L$ is decidable $\Leftrightarrow$ $L \le \{0\}^* \cdot \{1\}^*$

I think 1.) is false, because $\Sigma^*$ as a superset of many undecidable languages for example is decidable and 2.) is true, because there are Turing-acceptable languages with (exactly one) and without the property. I have no idea at 3.) and 4.).

Regarding 1 - $\Sigma^*$ is a superset of every language, not just "many". This is a very general and important point: the measure of how "complicated" a language is, is not in a direct correlation with how "big" the language is.

In 2 - you are correct.

For 3 - the answer is no - if $L_1$ and $L_2$ are CFL, then $L_1\cap L_2$ is decidable. Indeed - decidable languages are closed under intersection, and every CFL is decidable.

As for 4 (assuming that by $\le$ you mean "mapping-reducible") - observe that $0^*1^*$ is a regular language, and in particular - decidable. Thus, if $L\le_m 0^*1^*$, then surely $L$ is decidable.

Conversely, assume that $L$ is decidable, then there exists a mapping reduction from $L$ to every non-trivial language. Indeed, you can decide $L$ within the reduction, and just output a fixed string. So the answer is yes.


Is `→` a type operator? In Types and Programming Languages by Pierce,

  The level of types contains two sorts of expressions.

  First, there are proper
  types like Nat, Nat→Nat, Pair Nat Bool, and ∀X.X→X, which are inhabited
  by terms. (Of course, not all terms have a type; for example (λx:Nat.x) true
  does not.)

  Then there are type operators like Pair and λX.X→X, which do not them-
  selves classify terms (it does not make sense to ask “What terms have type
  λX.X→X?”), but which can be applied to type arguments to form proper types
  like (λX.X→X)Nat that do classify terms.

Is →  a type operator? →  seems to me to take two types as arguments and return a function type.

Does it   belong to some kind?

I might miss it, but does TAPL say anything about it?

Similar questions for

x (for pairing two types, e.g. T1 x T2, c.f. Ch11).
∀X. in universal type ∀X.T in Figure 23-1 of Ch23 on p343
{∃X,} in existential type {∃X,T} in Figure 24-1 of Ch24 p366
λX:: . in type operator abstraction λX::K.S (c.f. Figure 29-1 in Ch29 on p446)
Space  in type operator application T1 T2 (c.f. Figure 29-1 in Ch29 on p446)

Thanks.

Yes, these can all be viewed as operators at the type level, but they're not all completely analogous. Most of these are type constructors in that they're formation operators for types, though type-level application is simply a type operator.

$\to$ may be viewed as an ordinary type constructor. In Pierce's notation, this is denoted $\lambda X . \lambda Y . X \to Y$. You can just as well think of it as binary algebraic structure on the set of types $(-) \to (-) : \star, \star \to \star$, where $\star$ is the kind of types. (If you have a higher kind above this, it could live there, but this depends on precisely what your calculus is.) The product of types, $\times$, may be viewed similarly. Type-level application is also a type operator.

$\forall X$, $\exists X$ and $\lambda X$ are also type constructors, but they're a little different from the previous two in that they're binding operators: just like the $\lambda$ term operator, they bind a variable in the context (though in this case, a type variable). This means these type constructors are no longer algebraic operators à la universal algebra like the simple type constructors $\to$ and $\times$.


Understanding a detail in the proof of bin packing approximation Input: $n$ item with sizes $s_1,...,s_n$, without lose of generality, all sizes are $\leq1$.  In addition, $s_i < \delta$ for all $i$ for some constant $\delta$.
Output: Minimal numbers of bins to pack the items, where each bin has volume 1.

The scheme used is first-fit, where if the current used bins are indexed, we insert the $i_{th}$ item to bin with the lowest index it fits into. Therefore, we open a new bin only when we can't fit an item into any bin.

Denote by $OPT$ the minimal number of required bins (for some input), and by $FF$ the number of bins output by first-fit scheme, the claim is that:

$$FF \leq OPT(1+2 \delta)+1$$
The proof is divided into cases, one when $\delta\geq {1 \over 2}$
, and the second where $\delta< {1 \over 2}$.
My problem is in the later case.
In class we were shown that when the algorithm (that uses first-fit scheme) ends running, there are at least $FF-1$ bins, such that their empty space is $<\delta$. (which I understand why)
Here a
link
to the final configuration of the algorithm to make things more clear.

Then the professor claimed that: $(FF-1)(1 - \delta) \leq OPT$.
Why is that?

We have $u = 1 - e$ where $u$ is used space and $e$ is empty space.

Since for at least $FF - 1$ bins we have $e < \delta$ (which you understand why), for those we also have $1- e > 1 - \delta$ or $u > 1-\delta$.

So in at least $FF - 1$ bins we use at least $1 - \delta$ space. Since each bin has maximum size $1$ we can also say that at least $FF - 1$ bins are at least $1 - \delta$ fraction full. In other words, we have at least $(FF - 1)(1 - \delta)$ bins worth of 'stuff', so that must be less than or equal to the optimal amount of bins we need to use (or else we'd have more stuff than that could fit).


What is the time complexity of the SGVB estimator? In the context of variational autoencoders, we want to maximize the evidence lower bound and this is typically done using Stochastic Gradient Variational Bayes (SGVB). I was curious if there is any work out there or ways to determine the time complexity of SGVB.

Asymptotic running time analysis is not terribly useful for gradient descent used to train machine learning models.  In practical machine learning, we run gradient descent for some fixed number of epochs, e.g., 200 epochs; which takes time proportional to 200 times the size of the training set times the time per evaluation of the neural network.  That value 200 is arbitrary and set based on what achieves the best accuracy results, and there is little theoretical basis for choosing it.


Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable I tried to prove by contradiction.

$L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable.
$$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\}$$
$$L_{2}=\emptyset$$
then,
$$\overline L_{1}={HALT_{TM}}=\big\{ \langle M, w \rangle \mid M\text{ is TM and }M\text{ halts on input }w \big\}$$
$$\overline L_{2}=\Sigma^{*}$$
The intersection, $\overline{L_{1}}\cap \overline{L_{2}}$ is $\overline L_{1}={HALT_{TM}}$ is decidable and this is the contradiction.

Is it true?

Thanks.

Unfortunately your proof is not correct. The claim you want to prove or disprove is:

  The union of any undecidable language and any finite language is undecidable.

To do a proof by contradiction, you need to take the opposite:

  The union of some undecidable language and some finite language is decidable.

Note that the "any" (universal quantifier) turns into "some" (existential quantifier) when you apply the negation.

You showed that a contradiction follows from:

  The union of any undecidable language and any finite language is decidable.

But unfortunately, that only proves:

  The union of some undecidable language and some finite language is undecidable.

In other words, you can't just pick specific languages and show that their union is decidable: you need to show that your proof will work for any arbitrary $L_1$ and $L_2$ fitting the requirements.

I would suggest that you instead start with an arbitrary undecidable $L_1$ and finite $L_2$ and, from there, show that $L_1 \cup L_2$ is undecidable. Here's a hint to get you started: is $L_1 \setminus L_2$ decidable or not?


Can the "divide" step in a merge sort be avoided? So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps.

If you iterated over the original array while jumping by two, you could get the elements at at index i and i+1 and put them into their own sorted arrays. Once you have all these sub-arrays ([7,14], [3,12], [9,11] and [2,6] as shown in the diagram), you could simply proceed with the normal merge routine to get a sorted array.

Is iterating through the array and immediately generating the required sub-arrays less efficient than performing the divide steps in their entirety?

The confusion arises from difference between the conceptual description of the algorithm, and its implementation.

Logically merge sort is described as splitting up the array into smaller arrays, and then merging them back together. However, "splitting the array" doesn't imply "creating an entirely new array in memory", or anything like that - it could be implemented in code as

/*
 * Note: array is now split into  [0..n) and [n..N)
 */

i.e. no actual work takes place, and the "splitting" is purely conceptual. So what you suggest certainly does work, but logically you're still "splitting" the arrays  - you just don't need any work from the computer to do so :-)


Seemingly non sequitur in proof I'm trying to understand a small proof in an article about computing lumpability on Markov chains. There is a small detail that I cannot understand, i.e. I don't think it follows from the argument.

The article is Simple $O(m\log{n})$ Time Markov Lumping written by Valmari & Franceschinis.

Given a weighted graph they define the notion of compatible partition of its nodes. Which is a partition $P$ such that for all $B, B' \in P$ and all $s_1, s_2 \in B$ we have that:

$$
W(s_1, B') = W(s_2, B')
$$

They describe an algorithm to compute the coarsest refinement of an initial partition that is compatible (the coarsest croip= compatible refinement of initial partition). The algorithm follows the idea of Paige and Tarjan to compute bisimulation: we take a block $S$ from the partition as a splitter and check whether some other block $B$ breaks the condition above, and if it does we split $B$ into $B_1, \ldots, B_k$ such that the $B_i$ satisfy the condition above when taking $B' = S$.

How exactly these checks are performed shouldn't be essential for the correctness of the algorithm. In the proof of correctness they prove the following lemma:

  Lemma 2. Let $d_1, d_2$ be nodes of the graph. If the algorithm ever puts $d_1$ and $d_2$ into different blocks, then there is no
  croip where $d_1$ and $d_2$ are in the same block.

The proof for when the algorithm separates $d_1$ and $d_2$ during its execution is the following:

  Proof. We show that it is an invariant property of the main loop of the algorithm (that is, always valid on line 2*) that if
  two states are in different blocks of the algorithm, then they are in
  different blocks in every croip.

  If $d_1$ and $d_2$ are in different blocks initially, then they are in
  different blocks in $I$ and thus in every croip.

  The case remains where lines 14 to 20 separate $d_1$ and $d_2$ to
  different blocks.

  This happens only if $W(d_1, S) \neq W(d_2, S)$. Let $P$
  be an arbitrary croip. It follows from the invariant that each
  block of $P$ is either disjoint with $S$ or a subset of $S$,
  because otherwise the algorithm would have separated two states that
  belong to the same block of a croip. Therefore, there are blocks $S_1 , \ldots, S_k$ in $P$ such that $S_1 \cup \cdots \cup S_k = S$. The fact $W(d_1, S) \neq W(d_2, S)$ implies that there is $1 \leq i \leq k$ such that $W(d_1 , S_i) \neq W(d_2, S_i )$. So $d_1$ and $d_2$ belong to different blocks in $P$.

I have a problem understanding the text in bold. To me: it's simply false.
They justify it saying otherwise the algorithm would have separated two states that belong to the same block of a croip.

However:

we still haven't proved the algorithm correct, so I don't really see how the algorithm doing something should imply anything at this point
I don't get if the two states separated are $d_1$ and $d_2$ or if they are referencing other states

So, I see this as a non sequitur, which would invalidate the proof of this lemma and thus the whole correctness proof of the algorithm.

Given that the algorithm was developed to fix a wrong algorithm published previously from other authors, I believe Valmari and Franceschinis were very careful in the proofs, so I'm probably missing something trivial. Can anybody point out what I'm missing?

* The algorithm is simply a main loop that chooses a new splitter $S$ for each iteration and splits all the blocks in the partition and goes on.

The invariant states that if at some point of the algorithm, $d_1,d_2$ are in different blocks, then in every croip, $d_1,d_2$ are in different blocks. The contrapositive of the invariant states that if $d_1,d_2$ are in the same block of some croip, then they are always in the same block during the running of the algorithm.

Now consider a block $S$ of your algorithm and a block $T$ of an arbitrary croip. We want to show that either $T \subseteq S$ or $T \cap S = \emptyset$. If not, then take some $d_1 \in T \setminus S$ and some $d_2 \in T \cap S$. Since $d_1,d_2 \in T$, they are in the same block of some croip, and so the contrapositive of the invariant states that they are always in the same block during the running of the algorithm. But $d_1 \notin S$ while $d_2 \in S$, and we reach a contradiction. We conclude that either $T \subseteq S$ or $T \cap S = \emptyset$.


Constant Shaving on known algorithms Some problems such as sorting have famous complexity lower bounds (ex: $O(n \log (n))$ in this case) but I feel that doesn't totally remove the possibility of improving algorithms by shaving constants. Are there any really non trival, perhaps not practical sorts, that have excellent constant performance? For example do there exist algorithms that say achieve $\frac{1}{2} n \log(n)$ number of comparisons as opposed to say mergesorts $1.44 n \log(n)$, and can this leading constant, be reduced arbitrarily low?

It oculd be the case these algorithms have running time

$$ 0.0001 n \log(n) + 9^{\text{Graham's Numbers}}n + \pi^{\pi^\pi} $$

But I am still curious if non trivial reduction of constants exists, or if someone has proven tight bounds on what the constants must be.

Let's suppose that you want to do comparison-based sorting of $n$ distinct elements.

You can interpret the problem in terms of information theory. You want to discover which permutation the sequence is currently in. That is, you need to discover a number between $1$ and $n!$.

The comparison operator gives you one bit of information. But to discover a number between $1$ and $n!$, you need at least $\log_2 n!$ bits of information. Therefore, you need at least $\log_2 n!$ comparisons.

By Stirling's approximation:

$$\log_2 n! = n \log_2 n - \frac{n}{\ln 2} + O(\log n)$$

This is the number of comparisons you need. You cannot do better than this. For any comparison-based sort which takes $k n \log_2 n + o(n \log n)$ comparisons, $k \ge 1$. In particular, there is no comparison-based sort which uses $\frac{1}{2} n \log_2 n$ comparisons.

So no, you can't reduce constants arbitrarily.

We usually don't do this kind of analysis for time complexity, because in practice, "time" depends on many factors like the compiler settings, the CPU architecture, the laws of physics, and so on. However, it becomes very important when analysing space complexity; we do measure time in physical units ("this program will take three hours to run"), but we don't typically measure space the same way ("I need a cubic metre of disk").


Finite State Automata for recognising consecutive characters I'm currently working on this question as part of some homework, it has me stumped.

I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on Google, but nothing's helped me come any closer to a solution.

If I don't know the length of the input string, or I'm not searching for a particular pattern, how can I design a machine that will always land on the final state?

I've tried drawing some, but that always end up being a little off.

The FSA should have three states:

$q_a$ represents:  last character was not a b, and no bb yet
$q_b$ represents:  last character was a b, and no bb yet
$q_{bb}$ represents:  there was already a bb

Clearly, you start with $q_a$ and you accept in $q_a$ and $q_b$. Now try to figure out how to connect the states.


Data structure with constant time operations I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value in constant time.

This data structure should probably be sorted to find the maximum values and I have looked into red-black trees, however they have logarithmic-time operations.

It is impossible to build a data structure that supports insert, maximum, and delete all in constant time. Such a data structure is a priority queue, and a priority queue with all constant-time operations can do heapsort in linear time. Since there is a superlinear lower bound on sorting, this is impossible. One of insert, maximum, or delete must be logarithmic time.

Certain species of tree (like those with lazy deletion and incremental partial rebuilding) require only insert to be linear time. A skew binomial heap requires only delete to be linear time.


Shortest path with a given condition The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two alternative routes. Also, all the
connections between the points on the map are given.

I understood that the problem is about a graph with given edges and that i have to find the shortest path between two given nodes, but i didn't understand how to search the right path with the given condition (2 alternative paths between every two intermediary nodes).
Is the BFS algorithm applicable in this case? And wich other algorithm could I also use?

Thanks in advance for help!

First let's look at the special condition.
For each edge $p_i p_{i+1}$ in the path $P$ the has to exists an additional path that connects $p_i$ with $p_{i+1}$. This criterion is equivalent to: no edge of the path is a bridge edge.

This means that we can determine already before the actual shortest path search, which edges we are allowed to use, and which edges we are not allowed to use.

Therefore you can construct an efficient algorithms as follows:

compute all bridge edges (e.g. with Tarjan's bridge-finding algorithm)
remove all bridge edges from the graph
execute any shortest path algorithm, e.g. BFS, on the remaining graph

Some additional notes, since you wrote that you want to use multiple algorithms. However these approaches will perform a lot worse than the one described above.

of course you can also determine if an edge $p_i p_{i+1}$ is a bridge edge in other ways. E.g. remove the edge from the graph, and check if you can find a path from $p_i$ to $p_{i+1}$ with a DFS (backtracking), or with another BFS.
Also you can use Backtracking itself to find the shortest path at the end.


XOR-like behavior in flow networks XOR is not the correct name, but I am looking for some kind of exclusive behavior.

I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-flow algorithm. Flow networks are quite handy because a lot of problems can be reduced to them in an easy and understandable way. In my case these are matchings with some additional constraints. As these constraints are getting more complex I've been wondering if there are some existing constructions to model specific behaviors.

In this case I want to restrict the outgoing flow of a node to a single edge.

Given a graph $G=(V, E)$, integral capacities $c(u,v)$ and costs $k(u,v)$. An arbitrary node is called $A$. It's direct neighbors are called $B_1, ..B_n$. Can we replace the edges $AB_1,...AB_n$ (red) with some construction so that only one edge can receive flow? Which means that if $AB_1$ gets some flow (e.g. $5/10$) no other (red) edge can receive flow.

We could add intermediate nodes/edges and play with costs and capacities. The total capacity of our new construction has to stay the same and the cost of the different alternatives have to stay somehow proportional.

So my questions are:

Are there constructions like this in general? (Any keywords, links, papers)
Can you suggest a solution to my specific problem?

In general, the answer is no. If we put XOR-like restrictions on the out-going edges of a vertex, we can prove that finding a min-cut-max-flow is NP-Hard. The technique is to reduce 3-SAT to it.

Let's assume there are $n$ variables $x_1, x_2, ..., x_n$ in the 3-SAT and $m$ clauses $c_1, c_2, ..., c_m$. We create a graph $G(V,E)$ encoding the instance of the 3-SAT problem. For each variable $x_i$, we create a vertex $v_i$ connected to the source $s$ with an edge of $\infty$ capacity. Two more vertices $u_i, w_i$, which are connected to $v_i$, are created to represent $x_i$ taking the value 0 or 1 also with edges of capacity $\infty$.

For each of the clauses $c_i$, we create a vertex $o_i \in G$ corresponding to it and $o_i$ is connected to the variables or their negations in the clause with edges of capacity $1$. For example, if $c_i = (x_3 \lor x_4 \lor \neg x_5)$, we connect it to $u_3, u_4, w_5$ with edges of capacity. All $o_i$ are connected to the sink with edges of capacity 1.

Since $x_i$ and $\neg x_i$ cannot take the same value, we put the XOR restriction on edges $(v_i, u_i)$, $(v_i, w_i)$, $\forall i = 1,2,3,...,n$. It can be proved that there is a maximum flow of size $m$ if and only if the 3-SAT instance is satisfiable. Since the problem is trivially in $NP$ and the reduction is polynomial, we conclude the decision version of XOR restriction network flow is NP-Complete.