How to use stable matching algorithm in order to determine optimal schedule? This is a problem 1.6 from the book Algorithm Design by Kleinberg/Tardos:

There's a company that manages ships that do various tasks when in port. There're $n$ ships, $n$ ports, $m$ days in a month such that $m>n$.
At any given day there can't be two ships from the company in the same port. $(*)$
The company wants to perform maintenance on all the ships this month, via the following scheme: they want to truncate each ship’s schedule: for each ship $S_i$, there will be some day when it arrives in its scheduled port and simply remains there for the rest of the month (for maintenance). This means that $S_i$ will not visit the remaining ports on its schedule (if any) that month, but this is okay. So the truncation of $S_i$’s schedule will simply consist of its original schedule up to a certain specified day on which it is in a port $P$; the remainder of the truncated schedule simply has it remain in port $P$.
Now the company’s question to you is the following: Given the schedule for each ship, find a truncation of each so that condition $(*)$ continues
to hold: no two ships are ever in the same port on the same day.
Show that such a set of truncations can always be found, and give an algorithm to find them.

As far as I understand from the example the ship must visit at least one port before it's on maintenance (although this condition is not mentioned in the book). I also assume that each ship is supposed to visit all ports. Then because there're more days than ports and ships we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.
This is solution is too simple and it's not using Gale Shapley matching algorithm which I think is expected to be used in the book.

we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.

The following is a counterexample to your algorithm:

  Ship 1: Port 1, at sea, Port 2, at sea, Port 3, at sea

  Ship 2: at sea, Port 1, at sea, Port 2, at sea, Port 3

  Ship 3: Port 2, at sea, Port 3, at sea, Port 1, at sea

This has the solution where Ship 1 stays at Port 3, Ship 2 stays at port 2, and Ship 3 stays at Port 1.

But your algorithm does the following:

Day 1:

Ship 1 arrives at Port 1. Port 1 hasn't been visited so it stays for maintenance.
Ship 3 arrives at Port 2. Port 2 hasn't been visited so it stays for maintenance.

Day 2:

Ship 2 arrives at Port 1 where Ship 1 is already staying, which isn't allowed (and you're not allowed to not have Ship 2 not arrive at Port 1 given the rules described in the end of the problem's 3rd paragraph).

If we add to your algorithm your unjustified assumption that ships can't stay for maintenance at the first port they visit, then your algorithm does the following:

Day 1:

Ship 1 arrives at Port 1. It's not allowed to stay at the first port it visits.
Ship 3 arrives at Port 2. It's not allowed to stay at the first port it visits.

Day 2:

Ship 2 arrives at Port 1. It's not allowed to stay at the first port it visits.

Day 3:

Ship 1 arrives at Port 2. Port 2 hasn't been matched yet so it stays there.
Ship 3 arrives at Port 3. Port 3 hasn't been matched yet so it stays there.

Day 4: Ship 2 arrives at Port 2 where Ship 1 is already staying.

As for the question of how to solve this using stable matchings, here's a hint: you're trying to find a matching between ships and ports (where they stay for maintenance), such that the following is impossible:

Ship A is matched to Port A
Ship B is matched to Port B
Ship A arrives at Port B before it arrives at Port A (it's not yet on maintenance when it gets to Port B)
Ship A arrives at Port B after Ship B does (so Ship B is already staying there for maintenance)

How can you translate that into preferences for ship-port pairs so you can apply Gale Shapley matching?


Find The missing number in range [0,n] Given Array $A$ of size $n$ that contains all the integer values $[0,n]$ except one.

In this question we assume that the time we need to check one bit $j$ in number $A[i]$ is $O(1)$,and to check the number $A[i]$ is $O(\log n)$.

Find an algorithm that finds the missing number in $O(n)$.

So creating a trivial counter array and searching for a 0 count wouldn't help - it would be $O(\log n)$.

I also thought about counting the bits and finding the missing one, but that wouldn't help either.

Compare all the Least Significant bits,
and either there are less ones or zeroes.

We continue this search only on the set where there is less of some bit, half the input at each iteration.

$$n + \frac{1}{2}n + \frac{1}{4}n + ... < 2n.$$

And we accumulate the missing bits at each step, to come to the missing number.

So the running time is $O(n)$.


Undergrad resources for identifying regular languages with Myhill-Nerode matrices I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure properties of regular languages, the pumping lemma etc, to show that a language is or is not regular, all of our proofs and examples for identifying regular languages use the Myhill-Nerode theorem and boolean matrices as defined below.

Let $L = \{w_1, w_2, ...\}$ be a set of words over some alphabet $\Sigma$ and let $T_L$ be a matrix with entries $t_{ij}$ where

$$ t_{ij} =
\left\{
 \begin{array}{ll}
  1  & \mbox{if } w_iw_j \in L \\
  0  & \mbox{otherwise}
 \end{array}
\right.
$$

Then by Myhill-Nerode, L is non-regular iff all rows of $T_L$ are distinct.

Correction: Then by Myhill-Nerode, $L$ is non-regular iff $T_L$ has an infinite number of distinct rows.

My question is, are there any readily available books, papers, or lecture notes that lean heavily on this technique and are appropriate for undergrads?

I wanted to make this a comment, but it is too long.

First, your definition of the matrix is poorly written and probably wrong. There is no reason to introduce indices $i, j$. My guess is that the right definition is the following:
$T$ is the infinite matrix $(T_{u,v})_{u, v \in A^*}$ defined by
$$
  T_{u,v} = \begin{cases}
    1 &\text{if $uv \in L$}\\
    0 &\text{otherwise}
            \end{cases}
$$
Next, your claim

  $L$ is non-regular if and only if all rows of $T$ are distinct

is wrong. Take $A = \{a, b\}$ and $L = \{ u \in A^* \mid |u|_a = |u|_b\}^1$. Then
$T_{1,v} = T_{ab,v}$ for all $v \in A^*$, so the rows $T_{1, -}$ and $T_{ab,-}$ are equal although $L$ is not regular. What is true however is that $L$ is regular if and only if $T$ has finitely many distinct rows.
${}_{\text{(1) $|u|_c$ denotes the number of occurrences of the letter $c$ in $u$.}}$

References. The matrix $T$ is used in the larger setting of noncommutative formal power series under the name of Hankel matrix. Here is a good reference, but I am afraid it is not really appropriate for undergraduate students.

[1] J. Berstel and C. Reutenauer, Noncommutative rational series with applications. Encyclopedia of Mathematics and its Applications, 137. Cambridge University Press, Cambridge, 2011. xiv+248 pp. ISBN: 978-0-521-19022-0


Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable? Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable? If not, why not? If yes, how can such a program be realistically constructed?

I would prefer an intuitive explanation over a formal one, thanks.

As discussed in the comments, the question is not well-defined, since it's unclear what the input is.

However, under any reasonable assumption, no such program exists. One way to see this is through context-free languages: assume we can solve your problem even to the very restricted class of context-free languages. Thus, we have a program $P$ that given a grammar $G$, outputs a TM $M$ whose runtime is optimal (which is also not clearly defined, but let's ignore that for now) and recognizes the same language as $G$.

We can use this program $P$ in order to decide, given a CFG $G$, whether $L(G)=\Sigma^*$, by running $P$ and checking if it outputs a TM which is just a single accepting state (which is the only optimal TM under a reasonable optimality definition). Since this problem is undecidable, then $P$ cannot exist.


Dynamic Programming vs Greedy - coin change problem This is a fairly common problem:

Given coins of integer denominations $v_1 < v_2< ... < v_n$, make change for an amount A using as few coins as possible.

Given an input of powers of $p$,

$V = [1, 3, 9, 27]$

How would a dynamic programming vs greedy approach differ in this algorithm?  I don't have a good general idea of how these approaches would differ.

A dynamic approach would say that "x$ can be made out of change using, as the first coin, v1 or v2 or v3 ... or vn" and then build a table so that the second coin would be v1 or v2 or v3 ... or vn + one of the precomputed values. Here is a link talking about dynamic: http://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change

Greedy choice however uses the fact that, for many currencies, we simply can take the maximum value that still gives us less than then our amount and ignore all other possibilities. However, greedy doesn't work for all currencies.

For example:
V = {1, 3, 4} and making change for 6:
Greedy gives 4 + 1 + 1 = 3
Dynamic gives 3 + 3 = 2

Therefore, greedy algorithms are a subset of dynamic programming. Technically greedy algorithms require optimal substructure AND the greedy choice while dynamic programming only requires optimal substructure.


Why sequential consistency model is widely used if it is unsound From this talk and these lecture notes here and here I learned that sequential consistency does not actually model what really happens in practice. However, it is also pointed out that most of the work in formal methods assumes the sequential consistency model even though there exists other models which correctly characterize what really happens in practice. I'm unable to understand why the sequential consistency model is widely used if it is unsound with respect to what happens in practice. Is there a good reason for doing this? What confused me even further was that in the textbooks on concurrency theory that I could access (e.g. [1]. [2], [3]), I could not find any references to this topic.

Roscoe, B. (1998). The theory and practice of concurrency.
Bowman, H., & Gomez, R. (2006). Concurrency theory: calculi an automata for modelling untimed and timed concurrent systems. Springer Science & Business Media.
Gorrieri, R., & Versari, C. (2015). Introduction to concurrency theory: transition systems and CCS. Springer.

The underlying hardware often has more relaxed memory ordering compared to SC. For example, the X86 will allow for older stores to be reordered with newer loads for a different address due to store buffers. So instead of having a total order over all loads and stores (SC), you only get a total order over all store (TSO). ARM is even more relaxed. And apart from the hardware, the compiler can also reorder instructions if this isn't prohibited.
There are also weak memory models. Weak memory models are a relaxation of strong memory models like SC/TSO because a distinction is made between plain loads and stores and synchronizing loads/stores.
For most engineer it is way too difficult to reason about any other model than SC. SC is often the most intuitive model and that is why many API's are SC (e.g. a C++ atomic by default is SC or Java volatile) and why language level memory models like the Java Memory Model are rooted in SC. Only the experts understand how to relax consistency in favor of improved scalability/performance.


Series where each term is square of previous The problem statement is as follows:-

  In a court case, a judge cited a court of contempt and ordered a fine of $2 for first day.
  On subsequent days, the fine would be equal to the square of the previous day's fine.
  e.g. 2, 4, 16, 256 and so on.
  Find out:-

  a) What would be the fine on day $n$?

  b) How many days would it take the fine to reach $D$ dollars?

A big Oh answer would be appreciated.

As you say, the fine on day $n$ is $2^{2^n-1}$. To reach $D$, you need to solve the equation $2^{2^n-1}=D$, taking $\log$ we have $2^n-1=\log D$, rearranging and taking $\log$ again we get $n=\log(\log D+1)$.

If you want the answers in Big-O notation, you have $2^{2^n-1} =O(2^{2^n})$, and for the second part, $n=O(\log\log D)$.


Normalized measure from dynamic time warping I am trying to find the similarity between two time series, but not in terms of distance, in something more sensible such as percentage of similarity. In other words I need something that shows the similarity, not dis-similarity.

The dynamic time warping gives a very good response, when trying to compare the time-series. But the distance computed by dynamic time warping depends on the duration of the time series and the magnitude of the template and the query. Moreover, it shows the distance, which demonstrates the dis-similarity.

Is there a way to convert the distance from DTW into some form of normalized similarity measure?

Sure.  There's a straightforward way to convert an unnormalized distance metric into a normalized similarity measure.  Basically, use

$$S(x,y) = \frac{M - D(x,y)}{M},$$

where $D(x,y)$ is the distance between $x$ and $y$, $S$ is the normalized similarity measure between $x$ and $y$, and $M$ is the maximum value that $D(x,y)$ could be.

In the case of dynamic time warping, given a template $x$, one can compute the maximum possible value of $D(x,y)$.  This will depend on the template, so $M$ becomes $M(x)$, and the formula becomes

$$S(x,y) = \frac{M(x) - D(x,y)}{M(x)}.$$

So how do you compute $M(x)$?  Basically, multiply the length of the template (the number of samples in the time series), times the maximum value of each sample.  If each sample is in the range $[0,1]$, then the maximum value of each sample is 1, so $M(x)$ becomes just the length of $x$.  This gives a simple upper bound on $D(x,y)$.  [Trivia: in fact one could compute a slightly tighter upper bound, but in practice that's probably not necessary.]

It is easy to verify that the similarity measure is always in the range $[0,1]$ and thus is normalized as you were hoping for.


Extracting maximum information from a set of exam answers and their scores Imagine we have a multiple-choice exam with N questions.
Suppose we have a set of K answer sheets to the exam and their total scores (1 for a correct answer on a question, 0 for incorrect).

How much information can we extract from this set about the true answers to the exam, and what is the shape of the space of possible answers after extracting this information? (e.g., is it convex in some sense? is it a linear subspace? or something like that)

E.g. if we have at least one answer sheet with a score of N, then we know all the correct answers. If we have an answer sheet with a score of 0, then we can exclude at least one answer from each question. [If we have two different answer sheets both with a score of N-1, we know the correct answers to all questions in which they agree] - (on further thought, this is actually incorrect..). Etc.

What's this problem called? Is it solvable in polynomial time? (looks like it's reducible to integer programming)

Hardness

Recovering the correct answers to the exam is NP-hard.  I'll show how to reduce one-in-three 3SAT to it.

Suppose we have a 3CNF formula $\varphi$ on $N$ variables $x_1,\dots,x_N$.  The $i$th question on the exam is "Is $x_i$ true?"  There is one answer sheet per clause of $\varphi$.  If $\varphi$ contains a clause mentioning variables $x_i,x_j,x_k$, say $x_i \lor \neg x_j \lor x_k$, then there's a corresponding answer sheet that has answered "Yes" to question $i$, "No" to question $j$, "Yes" to question $k$, and left all other questions blank, and this answer sheet received a score of exactly 1.

Now if you can extract the correct answer to all of the questions, then you can extract a satisfying assignment for the corresponding one-in-three 3-SAT problem -- a task that is NP-hard.

Therefore, you should not expect to find any efficient algorithm for your task (i.e., to extract the correct answers, given the scores on the answer sheets), at least in the worst case.

That's the bad news.  Now for the good news:

Algorithms

In practice, a good way to approach your problem might be to throw a SAT solver or ILP solver at it.  This sounds like the kind of problem that they might be effective at, in practice, if $N$ is not too large.  Your problem can be readily formulated as an instance of integer linear programming (ILP), or indeed as an instance of SAT.


Is the complexity class NP computably enumerable? The definition of the complexity class $\mathsf{NP}$ seems to ensure (as good as possible) that it is computably enumerable. It looks as if the class could be enumerated by enumerating all Turing machines, and for each Turing machine report for each $k\in\mathbb{N}$ the language generated by stopping each computation after $n^k$ steps, and reject if the input hasn't been accepted before reaching this step limit.

This only gives a computable enumeration of Turing machines. However, it seems that the corresponding languages will be decidable, because the enumeration includes an explicit time bound for each of its Turing machines. Hence this should give an computable enumeration of $\mathsf{NP}$.

  Question: Is the conclusion from this reasoning correct, i.e. is $\mathsf{NP}$ computably enumerable? One issue that I have is that even for decidable languages, we can only (computably) decide whether two given languages are different, but not whether they are equal. Hence it seems that we can't avoid to report the same language more than once. The deeper issue here is that being computably enumerable is a property of subsets of the natural numbers, but the complexity class $\mathsf{NP}$ doesn't seem to correspond to a subset of the natural numbers in any canonical way.

I can't make heads nor tails from what you attempt to do, but I know that the answer to your question is: no, NP is not enumerable.

First, let's fix what that means. I assume you are asking if

$\qquad\displaystyle \mathrm{TM}_{\mathsf{NP}} = \{ \langle M \rangle \mid L(M) \in \mathsf{NP} \}$

is recursively enumerable. It's not by the extended Rice theorem since the Turing machine $M$ that never halts is an NP-acceptor for the empty language, so $M \in \mathrm{TM}_{\mathsf{NP}}$, but there certainly are $M'$ with $M \subsetneq M'$ and $M' \notin \mathrm{TM}_{\mathsf{NP}}$.

Intuitively, no algorithm can separate $M$ (which has infinitely many equivalent brethren, by the way) from any other Turing machine in finite time, and thus can never enumerate them.


Separating the snakes In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal or vertical lines along grid lines, from edge to edge or to a previously-built fence). It is allowed to "trim" at most a single sqaure from each snake (by all fences together).

