Algorithm to minimize surface area, given volume Consider the following algorithmic task:

Input: a positive integer $n$, along with its prime factorization
Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $xyz=n$

What is the complexity of this problem?  Is there a polynomial-time algorithm?  Is it NP-hard?

This problem basically asks: out of all rectangular solids whose volume is $n$ and whose dimensions are all integers, which one has the least surface area?

This problem was posed by Dan Meyer, under the title The Math Problem That 1,000 Math Teachers Couldn’t Solve.  So far none of the math teachers he worked with has found a reasonable algorithm for this problem.  In his context, the definition of "reasonable" is a bit imprecise, but as computer scientists we can ask a more precise question about the complexity of this problem.

The obvious approach is to enumerate all possibilities for $x,y,z$, but that takes exponential time.  Commenters at Dan Meyer's blog have proposed many efficient candidate algorithms that unfortunately all turned out to be incorrect.  Martin Strauss suggests that this problem seems vaguely reminiscent of 3-partition, but I can't see a reduction.

Let me also clear up some misconceptions that I've seen in the comments/answers:

You can't reduce from 3-partition by simply replacing each number $q$ with its power $2^q$, as the objective functions of the two problems are different.  The obvious reduction simply doesn't work.
It is not true that the optimal solution involves picking one of $x,y,z$ to be the nearest divisor of $n$ to $\sqrt[3]{n}$.  I see multiple people who are assuming this is case, but in fact, that is not correct.  This has already been disproven on the Dan Meyer blog post.  For instance, consider $n=68$; $\sqrt[3]{68} \approx 4$, and 4 divides 68, so you might think that at least one of $x,y,z$ should be 4; however, that is not correct.  The optimal solution is $x=2$, $y=2$, $z=17$.  Another counterexample is $n=222$, $\sqrt[3]{222}\approx 6$, but the optimal solution is $x=37$, $y=3$, $z=2$.  (It might be true that for all $n$, the optimal solution involves making at least one of $x,y,z$ be equal to either the smallest divisor of $n$ larger than $\sqrt[3]{n}$ or the largest divisor of $n$ smaller than $\sqrt[3]{n}$ -- I don't have a counterexample right now -- but if you think this statement is true, it  would need proof.  You absolutely cannot assume it is true.)
"Make $x,y,z$ be the same size" does not appear to necessarily yield the optimal answer in all cases; see Dan Meyer's blog post for counterexamples.  Or, at least, for some reasonable interpretations of the phrase "make them roughly the same size", there are counterexamples showing that this strategy is not in fact optimal.  If you want to try some strategy of that sort, make sure that you state the claim precisely and then provide a careful mathematical proof.
A running time of $O(n^3)$ is not polynomial.  For this problem to be in P, the running time must be a polynomial in the length of the input.  The length of the input is something like $\lg n$, not $n$.  The obvious brute-force algorithm can be made to run in $O(n^3)$ or $O(n^2)$ time, but that is exponential in $\lg n$ and thus counts as an exponential-time algorithm.  Thus that is not helpful.

Here is a modified version of a "choose divisor near cube root" algorithm.  It still must brute force many cases, so I'm not sure how much of a real improvement it is speed wise over the enumeration of all cases.  However, I submitted it as a correction to the algorithm on OEIS (that which generated incorrect results) because I believe it should be accurate at least.

Here is the algorithm to find (s1,s2,s3) and surface area of a rectangular prism given its volume n:

Given n, find the cube root.
Set an initial value integer s1 at the ceiling of that cube root.
Test to see if s1 is a divisor of n, and if not, reduce s1 by 1.
If a divisor s1 is found, set an initial s2 to be the ceiling of the square root of (n/s1).
Then test to see if s2 is a divisor of n/s1, and if not, reduce s2 by 1.
When a divisor s2 is found, s3 then is set to n/(s1*s2).
The current surface area is calculated by 2*(s1*s2 + s1*s3 + s2*s3).
The current SA is compared against the current minimum.  If its the first surface area calculated, it is stored as minSA. After the first, we test to see if the current SA is smaller than minSA, and if so, store it in minSA.

This algorithm enumerates some of the triples (s1,s2,s3) but needs only to test the divisors under the cube root. (Since not all three divisors can be above the cube root).  In a similar fashion, s2 needs only to test divisors of n/s1 under the square root of n/s1, since not both divisors can be above the square root)

A note on step 3: if the cube root is a divisor then n is a cube and we can stop there with minimal surface area 6*s1^2 from the box (s1,s1,s1).

Python:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0)))
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:
            s1 = s1 - 1
        s1quot = int(n/s1)
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))
            SA = 2*(s1*s2 + s1*s3 + s2*s3)
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1
    return minSA


Demonstrating that probability for every possible result is uniform at the end of an algorithm I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$.
At some point ($t=k+1$) the array will be full and we must choose a value inside the array to replace with the new one. The objective is to find an algorithm that outputs a uniform subset of $k$ elements. For example, with $k=2$ and $t=3$ it will output with uniform probability one of the following: $\{1,2\}$, $\{1,3\}$ or $\{2,3\}$. One possible algorithm is the following:

create array of $k$ elements
FOR $t=1,.\ldots,T$:
if array is not full insert an empty space
receive an input
discard the input with probability $1 - k/t$
else insert the input at a uniform location
END FOR
return array

It's easy to implement such a program and convince yourself that this is indeed a solution to the problem but how do I demonstrate it?
Essentially I need to demonstrate that each subset has probability $1/\binom tk$ to be the result at the end (that's because $\binom tk$ is the number of possible subsets of $k$ elements at time $t$).

The proof is by induction. The base case $t = k$ is clear. Suppose that the claim is true at some time $t$. We will prove it for time $t+1$.

Let the first $t+1$ elements be $x_1,\ldots,x_{t+1}$. By the induction hypothesis, at time $t$ each of the $\binom{t}{k}$ possible $k$-subsets of $x_1,\ldots,x_t$ is found in the array with equal probability. The probability that at step $t+1$ the array remains the same is $1-k/(t+1)$, hence each of the $k$-subsets of $x_1,\ldots,x_t$ appears at time $t+1$ with probability
$$
\frac{t+1-k}{t+1} \frac{1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}.
$$
Now consider some $k$-subset $S$ of $x_1,\ldots,x_{t+1}$ that contains $x_{t+1}$. For this set to be appear at time $t+1$, the following two events need to happen: at time $t$, the array consisted of $S \setminus \{x_{t+1}\}$ together with one of the $t-(k-1)$ remaining elements; and at time $t+1$, this element was replaced by $x_{t+1}$. In total, the probability is
$$
\frac{k}{t+1} \cdot \frac{1}{k} \cdot \frac{t-k+1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}.
$$


Chebyshev inequality comparison Given $n$ distinct values $(x_i)_{i=1}^{n}$ with mean $\mu$ and standard deviation $s$, for all $i$, we have $|x_i−\mu| ≤ s \sqrt{n − 1}$.
How does this inequality compare with Chebyshev inequality as $n$ increases?

Chebyshev's inequality states that
$$
\Pr[|x_i - \mu| > c\sigma] < \frac{1}{c^2}.
$$
Choosing $c = \sqrt{n}$, we deduce that with positive probability,
$$
|x_i - \mu| \leq \sqrt{n} \cdot \sigma \text{ for all } i.
$$


Optimizing NFL draft picks I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, and a salary cap, build the highest projected scoring NFL team that fits the salary cap. I am interested in finding an efficient way to do this.

An NFL team consists of 1 QB, 1 TE, 1 K, 1 D, 3 WRs and 2 RBs. Each position has a varying number of potential players available, but for the sake of argument we can say that from an initial list of about 600 players total, we can safely eliminate most of them so that there are 5-15 players to choose from for each position.

I have "solved" this problem with a brute force approach: I have a separate loop for each position, loop over all available players, and find the best team that fits the salary cap. This works, but having written a function containing 9 nested loops makes me feel dirty. To deal with a dataset with around 10 players in each position as options, it takes about 2 hours to finish. Past that, it would be too slow to be useful.

Several websites out there do exactly this: For Example. However, if you reject a player from their lineup and recalculate, it takes less than a second to find a new optimized lineup. It was pointed out to me that it is possible that they are doing a pre-computation and storing all possible teams in a database, and simply searching through it in order to find new optimized lineups when someone tweaks things, but I am hoping that is not the case.

So the question, finally: is there an efficient algorithm that guarantees an optimal solution, assuming that the best team mean maximizing the sum of projected points for the players on the team?

Yes, this can be solved using a dynamic programming algorithm very similar to the standard dynamic programming algorithm for the knapsack problem.

Basically, order the positions from 1 to 9.  You're going to fill in a two-dimensional table $T$, where $T[i,s]$ denotes the score of the highest-scoring team that fills in just the first $i$ positions and has a salary cap of $s$.  The key observation is: given the row $T[i-1,\cdot]$ of the table, you can compute $T[i,s]$ via a simple recurrence relation.  In particular,

$$T[i,s] = \max \{ T[i-1,s-s_j] + p_j : j=1,2,3,\dots\},$$

where $j$ ranges over the candidates for the $i$th position, $s_j$ is the salary of the $j$th candidate, and $p_j$ is the projected points generated by the $j$th candidate.   This lets you fill in the table, row by row.

The running time is quadratic: proportional to the total salary for the team, times the number of positions.  There are two nested loops, rather than 9.


If in all satisfying assignments all pair of variables can take all possible values is this tautology? I suppose this is both easy and false.

Let $\phi$ be propositional boolean formula on variables
$x_1 \ldots x_n$.

Suppose in all satisfying assignments of $\phi$,
all pairs of variables $(x_i,x_j),i \ne j$ can take all possible
values, i.e. any of $\{(F,F),(F,T),(T,F),(T,T)\}$.

  Is $\phi$ tautology?

In case the answer is negative, is there simple characterization
of those $\phi$ which are not tautologies?

The VC dimension of a set $S \in \{0,1\}^n$ is the maximal $d$ such that for all $i_1 < \cdots < i_d \in \{1,\ldots,n\}$ and all $b_1,\ldots,b_d \in \{0,1\}$, there is a point $x \in S$ such that $x_{i_1} = b_1,\ldots,x_{i_d} = b_d$. Your condition states that the VC dimension of the set of satisfying assignment of a formula is at least $2$. The formula is a tautology if the VC dimension is $n$. There are sets of arbitrary VC dimension, so even if you replace pairs by larger tuples, your conclusion would still be wrong.


Determining asymptotic running time by profiling The purpose of performance proﬁling is to measure program performance. One part of your PA1 assignment asked to measure performance of your d-smooth algorithm to verify if the running time of the program corresponds to the desired $O(n \log n)$. Assume that you have performed an experimental analysis of an algorithm, and proﬁling returned the following times: for instances of sizes $2^{10}, 2^{11}, 2^{12}, 2^{13}, 2^{14}$ the corresponding times are approximately 300, 500, 1100, 2900, 8300 milliseconds. There is an extra overhead resulting from clocking program performance and functions calls, and this overhead has to be considered in analyzing data. That is, the measured time consists of two components: the time for executing the operations, plus the overhead from proﬁling. The estimated overhead due to proﬁling is about 200 milliseconds independently of the input size. (that is, 200 is always an additive “constant”).
  Based on these experimental results, what is the running time for executing operations in this algorithm? ($c$ is a constant) In particular, is your implementation running in $O(n \log n)$?

  $c \log n$
  $c n$
  $c n \log n$
  $c n\sqrt{n}$ <----- Correct answer
  $c n^2$

(editor's note: I changed 81200 to 8300; the setters added 200 to 81000 instead of to 8100)

Why is $c n\sqrt n$ the correct answer?

If you remove the 200ms overhead, you get
$$
\begin{array}{c|ccccc}
n & 2^{10} & 2^{11} & 2^{12} & 2^{13} & 2^{14} \\
t & 100 & 300 & 900 & 2700 & 8100
\end{array}
$$
This shows that when $n = 2^{10+k}$, $t = 100 \cdot 3^k$. You take it from here. (You won't get $cn^{3/2}$, by the way! The setters made a mistake.)


Some questions about NP / coNP / CSP I need help with the following mock exam questions. True or false?

1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$.

True. Every finite set is in $P$ and because of the $NP$-completeness every set in $NP$ can be reduced to this set. Is it right?

2.) $NP \subseteq coNP$ $\Leftrightarrow$ $NP = coNP$.

I don't know if the "$\Rightarrow$" case holds. I only know $P \subseteq coNP$ and $P \subseteq NP$.

3.) For every fixed $k$ the problem $k$-$CLIQUE$ can be modeled as a Constraint Satisfaction Problem.

I have no idea. We've had $3$-$COLOR$ and $3$-$SAT$ as examples but also the fact that not every NP-problem can be expressed in terms of a CSP.

Thanks in advance!

2) Suppose that $\mathsf{NP} \subseteq \mathsf{coNP}$: in particular, SAT is in $\mathsf{coNP}$, and its complement coSAT, the set of boolean formulas that are not satisfiable, is in $\mathsf{NP}$. But coSAT is coNP-complete, so that we have a coNP-complete language in $\mathsf{NP}$, i.e. $\mathsf{coNP} \subseteq \mathsf{NP}$.