Below is an example with $n=3$ snakes. Fence #1 runs from edge to edge and trims a square from the bottom snake. Fence #2 runs from the leftmost edge to fence #1 and trims a square from the upper-left snake.

Below is another example with $n=4$ snakes.

Finally, here is an example where the snakes cannot be separated, since each initial fence would trim at least two squares from one of the snakes.

QUESTION: Is there a polynomial-time algorithm for deciding whether or not it is possible to separate the snakes?

NOTE: without the option to trim a single square from each snake, there is a simple greedy polynomial algorithm: at each step, find a horizontal or vertical fence that can be built without trimming any snake. If such a fence exists, build it; otherwise, declare that it is impossible.

This can be solved in polynomial time.

Say that in the input we are given the number of snakes $n$ and for every snake the squares it occupies. Let $m$ denote the total number of squares in all snakes. Assume every snake occupies at least three squares.

If no square has $x$-coordinate in some interval $[a, b]$, we can compress that interval into a single point. Then, the squares have coordinates in range $[0, 2m - 1]$. We will do DP in $\mathcal{O}(m^{5})$.

We calculate a DP with a state for every rectangle $(x_{0}, y_{0}), (x_{1}, y_{1})$.

We say that some snake is inside the rectangle if at least two of its squares are inside the rectangle. If at least two of some snake's squares are outside the rectangle, we say it is outside the rectangle. Notice that a snake can be both inside and outside the rectangle.

Say there are $k$ snakes inside the rectangle. The DP will represent whether we can separate the $k$ snakes with at most $k-1$ fences while obeying the trimming rules.

If any snake is both inside and outside the rectangle, we automatically fail and set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 0$. If only one snake is inside the rectangle, we set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 1$.

Otherwise, for every $x_{0} < x < x_{1}$, we will try to add a fence at this $x$-coordinate. If $DP[x_{0}, y_{0}, x, y_{1}]$ and $DP[x, y_{0}, x_{1}, y_{1}]$ and no snake inside the rectangle is outside of both of the two rectangles the fence splits our rectangle to, the fence works and we set the value of the DP to true. We similarly loop $y$-coordinates inside the rectangle. If no working fence was found, we set the DP to false.

In the end, the algorithm outputs $DP[0, 0, 2m-1, 2m-1]$

This DP can be optimised to $\mathcal{O}(n^{5} + m)$ by trimming states from the DP. We can assume that the DP-box doesn't start or end with an empty column or row, therefore there has to exist some snake with the leftmost square in the box, and we can store $x_{0}$ as the index of that snake, and whether the leftmost square in the box is the leftmost or second leftmost square of that snake (It cannot be any square after that, since then the snake would be outside the box). Storing $y_{0}, x_{1}, y_{1}$ similarly gives us $\mathcal{O}(n^{4})$ dp-states. We can further loop the $x$-coordinate of a fence over just the first and last $x$-coordinates of squares of snakes in the rectangle plus minus at most one, as every other fence either trims too much from a snake or would be equivalent to a fence placed directly to the left of it. Loop similarly over $y$. The number of such coordinates is $\mathcal{O}(n)$.


Convert $1.75\times10^{15}$ to IEEE-32 format? $1.75\times10^{15}$

I know how to convert decimal to binary

$(1.75)_{10}$ is equal to $(1.11)_2$

But to represent $10^{15}$ is the main problem for me. I can solve the question but this is the point where I got stuck.
How can I represent $10^{15}$ in base 2 ?

You need to understand how the IEEE-754 standard for floating point numbers works. It is not simply converting the number to binary.

Instead, the 32 bits that compose the representation of the floating-point number are split into 3 fields: sign, exponent, mantissa. Their sizes are 1bit, 8bit, and 23bit, respectively.
Each field is written in binary basis (unsigned).

If the value of the exponent field is $e$, and the value of the mantissa field is $m$ then, the these 32bits represent the number
$$ 2^{e-127} \times (1 + m\cdot 2^{-23})$$
the $s$ bit determines if the number is positive or negative.

So, to represent the number $1.5\cdot 10^{15}$ you will need to set:
$s=0$ (positive), $e=177$, and $m=2787263$. Calculate
$2^{e-127} \times (1 + m\cdot 2^{-23}) = 2^{50} + 2787263\cdot 2^{27} = 1500000014041088$, which is the closest you can get to $1.5\cdot 10^{15}$ with 32bit representation.

Use https://www.h-schmidt.net/FloatConverter/IEEE754.html as a simple converter and a way to learn how this representation works.

(Oops, I demonstrated the above for 1.5e15, while the question was about 1.75e15. Nevermind, replace with $m=4649908$ to get 1.74999999e15).


Why $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$ does not holds for the class of Recursively Enumerable Languages? "The class of Recursively Enumerable Languages is closed under Union,
  and Intersection but they are not closed under Complement."

I know why they are not closed under Complement & why they are closed under Union & Intersection but for other classes of languages we use a reasoning for closures based on the De'Morgan Law:

  $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$

That is,
If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third.
So what's wrong with the class of Recursively Enumerable Languages?
are not they sets?
Or am I using implication incorrectly?

The claim "If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third." is not accurate.  I'm not sure where you got it from, but it's not correct.

Recursively enumerable languages are closed under union and intersection.  However, they're not closed under complement.  And, there's no way to express complement using just union and intersection.  So, the fact that they're closed under union and intersection does not imply that they're closed under complete.  There's no paradox/contradiction here.


Why more and more languages do not have link stage when compiling? As far as I know, only C, C++, and Objective-C (in most used languages) need a linker when compiling, languages like Java and C# don't have one, and it seems more and more modern languages do not have a linking stage nowadays.

Why?
If there's no linker, the code cannot turn into machine code, so languages without a linker must have a virtual machine to run on(things like JIT still need a vm), right?
Languages can call each other by using abi if both them has a linking stage, right?

You seem confused about what a linker does. It does not produce machine code. It merely sticks together (links, if you will) pieces of machine code that have already been produced by a compiler (typically).

What you were probably thinking of is that a linker produces an executable, or at least that's what a linker like ld does. This was the point of ld: to take pre-compiled libraries (.a files in UNIX parlance) and combine them together with object files to produce executables so you wouldn't need to recompile a library for every program that used it.

That said, there's nothing that keeps a compiler from just outputting an executable directly, but I don't think that this is actually happening that commonly. I'm pretty sure most languages that compile to native code do still have a linking stage. They just don't require you to explicitly call it yourself. In fact, LLVM is a popular backend for modern languages targeting native code, and building a new linker is one of the projects of LLVM. The premise that modern languages, at least those that directly produce native code, don't have a linking stage is incorrect.

For languages that primarily target a VM, they may not use ld, but that doesn't mean they don't have linkers. The recent addition to Java of "modules" has lead to jlink. More fundamentally and historically, the most natural thing to call a linker in Java is the ClassLoader. It even mentions linking the class. This is a dynamic linker. It performs the link stage at runtime. Here's the description of linking from the Java Language Specification. Of course, as always, there's nothing that stops you from compiling Java to a native executable. In that vein, there's also nothing stopping Java bytecode from being machine code.


Maximum sum subset of an array with an extra condition We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every contiguous $n$ elements there are at most $k$ chosen.

As this is an old high-school level contest problem, I ask for some hints. Also, this means I know there exists a solution far quicker than the proposed by D.W. and most likely not very complicated, so the question is still open.

My ideas mostly involved dynamic programming. I was trying to calculate, for each prefix of the array, best score we can acquire. However, in order to do this, I think I would need to calculate it for every prefix, and every possible choosing of $k$ numbers in the last $n$ numbers of this prefix, resulting in complexity $O(n^{k+1})$, which is far from acceptable. Also, I thought of looking at pairs of positions in the array which are distant by $n$ and their relation to each other, but this approach fails, as in an optimal solution not in every contiguous $n$ element we would choose exactly $k$, sometimes it could be less.

Let's call the length of the array $t \cdot n$, so in your task $t=3$. Since in every fragment $[1, n], [n+1, 2n] \ldots [(t-1)n+1, tn]$ we can't take more than $k$ elements, so the number of taken elements won't be larger than $t\cdot k$. Let's call the indices of taken elements in the given array $x_1, x_2 \ldots x_{tn}$. It's easy to notice that $x_i + n \le x_{i+k}$, because there can't be more than $k$ elements in any window of size $n$.

With this knowledge we are ready to construct dynamic programming solution, which would choose in parallel indices for every segment $[x_1 \ldots x_k], [x_{k+1} \ldots x_{2k}] \ldots [x_{(t-1)k+1} \ldots x_{tk}]$ separately.

$$dp[k+1][k+1][k+1]...(t\,times)[tn]$$
We would iterate trough positions $i$ from $1$ to $tn$ and every time decide whether we want to take one more element in the first segment from the position $i$, in the second segment from the position $i+n$, in the third segment from the position $i+2n$ etc. Bear in mind that at any point any segment cannot have more chosen elements than one of its preceding segments.

For $t = 3$:
$$dp[a][b][c][i] = max(dp[a][b][c][i-1], dp[a-1][b][c][i-1] + A[i], dp[a][b-1][c][i-1] + A[n + i], dp[a][b][c-1][i-1] + A[2n + i], dp[a-1][b-1][c][i-1] + A[i] + A[n+i] \ldots)$$
There are in total $3^t$ different combinations of taking elements from $i$-th position and it can be easily fixed in code using additional $3^t$ states.
if $a \le b \le c$ is not met:
$$dp[a][b][c][i] = -inf$$

Result of the given task is stored in one of $dp[x][0][0][tn], dp[k][x][0], dp[k][k][x]$ states for any $x$ depending on how many elements does the optimal solution use.

So overall time complexity is $O(tn(k+1)^t3^t)$ and space complexity is $O(tn(k+1)^t)$.


Reasons for decreasing the number of threads in a parallel implementation What are the reasons for decreasing the number of threads in a parallel implementation ?

Assume that we have two implementations, the first one with 4 threads, and a second one with 8 threads, and both have exactly the same run time. What are the various reasons to prefer the first one?

I stress on the fact that the two implementations have the same run times.

The obvious reasons are the following:

If we have 8 processors, we can execute at the same time this implementation on two different sets of inputs thus performing twice the work,
Less resources consumption by the OS which handles less number of threads.

I'm looking for other reasons...

Some other benefits from a security point of view for running the 4 threads implementation would be :

Obfuscation of the actual processors being used by the algorithm, in case an attacker is looking to interfere with the execution.
If you have 8 processors you can run simultaneously the same algorithm twice using the same input to check the integrity of your results.


What does the symbol # mean when it comes to languages Given the following:

$$\{ w\#x \mid w^R \text{ is a substring of $x$, with $x$ and $w \in \Sigma^*$} \}$$

What does $w\#x$ denote?

This seems to just be a case of a lack of care in the definition. The symbol $\#$ isn't anything special, but is commonly used as a separator simply for the reason that it's not normally used for much else.

So in the language in question, all the strings in the language have two parts, $w$ and $x$, which are separated by the character $\#$, so you can easily tell which part of the string you're processing (just by keeping track of whether you've gone past the $\#$ or not).

Implicitly the strings $w$ and $x$ do not include the symbol $\#$, but the way it's written (at least in the question) this is not clear.

So, assuming that my interpretation is correct, a more explicit definition might be:

  Let $L$ be a language over $\Sigma\cup\{\#\}$, where $\# \notin \Sigma$ such that $$L = \{w\#x \mid w^{\mathcal{R}}\text{ is a substring of } x, \text{ and } w,x\in\Sigma^{\ast}\}$$


Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm For the following algorithm,

$X\leftarrow \{(i, n - i) | i = 1, ..., n- 1\}$
while $\max_{(a, b)\in X}b > 0$ do
$\quad X \leftarrow \{(|a - b|, \min\{a, b\})|(a, b) \in X\}$
return $\max_{(a, b)\in X}a$

show that the algorithm does not run in $o(n \log ^k n)$ for any constant $k$.
Summary: the algorithm uses the Euler's subtraction-based algorithm to compute the largest factor of $n$ in $1$ to $n - 1$.
My work: I can prove the upper bound case that $T(n) \in O(n^2)$. Since $n = (a + b)$ is strictly decreasing, gcd computation for each tuple takes at most $n$ operations. Since there are $n-1$ elements, $T(n) \in O(n^2)$.
I can also prove the lower bound case that $T(n) \in \Omega(n \log n)$. The best case for computing gcd of a single tuple occurs if $a = c_1 \cdot b$ or $b = c_2 \cdot a$ for $c_1, c_2 \in \mathbb{N}$. Then, the running time is $\Omega{\log n}$. Therefore, the total running time is $T(n) \in \Omega(n \log n)$.
My problem: But I don't know how to proceed from here. Basically, I need to prove $T(n) \in \Omega{(n^{1+\epsilon})}$ for $\epsilon > 0$. This means I need to prove something polynomial with the gcd computation of a single tuple.
Can anyone help me out with this problem?

It seems the algorithm tries to calculate n-1 gcd's simultaneously, and performs n-1 operations as long as one of the gcd's is not found. And since at least one gcd (gcd (n, 1)) takes n iterations, it is $\Theta (n^2)$.

Of course that is just due to the stupid implementation, but probably a good example for estimating the runtime of an algorithm, not the runtime of a problem.

You need to show that $n^2$ is not $o(n log^k n)$ for any k.


right and left derivatives of a cfg from parse tree? i just want to double check with what i concluded from this parse trees.

       A
      / \
     /   \
    B      C
   / \    / \
  0   D  D   E
         |   |
         0   1

from the above tree i get right derivation to be

  A -> C

  C -> D|E

  E -> 1

  D -> 0

and the left derivation as

  A -> B

  B -> 0|D

  D -> 0

i just want someone to proof check for me. and tell me if am wrong somewhere. Thanks!

What you wrote are not derivations, they are grammars.

The leftmost derivation in your case is $A \to BC \to 0DC \to 0DDE \to 0D0E \to 0D01$. I'll leave you to figure out the rightmost derivation.


Count-Min sketch: dyadic ranges Can anyone give me a proof as to why

  Any range over a unviverse {1...n} can be reduced to at most  $2log_2n$
  disjoint dyadic ranges?

Where a dyadic range is a range of the form $[x2^y+1....(x+1)2^y]$.

This is in reference to the method for answering range queries with a Count-Min Sketch as mentioned in the original paper on CM-sketches


Is the maximum coverage variant of Vertex Cover also NP-hard? In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible to it" in p.135.

  Given a set system G and a parameter k, Maximum Coverage Problem is to find k sets such that the elements covered is maximized, and Set Cover Problem is to identify the smallest size of sets so that all elements are covered.

I am curious about how this reduction is conducted?

Further, considering the Vertex Cover problem which is to find a cover with smallest number of vertices, can I reduce this problem to the following problem in the same way:

The problem of concern:

  Given a Graph and a parameter k, find k vertices such that the number of edges linked to these vertices is maximized.

Is this problem also NP hard?

Optimization problems cannot be NP-complete. Only decision problems – where the answer is YES or NO – can be NP-complete. This is because the notion of NP-completeness is defined only for decision problems. When we (loosely) say that an optimization problem is NP-complete, we really mean that their decision version is NP-complete.

The decision version of Set cover: given a set system $S$ with union $U$ and a number $r$, can we cover $U$ with $r$ sets from $S$?

The decision version of Maximum coverage is: given a set system $S$, a number $r$ and a number $t$, are there $r$ sets from $S$ that together cover at least $t$ elements?

See if you can prove that the decision version of Maximum coverage is NP-complete given that the decision version of Set cover is NP-complete, and then see if you can do the same for your new problem related to Vertex cover.

I should mention that Uri Feige proved in 1998 the following strong result regarding Maximum coverage. There is a polytime reduction $f$ taking a 3CNF $\varphi$ to an instance $(S,r,t)$ of Maximum coverage such that:

If $\varphi$ is satisfiable then there are $r$ sets from $S$ that together cover at least $t$ elements.
If $\varphi$ is not satisfiable then all choices of $r$ sets from $S$ cover at most $(1-1/e)t$ elements.

Informally, we say that it is NP-hard to approximate Maximum coverage up to $1-1/e$. Why?

A polytime algorithm $A$ for Maximum coverage is a $\theta$ approximation if given an instance $(S,r)$ with optimal value $O$, $A$ outputs a subset of $S$ of size $r$ that covers at least $\theta O$ elements. If there was a polytime $1-1/e+\epsilon$ approximation algorithm for Maximum coverage, for any $\epsilon > 0$, then you could use it to solve 3SAT, as follows:

Given $\varphi$, run $f$ and calculate the instance $(S,r,t)$.
Run $A$ on $(S,r)$, getting a cover which covers $B$ elements.
$\varphi$ is satisfiable iff $B > (1-1/e)t$.

I leave you to figure out why this works.

The approximation ratio $1-1/e$ is achieved by the greedy algorithm, so this result is optimal.


Teaching NP-completeness - Turing reductions vs Karp reductions I'm interested in the question of how best to teach NP-completeness to computer science majors.  In particular, should we teach it using Karp reductions or using Turing reductions?

I feel that the concepts of NP-completeness and reductions are something that every computer science major ought to learn.  However, when teaching NP-completeness, I've noticed that the use of Karp reductions has some downsides.

First of all, Karp reductions seem to be unnecessarily confusing for some students.  The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too".  That's very intuitive -- but it maps much better to Turing reductions than to Karp reductions.  As a result, I see students who are trying to prove NP-completeness get led astray by their intuition and form an incorrect proof.  Trying to teach both kinds of reductions and emphasizing this aspect of Karp reductions sometimes feels a little bit like needless formalism and takes up unnecessary class time and student attention on what feels like an inessential technical detail; it's not self-evident why we use this more restricted notion of reduction.

I do understand the difference between Karp reductions and Turing (Cook) reductions, and how they lead to different notions of NP-completeness.  I realize that Karp reductions give us a finer granularity of distinctions between complexity classes.  So, for serious study of complexity theory, Karp reductions are obviously the right tool.  But for computer science students who are just learning this and are never going to go into complexity theory, I'm uncertain whether this finer distinction is critical is critical for them to be exposed to.

Finally, as a student, I remember feeling puzzled when I ran across a problem like "tautology" -- e.g., given a boolean formula, check whether it is a tautology.  What was confusing was that this problem is clearly hard: any polynomial-time algorithm for it would imply that $P=NP$; and solving this problem is obviously as hard as solving the tautology problem.  However, even though intuitively tautology is as hard as satisfiability, tautology is not NP-hard.  Yes, I understand today why this is the case, but at the time I remember being puzzled by this.  (What went through my head once I finally understood was: Why do we draw this distinction between NP-hard and co-NP-hard, anyway?  That seems artificial and not very well-motivated by practice.  Why do we focus on NP rather than co-NP?  They seem equally natural.  From a practical perspective, co-NP-hardness seems to have essentially the same practical consequences as NP-hardness, so why do we get all hung up on this distinction?  Yes, I know the answers, but as a student, I remember this just made the subject feel more arcane and poorly motivated.)

So, my question is this.  When we teach NP-completeness to students, is it better to teach using Karp reductions or Turing reductions?  Has anyone tried teaching the concept of NP-completeness using Turing reductions?  If so, how did it go?  Would there be any non-obvious pitfalls or disadvantages if we taught the concepts using Turing reductions, and skipped the conceptual issues associated with Karp reductions?

Related: see here and here, which mentions that the reason why we use Karp reductions in the literature is because it enables us to distinguish between NP-hardness and co-NP-hardness.  However, it does not seem to give any answer that's focused on a pedagogical perspective of whether this ability is critical for the learning objectives of an algorithms class that should be taken by every CS major.  See also here on cstheory.SE, which has a similar discussion.

I would say very definitely teach using Karp (many-one) reductions. Regardless of the benefits of using poly-time Turing reductions (Cook), Karp reductions are the standard model.

Everybody uses Karp and the main pitfall of teaching Cook is that you'll end up with a whole class of students who become pathologically confused whenever they read a textbook or try to discuss the subject with anyone who wasn't taught by you.

I agree that Cook reductions are in several ways more sensible and that there's no distinction between NP-hardness and coNP-hardness in practical terms, in the sense that they both mean "This problem is pretty hard and you're not going to get a general, efficient, exact algorithm that can cope with large instances." On the other hand, the distinction between NP and coNP isn't entirely an artifact of a theory based on Karp reductions: you don't often talk about graphs that are non-3-colourability or in which every set of $k$ vertices contains at least one edge. Somehow, the "natural" version of the problem often seems to be in NP rather than coNP.


Do the polynomials in "polynomial time" have integer, real or complex coefficients? This is probably a very basic question but do the polynomials in "polynomial time" have integer, real or complex coefficients?

Everywhere I looked it just says "polynomial expression". I am guessing the polynomial must have integer coefficients?

When people say polynomial time, they mean that the time has polynomial growth, that is if we denote the time by $T(n)$, then $T(n) = O(n^c)$ for some real $c$. We get the same definition if we only allow integer $c$. Since $T(n)$ is real-valued, it wouldn't make sense to consider complex polynomials here.

The exact running time need not actually be a polynomial. For example, an algorithm running in time $n\log n$ (exactly) still runs in polynomial time, since (for example) $n\log n = O(n^2)$.


Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays A homework problem in my current CS class asks us to produce a comparison-based procedure for taking (essentially—there are some poorly-specified rules about duplicates) the set intersection of $k$ unsorted arrays of at most $n$ elements each. For full credit, we are supposed to do this in $O((k-1)n)$ comparisons. (Specifically, we are given a Java array of arrays of Comparable elements.)
I'm pretty thoroughly convinced that this is impossible, and that the best worst-case comparison bound for such a procedure is $\Theta(N\log n_0)$, where $N$ is the sum of the lengths of the arrays and $n_0$ is the length of the shortest array. I don't, however, know how to prove this is the best.
Since producing such an algorithm is current homework, please adhere to the following restriction in your answers/comments: if I am wrong, and it is possible to do better, do not reveal the algorithm unless it is very difficult (in which case a link to a relevant paper would be appreciated).
What I've tried so far
The shortest array has $2^{n_0}$ subsets. This gives an immediate information-theoretic lower bound of $\Omega(\log_2(2^{n_0}))$. Unfortunately, this is just $\Omega(n_0)$, and $O(n_0)$ obviously can't be obtained.
Edit
I missed a line in the (rather long) assignment. It looks like what he's looking for is actually a lot less interesting than what I thought he wanted. However, I'm still curious about how to prove a lower bound of $\Omega(N \log n_0)$, if that is the lower bound.

I think we can prove that $O(n)$ time is not attainable for the special case $k=2$, using an adversary argument.

Fix a constant $c>0$.  Let's take two lists of $n$ items, where the resulting $2n$ items are all different.  Consider an algorithm that has done $cn$ comparisons between the $2n$ items in the two lists.  This defines a partial order $\preceq$ on the $2n$ items, where if the algorithm has compared $x,y$, we have either $x \prec y$ or $y \prec x$, and where we let $\preceq$ be the reflexive, antisymmetric, transitive closure of $\prec$.

I'm pretty sure that, with high probability over the choice of the lists, there exists some item $x$ in the first list and some item $y$ in the second list such that $x,y$ are incomparable under $\preceq$.  (This needs proof; I'll let you fill this part in.)

Now we can consider a parallel universe where everything is exactly the same as before, except that in the alternate universe, $y=x$.  This alternate universe is also compatible with all of the comparisons that have been made by the algorithm.  Thus, the algorithm cannot distinguish these two universes, so it must produce the same output in both cases.

However, the correct output for the two universes differs.  The correct output in the first universe is the empty set, while the correct output in the second universe is the element $\{x\}$.  Consequently, the algorithm must be incorrect in at least one of these two universes.  In other words, for at least one of these two inputs, the algorithm produces the wrong output.

It follows that, when $k=2$, any $O(n)$-time algorithm must produce an incorrect answer on at least one input.  In other words, any correct algorithm must take $\omega(n)$ time.


Number of nonnegative solutions of linear Diophantine inequality Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it.

Is there exists algorithm which run in polynomial time? For example if $A \le 10^{10}, B \le 10^{10}$ it should work less than a second. Thanks in advance.

I've found a paper for you (however it's about more general case).

Welcome to the site!


Time-complexity for basic multiplication and division algorithms The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen.

p.253 says that "number of shifts required is $O(n^2)$" and "a total of $O(n^2)$ additions of bits are required for all n additions".

Why isn't this algorithm $O(n)$? I can see only two non-nested for loops.

p.254 says that "this means that we need $O(n^2)$ bit operations to find the quotient and remainder when a is divided by d".

Why isn't this algorithm $O(n)$? I can see only one while loop.

The one loop that you see is for number of additions. But it is also assuming number of bits to be to the order of n. For one iteration, you will perform operation over O(n) bits. For n iterations, it will be to the order of n squared.


Language of words whose run lengths are all distinct Assume $ \Sigma=\{0,1\}$, is $L$ a regular language? If it is not, how should we prove it with pumping lemma?

  $$L = \{1^{a_1} 0^{a_2}\ldots 01^{a_k} \mid k \in \mathbb N , a_i \geq 0 , \text{ the $a_i$ are all different}\}  $$

The definition of your language is not completely clear, but whatever it is, if you consider
$$ L \cap 1^* 0^* = \{ 1^a 0^b \mid a \neq b \} $$
then you immediately see that $L$ is not regular.

If you have to prove it using the pumping lemma, then simply take a proof that works for the above language; it will work for $L$ as well.


show that NP is a subset of decidable languages More specifically the problem says: "Let us call the set of decidable languages D. Show that NP ⊆ D"
My problem is that I always assumed that NP is decidable, but to prove it, I never thought it
Somebody have any idea about how do it? or start resolving it?
I think I can prove it saying something like the NP problems effectively end in a polynomial time (although not deterministic) so there must be a MT-ND that accepts it and always ends, I suposse

Every language that is in NP is by definition decidable. Becase if a language L is in NP, than there is a nondeterministic Turing Machine that decides it in polynomial time, and thus L is decidable.


Length of shortest codeword in Huffman encoding Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1?

I thought of 2 cases where this might be true, but they're not exactly proofs -

Case 1: There is only one character which occurs more than 1/3rd of the time. In this case, a good huffman encoding scheme will ensure that this character corresponds to a single-character encoding, because there are no competing characters. Even though there may be characters that occur with high probability (but still less than 0.33), they must have length greater than 1 to ensure the prefix-free nature of the encoding.