3) This depends on your definition of a CSP, I guess. Following the definition of a non-uniform CSP, the constraint satisfaction problem of a relational structure $\Gamma$ is the set of relational structures $\Delta$ on the same signature such that $\Delta$ homomorphically maps to $\Gamma$. Here, the signature is $\{E\}$, where $E$ is a binary relational symbol that indicates adjacency in graphs. Suppose that there exists $\Gamma$ such that $\mathrm{CSP}(\Gamma)$ is the $k$-CLIQUE problem. Then, letting $K_k$ be the $k$-clique, we have that $K_k$ homomorphically maps to $\Gamma$. But if $v$ is any vertex of $K_k$, we have that $\{v\}$ homomorphically maps to $K_k$, and since the composition of homomorphisms is a homomorphism, we have that $\{v\}$ has a homomorphism to $\Gamma$, a contradiction since $\{v\}$ does not contain a $k$-clique. Thus, the k-CLIQUE problem cannot be represented as a non-uniform constraint satisfaction problem.

Please let me know if the definition I used for the CSP is not the one you are used to!


Proof that L^2 is regular => L is regular I'm trying to show $L^2 \in \mathsf{REG} \implies L \in  \mathsf{REG}$  with  $L^2 = \{w = w_1w_2 \mid w_1, w_2 \in L\}$ but I cant seem to find a proof that feels right.
I first tryed to show $L \in \mathsf{REG} \implies L^2 \in  \mathsf{REG}$, by constructing an machine $M$ that consists of two machines $A=A'$ with $A$ recognizing $L$.
$M$ has the same start states as $A$ but the final states of $A$ are put together with the starting states of $A'$. Further $M$ uses the same accepting states as $A'$. Hope that makes sens so far :D
Now to show $L^2 \in \mathsf{REG} \implies L \in  \mathsf{REG}$ I'd argue the same way, but:
The machine $M'$ that accepts $L^2$ has to recognize $w_i \in L$ in some way, and because $L^2$ is regular, $M'$ has to be a NFA/DFA. So the machine has to check if $w_i \in L$ and this cant be done by using something else than a NFA/DFA.
This feels wrong and not very mathematical, so maybe somebody knows how to do this?

Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a non regular language whose "square" is regular, namely $L  = \{ 1^p \mid p \text{ is an odd prime}\}$, under the Goldbach conjecture, and $L'  = \{ 1^{a^2} \mid a \geq 0 \}^2=\{1^n \mid n \text{ is the sum of two squares}\}$.