Case 2: There are multiple characters that occur more than 33% of the time. We can also make the stronger assertion that in this case, there can only be at most 2 such characters. This can be further subdivided into cases where 1) there are a total of 2 characters in the encoding scheme, and 2) where there are more than 2 characters in the scheme. In case 1), both the characters can correspond to a single-character encoding scheme (0 and 1 for each respectively). In case 2), at most 1 of the 2 largely prevalent/frequent characters must have an encoding of length of 1  (since we're considering a good huffman encoding scheme) while the other n-1 characters have a length of at least 2.

I'm afraid that this is not the right approach. Could someone please help me out?

Consider the distribution $\Pr[a]=0.34,\Pr[b]=\Pr[c]=\Pr[d]=0.22$.

Huffman's algorithm will first merge (say) $c$ and $d$ to create the symbol $cd$ with probability $0.44$. It will then merge $a$ and $b$ to create the symbol $ab$ with probability $0.56$. Finally, it will merge the remaining symbols.

All codewords thus have length 2.

You can check that the same example works up to $\Pr[a] = 0.4$ (we need $\Pr[a] \leq 2\Pr[b] = (2/3)(1-\Pr[a])$). What if $\Pr[a] > 0.4$? Consider the time at which Huffman's algorithm merges $a$ with some symbol $X$ (which may be composed of several original symbols). If $a$ and $X$ are the only symbols, then $a$ will be encoded using a symbol of length 1. Otherwise, there is some other symbol $Y$ of probability at least $\max(\Pr[a],\Pr[X]) > 0.4$. We see that $a,X,Y$ must be the only remaining symbols, and furthermore $\Pr[a] > \Pr[X]$ (otherwise there would 3 symbols whose probability exceeds 0.4).

Suppose that $Y$ was obtained by merging two other symbols $Z,W$. At that point, since $X$ itself or one of its constituents wasn't merged, we must have $\Pr[X] \geq \max(\Pr[Z],\Pr[W]) \geq \Pr[Y]/2$. But $\Pr[Y] > 0.4$ and so $\Pr[X] > 0.2$, and so the probabilities sum up to more than 1. This contradiction shows that $Y$ is an original symbol, and so in this case there is a codeword of length 1.

Concluding, the threshold for guaranteeing a codeword of length 1 is 0.4.


Optimal way to find maximal sum (with constraints) of array elements Problem: Find the maximum sum of the elements in an array, with the following constraints:

all the elements of the array are non-negative integers
each element can either be left out completely from the sum (skipped), can be added, or can be subtracted from the sum
when reading the array left to right (i.e. from index 0 to index size - 1), the sequence of operations must be subtract, add, subtract, add, ... etc, with optional skips in between (e.g. subtract, skip, skip, add, subtract, skip, add)
in other words: the first element included in the sum must be subtracted, the next element included into the sum must be added, the next subtracted, etc... (i.e. we always start with subtraction).

Example: Suppose we have the following array: [1, 2, 3, 4, 5].

Then the sums following is valid:

-1 + 2 -3 +4 -5

-1 + 0 + 3 -4 +5

-1 + 0 + 0 + 0 + 0

0 -2 + 0 + 0 + 5

0 + 0 + 0 + 0 -5

0 + 0 + 0 + 0 + 0

Some invalid sums:

+1 -2 +3 -4 +5  // We did not start with subtraction (+1)

-1 -2 +3 -4 +5  // Two consecutive subtractions (-1 -2)

-1 +2 +0 +4 -5  // Two consecutive additions (+2 +4).

My solution: There are 2^N possible valid sums (where N is the size of the array), since if we read the array left to right, each element can either be included into the sum or not.
For each of these cases, let's calculate the sum that we get, and choose the minimum of those sums.

Pseudo code of my solution:

func findMax(a []) {
    max := 0;
    for (i := 0; i < 2 ^ a.size; ++i) {
        code := i;       // binary representation of the next possibility
                        // 0: we do nothing
                        // 1: we add or remove the next element
        sum := 0;
        sign := -1;
        for (j := 0; j < a.size; ++j) {
            if (code[j] == 1) {    // jth digit of code
                sum := sum + sign * a[j];
                // if (sum < 0) { goto end } // (1) would this help?
                sign := -sign;
            }
        }
        if (sum > max) {
            max = sum;
        }
end:
    }
    return max;
}

Optimization This solution has exponential run-time complexity in the size of the array, therefore I was asking myself how to optimize it. The only idea I have is to backtrack (i.e., don't continue the calculation for a given case), whenever the partial sum becomes negative (see commented out line (1) in the pseudo code). However, I'm not sure that a.) this could not weed out in some way the maximum we are looking for (although I can't think of any counter examples) and b.) that there other, even more efficient ways to backtrack.

Questions

1.) Is there an example, where back-tracking upon encountering a negative partial sum (i.e. the solution suggested at line (1)) would prevent us from finding the real maximum sum?

2.) Is there some even better way to back-track?

3.) What other approaches exist for this problem?

This is a classic Dynamic Programming problem. Basically, dynamic programming is a way of turning a recursive algorithm into an iterative one with better runtime, by saving previous results that we might need again.

In this case, we can write the problem as two recursive functions:

maxSumSubtractFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Two options: take whichever is better
        -A[startIndex] + maxSumAddFirst(startIndex+1), # Use this one
        maxSumSubtractFirst(startIndex+1) # Skip this one
    )

maxSumAddFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Same as above
        A[startIndex] + maxSumSubtractFirst(startIndex+1),
        maxSumAddFirst(startIndex+1)
    )

In other words, we have two choices for each element: either include it (and flip the sign for the next one), or skip it (and keep the sign the same).

Now, we could run maxSumSubtractFirst(0) and get the answer that way, but this could take $O(2^n)$ in the worst case. We can do better.

Since each function will always return the same output given the same input, we can make two arrays the same length as our input, then store the results of maxSumSubtractFirst in one, and maxSumAddFirst in the other. If we start from the end (the largest index) and work backward, we'll never have to recurse at all: just look up the results in the array, which takes $O(1)$.

Now we can take the first element in the maxSumSubtractFirst array, and that's our answer. We've only had to call each function $n$ times, and each call takes $O(1)$, so this version of the algorithm runs in $O(n)$—a significant improvement over $O(2^n)$!

(Note that, as written, this only gets you the value of the sum, not the sequence of choices that led to it. But that's easy to change: make additional arrays to hold the choices, and fill them in with each call to maxSum*First.)


Lower bound on $1^k+2^k+\dots+n^k$ I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.)

Now I want to find a lower bound on the expression I got. Specifically, I want to prove that

$$ 1^k + 2^k + \dots + n^k = \Omega(n^{k+1}). $$

You can estimate your sum from below by
$$
1^k + \cdots + n^k \geq \sum_{m=\lceil n/2 \rceil}^n n^k \geq \frac{n}{2} \cdot \left(\frac{n}{2}\right)^k = \Omega(n^{k+1}).
$$
It is even easier to see that $1^k + \cdots + n^k \leq n^{k+1}$, and so $1^k + \cdots + n^k = \Theta(n^{k+1})$.

You can get better bounds by approximating the sum with an integral:
$$
\frac{n^{k+1}}{k+1} = \int_0^n x^k \, dx \leq 1^k + \cdots + n^k \leq\int_1^{n+1} x^k \, dx = \frac{(n+1)^{k+1}-1}{k+1}.
$$
This shows that
$$
1^k + \cdots + n^k = \frac{n^{k+1}}{k+1} + O(n^k).
$$

There is also an exact formula, known as Faulhaber's formula.


Leveling array values with the smallest move I'm not an expert of the theory of algorithm, so please forgive me if this problem is nonsense, but I want to find good algorithm to solve below problem.

There is a array of integer each of which has been assigned with random initial value such like [1,5,-3,4] or [123, 543, 295, -703, …]

You move values from one element of the array to another to achieve smaller variance. For [1,5,-3,4], the trivial final state is  [2,2,2,1].

There is a constraint. The total amount of moving distance should be as small as possible. There are many paths to move [1,5,-3,4] to [2,2,2,1], but the following way should be worse one:

move 1 from the fourth element to the first one.

[1,5,-3,4] -> [2,5,-3,3] (distance = 1 * 3)

move 3 from the second element to the third one.

[2,5,-3,3] -> [2,2,0,3] (distance = 3 * 1)

move 3 from the fourth element to the third one.

[2,2,0,3] -> [2,2,2,1] (distance = 2 * 1)

(total distance: 8)

because there is shorter (better) way to achieve this:

move 3 from the fourth element to the third one.

[1,5,-3,4] -> [1,5,-1,2] (distance = 2 * 1)

move 2 from the second element to the third one.

[1,5,-1,2] -> [1,3,1,2] (distance = 2 * 1)

move 2 from the fourth element to the third one.

[2,2,0,3] -> [2,2,2,1] (distance = 2 * 1)

(total distance 6)

What is the algorithm which can find the shortest path to level values of array?

Your problem seems to be the same as that of calculating the Earth mover distance between the starting and target distributions. Wikipedia suggests using the Hungarian algorithm to calculate the distance.


Express a number as a sum of consecutive primes (How many ways?) I found this problem on codeforces in an ACM archive.

Given a number $n$, find the number possible of ways of expressing that number as a sum of consecutive primes. Example :

Given $n = 41$:

$41 = 41 =  2 +5+3 +7 + 11 + 13 = 11 + 13 + 17$

As we can see, there are three ways of writing $41$ as a sum of consecutive primes, keeping in mind that since $41$ is a prime, a sum that consists of only $41$ is a valid sum as well.

Knowing that $n \leq 10000$, list the number of ways you can express the input numbers as sums of consecutive primes.

My effort regarding this problem consists of the following :

Given that the max $n $ is $10000 $, I populated a vector of primes using the sieve of eratosthenes (its size is precisely $1229$).

Following, I computed a vector of prefix sums, such that at index $p$ of that particular vector, we have the sum of all consecutive primes up to inclusively $p$ (non prime indexed entries are equal to $0$).

For example: $\text{prime_sums[2] = 2 }, \text{ prime_sums[3] =5 },\text{ prime_sums[5] = 10}$, etc.

Now, using this particular vector we could simply do traversals of the  sum array for each of the input numbers and upon finding a way to write it as a sum (by comparing its value with that of each sum we encounter) , we would do multiple subtractions between elements of the sum array in order to find other possible ways to express our number as a sum of consecutive primes.

But this kills the speed of the program and feels really inelegant and awkward. Can you suggest alternative ways?

I assume that n is large, and that we only want the answer for one single n. In that case, we would avoid creating a sieve of all the primes up to n, if possible, because it would take O (n); I think we can do this faster.

Create a list of all primes p ≤ M, using a sieve, with a cleverly chosen M. This takes about O (M) and finds about $M / \ln M$ primes. Then we find all solutions involving primes up to M by adding up primes starting with p = 2 until the sum is ≥ n, recording a solution if the sum equals n, removing the first primes until the sum is < n, adding primes until the sum is ≥ n etc. This only takes O ($M / \ln M)$ which is less than O (M) for the sieve, so we can ignore it.

This part of the algorithm finishes when we would need to add a prime p > M
to the list (which we don't have). At that point we know that the sum of the K largest primes ≤ M is less than s, for some K, and that we have found every possible way to write n as the sum of more than K primes. Now we have to find ways to write n as the sum of k ≤ K consecutive primes; in addition k is odd if n is odd, and k is even if n is even.

For every k, we do this by creating a sieve of primes around n / k; this sieve should be large enough to contain more than k primes. When we have the sieve, we find the first k/2 primes > n/k and k - k/2 primes ≤ n/k. If the sum is less than n then we add the next larger prime and remove the smallest one until the sum is ≥ n; if the sum is > n then we add the next smaller prime and remove the next larger one until the sum is ≤ n. If the sieve turns out to be to small we create a bigger one. If the sum is n, we have a solution.

Creating the sieve takes at least O ($(n/k)^{1/2} / \log n$) steps for trial divisions. Instead of creating the sieve around n/k, we could have made the original sieve larger, choosing M ≈ n / (k - 2) instead of M ≈ n / k, which would have cost about $n / k^2$ steps.

Both costs balance when $n / k^2 = (n/k)^{1/2} / \log n$ or $n^{1/2} = k^{3/2} / \log n$ or $n \log^2 n = k^3$ or $k = (n \log^2 n)^{1/3}$ or $M = n/k = (n \div \log n)^{2/3}$

The estimate for creating the small sieves may have been a bit generous; if we use this method with $M = n^{2/3}$ then it should run in $O (n^{2/3})$.


What is the difference in time-complexity for sorting these 2-d arrays? Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements

Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements.

It is given that each row is sorted in ascending order,
Can you sort each of these in $O(n\log(n))$ or better using comparison sort?

I'm leaning towards k-way merge implementing a min-heap following this implementation merging sorted arrays, but I can't seem to figure out what the difference between this cases is.

$B$ for example will have $10$ elements constantly in the min-heap, so the time complexity will be $10n \log(10) \in O(n)$? Is this even possible in comparison sorts?

While $A$ would have $n/10$ elements in the min-heap, but are the run times equivalent?

The algorithm you suggest for $B$ is a comparison-based algorithm with complexity $O(n \log h)$, where $h$ is the maximum number of elements in the heap. Since $h = \Theta(1)$, you have that $B$ can be sorted in time $O(n)$.

Regarding $A$, the lower bound of $\Omega(m \log m)$ on any comparison-based algorithm that sorts $m$ elements still applies. Indeed, the first elements on each row (i.e., those of the first column) can be in any order relation with one another.

Any algorithm that sorts $A$, is also an algorithm that sorts the $m = \frac{n}{10} = \Theta(n)$ elements in the first column, and therefore it must have time $\Omega(m \log m) = \Omega(n \log n)$.


Number of ways to choose same number of elements from two different sets Given two sets of elements S and R, with p elements and q elements respectively. 1 <= p,q <= n. Now, the number of ways to choose same number of elements from set S and R is $$\sum_{i=0}^{\min(p, q)} pCi * qCi$$. I want to calculate the result for all possible combinations of p and q. I can think of a O(n^3) solution by first calculating all the mCr values for all possible combinations of m and r. And then for each pair of (p, q) answer is the sum of products of the pre-calculated terms. Is there any way to do it within O(n^2) time?

Sometimes a summation of products of binomial coefficients can be simplified using  Vandermonde's identity.

In your case, Assuming $p\ge q$ we have $\sum^q_{k=0}{p\choose k}{q\choose k}=\sum^q_{k=0}{p\choose k}{q\choose q−k}$, which by Vandermonde equals $p+q\choose q$.

Actually this equality can be understood with elementary combinatorial arguments. Put the $p+q$ elements in one box. Now grabbing $q$ elements from the box means you have selected some $i$ elements from $S$ and $q−i$ elements from $R$. Or unselected $i$ elements from $R$ which is the same.


Optimal strategy in repeated cake-cutting Alice and Bob play the famous game of divide and choose $n$ times with $n$ identical cakes. Each time, Alice cuts the cake to two pieces, and Bob chooses the piece he prefers. Alice does not know Bob's preferences, but she assumes that they come from a uniform distribution.

What is the strategy that maximizes Alice's expected total value?

Here is my solution so far.

Let's assume that the cake is the interval $[0,1]$. Alice cuts the cake by choosing some  $x\in [0,1]$. Let $h\in[0,1]$ be a point such that Bob is indifferent between the cake to the left of $h$ and the cake to the right of $h$. Let $V(x)$ be Alice's valuation of the interval $[0,x]$; it is a continuous and increasing function of $x$. Then:

If $h> x$, then Bob picks $[x,1]$ and Alice gets $[0,x]$ and gains $V(x)$.
If $h< x$, then Bob picks $[0,x]$ and Alice gets $[x,1]$ and gains $V(1)-V(x)$.
If $h=x$ then, let's say Bob picks a piece at random  so Alice gains on average $V(1)/2$.

If Alice knows $h$, then she has a simple optimal strategy:

If $V(h) > V(1)-V(h)$, then select $x^* = h-\epsilon$, for some $\epsilon>0$, and gain $\approx V(h)$.
Otherwise, select $x^* = h+\epsilon$, for some $\epsilon>0$, and gain $\approx V(1)-V(h)$.

Initially, Alice does not know $h$, so she assumes it is distributed uniformly in $[0,1]$. If Alice cuts at $x$ and Bob chooses left, this tells Alice that $h\in[0,x]$; if Bob chooses right, this tells Alice that $h\in[x,1]$. So, using binary search, Alice can estimate $h$ to an arbitrary precision. This seems to be an optimal strategy when $n\to\infty$: spend a lot of rounds initially for getting an accurate estimate of $h$, and use this estimate from then on to get the optimal possible value.

I am stuck at the case where $n$ is finite and small. The question bogs me even for $n=2$: what is the optimal first cut?

Let $v(x) = \frac{V(x) - V(0)}{V(1) - V(0)}$ so $v(x)$ nicely goes from $0$ to $1$. Maximizing $v$ also maximizes $V$. To cover my ass for future mistakes regarding $<$ vs $\leq$, I will assume that you will never exactly guess $x = h$.

Now, if $n = 1$, we can find the expected value from cutting at $x$ by integrating over all possible $h$:

$$e_1(x) = E[v(x)] = \int_0^x (1 - v(x))dh + \int_x^1 v(x)dh = (1 - 2x)v(x) + x$$

Which allows you to maximize $e_1$ with differentiation to find the optimal $x$. Note that in the above example "all possible $h$" meant $[0, 1]$. But what if we know that $h \in [a, b]$ due to previous information?

Then we get the following sum of integrals for when also $x \in [a, b]$:

$$\int_a^x (1 - v(x))dh + \int_x^b v(x)dh = (a + b - 2x)v(x) - a + x$$

Which makes the total expected valuation:

$$e_{1,a,b}(x) = E[v(x) | a \leq h \leq b] = \begin{cases}
v(x) & \text{if $x < a$}\\
(a + b - 2x)v(x) - a + x & \text{if $a \leq x \leq b$}\\
1 - v(x) &\text{if $x > b$}
\end{cases}$$

Now let's analyze $n = 2$. Suppose our first cut is at $x$, then there is a $x$ chance $h \leq x$ and $1 - x$ chance $h \geq x$. In both those scenarios we will then choose our best possible $y$. This gives equation:

$$e_2(x) = e_1(x) + x\left( \max_{0 \leq y \leq 1} e_{1,0,x}(y)\right) + (1-x)\left( \max_{0 \leq y \leq 1} e_{1,x,1}(y)\right)$$

$$\max_{0 \leq y \leq 1} e_{1,0,x}(y) = \max\left(\max_{0 \leq y \leq x} ((x - 2y)v(y) + y), \max_{x \leq y \leq 1} (1 - v(y))\right)$$

$$\max_{0 \leq y \leq 1} e_{1,x,1}(y) = \max\left(\max_{0 \leq y \leq x} v(y), \max_{x \leq y \leq 1} ((x + 1 - 2y)v(y) - x + y)\right)$$

Now let's say $v(x) = x$, a simple linear increase in desire for more cake. Now we can actually solve:

$$\max_{0 \leq y \leq 1} e_{1,0,x}(y) = \max\left(\begin{cases}x(1-x)&0\leq x \leq \frac{1}{3}\\\frac{1}{8}(x+1)^2&\frac{1}{3} \leq x \leq 1\end{cases}, 1 - x\right)$$

$$\max_{0 \leq y \leq 1} e_{1,x,1}(y) = \max\left(x, \begin{cases}\frac{1}{8}(x-2)^2&0\leq x \leq \frac{2}{3}\\x(1-x)&\frac{2}{3} \leq x \leq 1\end{cases}\right)$$

Now $e_2$ is complicated, but is essentially a piecewise function which can be solved.


Chomsky NF or Greibach NF benefits for LR parser? Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind:

total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating action table),
the size of action/goto table (in total)
is there any "side-effect" of removing some of shift-reduce conflicts

?

The point of generating a parser (usually) is to parse: "Analyse (a string or text) into logical syntactic components" (some online dictionary). That's different from simply recognizing that a text is a member of a language. A given language has a variety of grammars which will recognize its sentences, but typically there is a specific grammar which defines the "logical syntactic components" and their relationship to each other, as in the above definition. In real-world applications -- compilers, for example -- one expects an output which is more interesting than simply "the input is/is not a valid program".

In some cases, it is possible to recover the original parse tree from the parse tree generated by parsing a transformed grammar. (This is true for CNF, with the usual transformation strategy.) In other cases (such as GNF, as far as I know), it is annoyingly difficult, making such a transformation of limited use for parsing (as opposed to recognition).

Also, not all grammar transformations preserve LR(k)-ness. In particular, the usual CNF transformation involves refactoring of every production into a series of rules with precisely two non-terminals. This often has the effect of converting an LR(1) grammar into a grammar which is not LR(k) for any k. So that's not much help, either.


Getting from one language to the other using closure properties(automata) I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$$

Such that:

$m,n,o \geq 1;$

$m>n>o>0;$

$i_1,i_2,...,i_{2m} \geq 0;$

$j_1,j_2,...,j_{2n} \geq 0;$

$k_1,k_2,...,k_o \geq 0$

this language is also: $$L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$$

My attempt: basically, they both look very similar, but I am not sure the coming procedure is correct:  If we take $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$, Unionize bc, ef and hq to obtain the following: $L=\left\{aB^{i_{2m}^*}dE^{j_{2n}^*}gH^{k_o^*}\right\}$, And then using assignment or homomorphism, defining $h:B^{i_{2m}^*} -> 0^{i_{2m}^*}$, $h:E^{i_{2n}^*} -> 1^{j_{2n}^*}$ , $h:H^{k_o^*} -> 2^{k^*_o}$ obtaining: $L=\left\{a0^{i_{2m}^*}d1^{j_{2n}^*}g2^{k^*_o}\right\}$. Since we can decompose string S using the pumping lemma into $S=uvxyz$ as we choose, We can only regard the $0^{i_{2m}^*}1^{j_{2n}^*}2^{k^*_o}$ part. Because of that, And knowing in advance that $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$ is not context free, we can deduct that $L=\left\{a0^{i^*_{2m}}d1^{j^*_{2n}}g2^{k^*_o}\right\}$ is not context free as well.