For a simpler example, consider the set
$$\text{NP}=\{1^n\mid n \text{ is not prime}\}$$
Clearly NP is not regular (otherwise also its complementary would be regular), but NP$^2$ is regular, as its complementary is finite. Indeed, if $n$ is even and greater than or equal to 8, then $n=4+(n-4)$ and $4$ and $n-4$ are not prime and so $1^n\in \text{NP}^2$. Instead, if $n$ is odd and greater than or equal to 13, then $n=9+(n-9)$ and $9$ and $n-9$ are not prime, as $n-9$ is even and greater than 2, and again $1^n\in \text{NP}^2$ (actually, NP$^2=\{1^n\mid n\neq 3\}$, here I don't consider 1 as a prime number).

In general, if $L$ is a non regular language sufficiently "sparse", then there is a good chance that $(L^C)(L^C)$ is cofinite, and then regular. For example, again on a unary alphabet, one can consider the non regular language
$$\text{L}=\{1^n\mid n \text{ is not a power of }2\},$$
then it is easy to see that $L^2=\{1^n\mid n\not\in\{1,2 \}\}$, which is regular.
On a two letter alphabet one can consider the example below of Bernardo Subercaseaux (I think there's a little misunderstanding in his comment, as here we are considering the concatenation of a non regular language with itself), namely the language $L$ that is the complement of the language of well parenthesized strings on the alphabet $\{(,)\}$: in this case $L^2=\{(,)\}^*\setminus\{\varepsilon,(,)\}$, again regular.
Another simple example is given by the non regular language
$$\text{L}=\{w\in\{a,b\}^*\mid w \text{ is not of the form }a^nb^n\text{ with }n>0\},$$
then it is easy to see that $L^2=\{a,b\}^*$: indeed if $w\in L$, then $w=w\varepsilon\in L^2$, else if $w=a^nb^n$ then $w=a\cdot a^{n-1}b^n\in L^2$.


Formula to see where a memory address can be depicted in cache? I've been trying to find a formula that helps us identify where an address can be depicted in cache. I remember my  professor talking about some kind of division but I can't find it in my textbook nor internet (maybe I am not searching the right words). For example:
I have a cache that has $2^{14}$ blocks, each 32 bytes, and it is 8-way associative with $2^{11}$ sets and each address is 64 bits. So we have 48 bits for the tag, 11 for the index, and 5 for the offset. I would like to answer the following question:

Where can we find in cache, the addresses 300A21 (hex)?

My obvious answer is to convert it into a binary address: 0011 0000 0000 1010 0010 0001, and now, we know that index is  0000 1010 001, so it has to be into the set with this index (it is the 81st), and since
0 0001 is the offset, I guess that since we count from 0, it is the second word on the block (?).
Is there anything else I can say? Something that involves a division or modulo of the address?

Your Result Is Correct

Tag
Set
Offset

0011 0000
0000 1010 001
0 0001

Don't doubt your methods for finding the address location in a set-associative cache. Your approach is absolutely correct, but first, let's clarify some terminology:
From your question you use the term "index." If I am correct you are using this to refer to the "set" in the set-associative cache? I will use the term "set" from this point forward in place of "index" to avoid confusion since it is more explicit with regard to the type of cache in question.

Your Question. . .
You asked about:

Something that involves a division or modulo of the address?

The Short Answer Is. . .
. . .yes! However, just not with set-associative cache. Modulo division is used when attempting to find a block to which a memory address may be mapped using a Direct Mapped Cache scheme. Subdividing the cache blocks into sets that map to a main memory location based on a portion of its address removes the necessity to obtain a cache location via modulo division.
The Long Answer. . .
Direct mapping involves the process where block X of main memory is mapped to block Y of cache memory, mod N, where N is the number of blocks in cache.[1]
Example:
Provided you are given a cache memory consisting of four blocks and a main memory consisting of eight blocks, the direct mapping scheme will be as follows:

CacheBlocks
Mapping
Main MemoryBlocks
MappingFormula

CB 0
MM 0MM 4
MM 0
MM 0 % 4 = CB 0

CB 1
MM 1MM 5
MM 1
MM 1 % 4 = CB 1

CB 2
MM 2MM 6
MM 2
MM 2 % 4 = CB 2

CB 3
MM 3MM 7
MM 3
MM 3 % 4 = CB 3

MM 4
MM 4 % 4 = CB 0

MM 5
MM 5 % 4 = CB 1

MM 6
MM 6 % 4 = CB 2

MM 7
MM 7 % 4 = CB 3

The Difference
Direct Mapped Cache does not require any searching and is therefore less expensive. However, main memory is constantly being swapped in and out of cache. In the above example, you can see that either block of cache may only hold one of two blocks of main memory at a time. Imagine the scenario where CB 0 is polled for MM 0 but is currently holding MM 4. The CPU would need to expunge MM 4 and bring in MM 0. If the next read/store cycle required MM 4, the process would occur again leading to cache thrashing.[1]
In an ideal world we would use Fully Associative Cache, wherein each block of main memory has its own location in cache and does not have to share with any other addresses. The best way of implementing this type of cache is to have each memory address assigned to any free location at random. However, this requires additional structures within the CPU that search every cache location in parallel.[1] Not only does this translate into a higher monetary expense for the additional hardware structures, it also comes with a look-up cost by having to search each cache block for a hit.
The answer is to strike a happy medium by using Set-associative Cache that combines advantages of the two other types. Each main memory block may be assigned to a specific set location similar to direct mapping, but the exact block in cache will differ based upon the next free block within the set similar to Fully Associative Cache.

Links Regarding Different Cache Mapping Schemes
https://www.geeksforgeeks.org/cache-memory-in-computer-organization/
https://en.wikipedia.org/wiki/Cache_placement_policies

[1]Null, L., & Lobur, J. (2015). Ch. 6 Memory: Direct Mapped Cache. In The Essentials of Computer Organization and Architecture (4th ed., pp. 350-365). Burlington, MA: Jones & Bartlett.


Algorithm for scheduling unit time tasks with arrival times and deadlines Suppose we have $n$ tasks to order over $n$ days.
Each tasks takes 1 day to be completed.
Each task has a start date when the task becomes available and a deadline when the task must be delivered.

Here is an example:

Is there an algorithm that can solve this problem with a worst case efficiency of $O(n)$ where $n$ is the number of tasks and days.

The more general version of your problem is the scheduling problem where we have $n$ independent tasks, each with an arrival time, a resource requirement (time), and a deadline. We define the Earliest Deadline First algorithm such that at every timepoint, we choose to process the task with the nearest deadline. While time is continuous, it is trivial to see that we can discretize time to be all points at which a task finishes or a new task arrives.

It is known that EDF is an optimal uniprocessor scheduling algorithm i.e. if there is a feasible schedule, EDF will find it and if EDF does not find a feasible schedule, then no feasible schedule exists. [1], [2]. However, this is not linear time if we aren't guaranteed an ordering of the deadlines of the arriving tasks. Let's use a priority queue to represent the waiting tasks. At every time point, which there are $O(n)$ of, we must insert and/or pull the next task from a priority queue sorted on deadlines. Each insertion is $O(\log n)$ time, thus resulting in $O(n\log n)$ time.

If your input was sorted by arrival, we could easily find whether or not there is a valid schedule by following the algorithm above, iterating through the days, adding tasks for that day to a priority queue and selecting the task with the nearest deadline from the queue. We fail if we ever try to assign a task to a day on or past its deadline.

As mentioned in the comments, we can sort the input by arrival time in linear time using counting sort or pigeonhole sort. The issue then is to somehow make the priority queue also linear time.


Dynamic Programming for a variant of the coin exchange problem I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem:

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = {S1, S2, .. , Sm} integral-valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. See here for further detail.

Here, one can find a tabulation-DP-based solution for this problem. This solution is based on the following recurrence relation:

count(S, m, n) = count(S, m - 1, n) + count(S, m, n - S[m - 1]);

With base cases:

count(S, m, n < 0) = 0
count(S, m, n = 0) = 1
count(S, m <= 0, n >= 1) = 0

Intuitively, this recurrence relation defines a problem as the solution to two sub-problems: Those in where we discard coins, and those for which we assume the coins a progressively used once at the time.

Question: How can I modify this recurrence relation to count the number of ways we can sum to N disregarding order and with an even number of summands? For example, for N = 4 and S = {1,2,3}, there are four solutions total (disregarding order): {1,1,1,1},{1,1,2},{2,2},{1,3}, but only 3 of them have an even number of summands, i.e. {1,1,1,1},{2,2},{1,3}.

Previous research: At first I thought I could double the requested sum for the case of discarding coins, and requesting that each coin is consumed twice for the cases in where we would use some of the coins, i.e.:

count(S, m, n) = count(S, m - 1, 2*n) + count(S, m, n - 2*S[m - 1]);

This works for some sample cases, but it does not work. Any hints?

Add a parity parameter to $C$ and check for it in the base case, making the wrong parity invalid:

$$
\newcommand{\for}{\text{for }}
C(S, m, n, p) =
    \begin{cases}
      0& \for n < 0\\
      0& \for n = 0 \wedge p = 1\\
      1& \for n = 0 \wedge p = 0\\
      0& \for m = 0\\
      C(S,m-1,n,p) + C(S, m,n-S_m, 1-p)& \text{otherwise}
    \end{cases}
$$

Note that I'm using mathematical notation above so $S$ and $m$ are using one-based indices.

Since we want only an even number of summands we want $p = 0$, thus $C(S, m, n, 0)$ gives the answer you want.


Algorithm to distribute items "evenly" I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways to describe it... later I'll provide a way to measure if a result is better than other).

So, for the list:

[1, 1, 2, 2, 3, 3]

One of the best results, after re-distributing the values, is:

[1, 2, 3, 1, 2, 3]

There may be other results as good as this one, and of course this gets more complicated with a less uniform set of values.

This is how to measure if a result is better than other:

Count the distances between each item and the next item with the same value.
Calculate the standard deviation for that set of distances. A lower dispersion means a better result.

Observations:

When calculating a distance and the end of the list is reached without finding an item with the same value, we go back to the beginning of the list. So, at most, the same item will be found and the distance for that item will be the length of the list. This means that the list is cyclic;
A typical list has ~50 items with ~15 different values in varied quantities.

So:

For the result [1, 2, 3, 1, 2, 3], the distances are [3, 3, 3, 3, 3, 3], and the standard deviation is 0;
For the result [1, 1, 2, 2, 3, 3], the distances are [1, 5, 1, 5, 1, 5], and the standard deviation is 2;
Which makes the first result better than the second (lower deviation is better).

Given these definitions, I ask for a clue of which algorithms or strategies should I search for.

I ran across this question while researching a similar problem: optimum additions of liquids to reduce stratification. It seems like my solution would be applicable to your situation, as well.

If you want to mix liquids A, B, and C in the proportion 30,20,10 (that is, 30 units of A, 20 units of B, and 10 units of C), you end up with stratification if you add all the A, then all the B, and then all the C. You're better off mixing smaller units. For example, do single-unit additions in the sequence [A,B,A,C,B,A]. That will prevent stratification altogether.

The way I found to do it is to treat it as a kind of merge, using a priority queue. If I create a structure to describe the additions:

MergeItem
    Item, Count, Frequency, Priority

The Frequency is expressed as "one every N". So A, which is added three out of six times, has a frequency of 2 (6/3).

And initialize a heap that initially contains:

(A, 3, 2, 2)
(B, 2, 3, 3)
(C, 1, 6, 6)

Now, I remove the first item from the heap and output it. Then reduce its count by 1 and increase Priority by Frequency and add it back to the heap. The resulting heap is:

(B, 2, 3, 0)
(A, 2, 2, 4)
(C, 1, 6, 6)

Next, remove B from the heap, output and update it, then add back to the heap:

(A, 2, 2, 4)
(C, 1, 6, 6)
(B, 1, 3, 6)

If I continue in that fashion, I get the desired mixture. I use a custom comparer to ensure that when equal Priority items are inserted into the heap, the one with the highest Frequency value (i.e. the least frequent) is ordered first.

I wrote a more complete description of the problem and its solution on my blog, and presented some working C# code that illustrates it. See Evenly distributing items in a list.

Update after comments

I do think my problem is similar to the OP's problem, and therefore that my solution is potentially useful. I apologize for not framing my answer more in the terms of the OP's question.

The first objection, that my solution is using A, B, and C rather than 0, 1, and 2, is easily remedied. It's simply a matter of nomenclature. I find it easier and less confusing to think about and say "two A's" rather than "two 1's". But for purposes of this discussion I have modified my outputs below to use the OP's nomenclature.

Of course my problem deals with the concept of distance. If you want to "spread things out evenly," distance is implied. But, again, it was my failing for not adequately showing how my problem is similar to the OP's problem.

I ran a few tests with the two examples that the OP provided. That is:

[1,1,2,2,3,3]  // which I converted to [0,0,1,1,2,2]
[0,0,0,0,1,1,1,2,2,3]

In my nomenclature those are expressed as [2,2,2] and [4,3,2,1], respectively. That is, in the last example, "4 items of type 0, 3 items of type 1, 2 items of type 2, and 1 item of type 3."

I ran my test program (as described immediately below), and have posted my results. Absent input from the OP, I can't say if my results are similar to, worse than, or better than his. Nor can I compare my results to anybody else's results because nobody else has posted any.

I can say, however, that the algorithm provides a good solution to my problem of eliminating stratification when mixing liquids. And it looks like it provides a reasonable solution to the OP's problem.

For the results shown below, I used the algorithm that I detailed in my blog entry, with the initial priority set to Frequency/2, and the heap comparer modified to favor the more frequent item. The modified code is shown here, with the modified lines commented.

private class HeapItem : IComparable<HeapItem>
{
    public int ItemIndex { get; private set; }
    public int Count { get; set; }
    public double Frequency { get; private set; }
    public double Priority { get; set; }

    public HeapItem(int itemIndex, int count, int totalItems)
    {
        ItemIndex = itemIndex;
        Count = count;
        Frequency = (double)totalItems / Count;
        // ** Modified the initial priority setting.
        Priority = Frequency/2;
    }

    public int CompareTo(HeapItem other)
    {
        if (other == null) return 1;
        var rslt = Priority.CompareTo(other.Priority);
        if (rslt == 0)
        {
            // ** Modified to favor the more frequent item.
            rslt = Frequency.CompareTo(other.Frequency);
        }
        return rslt;
    }
}

Running my test program with the OP's first example, I get:

Counts: 2,2,2
Sequence: 1,0,2,1,0,2
Distances for item type 0: 3,3
Stddev = 0
Distances for item type 1: 3,3
Stddev = 0
Distances for item type 2: 3,3
Stddev = 0

So my algorithm works for the trivial problem of all counts being equal.

For the second problem that the OP posted, I got:

Counts: 4,3,2,1
Sequence: 0,1,2,0,1,3,0,2,1,0
Distances for item type 0: 3,3,3,1
Stddev = 0.866025403784439
Distances for item type 1: 3,4,3
Stddev = 0.471404520791032
Distances for item type 2: 5,5
Stddev = 0
Distances for item type 3: 10
Stddev = 0
Standard dev: 0.866025403784439,0.471404520791032,0,0

I don't see an obvious way to improve on that. It could be rearranged to make the distances for item 0 [2,3,2,3] or some other arrangement of 2 and 3, but that will change the deviations for items 1 and/or 2. I really don't know what "optimum" is in this situation. Is it better to have a larger deviation on the more frequent or on the less frequent items?

Lacking other problems from the OP, I used his descriptions to make up a few of my own. He said in his post:

  A typical list has ~50 items with ~15 different values in varied quantities.

So my two tests were:

[8,7,6,5,5,4,3,3,2,2,2,1,1,1,1]  // 51 items, 15 types
[12,6,5,4,4,3,3,3,2,2,2,1,1]     // 48 items, 13 types

And my results:

Counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sequence: 0,1,2,3,4,5,7,6,0,1,2,8,9,10,4,3,0,1,5,2,0,1,3,4,6,7,14,11,13,12,0,2,5,1,0,3,4,2,8,10,9,1,0,7,6,5,3,4,2,1,0
Distances for item type 0: 8,8,4,10,4,8,8,1
Stddev = 2.82566363886433
Distances for item type 1: 8,8,4,12,8,8,3
Stddev = 2.76272565797339
Distances for item type 2: 8,9,12,6,11,5
Stddev = 2.5
Distances for item type 3: 12,7,13,11,8
Stddev = 2.31516738055804
Distances for item type 4: 10,9,13,11,8
Stddev = 1.72046505340853
Distances for item type 5: 13,14,13,11
Stddev = 1.08972473588517
Distances for item type 6: 17,20,14
Stddev = 2.44948974278318
Distances for item type 7: 19,18,14
Stddev = 2.16024689946929
Distances for item type 8: 27,24
Stddev = 1.5
Distances for item type 9: 28,23
Stddev = 2.5
Distances for item type 10: 26,25
Stddev = 0.5
Distances for item type 11: 51
Stddev = 0
Distances for item type 12: 51
Stddev = 0
Distances for item type 13: 51
Stddev = 0
Distances for item type 14: 51
Stddev = 0

And for the second example:

Counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sequence: 0,1,2,0,3,4,7,5,6,0,1,8,9,10,0,2,0,3,4,1,0,2,6,7,5,12,11,0,1,0,3,4,2,0,1,10,8,9,0,7,5,6,0,
4,3,2,1,0
Distances for item type 0: 3,6,5,2,4,7,2,4,5,4,5,1
Stddev = 1.68325082306035
Distances for item type 1: 9,9,9,6,12,3
Stddev = 2.82842712474619
Distances for item type 2: 13,6,11,13,5
Stddev = 3.44093010681705
Distances for item type 3: 13,13,14,8
Stddev = 2.34520787991171
Distances for item type 4: 13,13,12,10
Stddev = 1.22474487139159
Distances for item type 5: 17,16,15
Stddev = 0.816496580927726
Distances for item type 6: 14,19,15
Stddev = 2.16024689946929
Distances for item type 7: 17,16,15
Stddev = 0.816496580927726
Distances for item type 8: 25,23
Stddev = 1
Distances for item type 9: 25,23
Stddev = 1
Distances for item type 10: 22,26
Stddev = 2
Distances for item type 11: 48
Stddev = 0
Distances for item type 12: 48
Stddev = 0


Correctness of the Betweenness centrality formula Betweenness centrality is defined as the number of shortest paths that go through a node in the graph.The formula is:
$$\sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$$
Where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma _{st}(v)$ is the number of those paths that pass through $v$.

However it doesn't seem to me that the formula calculates what is defined. Why do we divide by the total number of shortest paths between $s$ and $t$ each time? Shouldn't we just divide by $2$ to compensate the fact that  $s$ and $t$ will appear twice in different orders?

However it doesn't seem to me that the formula calculates what is defined.

The formula is right. The betweenness centrality is a value in an interval $[0, \ldots, 1]$. Thus, if the betweenness centrality of node $v$ is equal to $1$, then all shortest paths between two nodes of this graph pass through $v$. I will explain the correctness of this summation below.

  Why do we divide by the total number of shortest paths between s and t each time?

You are developing a summation of the percentages. This is needed to ensure that this sum will never exceed $1$. Suppose that you have $m$ different $s$-$t$ pairs of vertices in your graph. Thus, $\sigma_{st} = m$ and your summation goes through all $m$ $s$-$t$ pairs.
One can note that the term $\sigma_{st}(v)$ on this equation is binary (the shortest $s$-$t$ path passes through $v$ or not). Thus, if all $s$-$t$ paths go through $v$, you will have $m \cdot \frac{1}{m} = 1$.

  Shouldn't we just divide by 2 to compensate the fact that s and t will appear twice in different orders?

Indirectly, you're right. This formula measures the percentage of the shortest $s$-$t$ paths that pass through node $v$. In fact, a simple optimization of this algorithm for undirected graphs is to consider only $s$-$t$ paths where $s < t$. However, you can't divide it by $2$.

Curiosity: The only graph topology who has a node with betweenness centrality equal to $1$ is a star graph, like the examples shown in the figure below.


How is the computational power of a human brain comparing to a turing machine? This seems related to these questions at a glance:

What are some problems which are easily solved by human brain but which would take more time computers?

What would show a human mind is/is not reducible to a Turing machine?

But not quite, I am not asking about "time", but power. Also, I am not interested in the turing test. That said, my question can also be expressed as two parts:

Is there a language, which cannot be recognized by any turing machine, that can be recognized by a human?
Is there a language, which cannot be decided by any turing machine, that can be decided by a human?

And vice versa. The "language" I am talking about is the "mathematical" language, not only a "human" or "programming" language:

$$L \subseteq \Sigma^*$$

Since this is a question about computational power, I would make the following assumptions:

Human do not make mistakes
(here I mean mistakes like copying the wrong character or computing arithmetics incorrectly, typical human errors)
There is no space limit (turing machine gets infinite tape, you get infinite medium to write)
There are no time constraints
However, the recognition/decision must be achieved within finite time.
And of course, in finite space

Please give an example if you have an answer. Remember, this is a theoretical question, so practical issues are not in concern.

EDIT 1

OK, as someone pointed out, I will add the following assumptions.

Human is probably not easy to define in precise mathematical words, so let's just assume "you".

About a human recognizing a string in a language, I am talking about performing the same task the turing machine is "programmed" to do. Say, given a string, whether you (a human) can recognize it when it conforms to a set of rules, or decide whether it conforms to a set of rules or not. I am not sure if I can make the point clear enough...

EDIT 2

OK, to clarify, this is a question about model of computation, so yes, like André Souza Lemos mensioned, I am talking about "given a word $w$ and a language $L$, is sentence $w\in L$ decidable". I am not talking about a physical computer.

EDIT 3

OK, this is another idea I came up with. Does model of computation theory include inputs that are volatile by itself? That is, the input changes itself? That is probably not the "language recognition" problem though...

Given that Alan Turing devised the Turing Machine model of computation by abstracting what humans actually do when they compute by hand, I think one would be very hard-pressed to prove that a Turing Machine is more powerful than a human.

[note: by 'human' I assume a person augmented by a writing implement and an unbounded supply of scratch paper (which corresponds to the tape of course).  Without that I believe a human is actually a (dynamically self-reconfigurable) finite-state machine with an extraordinarily large number of states]


How to write a custom editor for a new programming language? Let's say I've finished my compiler for my new language. Next step is write a custom editor with syntax highlighting (type checking and semantic can wait), is there a cookbook or any kind of guidance to accomplish this project?

There has been a shift during the last 5-15 years in how editors and IDEs are built. It was recognized that IDEs have to perform a lot of the same tasks that compilers do.

In fact, in order to support things like lexical highlighting, syntax highlighting, semantic highlighting, refactoring, warnings ("yellow squigglies"), errors ("red squigglies"), intelligent code completion, and all the other things that we have come to expect from a modern development environment, the IDE pretty much is a compiler. It needs to do almost all the things, except for optimization and the actual code generation. But, lexing, parsing, semantic analysis, type inference, type checking, symbol resolution, overload resolution, implicit resolution, control flow analysis, data flow analysis, etc., they all need to be performed. Modern IDEs are actually even expected to do more work than the compiler does, such as NULL checking and tracking for C-like languages, finding unreachable code or unused variables and parameters, finding redundant checks, etc. (For example, I recently found a bug in some of my JavaScript code by the editor telling me based on type information in the documentation comments that the then branch of an if statement was unreachable because the condition I was checking for was impossible.)

So, the change that I alluded to above, is that editors and IDEs are starting to use the actual compiler to perform all this analysis. This leads to some interesting requirements for the compilers, because the way they are used in IDEs and the way they are used as batch compilers is fairly different:

Batch compilers deal with complete programs, IDEs deal with incomplete programs. (Analysis while you type.)
Batch compilers deal with working programs, IDEs deal with broken programs. (Most of the time, while you write the program, it will not be in a working state.)
Batch compilers can take as much time and as much memory as they want, IDEs must ideally give feedback within milliseconds after each keypress, and the "IDE compiler" must share its memory with the editor and the IDE.
A batch compiler's job ends as soon as it hits an error, an IDE only gets started. (E.g. giving hints about how to fix the error, or analyzing the rest of the file.)

This pretty much requires a high degree of re-entrancy, asynchrony, concurrency, and parallelism in the compiler. It requires it to be built in a modular design so that you can separate the optimizer and code generator. It requires it to be built as a library, not just a command line tool. It requires it to be built with open access to the parse tree, AST, flow graphs, etc.

So, not only are modern editors and IDEs built to take advantage of compilers, but modern compilers are built to be embeddable into IDEs.

One of the most high-profile compilers that were explicitly built to be able to be embedded into IDEs is Microsoft's Roslyn compiler for C# and VisualBasic.NET. (Actually, it was built to be even more than that: it was built to be a general platform for language analysis of and language tooling around C# and VB.NET that is easy enough to use that non-compiler writers can write e.g. their own static analysis rules.) Anything you see in Visual Studio, from IntelliSense to highlighting to squigglies to hints to errors to warnings … is built on top of Roslyn.

One of the reasons for creating Clang was that most existing C compilers were not designed to be used as anything but a command line batch compiler. Clang is explicitly designed to be embedded into IDEs and editors. As the documentation says, Clang is designed to Support Diverse Clients.

The Scala Compiler has long had a mode called the Presentation Compiler, which is an asynchronous version of the first 4 (of 27) phases of the compiler. The new compiler for Scala 3 is built from the ground up to support IDEs.

Going further, Microsoft has defined the Language Server Protocol originally for the TypeScript plugin in Visual Studio Code. The LSP is a JSON-RPC protocol that allows a language analyzer and an IDE to communicate with each other using a standard protocol. This turns the m×n problem of providing high-quality plugins for m languages for each of a set of n IDEs into an m+n problem of providing language servers for m languages and LSP clients for n IDEs.

If you implement a language server for your language, it will instantly work with any editor or IDE for which an LSP client is available (e.g. Eclipse, Atom, Sublime Text, Brackets, Emacs, Vim/Neovim, Visual Studio, Visual Studio Code, IDEA, …) And when you implement an LSP client for your IDE or editor, it will instantly work with any language for which a language server is available (e.g. Idris, C, D, Go, ECMAScript, TypeScript, ActionScript, Lua, PHP, Python, Ruby, Haskell, Erlang, Haxe, Elm, Elixir, even some not-so-obvious ones such as IBM Enterprise COBOL for z/OS maintained by IBM itself).

So, coming back to your question

  Let's say I've finished my compiler for my new language. Next step is write a custom editor with syntax highlighting (type checking and semantic can wait), is there a cookbook or any kind of guidance to accomplish this project?

The first piece of guidance on how to build a custom editor with syntax highlighting is to not build a custom editor with syntax highlighting. Build a language server.

The second piece of guidance is to not finish your compiler and then start working on the editing experience. Instead, build the compiler from the ground up to support the editing experience.


What's the output of this algorithm? Given the question below:

Consider that, on the procedure below, the variable X is defined globally and the parameters of the vr function are passed by value

procedure vr(u,v) {
   u = 2*u;
   x = u+v;
   u = u - 1;
}

Define the value of x in the end of the following:

x = 4;
y = 2;
vr(x,y);
print(x);

I always knew that parameters passed by value were actually a copy of the original value, but in this case i can't tell what scope is being used for the function.

I also would like to read more about cases like that. If you can, please leave any suggestive material so i can get more in depth of this subject.

I know that this is a very bad practice of naming variables and should be avoided, but in this case i guess it was intentional for the problem.

You can unroll the procedure:

x = 4;
y = 2;
u = x;
v = y;
u = 2*u;
x = u+v;
u = u-1;
print x;

This is semantically equivalent to your program.

Once you copy the value of x to u, the link between the two disappears. This is in contrast to references in C++ or mutable objects in python, which are really pointers; if u were a reference (i.e., if parameters were passed by reference), then the assignment u = x would have identified the two variables as pointing at the same location in memory. As it is, u is just a value (since parameters are passed by value), and so this linkage is absent.


Finding an automaton with a given number of states Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^*$.

My main problem is that to check for a string of length 4 (0111) I need at least 5 states to begin with. So to my (novice) little brain the question seems wrong.

Hint: for 0111 you need 4 transitions (one for each input letter). If you have a sequence of 5 separate states (which is probably your first try), than you will have 4 transitions between them. However, if you have 4 states connected in a circle, you will also have 4 transition between them...


how to derive the complexity of the randomization solution to the majority element problem The randomization solution is from  majority-element, and the corresponding complexity given confused me very much.

The complete procedure of calculating iterations give is :
$$
\begin{split}
EV(iter_{prob}) & \le EV(iter_{modif}) \\
& \le \lim_{n\to\infty} \sum_{i=1}^n i \times\frac{1}{2^i} \\
& =2
\end{split}
$$

I wanna know how to derive $ \lim_{n\to\infty} \sum_{i=1}^n i \times\frac{1}{2^i} $, and what does it stand for.

Given an array of length $n$, which is promised to have an element $x$ which appears more than $n/2$ times, the goal is to find $x$. Note that $x$ is unique.

The randomized solution goes as follows:

Choose a random element $y$.
Check whether $y$ appears more than $n/2$ times, in time $O(n)$.
If so, return $y$.
Otherwise, go back to the first step.

Since $x$ occurs more than $n/2$ times, the probability to select it is more than $1/2$. Hence the probability that we didn't choose it in the first $t$ attempts is less than $2^t$.

In order to calculate the expected time complexity, let us calculate the expect number of attempts until $y = x$; the expected time complexity would be that multiplied by $O(n)$.

Let $E_t$ denote the event the we got to the $t$th round, that is, that the first $t-1$ attempts did not result in choosing $y = x$. Let $X_t$ be the indicator variable for $E_t$. The number of rounds is thus $X = \sum_{t=1}^\infty X_t$. Linearity of expectation shows that
$$ \mathbb{E}[X] = \sum_{t=1}^\infty \mathbb{E}[X_t] = \sum_{t=1}^\infty \Pr[E_t]. $$
We get to the $t$th round if we failed to find $x$ in the first $t-1$ rounds, so $\Pr[E_t] < 2^{-(t-1)}$. Therefore
$$
\mathbb{E}[X] < \sum_{t=1}^\infty 2^{-(t-1)} = \sum_{t=0}^\infty 2^{-t} = 2,
$$
using the formula for the sum of a geometric series. We conclude that the expected running time of the algorithm is at most $2 \cdot O(n) = O(n)$.

Another way to compute $\mathbb{E}[X]$ is using geometric random variables. Suppose that $x$ appears in $pn$ of the elements; so $p > 1/2$. The random variables $X$ has distribution $G(p)$, that is, geometric with success probability $p$, and so
$$ \mathbb{E}[X] = \frac{1}{1-p} < \frac{1}{1-1/2} = 2. $$

A more sophisticated way to express this is that $X$ is stochastically dominated by a $G(1/2)$ random variable, and so $\mathbb{E}[X] \leq \mathbb{E}[G(1/2)] = 2$.


How to verify the solution to n queens problem I have made an algorithm by which I recently finished counting solutions to 28 queens problem and I have the number. How do I verify that it is correct?

I have heard that it can be done in quadratic time. That is, given a solution to an nqueen problem it can be verified in polynomial time. I would like to know the algorithm too.

Thanks

I suspect what they meant was that if you are given a placement of $n$ queens, you can verify in quadratic time whether that is a valid solution (i.e., none of the queens attack any of the others).

I don't know of any way to verify the count of the number of solutions in quadratic time, and I doubt that such a thing is possible in quadratic time.


Flowcharts vs DFA resp FSM equivalency First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I am a bit confused about this. There are classes where using logical synthesis, Karunaugh maps, state encodings, flip flops etc. one is able to construct hardware consisting of logic gates and flip-flops which realizes the desired DFA. Basically all processes that runs on the computer (no matter if is written in C# or Assembler), are at the lowest level realized through logical gates, zeros and ones. So it seems that programs firstly needs to be converted (by compiler I suppose) to some form as I've described. This might imply that every problem that is solvable using C# is solvable using FSM. But this is in contradiction to Chomsky hierarchy and all this theory related stuff, which says that you cannot do the same magic with regular expressions (which are based on FSM) that you can do on Turing machine (which is equivalent of any programming language, if I am wrong correct me please). Moreover, if flowcharts (or even C#, Java ... source codes) were equivalent to FSM why we do not have all software formally verified so far? There is mathematical apparatus for FSM and related stuff, so why do not formally verify everything and ensure the correctness? What I am missing here?

Converted comments to answer.

FSM is an ambiguous term but is often taken to mean "finite automaton", of which deterministic finite automata (DFAs) are representative. These are strictly less powerful than Turing machines and other Turing-equivalent systems of computation. That said, actual computers running C# programs are not Turing equivalent; in fact, they're a strictly weaker model of computation that finite automata, although many interesting finite automata can be modeled exactly, and many Turing machines can be simulated accurately. PC < FSM ~ DFA < TM.

Suppose that your PC has 1 TB of memory (RAM, registers, stack, HDD, etc.) This is 8796093022208 bits. Your computer can exist in 2^8796093022208 unique states. It is therefore incapable of recognizing any regular language whose minimal DFA contains more than 2^8796093022208 unique states. One such language is the language containing the first 2^8796093022208 words over a unary alphabet (when ordered lexicographically).


Is bounded waiting satisfied in the 2 Process Solution? Suppose, There are $2$ processes $P1$ and $P2$.

It is given that Mutual Exclusion and Progress are satisfied by these $2$ processes.

Suppose, Programming protocol is designed such that CPU only executes $P1$ and $P2$ is never alloted the CPU, So, here $P2$ starves.

My Question :- Is Bounded Waiting satisfied here ?

I think BW is satisfied, as there exists a bound on the number of processes that
may enter after process desires to enter CS. And, here that bound is only 1 as only $P1$ is getting executed and if suppose CPU stops executing $P1$ and then after that only $P2$ will be executed.

Please provide the reason that exactly what happens here ?

A little remark first: The bounded waiting (BW) property is defined with respect to algorithms, which is in turn defined as a set of concrete executions. Thus, we cannot conclude whether an algorithm satisfies BW if a specific execution does.

For your question: For the specific execution in which only $P_1$ takes steps, BW is satisfied. However, it is not because "there exists a bound on the number of processes that may enter after process desires to enter CS". Instead, BW is satisfied simply because $P_2$ does not desire to enter the critical section. See the following definition from Mutual Exclusion (wiki).

  A $k$-bounded waiting property can provide a bounded waiting guarantee and it requires in every execution, a process can only enter the critical section at most $k$ times while another process is waiting to enter the critical section.

A more precise definition can be found in the Book: The Art of Multiprocessor Programming; Exercise 9 in Section 2.10:

  Define $k$-bounded waiting for a given mutual exclusion algorithm to
  mean that if $D_A^j \to D_B^l$ then $CS_A^{j} \to CS_B^{l+k}$.

Here, $D_A^j$ means process $A$ finishes its doorway section for the $j$-th time, and $CS_A^j$ denotes the interval during which $A$ executes the critical section for the $j$-th time.

In the execution above, $D_{P_2}^j \to D_{P_1}^l$ does not hold because $P_2$ does not take any steps at all. Thus, BW is trivially satisfied.

Suppose that $P_2$ has finished its doorway section (i.e., $D_{P_2}^1$ holds) and then halts. If $P_1$ continues entering and exiting the critical section, then BW is broken.

A little remark again:

  I think BW is satisfied, as there exists a bound on the number of processes that may enter after process desires to enter CS.

It seems that you have a misunderstanding about $k$-bounded waiting property. $K$ here is about the number of entering (and exiting) the critical section, instead of the number of processes.


Why do DFAs with a single final state have less power? I came across this question in a test and I had to answer whether it is true or false.

  DFA with single final state has the same powers as DFA with more than one final state.

I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts and to me, it seems that since it is a DFA, regardless of the number of accept states, the power should be the same.

However, the question says that this is false and a DFA with more than one final state is more powerful. Is that true? I've never come across this in any textbook.

I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts

There are, equivalent or nonequivalent, definitions of "power" and "has power" in computation theory. Here is one definition of power that is suitable for the current situation.

A (descriptive) power means a set of languages over an alphabet. Given a set of automata $S$, the (descriptive) power of $S$ is $P(S)=\{L(A)\mid A\in S\}$, where $L(A)$ is the language accepted by $A$. Given two sets of automata $S_1$ and $S_2$, if $P(S_1)=P(S_2)$, we say $S_1$ and $S_2$ has the same power or $S_1$ is as powerful as $S_2$ or $S_1$ is equivalent to $S_2$ in power. If $L(S_1)\subsetneq L_{S_2}$, we say $S_1$ is less powerful than $S_2$.

For a more rigorous definition, we should define the meaning of "$L$ is the language accepted by $A$". However, since that meaning is clear in the context of DFA and NFA, we will skip it here. Note that we only talk about "power" for a set of automata. When we compare powers, the same alphabet is usually implied.

  Since it is a DFA, regardless of the number of accept states, the power should be the same.

Take a moment to reflect. Are you sure you have seen or proved that claim? I would bet you have not, although there are many popular cases of different automata having the same power, such as NFA and DFA have the same power.

On the other hand, there are many cases where if you restrict some aspect of automata, you will decrease its power, which is of course reasonable. For example, if you restrict the stacks of PDAs to be finite, they become equivalent in power to finite automata. If you restrict (deterministic) PDAs to only have one or two states, you will get various powers depending on how PDAs are defined to accept (here are some result).  If you restrict Turing machines to be read-only, they can be considered as two-way finite automata, which have the same power of the usual DFAs.

For an extreme example, if you change DFAs to DFAs with only one state, you will only have two DFAs, one DFA whose start state is not an accept state and one DFA whose start state is also an accept state, whose power is two languages, the empty language and the language of all words over the alphabet.

  DFA with single final state has the same power as DFA with more than one final state.

Final states are also commonly called accept states in the context of DFA or NFA. Fix our alphabet. Let $S_n$ be the set of all DFA that have $n$ accept states, where $n\ge1$. We will show a more general proposition.

(Less accept states, less power). $S_n$ is less powerful than $S_{n+1}$ for all $n$.

Proof. Suppose we have $A\in S_n$. Let $A'\in S_{n+1}$ be the same as $A$ except that $A'$ has one extra accept state that is not used by any transition. Since $L(A)=L(A')$, $S_n$ is at most as powerful as $S_{n+1}$.

Let $a$ be a symbol in the alphabet. Here is the beautiful example by Hendrik Jan. Let $K=\{\lambda, a, a^2, \dots, a^n\}$.

Suppose $K=L(B)$ for some DFA $B$. For the sake of contradiction, suppose both $a^i$ and $a^j$, where $i<j$, are accepted by state $q$ in $B$. That means, given $j-i$ $a$'s, $q$ is transitioned to itself. So given another $j-i$ $a$'s, $q$ will be transitioned to itself again. And so on. That means, all strings $a^i, a^j, a^{i+2(j-i)}, a^{i+3(j-i)}, \cdots$ are accepted. That contradicts the fact that $B$ only accepts the $n+1$ strings in $K$. So all states of $B$ in which these words are accepted must be different. That is, $B$ must have at least $n+1$ accept states.

I will leave it as an exercise for you to construct a DFA with $n+1$ accept states that accepts $K$. Since $K\not\in P(S_n)$ but $K\in P(S_{n+1})$, we have proved "less accept states, less power".

Exercise 1. Show that DFAs with $n$ reject states have less power than DFAs with $n+1$ reject states for all $n\ge1$.

Exercise 2. Let $S_{m,n}$ be the set of DFAs with $m$ accept states and $n$ reject states, $m+n\ge1$. Compare their powers.

Exercise 3. (Provided by Mr. Sigma) Show that NFAs with a single accept state have the same power as all NFAs.

Exercise 4. Show that NFAs with a single accept state and without $\epsilon$-transition have the same power as all NFAs.


What are logical addresses and where do they actually reside? While studying about memory management, paging and segmentation there is a lot of usage of phrases like CPU generates logical addresses and logical addresses are converted to physical addresses etc. I know that the term physical address refers to actual RAM, but I do not have clear idea about what logical address is and where does it reside.

So my questions are:

What is meant by CPU generates logical address?
Where do logical addresses reside (in RAM or somewhere else)?

Can anyone please explain these things.

Well, this is the entire point of "virtual memory".

When your program runs, the OS makes it believe it has all the memory just for itself. That is, addresses 1 to 10,000 (say), are all empty and ready for this program to use. If you run two programs, each one of them gets its own space - each one can access address 1 to 10,000 without any interference between the programs.

Obviously, for this to work, the OS must perform some clever bookkeeping, mapping the programs' "virtual memory" into places in the real memory (or hard disk). That is, when the first program access cell 200, the information needs not be in cell number 200 in the real memory. It may be somewhere else, but the OS is responsible of converting the (virtual/logical address) "200" of the first program to some (real) address X, as well as the virtual "200" address of the second program, to some other (real) address Y.


What is the relation between differential-privacy mechanism and entropy? Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy?

For example :
Laplace distribution that is used to model the noise function happens to saturate the lower bound of Shannon entropy under epsilon differential privacy constraints. See Theorem 8 in Yu Wang, Zhenqi Huang, Sayan Mitra and Geir E. Dullerud, Entropy-minimizing Mechanism for Differential Privacy of
Discrete-time Linear Feedback Systems for an example.

But what is the significance of this saturation?

In general, if you're not sure about the significance of mathematical results in a published paper, often a good first place to look is the paper's introduction and/or conclusion.  The authors often try to provide some explanation why you should care about their results in the introduction and conclusion.

In this case, the following two quotes from the introduction of the paper you cited provide a pretty clear explanation for why the authors care:

  we first study an $\epsilon$-differentially private noise-adding mechanism
  for one-shot queries that provides the best output accuracy,
  which is measured by the Shannon entropy. [...]

  In Section III, we prove that, for a one-shot $n$-dimensional
  input, there is a lower bound $n + n \ln(2\epsilon)$ on the entropy of
  the output for an $\epsilon$-differentially private noise-adding mechanism, and the lower bound is achieved by Laplacian noise
  with parameter $\epsilon$.

In other words, the Shannon entropy measures the accuracy of the output after adding the noise (lower is better); Theorem 8 proves that Laplace noise achieves the lowest possible Shannon entropy, in a particular situation; therefore, we can conclude that Laplace noise is optimal in  the sense that it achieves the highest possible output accuracy, in that situation.


Doubt on Floating Point Representation $1-2^{-23}$ and $2-2^{-22}$ both represents floating point representation or normalised representation.But are those two represent same value or both have different value? Is floating point representation same as IEEE representation??

Is floating point representation same as IEEE representation?

Well, not exactly. Floating point is more the abstract idea for "a fractional number" (of arbitrary magnitude) or rather "a number of varying precision.

On the other hand, IEEE(754) is a specific implementation of this idea. Other standards exist and all of them implement "floating point" numbers.


Is it possible to sort a linked list without copying its values but linking the nodes? Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order.

Also can this be done in a quadratic time?

I will be attempting this in Python.

Copy the list into an array, sort the array, construct a linked list from it.   Done.  It suffices to populate the array with pointers (references) to the values; you don't need to copy the values themselves. The running time will be $\Theta(n \log n)$ if you use an appropriate sorting algorithm -- much faster than quadratic time.


More efficient algorithm for determining if one list is a sublist of another list I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list.

What if the list is sorted?

An algorithm that can do this is by comparing every element of the first list with every element from the second list. I think there is an algorithm with a better complexity. Can anyone give me any idea?

Let's start with the case when the lists are sorted. In that case, you can apply a simple modification of the basic merge algorithm on sorted lists: discard the elements instead of constructing a merged list, and only keep track of whether an element from list 1 was missing from list 2.

In the pseudo-code below, head(list) is the first element of list, and advance(list) means to discard the head of list. In other words, head(cons(h,t)) = h and advance(list) when list = cons(h,t) means list := t.

while list1 is not empty:
    if list2 is empty or head(list1) < head(list2):
        return false
    else if head(list1) = head(list2):
        let x = head(list1)
        while list1 is not empty and head(list1) == x: advance(list1)
        while list2 is not empty and head(list2) == x: advance(list2)
    else: (head(list1) > head(list2))
        advance(list2)
return true

Exercise: prove that this algorithm returns true when all the elements of list1 occur in list2 and false otherwise.

Let $n_1 = \mathrm{length}(\mathtt{list1})$, $n_2 = \mathrm{length}(\mathtt{list2})$ and $n = \max(n_1, n_2)$. The algorithm above removes at least one element of list2 at each iteration, and in the worst case it removes all the elements of both list. Therefore it executes at most $n_2$ iterations of the loop and performs at most $n_1 + n_2$ removals of the head of the list: its complexity is $O(n)$.

Now suppose that the lists are not sorted. An obvious solution is to sort them, then apply the known algorithm. Since sorting is $O(n \log n)$, this algorithm is $O(n \log n)$.

Exercise: make sure you understand why my statements about complexity are true.

Exercise (difficult!): can you do better than $O(n \log n)$ in the general case?


Is there any neutral element for the cryptographic hash function SHA256? (or its variants) My question is
Is is possible to compute a string given that after applying a SHA256 function the result is the same string?

No one knows.  It is believed to be computationally infeasible to find such a string, if one exists.  No one knows whether such a string exists.
By standard heuristics (modelling SHA256 as a random function), there is approximately a $1/e\approx 0.368$ chance that no such input exists, and approximately a $0.632$ chance that such an input exists, so if I were forced to bet, I would bet that it's more likely there exists such an input than that there doesn't, but no one knows.  Don't interpret this chance too seriously: for the specific SHA256 function, either such an input exists or it doesn't.  We don't know which is the case.
If such an input is found, it is believed that it would take about $2^{256}$ steps of computation to find it, which is completely infeasible.


Is there a language for which any string (that works) can be shown to not be pumped using the Pumping Lemma? Of course, whenever the Pumping Lemma for Regular Languages (or CFLs) is applied to a language $L$, only a single string $w \in L$ and $|w| \ge p$ needs to be picked (to eventually show that $w$, when pumped, leaves the language).

Is there a non-regular (or non-context-free) language $L$ for which every string $w \in L$ having $|w| \ge p$ can be used to derive a contradiction?

I'd say the language $L = $ { $0^n1^n | n > 0$ } fits the bill for the Pumping Lemma for Regular Languages.  Any substring to be pumped would consist either of all the same symbol, in which case pumping up produces a string with an unequal number of $0$'s and $1$'s, or it contains instances of both symbols, in which case pumping up produces a string with a $1$ followed by a $0$; in neither case is the pumped-up string in $L$.


What is the height of avl tree with n nodes what is the height of avl tree with n nodes ? Can you explain it with formula ? I couldn't find any formula to solve this problem.

AVL trees are self-balancing binary search trees (another example is red-black trees). By definition, a self-balancing binary tree maintains the property that its height is $\Theta(\log n)$, where $n$ is the number of leaves or vertices (the two properties corresponding to the two different definitions of $n$ are equivalent).

Usually it is costly to have a data-independent height, and so the height depends on the history of the data structure (it depends on the exact order in which values were inserted and deleted), but it is always $O(\log n)$. (Note that every binary tree has height $\Omega(\log n)$.)


Prove that $(L^R)^* = (L^*)^R$ Prove that $(L^R)^* = (L^*)^R$ for all languages $L$.

My attempt: Suppose $w \in (L^R)^*$. So, $w = w_1\dots w_l$, for some $w_1, \dots , w_l \in L^R$. Since $w^R \in L$, then $w^R = w_l\dots w_1$, for some $w_l, \dots , w_1 \in L^*$. Therefore, $(L^R)^* \subseteq (L^*)^R$.
Honestly, I don't know how to proceed onwards, because this part doesn't sound right. I feel like I messed up with those symbols as this topic is really abstract. Any help? Thanks in advance.

If $w \in (L^R)^*$, then $w = w_1 \ldots w_\ell$ for some $w_1,\ldots,w_\ell \in L^R$. Hence $w_1^R,\ldots,w_\ell^R \in L$, and so $w_\ell^R \ldots w_1^R \in L^*$. This shows that $w = (w_\ell^R \ldots w_1^R)^R \in (L^*)^R$.
Similarly, if $w \in (L^*)^R$ then $w = x^R$ for $x \in L^*$. Since $x \in L^*$, $x = x_1 \ldots x_\ell$ for some $x_1,\ldots,x_\ell \in L$. Then $x_1^R,\ldots,x_\ell^R \in L^R$, and so $w = (x_1 \ldots x_\ell)^R = x_\ell^R \ldots x_1^R \in (L^R)^*$.


Online supervised learning algorithm I have labeled examples coming in on the fly, thus I need to create a classifier from sequential data instead of a static example set. Incoming data is fully labeled, there are no unlabeled examples. Each incoming example has a number of features.

E.g. let X by an incoming example with 3 features

X := (day = sunday, weather = sunny, season = summer, label = go to the beach)

I want to incrementally train a classifier such that whenever I see the next occurance of (sunday, sunny, summer) I want the classifier to suggest going to the beach.

Due to memory restrictions I am unable to keep the entire set of training examples.

Can you point me to adequate online/incremental learning algorithms for such a particular problem?

Wikipedia has an overview of online machine learning; I suggest you start there and then look at some of the references linked there, and take a trip to your library to check out some books.

One approach is to use learning algorithms that allow you to iteratively update the learned model, as you receive each training point.

Another approach might be to use an ensemble classifier: you learn multiple weak classifiers, each of which outputs its own prediction at the label, and then to classify any point you run all of the weak classifiers and you take a majority vote of their predictions.

One simplistic method would be to periodically train a new weak classifier and add it to your ensemble.  For instance, suppose you have storage for $n$ points.  You could add each point to storage as you receive it, then when your storage gets full, train a weak classifier on all $n$ of those points, add it to the ensemble, and clear out your storage.

It might be better to bias your storage strategy towards remembering points that you have classified wrong.  For instance, as a simple example, you could reserve $n/3$ storage slots for remembering past points that were misclassified and $2/3$ storage slots for storing the last $2n/3$ points you received.  When the latter gets full, you could train a new weak classifier on all of those $n$ points, add it to the ensemble, then classify all $n$ of those points with the ensemble classifier, discard all the ones that were correctly classified by the ensemble classifier, and keep a random sample of size $n/3$ chosen from the remaining points (moving them into the $n/3$ slots for misclassified points and emptying out the $2n/3$ slots for new points).

Finally, you might also be able to adapt boosting methods to an online setting.  Boosting methods assign a weight to each training point; the higher the weight, the harder the weak classifier tries to classify that point correctly (i.e., the greater the penalty for misclassifying that point).  The idea is that points which have been classified wrong in the past will receive a higher weight, and so future weak classifiers will be biased towards trying to classify those points correctly.  Rather than trying to store all training points you've ever seen, I could imagine trying to store a random sample of the training points, where each point is selected with probability proportional to its weight.  Thus, you could store $n$ training points and their weights; after you train each new weak classifier, you can update the weights of all $n$ remembered points and then sample $n/2$ of them (say, the $n/2$ with highest weights, or take a random sample with distribution given by the weights).

I don't know how well these methods would work, but you could give them a try in your setting and see.  But start by exploring the literature.  You know what they say: a week in the computer lab can save you a day in the library.


Find pixel mapping matrix with minimum iterations The Situation
 I am an electronics engineer and on a volunteer team that have built a prototype eye that has 200*200 sensors that are mapped to the optic nerve, the connection to the optic nerve is random (organic connection is grown) so I need to have the patient draw what they see, I am trying to limit the number of drawings (difficult for a blind person) the patient has to do to get the relationship between the artificial eye output and the correct perception of the image.

The Problem
Given a input image/matrix and an viewable/readable output matrix, what is an algorithm to automatically identify the encoding  with the least number of iterations.

By changing the input one pixel at a time and then examining the output, the relationship can be discovered, this is, however, very inefficient.

Number the pixels from $0$ to $n^2-1$. Then create $\lceil \log_2n^2\rceil$ many pictures. In the $i$-th picture all pixels are black, if the $i$-th bit in their number is $1$, white otherwise.

Note: If you have $2^k$ colors available, you can choose the color for each pixel based on $k$ successive bits of the number. This will reduce the number of images by a factor of $k$.


Complexity of an optimisation problem in 3D I have a collection $P \subseteq \mathbb{R}^3$ of $N$ particles and there is a function $f : P^2 \to \mathbb{R}$. I want to find which configuration of the system minimizes the value of $f$.

Can this problem (or similar ones) be reduced to TSP? Could you point me to literature on the topic?

In my application, $f$ is the atomic van der waals force, which for each pair of particles of atoms is attractive or repulsive depending on some predefined thresholds.

In addition, it would be great to have a list of concrete examples of problems that can be reduced to TSP.

Since TSP is NP-complete, most problems you'll encounter in practice can be.  (NP is a pretty general class.)  A classic paper of Karp gives a large number of other NP-complete problems that, by definition, can be reduced to TSP.


Can a language have more than one DFA? For Example when we consider a DFA that allows the strings having neither sub strings 00 or 11 I can produce the following two DFAs:

First of all, your left DFA is incorrect - it accepts e.g. 011.

Secondly, DFAs can be canonically minimized, so in that sense, you can always find one canonical DFA for a certain language.

But in general, there are infinitely many different DFAs for every language, so you could get different correct answers.


An iterative algorithm for finding the partitions of a set into subsets of a fixed size The question is whether someone could provide an algorithm for finding all the partitions of a set S into subsets of fixed size (assume the fixed size is 2, to make things simpler, in which case the cardinality of S is even) which is iterative and not recursive and which runs in time proportional to the output (and produces no duplicates).  The algorithm, being deterministic, will produce the output in some sorted way. Ideally, it is possible to give a partition as input and generate all the partitions that follow the given one in the ordering in which the algorithm outputs the partitions.  Please advise if the question is not clear.

Let's first describe a notation for our partitions. Let $p_i$ represent the $i$th partition which is made up of $|S|/2$ disjoint pairs of $S$. We can represent $p_i$ as  $$p_i=b_{i,1},b_{i,2},...b_{i,S/2}$$

In order to ensure uniqueness of partitions, we will enforce a sorting on each partition. For each partition $p_i$, each pair in $p_i$ must be sorted. The pairs must also be sorted among themselves i.e.

$$b_{i,j}[0] < b_{i,j}[1]  \;\;\text{and} \;\; b_{i,j} < b_{i,j+1} \;\;\forall j$$

The ordering of the partitions is then defined similarly to other lexicographic orderings.

$$p_i > p_{k} \iff \exists j \;\; \text{s.t.}\;\; \forall j'\in[1, j) \;\;  b_{i,j}=b_{k,j} \land  b_{i,j'}>b_{k,j'}$$

Now, given some partition $p_i$, we can return the next lexicographically larger partition $p_{i+1}$ by using logic similar to the algorithm for obtaining the next permutation of a set of elements. Let us first describe a function $swap(p_i, j)$ and $sort(p_i, j)$.

$swap(p_i) \rightarrow \;\;$ Find the largest $j$ such that there exists a larger element in any of the pairs $b_{i,j'}$ for $j'>j$. Let $x$ be the smallest such element i.e. $x = \min(\{x'\in b_{i,j'} | j' > j \land x' > b_{i,j}[1]\}).$

Then swap $b_{i,j}[1]$ and $x$ and return $j$.

$sort(p_i, j) \rightarrow \;\;$ Sort all of the elements from $b_{i,j}[0]$ to $b_{i,S/2}[1]$ i.e. after calling $sort(p_i, j)$, the sequence $b_{i,j}[0], b_{i,j}[1], ..., b_{i,S/2}[0],b_{i,S/2}[1]$ should be non-decreasing.

Now, we claim that given a partition $p_i$, we can obtain $p_{i+1}$ by running $sort(p_i, swap(p_i)+1)$. The reasoning is identical to that of the "next permutation algorithm" - We must find the largest $j$ such that we can swap $b_{i,j}[1]$ with the next largest value while not changing anything in $b_{i,j'}$ for $j' < j$. After the swap, we must sort the remaining elements to ensure that it is the smallest increase possible. If the remaining elements were not sorted, then by sorting them we would obtain a partition greater than $p_i$ but less than $p_{i+1}$, which is a contradiction.


Is the term $(\lambda x.x)(y y)$ a normal form in call-by-value reduction strategy? I am learning λ-calculus and I have some confusion about it.
Is the term $(\lambda x.x)(y y)$ a normal form in call by value reduction strategy? (where $y$ is a free variable)
From the wikipedia, it says:

Call by value
Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or abstraction).

Here the term $(\lambda x.x)(y y)$ is a beta redex, but the argument  $(y y)$ is not a value.
So the term $(\lambda x.x)(y y)$ is a normal form, because there is no further beta reduction possible.
Is my understanding correct?
Very thanks.

Sorry for updated the question, because I just realized that there may be 2 questions behind:

In λ-calculus, does the terminology "normal form" depend on the evaluation strategy? i.e. When we say a term is a normal form or not, is there any evaluation strategy behind it? For example, CBV ⊢ (λx.x)(yy) be a normal form and CBN ⊢ (λx.x)(yy) be not a normal form?

When we say "a λ-calculus with call-by-value", is it equivalent to say "λ_v-calculus"? I am reading Sabry and Felleisen's paper "Reasoning about Programs in Continuation-Passing Style". That paper mentioned λ_v-calculus and in p.8 it says (λx.x)(yy) has no βv-redex.

After some research, I think I can answer this question by myself now.
Short answer
Wikipedia is correct, that is
If the $\lambda $-calculus uses call by value reduction strategy, the term $(\lambda x.x)(y y)$ is a normal form.
Long answer
Standard $\lambda $-calculus does not distinguish reduction strategies. It only gives you some Reduction Rules (e.g. $\beta $-rule). You searching for a β-redex in a given term, as long as you find a β-redex, you can reduce one step.
This means that

You can reduce a $\beta $-redex inside a $\lambda $-abstraction.
You can reduce the operand $\beta $-redex first and then reduce the operator $\beta $-redex.
At any step, you can use either call-by-value or call-by-name reduction strategy.

Church–Rosser Theorem tells us that the outcome of $\lambda $-calculus (if it exists) is independent of the order in which the calculations are executed.
The benefit of Church–Rosser Theorem is that we can define an Equational Theory at top of the Reduction Rules.
Note that in the description above, I used extremely imprecise terminology, i.e. reduction strategy. Now i will fix this impreciseness:

I think reduction strategy and evaluation strategy mean the same thing.
For now, we cannot use the term "evaluation" because we have not yet defined an Evaluation Theory.

Unfortunately, there is very little literature describe how to define the Evaluation Theory for standard $\lambda $-calculus. The reason may be that:
In general, to define the Evaluation Theory, we need an abstract machine, but the use of an abstract machine means a fixed evaluation strategy, but standard $\lambda $-calculus does not depend on the evaluation strategy!
Therefore standard $\lambda $-calculus has no corresponding Evaluation Theory is logical.
OK, so far so good.
However the standard $\lambda $-calculus is not suitable to reason about programming languages. For example, Scheme/SML use call-by-value evaluation strategy, Haskell use call-by-name (or more precisely call-by-need) evaluation strategy.
To reason about these programming languages, a new $\lambda $-calculus needs to be devised. For example, Plotkin's call-by-value $\lambda $-calculus ($\lambda_v$ for short).
As standard $\lambda $-calculus, we now need to devise Reduction Rules, Equational theory and Evaluation theory for $\lambda_v$. I won't repeat Plotkin's formula here, but give two key points:

In Plotkin's paper, "value" does not mean "has no β-redexes", but "not a combination" (A term of form $(MN)$ is a combination).
Equational theory must satisfy Church–Rosser Theorem (for $\lambda_v$ version).

Back to the original question:
Is the term $(\lambda x.x)(y y)$ a normal form in call by value reduction strategy?
Answer:

The question involved "normal form" and "reduction strategy" (which is another name of evaluation strategy). It doesn't make sense, because one refers to an Equational Theory and the other refers to an Evaluation Theory.

The question involved  "call by value", we can fix this ill-question by assuming the calculus to be $\lambda_v$ and since the question also involved "normal form" and $(\lambda x.x)(y y)$ is not a closed term, we use Equational theory of $\lambda_v$.
The answer is:
$(\lambda x.x)(y y)$ has been a normal form, because $(y y)$ is not a value but a combination.

$(\lambda x.M)N = [N/x]M$ (if $N$ is a value)     ($\beta$ -rule)

You may argue that why $(y y)$ is not a value?
Can I define my own $\lambda_v$-calculus and let a normal form (e.g. $(y y)$) a value?
The answer is no.
For example, suppose that a normal form can be a value, then there are two ways to normal the term $(λx.(λy.z) (x (λx.xx))) (λx.xx)$.

$ \to (λy.z)((λx.xx) (λx.xx))$, then loop
$\to (λx.z)(λx.xx) \to z$

This make Church-Rosser theorem fail.
Similarly, adding $\eta$ rule also makes Church-Rosser theorem fail.
For example, suppose that we add $\eta$ rule, then there are two ways to normal the term $ (λx.y) (λx.((λx.xx) (λx.xx))x)$.

$ \to (λx.y) ((λx.xx) (λx.xx))$, then loop
$\to y $

Reference
Call-by-name, call-by-value and the λ-calculus
Reasoning about programs in continuation-passing style


Is this a proof that SET COVER is not an NP-hard problem? In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows:

  Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = \{p_1, \ldots, p_m\} \subseteq 2^X$ be a family of its
  subsets. Find minimum size sub-family $M$ of $P$ such that
  $X \subseteq \bigcup \{p \mid p \in M\}$.

  An instance of the set cover problem is $\epsilon$-dense if there is
  $\epsilon > 0$ such that any element of $X$ belongs to at least
  $\epsilon \, m$ sets from $P$. We show that the dense set cover
  problem can be approximated with the performance ratio $c \log k$ for
  any $c > 0$ though it is unlikely to be NP-hard.

In page 3, Lemma 2.1 implies—and Theorem 2.2 proves—that $\epsilon$-DENSE SET COVER is not NP-hard. But, since SET COVER is $\frac{1}{m}$-DENSE SET COVER (any element of $X$ belongs to at least 1 of the $m$ sets), would this mean that SET COVER is not NP-hard?

Weighting of elements from set $P$ of SET COVER problem can be obtained by solving a system of linear inequalities for a given $\varepsilon$ that involves $\{0,1\}$-matrix $I=[x_i\in P_j]:$ $Iw\geq\varepsilon\sum\limits_{i=1}^mw_i.$ If it is not feasible then $\varepsilon$-DENSE SET COVER is void. Found weighting can be easily removed by repeating elements of $P$ with respect to the weighting but the resulting problem will be the same. Feasible SET COVER could be reduced to dense one for $\varepsilon=\frac{1}{m}$ but generally aforementioned reduction could lead to void dense problem for constant $\varepsilon.$

In the geometric case when VC-dimension is finite the dense problem with constant $\varepsilon$ could be solved in polynomial time due to result of Haussler and Welzl "epsilon-nets and simplex range queries" claiming existence of feasible solution to $\varepsilon$-dense problem of length $$\frac{8d}{\varepsilon}\log\frac{d}{\varepsilon}.$$
Having upper bound on the problem optimum we could solve te problem by brute-force search. Here $d$ denotes VC-dimension.


Complement of CFL is Recursive If CFL are not closed under complementation, it means that if a language '$L$' is CFL then its compliment $L^C$ is not CFL. Then how can we discuss about $L^C$ being recursive?

My doubt arose because I think if a language cannot be decided CFL or not then how can it be declared Recursive ?

You can think of it as " every CFL is Recursive".
And Recursive languages are closed under complementation.

Therefore, if a language $L$ is CFL then it is also recursive and hence, $L^C$ is also recursive.


In a NPDA if the stack is empty, where the start/end state are the same can you go again Thoughts

I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I am back in q0 and the $ is removed from the stack I stop

There are several alternatives for the definition of a PDA, all of which are equivalent, in the sense that computationally they specify the same class of languages. To answer your question, you can perhaps take a look at the precise definition of PDAs you are working with.

For the following, with $X_\varepsilon$ I mean $X\cup\{\varepsilon\}$.

Some definitions use the signature $$\delta : Q\times\Sigma_\varepsilon\times\Gamma\to \mathcal{P}(Q\times\Gamma^*)$$ for the transition function, where $\Gamma$ is the stack alphabet. From this signature, it is evident that you need to have a symbol in the stack in order to move on. Of course, with this definition all PDAs are initialized with some initial symbol in the stack, before they start running. Otherwise, the PDA will never be able to make its first transition.

There are definitions, though, that use the signature $$\delta : Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\to \mathcal{P}(Q\times\Gamma^*)$$
or
$$\delta : Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\to \mathcal{P}(Q\times\Gamma_\varepsilon)$$
The difference of the two last signatures is in the number of stack symbols they are allowed to push with each transition. But both definitions allow no symbol $(\varepsilon)$ to be popped from the stack. So with these signatures, moves are allowed under empty stacks and the PDA is usually initialized with an empty stack.

From the PDA in the picture, it looks like you are using one of the two latter definitions or something similar, where a PDA is allowed to pop nothing from the stack. So, when you arrive again in $q_0$ with an empty stack (because you removed the last symbol $(\$)$ in it) you are allowed to move to state $q_1$ by reading nothing from the input string, popping nothing from the stack and pushing again the dollar symbol.


Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$? Assuming $\Sigma  = \{  0, 1\}$..

Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$?

So it is the same as showing that $\overline{L}\in NP$, but I'm not really sure on how to prove this.

Does anyone have an idea?

Hint: Suppose we are given a word $w$ of length $n$ which is not in $L$, and let $w_1,\ldots,w_n$ be the words of length $n$ which are in $L$. A witness that $w \notin L$ is the list $w_1,\ldots,w_n$ (all different from $w$!) together with witnesses that $w_1,\ldots,w_n \in L$.


Asymptotic bound of a recursive function Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N?

F(i):
    if i<3then
        return 0
    end if
    return F(i−1) + F(i−2)

$• A. O(N)
• B. O(N^2)
• C.O(2^N)
• D. O(N log(N))$

This may seem like a dumb question but I have no idea how to get asymptotic bounds for recursive methods. I got the following recurrence relation:
$T(n)=T(n-1)+T(n-2)$
but I'm not sure where to go from here. The answer is supposed to be C.

The recurrence relation $T(n) = T(n-1) + T(n-2)$, with initial conditions $T(2) = T(1) = 1$, has as solution the Fibonacci numbers, whose asymptotic growth is known to be $\Theta(\phi^n)$, where $\phi = \frac{1+\sqrt{5}}{2} < 2$. The same bound holds for arbitrary positive initial conditions.


Number of Solutions for Brute Force Algorithm of Travelling Salesperson Problem We are learning about the travelling salesperson problem in my high school class and we are discussing how computers could solve for the problem, even though the problem is intractable, using a brute force algorithm.
I was wondering if the brute force algorithm calculates ALL possibilities for a number, n, or only UNIQUE possibilities.
For example:
If there were 4 locations, labelled A, B, C & D. Starting from A, would you include both A,B,C,D and A,D,C,B even though they are essentially the same?

Thank you for the help :)

In the classic variant of the Travelling Salesperson Problem, the distance from X to Y is the same as the distance from Y to X for any two locations X and Y. Hence, as you noticed, an algorithm does not need to distinguish between the two solutions A, B, C, D and A, D, C, B. However, whether a brute force algorithm considers both solutions or not would depend on how exactly it is implemented. Some will and some won't. It is not too much of a waste to consider them both -- after all, it only takes twice the time. And it may be easier to program the algorithm that way.

There is also a so-called asymmetric variant of the Travelling Salesperson Problem where the cost of moving from X to Y is not necessarily the same as the cost of moving from Y to X. Note that in this case, the two solutions A, B, C, D and A, D, C, B are not "essentially the same" anymore and it is important to consider them both.


RAID: dedicated and distributed parity I understand what parity is (Sort of):
A data recovery mechanism where missing data is calculated based on the data that exists. However i have encountered terminology which i can't define or put into perspective of the RAID system.

This terminology is 'dedicated' and 'distributed' Parity. Now i imagine that it is somehow related to the distribution of data among separate disks, but can anyone give a more detailed definition and explanation of 'Dedicated' and 'Distributed' parity?

Thanks in advance.

The answer to your question can be infered from the wWikipedia page on
"Standard RAID levels".

Parity is just one simple case of techniques for error detection, and the name
seems to be used here to stand for various techniques of error
detection and correction.

The idea of dedicated vs distributed parity, is related to whether the
redundancy of information is on a special dedicated disk or whether it
is distributed over all disks of the RAID system.

This does not apply to RAID 1 where redundancy is achieved by simple
duplication of Data.

In the case of RAID 3 (and apparently RAID 2), data is striped (read
"spread" for faster access) over several disk why the redundancy data
(parity bytes or bits) is in a separate dedicated disk.

In the case of RAID 5, the redundancy is spread over all the disks and mixed into the original base data
(distributed parity) so that the original data can be retrieved
from any set of n-1 disks, when any one of the n disks fails. The
content of the failed disk can be recomputed from the n-1 others.

Distributed parity seems to be preferred to dedicated parity, though the
wikipedia page is not really clear as to why. My own suspicion is that
it allows for more effective error correction than dedicated parity, which keeps the original data and the redundancy (parity) data separate.
But this should be checked.