Would really appreciate your corrections or knowing if there exists a better and easier way to deduct that.

Thank you very much.

If I understand your argument correctly, you are reducing languages in the wrong direction.

  If $L$ is not context-free, then $K$ is not context-free.

Is equivalent to

  If $K$ is context-free, then $L$ is context-free.

We have to reverse the construction, as we are using the closure properties of the context-free languages. In do not know of any useful closure properties of the non-context-free languages.

PS. The pumping argument seems out of place here.


Why do the following algorithms for Quadratic Primes perform so differently? I'm trying to solve for https://projecteuler.net/problem=27, and I have to optimize one part of the implementation from slow() to fast(). Why do they perform so differently? I'm guessing branch predictions, but I don't quite understand how they are different to the optimizer. The code is in javascript.
function primes(n) {
    const P = new Array(n).fill(1)
    P[0] = 0
    P[1] = 0
    for (let i = 2; i <= n; i++) {
        for (let j = 2*i; j <= n; j += i) {
            P[j] = 0
        }
    }
    return P
}
const P = primes(1_000_000)

function slow(a, b) {
    for (let i = 0; ; i++) {
        if (P[i*i+a*i+b] == 0) {
            return i - 1 // the reason why it's slow is probably because of the fork-away of return inside the loop.
        }
    }
}

function fast(a, b) {
    let i
    for (i = 0; P[i*i+a*i+b] == 1; i++) {}
    return i // so this optimization works as long as we only need 1 index value
}

function qp(n, algo = npc) {
    let max = 0
    let maxa, maxb
    for (let a = -n; a <= n; a++) {
        for (let b = -n; b <= n; b++) {
            // here's the trick. CPU can optimize if it can SOMEHOW predict the branch pattern, which probably goes all the way false.
            // if we write npa(), we are nesting another loop-branch within, and then CPU refuses to take a guess on the outer loop.
            const i = algo(a, b)
            if (i > max) {
                max = i
                maxa = a
                maxb = b
            }
        }
    }
    return [maxa, maxb]
}

// pretty much that same:
fast(-61, 971)
slow(-61, 971)

// huge difference:
qp(200, fast)
qp(200, slow)

Here are some benchmarks in chromium:
     |   n |  time
slow | 100 |   165
     | 200 |  1090
     | 400 | 10176
fast | 100 |    12
     | 200 |    27
     | 400 |    99

Well, I finally find out I'm just writing bad code that results in too many computations.
The condition in slow() should be P[i*i+a*i+b] != 1 instead of P[..] == 0 because there are cases when the index is smaller than 0.


Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity Problem Statement:
Suppose we have a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string.
I tried to achieve this with O(1) complexity.

I am looking for a algorithm to implement above scenario. I implemented this problem with below algo, but I feel that we can improve its complexity. Any suggestion will be helpful.

Algorithm:

Here is trick to utilise hash code, we can also use character histogram.

Step 1:Create an array of prime numbers.

   int primes[] = {2, 3, 5, 7, ...};

   We are using prime number to avoid false collisions.

Step 2:Create a method to calculate hash code of a word\string.

   int getHashCode(String str){
     int hash = 31;
     for(i =0 to length of str){
        hash = hash*primes['a' - str.charAt[i]];
     }
     return hash;
   }

Step 3: Now store all words in a HashMap.

void loadDictionary(String[] words){

  for( word from words for i = 0 to length of words)   {
     int hash  = getHashCode(word);
     List<String> anagrams = dictionary.get(hash);
     if(anagrams ! = null){
         anagrams.add(word);
     } else
        List<String> newAnagrams = new ArrayList<String>();
        newAnagrams.add(word);
        dictionary.put(hash, newAnagrams);
     }
  }
}

Step 4: Now here is the approach to find anagrams:

   int findNumberOfAnagrams(String str){
      List<String> anagrams = dictionary.get(getHashCode(str));
      return anagrams.size();
   }

You may get some inspiration from the articles The world's fastest scrabble program by Andrew W. Appel and A Faster Scrabble Move Generation
Algorithm by Steven A. Gordon.
Both algorithms rely on a clever use of finite automata.

See also this question on Stackoverflow.


Cell walls in Conway's Game of Life? Do there exist robust structures in Conway's Game of Life?  For instance, has anyone constructed a spaceship with a shield that absorbs all small oscillators and gliders it collides with?

See "eaters" category.

They can absorbe gliders and spaceships, but I'm not an expert and I don't know if there are "walls" capable of absorbing everything. Perhaps it is a nice subject to investigate! (see the references at the bottom of Wikipedia pages for modern approaches using constraint solvers).

From the lexicon:

:eater Any still life that has the ability to interact with certain patterns without suffering any permanent damage. (If it doesn't suffer even temporary damage then it may be referred to as a rock.) The eater1 is a very common eater, and the term "eater" is often used specifically for this object. Other eaters include eater2, eater3, eater4 and even the humble block. (In fact the block was the first known eater, being found capable of eating beehives from a queen bee.) Another useful eater is shown below, feasting on a glider.


Is there another type of list than arraylist and linked-list? My question is not about how arraylists or linked-lists work, but why there aren't other types of lists.
From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to use property for your list or not to.
In the case of a arraylist, you know where an item lies by looking where the element at index 0 is and then adding element-index x item-size, so you have constant access time.
For the case of a linked-list, you don't use the structure of memory and need to follow a sequence of pointers, but rearranging the list is easy.
Does this already explain why these 2 types of lists are all that's possible? Or is there another non-existence proof? Are there other types of lists I just don't know of yet?

Yes, there are many types of lists depending on the arrangement of objects and the complexity of different types of operations. For example:

Binary Tree or d-ary tree is a hierarchical structure that stores nodes in the form of parent and child nodes.

Directed or Undirected Graph can be represented using adjacency list data structure which represents all possible connections between a set of objects. In other words, it is an array of lists.

Doubly Connected Edge List is used for performing fast operations on planar graphs and 3-dimensional polytopes.

Skip List is a randomized data structure that provides $O(\log n)$ insertion in a linked list

Likewise, you can even design your own data-structure based on different requirements. It is all about how you arrange and connect the objects.


Recursive type encoding on System F (and other pure type systems) I am studying pure type systems, particularly the calculus of constructions, and trying to use an encoding for recursive types on it, which, according to Philip Wadler, is possible. As an example, I'm using the Morte Haskell library to encode Scott numerals as given by Cardelli.
A summary of the encoding is as such: given a (positive) recursive type...
$$\mu X.F\ X$$
...we may encode it as a type on System F as...
$$Lfix\ X.F\ X\ =\ \Lambda X.(F\ X\rightarrow X)\rightarrow X$$
...or, using pure type systems' notation (with an explicit $F$)...
$$Lfix\ =\ \Pi F: *\rightarrow*.\Pi X: *.(F\ X\rightarrow X)\rightarrow X$$
...since $F$ is a type constructor ($*$ is the type of types).
In order to encode such, we need to declare three functions, $fold$, $in$ and $out$, according to Wadler, and used by Cardelli on the encoding for Scott numerals.

fold  :  All X. (F X -> X) -> T -> X
fold  =  \X. \k: F X -> X. \t:T. t X k
in    :  F T -> T
in    =  \s: F T. \X. \k: F X -> X. k (F (fold X k) s).

(Where $T$ is $Lfix\ X. F\ X$.)
It's trivial to write the $fold$ function as given. But when trying to write the $in$ function, it doesn't seem to typecheck. The expression $(fold\ X\ k)$ has type $T\rightarrow X$, and $(F\ (fold\ X\ k)\ s)$ should be of type $F\ X$. Then we infer that $F$ should be of type $(T\rightarrow X)\rightarrow F\ T\rightarrow F\ X$ (looks like a fmap). This doesn't typecheck, because F is a type constructor (of type $*\rightarrow*$).
This doesn't look like a typo... am I missing something?

There is a convention in category theory that the same symbol is used for a type constructor and the map function over that type constructor. Hence, if f : X -> Y then F f : F X -> F Y.


Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw? Basically what the title says. Why can you "ignore" the "xy" part if you want to prove whether a language is regular?

Both pumping lemmas have an intuitive explanation in terms of an automaton that can recognize a language.

A regular language can be recognized by a finite automaton. All words are recognized through:

either a finite path through the automaton: words that are shorter than the pumping length;
or a path that goes through a node at which there is a loop, in which case it is possible to go through the loop any number of times: that's the $y^n$ part, where $y$ is the path through one round of the loop and $n$ is the number of lops.

A context-free language can be recognized by a pushdown automaton. All words are recognized through:

either a finite path through the automaton: words that are shorter than the pumping length;
or a path that includes both a loop with pushes to the stack, and another loop with corresponding pops. Pushes and pops have to balance in order to get an empty stack at the end. Then the word contains a loop with pushes $v$, some further path $w$, and a loop with pops $x$. The number of runs through the two loops has to be the same, but it can be any number, hence the middle bit $v^n w x^n$.

You can also get a similar intuition from the ways regular and context-free languages can be specified by a regular expression and a context-free grammar respectively.

If a word is recognized by a regular expression, then:

either the word does use a part of the expression under the $^*$ (Kleene star) operator, and that part $y$ can be repeated any number of times;
or the word doesn't use any part of the expression under a star, and it can't be longer than the expression itself.

If a word is recognized by a context-free grammar, then:

It may be that the word is recognized by a parse tree where there is a subtree $\mathcal{T}_1$ which is recognized by the nonterminal $A$, and a subtree $\mathcal{T}_0$ of that subtree is recognized by the same nonterminal $A$. In that case, let $w$ be the part of the word that is recognized by $\mathcal{T}_0$ and $vwx$ be the part that is recognized by $\mathcal{T}_1$. You also get a valid parse tree if you replace $\mathcal{T}_1$ by $\mathcal{T}_0$ or vice versa. Furthermore, since $\mathcal{T}_1$ contains $\mathcal{T}_0$, after replacing $\mathcal{T}_0$ by $\mathcal{T}_1$, you can replace the copy of $\mathcal{T}_0$ inside $\mathcal{T}_1$ by $\mathcal{T}_1$, and so on. This means that you can replace $vwx$ by $w$, $v^2wx^2$, $v^3wx^3$, etc. and still get a word with a valid parse tree.
Otherwise, there is no subtree of the parse tree which reuses the same nonterminal, and in that case the length of the word is bounded because the depth of the parse tree is bounded by the number of nonterminals in the grammar.


NP-hardness of language of graphs with $\alpha(G)=n/3$ How to prove the NP-hardness of the language $\{G \mid \alpha(G) =\frac{1}{3} |V(G)|\}$?
Here $G$ is a graph, $V(G)$ is its vertex set, and $\alpha(G)$ is the independence number of $G$, which is the maximum size of an independent set.

1-IN-3SAT is the following problem: given a 3SAT instance, determine whether there is a truth assignment in which each clause contains exactly one true literal. It is known that 1-IN-3SAT is NP-complete.
Given an instance of 1-IN-3SAT, construct an instance of your problem in which each clause corresponds to a triangle, and contradicting literals are connected by edges. Details left to you.


How to avoid drawing dense maps? The problem I have in hand is like drawing Google Maps by myself, in particular, roads. When my map scale is huge, I face no problem, but when I zoom out there are too many things to draw -- sure, I can rank the elements, and for example draw only important roads (like highways), but at given scale there will be always some case, when the road has so many intersections and turns, and instead of nice drawing I will get ugly blob.
So I would like to simplify it, yet not in misleading way. I would like to avoid drawing dense map (part of it).

is there official name of this problem/algorithm for it?
if there is special case for maps?

And if there is nothing anything "official" -- how to tackle this problem?

You could smooth the path of the road by fitting a spline to it (or some other curve), with parameters chosen based on the zoom level to ensure that it follows a smooth path on the screen.


Prove whether this problem is decidable or undecidable So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state.

I convinced myself that this problem is decidable, but I am having trouble proving so. A rough outline of my answer would be : Assume we have a TM T that has only one halting state, and if it wants to go through all the states it needs to pass through this halt state and we somehow need to show how they cycle through all the states as such.

Any help would be beneficial, thanks!

I believe that you ask whether the following language is decidable:

$$L_{\text{visit all}} = \{ \langle M,w\rangle \mid \text{  $M$ run on $w$ visits all its non-halting states}\}$$

I believe this language is undecidable. The reason is similar to the reason why the following language is undecidable:
$$L =\{ \langle M,w\rangle \mid \text{$M$ visit the state $q_1$ when running $w$}\}$$
Very iformally: You can see it by "designating" one state to be special, so if we reach it, it means acceptance. Then reaching all states is equivalent to halting problem.


How can $\Theta$ and $O$ complexities be different? From the definition of the $\Theta$-notation,
$$f(n)=\Theta(g(n))\\\implies \exists n_0, \exists c_1,c_2\gt 0, \forall n\gt n_0, c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$

We can see that the inequality is followed for all $n\gt n_0$, and hence we can say that $c_2\cdot g(n)$ is the maximum that this function can reach. Therefore, $f(n)=O(g(n))$ as well.

If we take the example of quicksort, sources say that the $\Theta$ complexity is $n\log{n}$, but $O$-complexity is given as $n^2$.

If the $O$-complexity given is true, then $f(n)\le c_2\cdot n\log{n}$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity?

If the $O$-complexity given is true, then $f(x)\leq c_2n\log n$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity?

Yuval has covered the quicksort aspects of your question but you have a couple of fundamental misunderstandings about asymptotics.

There is no such thing as "$\Theta$-complexity" or "$O$-complexity". Asymptotic notations such as $\Theta$ and $O$ are simply ways of describing the growth rate of functions. Those functions could be used to measure anything at all (including nothing at all). The complexity is the function (or, rather, the running time is measured by the function); the asymptotic notation is just a way of describing that function's behaviour.  As an analogy, suppose that I tell you that my height is "less than two metres": you wouldn't say that my "less-than height is two metres". Likewise, if I say that I weigh about 70kg, you wouldn't say that my "about weight is 70kg." "Less than" and "about" are just ways of describing the numbers that measure those physical properties.

The second misconception is that, for a given function $f$ there is some unique function $g$ such that it's correct to write $f=O(g)$. Remember that $f=O(g)$ means (in a way that's more precise than the following description) "$f$ is kinda less than $g$."  To continue the analogy of the previous paragraph, it's completely true to say that my height is less than 2m and that my height is less than 102m.  Indeed, there's also no contradiction in saying "My height is about 1.8m and less than 2m", which is directly analogous to "The running time is $\Theta(n\log n)$ and $O(n^2)$."


Semi-Thue system, which terminates I observed that with rewrite rules:

$abb \rightarrow bab $

$baa \rightarrow aba $

Every derivation ends, moreover, if there is same amount of $a$'s and $b$'s in input, then derivation ends in $(ab)^*+(ba)^*$.

Why do these two properties hold?

Consider the potential function
$$
\Phi(w_1 \ldots w_n) = \sum_{i=2}^n 2^i 1_{w_i = w_{i-1}}.
$$
Applying one of the rewrite rules always decreases the potential: if we change $abb$ to $bab$ at positions $i,i+1,i+2$, then we lost $2^{i+2}$ and might have gained $2^i$. Since the potential is non-negative, every derivation ends.

Suppose now that the initial word contained an equal number of $a$'s and $b$'s. The same is true for the final word, since the rules don't change the number of $a$'s or $b$'s. It therefore suffices to prove that any word that has $n$ letters $a$ and $n$ letters $b$, and doesn't contain $abb$ or $baa$, has the form $(ab)^n$ or $(ba)^n$. We prove this by induction.

The base cases $n=0,1$ are trivial, so suppose that $n \geq 2$. Assume without loss of generality that the final word ends with $b$. It must have a suffix of the form $ab^k$ (since it contains at least one $a$). Since it contains no $abb$, we must have $k = 1$. Remove the suffix $ab$ and apply induction to deduce that the word is either $(ab)^n$ or $(ba)^{n-1}ab$. The latter case cannot happen since it contains $baa$, and so the word must be $(ab)^n$.

We can slightly strengthen this result by noticing that the rewrite rules never change the final letter of the word. So we reach $(ab)^*$ if the original word terminated with $b$, and reach $(ba)^*$ otherwise.


Multi-point evaluations of a polynomial mod p Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this?
I tried using Berlekamp's algorithm for factorization but it takes $O(n^3)$ just to factorize and then $O(n)$ per point evaluation. Is there any other way to bring the complexity down considerably like to  $n\log(q)$ where $q$ is the number of points I want to evaluate the polynomial at? Or possibly polynomial time? All the coefficients and the values of $x$ that the polynomial is to be evaluated at lie between the $0$ and $prime - 1$, the prime is of order $10^6$.

No, $O(n \lg q)$ running time is not achievable.  It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$.

However, you can find algorithms that are more efficient than the naive solution.  The naive solution for evaluating a polynomial of degree $n$ at $q$ points takes $O(nq)$ time, by using Horner's rule $q$ times.  It turns out there are faster algorithms to do this, namely, in $O(\max(n,q) \log^2 \max(n,q))$ time.  For simplicity of exposition, let me assume $q=n$, so the goal is to evaluate the polynomial $f(x)$ at points $x_1,\dots,x_n$.

We're going to use divide-and-conquer.  Define

$$\begin{align*}
f_0(x) &= f(x) \bmod (x-x_1)(x-x_2)\cdots(x-x_{n/2})\\
f_1(x) &= f(x) \bmod (x-x_{n/2+1})\cdots(x-x_n)
\end{align*}$$

Now we have

$$f(x_i) = \begin{cases}
f_0(x_i) &\text{if }i\le n/2\\
f_1(x_i) &\text{otherwise.}\end{cases}$$

Thus, it suffices to evaluate $f_0(x)$ at the points $x_1,\dots,x_{n/2}$ and evaluate $f_1(x)$ at the points $x_{n/2+1},\dots,x_n$.  We can do this by a recursive invocation of the same procedure.  Since both $f_0(x)$ and $f_1(x)$ have degree at most $n/2$, we're invoking the procedure recursively on two subproblems of size $n/2$.

This requires us compute $f_0(x)$ and $f_1(x)$ from $f(x)$.  This can be done in $O(n \log n)$ time, using FFT-based polynomial division, which works similar to FFT-based polynomial multiplication (see here, here, and these slides).

The running time of this divide-and-conquer algorithm is

$$T(n) = 2 T(n/2) + O(n \log n),$$

which has the solution $T(n) = O(n \log^2 n)$.  Thus, you can evaluate a polynomial of degree $n$ at $n$ arbitrary points in $O(n \log^2 n)$ time.

Since you are working modulo $p$, you want to use a Discrete Fourier Transform designed for mod $p$ arithmetic.

Thanks to Niklas B. for pointing me to http://www.dis.uniroma1.it/~sankowski/lecture4.pdf.


Can any problem in P be converted to any other problem in P in polynomial time? Is it possible to convert any problem in P to any other problem in P in polynomial time?

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$.

Here "non trivial" means that $B$ has at least one yes instance $I_Y$ and at least one no instance $I_N$ (i.e., the language associated to $B$ is not $\emptyset$ nor $\Sigma^*$).

To map an instance $I_A$ of $A$ to an instance $I_B$ of $B$ simply solve $A$ using a polynomial-time algorithm. If $I_A$ is a yes instance let $I_B = I_Y$, otherwise let $I_B = I_N$.

It is not possible to reduce any problem $A \in P$ to any problem $B \in P$. To see this let $A$ be a non-trivial problem and let $B$ be a trivial problem.
Two possible languages corresponding to $A$ and $B$ are $\{ \varepsilon \}$ and $\emptyset$, respectively.


The class of languages that can be certified in a small amount of space NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time.

I wonder, if we consider the same notion but with space considerations to get a class $X$, Is such a class known to be of any importance? Why?

To be more precise, $L\in X$ iff there exists a TM $M$ s.t.

$\forall x\in \{0,1\}^* (x\in L \iff  \exists u \in \{0,1\}^{p(n)}$ s.t. $M(x,u)=1$ s.t. $M$ uses space bounded by a polynomial $P$.

Clearly, NP$\subset$ X. Is there any interesting thing that we can know about $X$?

(Note that X is not known to differ from NP.)  Yes - X is equal to PSPACE.  In fact, one gets that from just brute force, rather than needing Savitch's theorem.

You might also be interested in NL, which is only known to satisfy

L  $\subseteq$  NL  $\subseteq$  coNLOGLOGTIME-uniform SAC1   .

(Note that, to get a certificate characterization of NL, we probably must

"restrict the verifier to have one-way access to the certificate".)


Does loop invariant has nothing to do with termination? Consider the following program fragment:
var x, y: integer;
x := 1;
y := 0;

while y < x do
begin
    x := 2*x;
    y := y+1
end;

For the above fragment, which of the following is a loop invariant?
(A)x=y+1
(B)x=(y+1)^2
(C)x=(y+1)2^y
(D)x=2^y
(E)None of the above, since the loop does not terminate
As per my solution, the loop never seems to terminate. I came with the answer E but the D is the answer to the above questions. Isn't the loop invariant affected by the nontermination of the loop?

The loop invariant is just a proposition which holds on each iteration of the loop (in your question, the relationship between $x$ and $y$ holds regardless, so no, it is not affected by loop nontermination). It doesn't inherently say anything about termination. It is potentially something that you can use to argue about termination.
The Wikipedia article on correctness additionally describes the difference between partial and total correctness. For partial correctness, we don't require a program terminates, only that the result is correct if it is returned.