Attack on hash functions that do not satisfy the one-way property I am revising for a computer security course and I am stuck on one of the past questions. Here is it:

  Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to authenticate that the message has come from her. She proposes to send a single message with two pieces:
  $$ A \to B: \quad M, h(M \mathbin\parallel S_{ab})$$
  where $h$ is a hash function and $\parallel$ denotes concatenation.

  Explain carefully what Bob does to check that the message has come from Alice, and why (apart from properties of $h$) he may believe this.
  Suppose that $h$ does not satisfy the one-way property and it is possible to generate pre-images. Explain what an attacker can do and how.
  If generating pre-images is comparatively time-consuming, suggest a simple countermeasure to improve the protocol without changing $h$.

I think I know the first one. Bob needs to take a hash of the received message along with his shared key and compare that hash with the hash received from Alice, if they match then this should prove Alice sent it.

I am not sure about the second two questions though. For the second one, would the answer be that an attacker can simply obtain the original message given a hash? I'm not sure how that would be done though.

For the second one, would the answer be that an attacker can simply obtain the original message given a hash?

Well, the message $M$ is already given to the adversary (it is sent to Bob over an insecure channel), so he needs not find it. To break the scheme he needs to send a new pair $M^*, h(M^*\|S_{ab})$ such that Bob will accept $M^* \ne M$ as the message sent by Alice.

For the second question: If it is easy to generate pre-images of $h$,
the adversary might be able to learn the secret key $S_{ab}$ from $h(M\| S_{ab})$ thus breaking the scheme.
(Note this might not be trivial. The inverting process might output $M_1, S_1$ such that $h(M\|S_{ab})=h(M_1\|S_1)$, but this is not useful for the adversary.. Furthermore, if the adversary try again to invert $h$, he might get the same pre-image.)

For the third question: Now we assume inverting $h$ takes a lot of time, so let's make the adversary's life harder by requiring him to invert it many times in order to break the scheme. For instance, use the hash $k$ times $h(h(h(....h(M\|S_{ab})..))$. Other solutions exist as well.


Counting certificates for a language Let $M_{1}$ and $M_{2}$ be two (non-deterministic) turing machines accepting the language $L \subseteq \Sigma^{\ast}$.

Is is right to claim that:

$\#M_{1} \in \textbf{#C}$ if and only if $\#M_{2} \in \textbf{#C}$ ?

where $\textbf{#C}$ is a counting complexity class, that is closed under reductions (such as $\textbf{#P}$, $\textbf{#P-Hard}$, $\textbf{GapP}$, $\textbf{GapP-Hard}$, $\textbf{PP}$, etc).

If so, can we use the notation "$\#L \in \textbf{#C}$" ?

Take the language to be $L=\Sigma^*$. $L$ can be solved trivially, so there is a polytime NTM that doesn't use any nondeterminism and solves $L$, call it $M$. The counting function for $M$ is $\#M(x)=1$ which is trivial.

Take $N$ be the following polytime NTM:

$N :=$ on input $x$,
1. nondeterministicly guess $b\in\{0,1\}$,
2. nondeterministicly guess an assignment $\tau$ for $x$,
3. if $b=0$,accept,
4. if $b=1$ and $\tau$ satisfies $x$, accept.
5. otherwise reject.

It is easy to see that $L(N) = L = L(M)$. However $\#N(x)=2^{numvar(x)}+\#SAT(x)$ which is essentially $\#SAT$ and is complete for $\#P$.

$numvar(x)$ denotes the number of propositional variables in $x$.

Therefore the notation $\#L$ is not well-defined (even if we assume $L \in \mathsf{NP}$). You have to fix a NTM $M$ first for $L$ and then talk about $\#M$. Depending on the NTMs you choose for $L$ you will get different counting languages.

In some cases like $SAT$, the intended NTM for the language is clear from context. In such cases, we may use the notation $\#L$ to mean $\#M$ where $M$ is the intended NTM for $L$. Note that even in those cases we are still fixing an NTM for $L$, we just don't state that explicitly.


Removing left factoring from Context-Free Grammar I know that, removing left factoring is a simple task.
And i understand following procedure:

$S→aA | aB$
Becomes:
$S→aS'$
$S'→A|B$

Yet I'm running into problems with this particular grammar:

$S→AD|bbS|bScS|BS $
$A→aAbb | abb$
$B→aB|ba|b$
$D→cDd|cccd$
How to remove left factoring from it, I'm trying to convert  it into LL(1) grammar

Your grammar can be abbreviated as follows:
$S \rightarrow  a^{m}b^{2m}c^{n+2}d^{n}\;|\;(a^{*}(ba|b)|bb)S\;|\;bScS; \; m,n \ge 1$
You can't factor out, for instance, the subexpressions generating the sequences of $a$'s that appear on the left. The language is not even LL($k$), let alone LL($1$).
Consider the following analogous, and simpler, example:
$S \rightarrow aS\;|\;T\; \\
T \rightarrow aTb\;|\;\varepsilon$


Is any of the assumptions hold true for the mentioned? Suppose the use of linear regression. The result of the MSE is 120.5(mean squared error) for the train-set. Wev'e reached the minimum of training the data.
Is it possible that by applying Lasso(L1 form) we would get a lower MSE for the train? and for the test? is the same also holds for Ridge(L2 form)?

Lasso Train
Lasso Test
Ridge Train
Ridge Test

Regularization will always increase the MSE loss on the training set (training loss).  Intuitively, it constraints/limits the set of regression lines you can use.
However, the MSE loss on the test set can be either increase (for the same reason) or decrease (if it has helped combat overfitting and helped bias the classifier towards a simpler hypothesis, and if simpler hypotheses are more likely to be correct).


What is the rationale behind implicitly widening integer types in numeric operations? Languages such as Java and C specify implicit widening of integer types for numeric operators, especially arithmetic operators, to a minimum of 32 bits. What is the rationale behind doing this?

My impression is that it's based on the end-programmer's expectations - that is, 200 + 100 should yield 300, and not overflow to 44. Is there additional impetus behind this implicit type conversion?

This decision to widen only to 32 bits seems a bit arbitrary to me. Besides performance/memory concerns (some target instruction sets don't support 64-bit numbers, so more instructions are necessary), why not widen to 64 bits to minimize overflow as much as possible? If a language were designed which required 64-bit integer promotion for the operands of a numeric operation, would a sufficiently sophisticated optimizer be able to optimize down to 32-bits where sufficient (or, given that I have a pretty poor grasp on computability, is such an optimization impossible)?

TLDR: why are 200 and 100 in 200 + 100 widened to 32 bits? Why not 64 bits? Would a language be significantly inefficient if converted operands to 64 bits, especially if implemented with a "good" optimizer?

First of all, when you write 200 + 100 the compiler deduces the type for both numbers. It's assigning int which has a width of 32bits on most languages and target architectures, so your 200 was never just 0xC8, it always were 0x000000C8 (on little endian).

Why are we still using 32bits?
My guess is that 32bits is still the sweet spot for avoiding overflows while not using too much memory.

Moving from 32bits to 64bits requires twice the memory, that is trivial, but has some details.

Twice the memory will have to be moved, and the memory copying speed won't increase.
Twice the memory will not only reside on your ram, but also on the cache of your CPU, and while your system may have a lot of ram it still has quite limited cache. Take for example the i7-4790K, quite more powerful and expensive than your average CPU. It says it has 8MB of cache, but that is Level-3 cache, it has 4x32kB data Level-1 cache to use across it's 4 cores, now memory seems expensive.
When I mentioned the Level-1 cache I was only bringing you closer to the real thing. Your CPU operates on it's registers and they are even more limited.

This may seem interesting now: Memory hierarchy

"Most modern CPUs are so fast that for most program workloads, the bottleneck is the locality of reference of memory accesses and the efficiency of the caching and memory transfer between different levels of the hierarchy"

Edit: I forgot to mention that because of the no-overhead backwards compatibility of the amd64 (x86-64) architecture, 32bits operations are done just as fast as 64bits operations, but probably that also applies to 16bits.


Evolving expert systems with machine learning Expert systems seem to have been left at the wayside a little bit in the 21st century. In fact, expert-systems was not even a tag on this site (until I just created it). The traditional focus in expert systems has been on rule based systems and logical resolution via, for example, 2-SAT backward chaining. Have there been attempts to integrate modern machine learning with traditional expert systems theory?

I have been interested in this question and started simple experiments. The idea is to have a basic axiom set that cannot be changed combined with dynamic extension and sensor input. Genetic algorithms add axioms. There can be many sets existing at the same time. In an additional step integration of the sets is attempted by replacing n-ary predicates with (n+m)-ary predicates.

Example: virtual rats learn ways through mazes. There are several mazes and rats can learn any of them. Each maze defines a mapping of sequences of go-left/straight/right decisions to reward/n-reward consequences. The height of the reward also depends on the number of rats that found the way before. The variation is maintained because there is competition, so when a rat variant knowing one maze becomes frequent then knowing a less commonly known maze would become more valuable. In addition to the mazes, there are regularities in the dynamics of the environment, something like: type-1 maze will change to type-2 after 100 runs and change back after 50 runs. This allows the integration of different strategies because switching after frustration is
usually good thanks to the relative stability of conditions.

I did not get beyond initial steps before I had to focus completely on a commercial project again. But I would love to resume work on the idea. If you find more information, please let me know: peter.krall@red-queen-innovations.eu


Prove an arithmetic property of a partial recursive function I have this program written in haskell :

I have to prove that:
    $(\forall a \in \mathbb{N})[!D_V [h](a) \Rightarrow log_2 (D_V[h](a) )\equiv 2  (mod$ $ 10) ]$.

The predicate $P_2$ for the $g$ function is obvious :
$P_2(f,g) \equiv (\forall x,y \in \mathbb{N})[!g(x,y) \Rightarrow g(x,y)\backsimeq xy]$.

But the predicate for the function $f$ which would give me authomaticaly the one for $h$ I have no idea what it should be.

Any ideas and help in solving this problem is welcomed :)

Notations:

$D_V[h]$: denotational semantics with passing by value of the function $f$.
$!F(x)$ means that $F$ is defined at point $x$.
$F(x) \backsimeq V$ means has the value $V$ at the point $x$ or is undefined.

The function $f$ computes the recurrence relation
$$
f(x) = \begin{cases}
4 & x \leq 1, \\
f(x-1)^2 f(x-2)^4 & x > 1.
\end{cases}
$$
Taking $\ell = \log_2 \circ f$, we get
$$
\ell(x) = \begin{cases}
2 & x \leq 1, \\
2\ell(x-1) + 4\ell(x-2) & x > 1.
\end{cases}
$$
Now, modulo 10 we have
$$
2 \cdot 2 + 4 \cdot 2 = 12 \equiv 2 \pmod{10}.
$$
An easy proof by induction then shows that $\ell(x) \equiv 2 \pmod{10}$ for all $x$.


Flow in a network: Conservation of flow definition This might be too easy... But I just don't get it.

I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow_network

$\sum\limits_{w\in V} f(u,w) = 0 $
$(\forall u \in V-\{s, t\})$

That implies
$\sum\limits_{(u,v)\in E} f(u,v) = \sum\limits_{(v, z)\in E} f(v,z)$

It sounds trivial, but how does that implication work?
The flow is 0 when there is no edge. So I think I can rewrite the first sum to:

$\sum\limits_{w\in V} f(u,w) = 0 \iff
\sum\limits_{(u,v)\in E} f(u,v) = 0 $ for a node $u$

That would result in every flow being zero, wouldn't it?
What am I doing wrong?

Thanks in advance :)

The short answer is $f(u,v)=-f(v,u)$.  Note that the first sum includes both vertices $w$ such that $(u,w) \in E$, as well as vertices $w$ such that $(u,w) \notin E$ but $(w,u) \in E$.  Now unpack the implications of the first sum, separating by these two cases, and I think you'll see what happens.

For a more lengthy explanation, this is covered in standard textbooks.  Make a trip to a library to check out a few textbooks to find a detailed derivation; or, there are even online algorithm texts.


Determine aproximation factor in a greedy algorithm Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences.
  We want to choose a menu such that we minimize the cost and such that at least one preference for each guest is satisfied.

I implemented an easy greedy algorithm that orders each element in respect of their $\frac{\text{# of people satisfied}}{\text{cost}}$ for example if element "a" satisfies 3 people if choose and has a cost of 10, its ratio would be $3/10$. I chose each element in a non-increasing order. Until i run out of people to satisfy.

How do i find the approximation factor for this algorithm? I think it should be around 2 since it's very similar to a greedy approach to knapsack problem, but i have no clue on how to demonstrate it.

So if you are not updating the #satisfied/cost ratio after every selection, this algorithm won't perform well. Let $n$ be the number of people and $m$ the number of meals. We denote  the cost of meal $i$ by $w_i$. Let's say people $1...n-1$ are all satisfied by meals $1...m-1$ which all have the same cost, but person $n$ will only eat meal $m$. If the cost of meal $m$ is any more than $w_1/(n-1)$, then your algorithm will select every meal.

If we instead modify the algorithm so that after every meal selection we recalculate the ratio excluding people that have already been satisfied, we can prove that the bound is $H_d$, where $d$ is the maximum number of people that a single menu item can satisfy and $H_d$ is the $d$th harmonic number.

Consider instead framing the problem as a weighted set cover problem. Each meal $i$ covers some subset of people $S_i \subseteq \{1,...,n\}$ and has a weight $w_i$. You want to select meals such that all people are covered and the cost of the meals is minimized. The slightly modified version of your algorithm below is an $H_d$ approximation to the weighted set cover problem. The proof is rather involved and can be found in section 5.3 here. Note that $j\gets \arg\min_k\frac{w_k}{|S_k\bigcap Uncovered|}$ in the algorithm is equivalent to selecting the max in your ratio i.e.

$$\arg\min_k\frac{w_k}{|S_k\bigcap Uncovered|} = \arg\max_k\frac{|S_k\bigcap Uncovered|}{w_k}$$
The algorithm is below:


Algorithms: Determining Asymptotic Notation from a given execution time I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it.

Question 1: An Algorithm with an worst-case execution time of 3n*(log n), being n the number of elements in the input, is:

a) An algorithm with an execution time of type Θ(n log n).
b) An algorithm with an execution time of type O(n log n).
c) An algorithm with an execution time of type O(n^2).
d) None of the above.

Question 2: An Algorithm with an execution time of 2^100 + (1/3)*n^2 + 100n, being n the number of elements in the input, is:

a) An algorithm with an execution time of type Θ(n^2).
b) An algorithm with an execution time of type O(2^n).
c) An algorithm with an execution time of type Θ(2^n).
d) None of the above.

I want to know how I can think about these problems in order to solve them. Any help is welcome (even by just giving the solution to these two questions). Thanks.

Assuming that $f(n)$ and $g(n)$ are asymptotically positive (as it is usually the case) you can use the following sufficient condition to determine the asymptotic relation of $f(n)$ and $g(n)$.

If $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ exists and is $c \in \mathbb{R_0^+} \cup \{+\infty\}$, then:

If $c< +\infty$ then $f(n) = O(g(n))$ (and $g(n) = \Omega(f(n))$). In particular:

If $0 < c < +\infty$ then $f(n) = \Theta(g(n))$ (and $g(n) = \Theta(f(n))$).
If $c=0$ then $f(n) = o(g(n))$ (and $g(n) = \omega(f(n))$).

If $c > 0$ then $f(n) = \Omega(n))$ (and $g(n) = O(f(n))$). In particular:

If $0 < c < +\infty$ then $f(n) = \Theta(g(n))$ (and $g(n) = \Theta(f(n))$).
If $c = +\infty$ then $f(n) = \omega(g(n))$ (and $g(n) = o(f(n))$).

Moreover, in computing the limit, you can replace  $f(n)$ with a function $h(n)$ such that $h(n) \sim f(n)$ (see, e.g., this page on Wikipedia). The same holds for $g(n)$.
For polynomials this amounts to taking the monomial of highest degree. Moreover, since scaling $c$ by a (positive) constant does not change the asymptotic relation between $f(n)$ and $g(n)$, you can also drop any multiplicative constant (which will always be positive since $f(n)$ and $g(n)$ are asymptotically positive).

For example, instead of comparing $f(n) = 3n^2 + 2n +50$ with $g(n) = 5n^5 + 4n^3 - 2^{10}$, you can compare $x^2$ with $x^5$ instead. This immediately shows that $c$ exists and is $0$, therefore $f(n) = O(g(n))$
 and, in particular, $f(n) = o(g(n))$.

While the above rules will probably work for the vast majority of the functions you will encounter, they can't always be used. Consider, for example, $f(n) = 2 + \sin(n)$ and $g(n) = 1$. Here $f(n) = \Theta(g(n))$ but $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ does not exist.


Solve Time Complexity problem using Time Hierarchy I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use Time Hierarchy.

I need to show that the following are either equal, on inclusive of one another...

TIME($2^{n^2}$) and TIME($n^3 \times 2^n$)

My intuition tells me that...

TIME($n^3 \times 2^n$) $\subset$ TIME($2^{n^2}$)

Can someone explain how I can prove this using the rules of Time Hierarchy?

Your intuition that $ \text{TIME}(n^3 \times 2^n) \subsetneq \text{TIME}(2^{n^2})$ is correct.

It is easy to see that $2^{n^2}$ is time-constructible. Given $n$, you can compute $n^2$ in $\log^2 n$ time, then write 100...00 with $n^2$ zeros, in time $O(n^2)$.

The Time-Hierarchy Theorem states that, for such time-constructible  $f(n)$,

$$ \text{TIME}(o(\frac{f(n)}{\log f(n)})) \subsetneq \text{TIME}(f(n))$$

It is clear that $ n^3 \times 2^n \in o(\frac{2^{n^2}}{\log 2^{n^2}}) = o(\frac{2^{n^2}}{n^2}) $.

Therefore, $ \text{TIME}(n^3 \times 2^n) \subseteq \text{TIME}(o(\frac{2^{n^2}}{\log 2^{n^2}})) \subsetneq \text{TIME}(2^{n^2})$.


Help with model answer for time complexity Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n?
I tried to write this in python to understand when it would be n-1 and the answer is always n. I am assuming that the loop counter in pseudo-code is evaluated one more time than the body is executed as is said in the Cormen book.
My thinking is that if the length of n is 1, the loop evaluation is still tested so regardless the answer would still be n, even if the loop body itself did not run.
Max(A)

1 MaxInt = A[1]
2 index = 2
3 while index ≤ n // Why is the best n-1 here?
4   if MaxInt < A[index]
5     MaxInt = A[index]
6   index = index+1
7 return MaxInt

I know it has to be something very simple but I cant seem to work it out as testing with 1 or 1000 the answer I get back for a count is always n-1 (0, 999) and if I assume that the loops asserts a final time that is + 1, so 0 + 1 = 1, which is n and 999 + 1 = 1000 which is n.

The loop body will be executed $n - 1$ times because your index variable is initially set to $2$ rather than $1$.
Hence, at the start of the loop body, the values for index are from the range $\{2, 3, ..., n\}$, which has $n - 1$ elements.


Finding short readable representation of words I am looking for Input/Literature on

a readable way to represent words (which are accepted by automata)
an Algorithm, that constructs the Representation

For example, a word $w$ might contain a subsequence $v$ which is repeated $m$ times, i.e. $w= u \, \underbrace{v\cdots v}_{100} \,x$ where $u,v,w,x \in \Sigma^*$

In a readable representation, I would expect this subsequence to occur only once, together with the information about the 100 repetitions.

Motivation:

I am working on an interactive input interface for a tool, that works with words that are accepted by automata.
It requires the user to interact with possibly long words

generated by the system
or select words interactively himself

My Approach:

The representation I currently use structurally can be understood is an ordered tree, where

the leaves are symbols $a \in \Sigma$
the inner nodes are repetition counters $i \in \mathbb{N}$

Example:

$w = ABABAC \, ABABACAC \,ABABACAC \,ABABACAC$

Representations

$\overbrace{AB}^{2}AC\overbrace{\overbrace{AB}^{2}\overbrace{AC}^{2}}^{3}$
$\overbrace{\overbrace{AB}^{2}AC}^{2}\overbrace{AC\overbrace{AB}^{2}AC}^{2}AC$

I have implemented an algorithm which, given $w$, finds the 2. representation.
I would consider 1. more appealing, and I assume, that I would generally prefer representations that are minimal with respect to length (where length is the total amounts of symbols/tree-leaves)

My Questions:

Is there a good algorithm to find representations minimal with respect to length?
Does that have a name? Is there Literature on the topic? (I couldn't find anything useful)
Can someone think of an alternative/better approach?

Given a string $S$ of length $n$, one can find the minimal representation in $O(n^3)$ time using dynamic programming.

Let's consider a representation as a binary tree.  Each node of the tree generates a string (a substring of $S$).  Each leaf generates to a single letter.  The tree has two types of internal nodes: a concatenation node, which generates the concatenation of the strings generated by its two children; and a repetition node, which takes the string generated by its only child and repeats it $r$ times, where $r$ is an integer stored in the node.  Your diagrams can all be represented in this form.

Now given a string $S$, we can find the minimal binary tree that generates it, using dynamic programming.  We'll let $A[i,j]$ denote the minimal binary tree that generates the substring $S[i..j-1]$.

We can derive a recursive expression for $A[i,k]$.  In particular, consider all of the following trees:

a tree with a concatenation node at the root, and a left child $A[i,j]$ and a right child $A[j,k]$ (one such tree for each $j$)
a tree with a repetition node at the root, holding the integer $r$, and a single child $A[i,i+(j-i)/r]$ (one such tree for each divisor $r$ of $j-i$)

We will find the smallest of these trees, and store the result in $A[i,k]$.

By evaluating this recursive relation in a bottom-up fashion (i.e., fill in entries of $A[i,j]$ in order of increasing value of $j-i$), we can fill in the entire table.  There are $O(n^2)$ entries in the table, and each entry takes $O(n)$ time to fill in, so the total running time is $O(n^3)$.

As far as related concepts, your idea is similar to a context-free grammar, augmented with the notion of repetition (e.g., we add a production $A \to r \otimes B$, which means that if a word $w$ that can be produced by $B$, then $w^r$ can be produced by $A$).  I haven't seen that particular notion explored, but context-free grammars are well-explored.

If you want heuristics to find a relatively small representation, but not necessarily the minimal one, you might be interested in the Sequitur algorithm and other uses of context-free grammars for data compression.  I think that the Sequitur algorithm can be modified to work in your setting: i.e., given a string, find a (hopefully small) representation of that string.


how to binarize an image? I don't want to binarize a certain image through another program, I want to know how to binarize things myself. All I know is that there is something to do with a threshold and if it is above the threshold it is either 1 or 0 and the opposite if below. My images are using RGB but I can also use HSB or HSV. I just want the algorithm to do so . :)

There is Otsu method to use variance when splitting.

Taking your own steps you should convert RGB to grayscale (simple mean like $(R+G+B)/3$, or use luminance grayscale).

The next step is to give some threshold, from Otsu or arbitrary given by your choice, and operating on grayscale image everything below (or equal) is 0, so it will be black, and greater than threshold is 1 (white).

Operations on other scheme like HSL is exactly taking luminance, but the full change RGB -> HSL is not needed because you discard color info.

Situation when values are out of range does not occur, so do not worry.


How can I examine the subnetworks of a nearly fully connected graph? I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a weight given by a weight matrix.
My goal is to visualize subnetworks (areas where points close to each other also have a dense set of edge weights) where the subnetwork is colored by the given weight. However, this is extremely computationally expensive, as there are 9M edges. I'm looking for an algorithm that can either return the subnetworks, visualize these subnetworks, or something similar.

It sounds like you don't need to be talking about this as a "graph" data structure.. you have points in R3 and you want to partition them into clusters based on their distances (or their pairwise weight matrix). This is more a statistical clustering problem than a graph clustering problem.
Here are some python functions to accomplish these:
https://scikit-learn.org/stable/modules/clustering.html


Min spanning tree that preserves total weight of original graph I have a directed, weighted graph with no double edges. Each node represents a person, and each edge represents a debt. I want to reduce the total number of transactions required to settle all debt, i.e. have the smallest number of edges while maintaining fairness.

I've noticed that you can eliminate edges when you owe person A who owes person B, but you also owe person B. Therefore, you can take on the debt of A directly, reducing the size of the graph to two edges instead of 3:

   ME                   ME
  /  \                 /  \
 /    \               /    \
B <--- A     ====>   B      A

(ME points to A and B)

I'm having trouble coming up with a general approach for this, and I'm not sure what to google since this is an unusual use of spanning tree.

I've thought about building up the graph one edge at a time, then analyzing what simplifications can be made, but the build order seems to matter and often does not produce the most optimal graph.

Edit: formalized constraints

There is a set of individuals $p$ that may owe each other money. For any pair $(p_i, p_j)$, if they owe each other money, it is one directional, i.e. $p_i$ cannot owe money to $p_j$ if $p_j$ owes money to $p_i$.

You are given a list with entries $p_x \to p_y, n$ where $n \in R$. This means that $p_x$ owes $p_y$ $n$ amount of dollars.

Your goal is to return a list of identical form with the following constraints:

It is fair in the sense that each individual in $p$ incurs a wealth difference as if the transactions in the original list were performed.
It is the shortest such list possible

Let us represent the people involved by numbers $1,\ldots,n$. For person $i$, let $\delta_i$ be the total amount that person $i$ is owed minus the total amount that she owes; notice that $\sum_{i=1}^n \delta_i = 0$. After all transactions have cleared, the capital of person $i$ should change by $\delta_i$. I will now show how to implement this scheme using at most $n-1$ transactions, using an iterative procedure.

If all $\delta_i$ are zero then no transactions need to be done, so we can assume that there exists some non-zero $\delta_i$. Let $i$ be a person such that $|\delta_i|$ is minimal. Since the $\delta_i$ sum to zero, there must be some $\delta_j$ with opposite sign. By our choice of $\delta_i$, $|\delta_j| \geq |\delta_i|$. If $\delta_i > 0$ then we tell person $j$ to pay person $i$ the amount of $\delta_i$, and if $\delta_i < 0$ then we make the opposite transaction. We update the $\delta$ vector accordingly: $\delta_i := 0$ and $\delta_j := \delta_j + \delta_i$ (maintaining the invariant that the $\delta_i$ sum to zero), and continue to the next iteration. In each iteration we zero out at least one $\delta_i$, so in iteration $n-1$ there will be at most two non-zero $\delta_i$, which will both be zeroed during the iteration (since they sum to zero). This shows that there are at most $n-1$ transactions in total.

Minimizing the total number of transactions is NP-hard, by reduction from the following problem:

  Given $n$ numbers in the range $[-n,+n]$ summing to zero and an integer $k$, can the numbers be partitioned into $k$ sets summing to zero?

This problem is shown to be NP-hard on math.se.

We will reduce this problem to the following:

  Given an owe graph and an integer $\ell$, can the graph be implemented using at most $\ell$ transactions?

Suppose that we are given a list of $n$ numbers $x_1,\ldots,x_n$ summing to zero and an integer $k$. Running the algorithm above, we construct an owe graph in which $\delta_i = x_i$. I claim that this owe graph can be implemented using $n-k$ transactions iff the list can be partitioned into $k$ parts summing to zero.

Suppose first that the list can be partitioned into $k$ parts summing to zero. Running the algorithm above for each of the parts, we end up with $n-k$ transactions. Conversely, suppose that the graph can be implemented using $n-k$ transactions. Thought of as a graph, these support at least $k$ connected components, each of which corresponding to a list summing to zero.


If it's Possible to Create the If-Statement from Simpler Primitives This question is about how to create an if statement (one of the control-flow statements) from scratch.

An if-statement is typically a built-in construct in languages. However, I am wondering if there is a way to construct an if-statement from some other non-control-flow primitives. I am also wondering how to do this with Boolean algebra, and there is a link there to how to represent if/else statements with circuits.

I started off trying like this:

var x = true
var run = {
    true: [],
    false: []
}
var state = []
while (true) {
    x = !x
    var arr = run[x == true]
    for (var i = 0, n = arr.length; i < n; i++) {

    }
}

That x toggle seemed like it could be used to somehow shift the evaluation path. Then in the state array there would be states of the application listed, and so the application would go into that state if the x was 0 vs. 1. But there pops up the if right there, so it's hard to make it work without resorting to if somewhere. The for loop is also a form of control-flow, so would hope to avoid that.

Was going to try to test it out to simulate a program such as this:

if (a == 1) {
    if (b == 1) {
        console.log('1.1')
    }

    if (b == 2) {
        console.log('1.2')
    }
}

if (a == 2) {
    if (b == 1) {
        console.log('2.1')
    }

    if (b == 2) {
        console.log('2.2')
    }
}

if (a == 3) {
    if (b == 1) {
        console.log('3.1')
    }

    if (b == 2) {
        console.log('3.2')
    }
}

The program would then run:

myiftest(1, 1) // a == 1, b == 1
myiftest(1, 2)
...

There are ways to sort of cheat, such as using && to hack the conditional. For example:

a == 1 && b == 1 && console.log('1.1')

You could also do it with a while loop:

while (a == 1 && b == 1) {
  console.log('1.1')
  break
}

I would like to see if there's any way to do this using only non-control-flow statements in JavaScript (or in C, Ruby, or Python, any modern iterative language, or even Assembly which might make it easier), i.e. not cheating like the above. I don't even know if it's possible, so any form that shows it is possible (or not possible!) would be great to know.

It's okay to use the while(true) loop to start it out, so the program actually runs (if necessary).

Even in assembly the "if" statement is built into the jmp or jump-/branch-related statements.

Contrary to what you (and many people) may think, in the field of programming languages, the most primitive control-flow operation is actually pattern matching!

With a simple type system (say the simply-typed lambda calculus) plus unit types and sum types, you can encode the boolean type easily. Let $\mathbf{1}$ be the unit type. The boolean type is simply $\mathbf{1} + \mathbf{1}$, i.e. the sum of two unit types (because each variation has exactly one inhabitant, respectively "true" and "false").

Now, when we get a sum type, we can destruct it by pattern matching. That is, for each branch of the sum type, we return a different expression. This is the most basic control-flow operation! The expression if b then et else ef is simply sugar for:

match b with
| left -> et
| right -> ef

Interesting, isn't it?

Of course, this is not how machines work, but from a lambda-calculus/type theory standpoint, pattern matching is the father of all conditional execution!


Is there an example of an oracle A such that P = NP but $\mathsf{P}^A\neq\mathsf{NP}^A$? The question is stated in the title, I would like to see a counter example if there is any.
Thanks.

Jonathan Katz explains the original construction due to Baker, Gill and Solovay in his lecture notes.

The idea is to construct such a language by diagonalization. The first step is to show the lemma that for any deterministic, polynomial-time oracle machine $M$, you can construct a language $B$ so that $M^B$ (that is, $M$ with oracle access to $B$) does not decide the language $L_B = \{1^n\textrm{ | }B \textrm{ contains a string of length } n\}$. For sufficiently large $n$, $M$ can not query all strings of length $n$ of $B$, so it is possible to "hide" (or not) a string of length $n$ in $B$ so that $M$ gives the wrong answer.

Note that $L_B$ is in $NP$ since for a given $n$ we can guess the string of length $n$ (if any) that is in $B$ and then query the oracle once.

This doesn't give the desired result (it says that for any deterministic, polynomial-time TM there is a language rather than for any language there is a TM). However, we can enumerate all deterministic, polynomial Turing oracle machines $M_1,M_2,M_3,\ldots$. We can (by the lemma) construct a language $B_1$ for which $M_1^{B_1}$ fails to decide $B_1$. Using a construction similar to in the lemma, we can then modify $B_1$ to obtain $B_2$ so that both $M_1^{B_2}$ and $M_2^{B_2}$ fail to decide $B_2$, and so on...

We eventually obtain a language $B_{\infty}$ so that $L_{B_{\infty}}$ is in $NP^{B_{\infty}}$, but not in $P^{B_{\infty}}$


Cook–Levin theorem and reduction as injective function I saw that the injectivity "derives directly from the theorem", but i can't see how it's happen, any explanation?

Your question is a bit unclear, but let me hazard a guess. Let $L$ be an NP language. According to the Cook–Levin theorem, there is a polynomial time reduction $\phi_L$ from $L$ to SAT, that is, $\phi_L$ is a polynomial time function that satisfies $x \in L$ iff $\phi_L(x) \in \mathrm{SAT}$. You are asking why $\phi_L$ is injective.
Roughly speaking, $\phi_L(x)$ constructs a formula which describes the operation of a nondeterministic Turing machine for $L$ executing on $x$. The input $x$ is hardcoded in this description, and in particular, we can extract $x$ from $\phi_L(x)$. This implies that $\phi_L$ is injective.


Grammar generating odd number of 1s I have the language $L = \{w ∈ \{0, 1, 2\}^∗ \mid \text{the number of 1s in $w$ is odd}\}$.

I am stuck halfway through this process.

I have

$$
\begin{align*}
    &A \to 0A \mid \epsilon \\
    &B \to 2B \mid \epsilon \\
    &C \to AB \mid BA
\end{align*}
$$

This should take care of 0s and 2s.

Now I have this, but I'm not sure if this is right

$$
\begin{align*}
    &X \to 1Y \mid Y1 \\
    &Y \to YC1C1 \mid C \mid \epsilon
\end{align*}
$$

I would split the language in a part that assures that the number of 1s is odd (like, one 1), and another part of the language that maintains that. Similar to induction. So the first step is to write

$$S \rightarrow A1A$$

This makes sure there is at least one $1$ in our grammar, and $A$ is must maintain that. Any number of $0$s or $2$s have no effect, as well as the empty string:

$$A \rightarrow 0A \mid A0$$
$$A \rightarrow 2A \mid A2$$
$$A \rightarrow \lambda$$

However, if $A$ contains a $1$, it must contain at least another one. How can we enforce this? Simple! We re-use $S$, which already enforces this:

$$A \rightarrow 1S\mid S1$$

Note that I made every rule symmetrical regarding order. This is not a good practice in general when writing grammars for actual parsing, as it leads to highly ambiguous grammars. However here the focus is on getting the requirements right, so having not to worry about order at all makes it a bit easier.


PAC learning vs. learning on uniform distribution The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for any distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists $m$ such that on an input of $m$ i.i.d samples $(x, f(x))$ where $x\sim D$, $A$ returns, with probability larger than $1-\delta$, a function which is $\epsilon$-close to $f$ (with respect to $D$). The class $\mathcal{F}$ is efficiently PAC learnable if it is PAC learnable, and $A$ runs in time $\text{poly}(1/\epsilon, 1/\delta, n)$ (where $|x| = n$) and the description of $f$.

Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?

Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?

This has been asked on TCS.SE.
It looks like the short answer is yes -- Aaron Roth gives the example of width-$k$ conjunctions for $k \gg \log n$. And in the comments, Avrim Blum is quoted as giving the answer of $2$-term DNF.

I don't totally understand the examples there -- it must take a bit more work to really derive the result (I will update this answer if I find a self-contained proof). But the general problem here with the uniform distribution is that if the target function $f$ is "sparse", meaning it labels at most a $\delta$ fraction of the input distribution with $1$, then it is easy to learn by simply guessing $0$.

Beyond just efficient (polynomial) PAC learning, there are other examples where the uniform distribution seems to help. For example, a classic hard problem for PAC learning is DNF, a problem which is conjectured to be not PAC learnable, and quite hard. On the other hand DNF over the uniform distribution is almost PAC learnable: we have a qausipolynomial time algorithm for it. See these notes and these notes.

In summary, there appears to be a lot of work on learning under the uniform distribution (search "PAC learning under uniform distribution" for additional references). And it seems that this problem is easier than studying PAC learning, where we aren't able to prove much. Quoting Ryan O'Donnell's notes above:

  General PAC-learning insists that one algorithm works simultaneously for all distributions. In fact, the machine learning community interested in real-world applications finds the uniform setting questionable: "They’ll punch you in the nose if you try to tell them about algorithms in this
  framework." --Ryan. But, in a more general framework, no one can really prove anything.


Help on using the pumping lemma? I'm trying to prove that a language is not regular. That language is:

{w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}.

I have an inkling that this language is not regular, so when I go to apply the pumping lemma, I would apply it on some subset of the language, and the pump on that, right? So, let's say I choose to pump on a, and then I'm able to produce a string that should be in the language, but it isn't. I can do this because when I pump on a, I can produce a string that is not in the language because it will not be the same mod 2. But, I am having a hard time understanding if this is really true. I'm trying to construct a DFA that is able to count the amount for a's and b's, but I'm not having much success. Am I right or wrong?

This language is regular. Since you're looking for equivalences mod 2 we need only consider the evenness or oddness of the count of the two kinds of symbols in the input. Consider a finite automaton with four states: EE, EO, OE, OO, where state EE records that the number of $a$'s seen so far is even and the number of $b$'s is also even. Similarly, being in state EO means you've seen an even number of $a$'s and an odd number of $b$s. States OE and OO are defined similarly.

Now consider the transitions between states. For example, in state EO with input a, the number of $a$'s changes from even to odd, while the number of $b$'s doesn't change, so we have the transition $\delta(\text{EO}, a) = \text{OO}$. The other seven transitions are defined similarly.

The start state is EE, since you've seen 0 $a$'s and 0 $b$'s and obviously 0 is an even number. The final states are EE and OO, for obvious reasons.


What category of AI would a 2048 bot be considered? I have just delved into the realm of AI and from what I can tell its a very vast field of study. I am a game programmer, so AI in games is particularly interesting to me. My question is, what type of AI would a bot that can beat 2048 fall under?

I learned the basics of machine learning, but I wasn't sure if this is how you could apply machine learning. I want to know what category this falls under so I know what to research and learn to make my own bot. Also, if you don't know what 2048 is, check it out here.

I would initially say that you can classify 2048 as a MDP problem.

For this reason, I would consider looking at Reinforcement Learning (an area of Machine Learning).

Another option, however, more specific would be to look at the performance of Monte Carlo Tree Search.

There is a great discussion in StackOverflow about 2048 different approaches have been tried:
https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048


Problem in understanding big-O notation and similiar I am trying to understand the concept of big-O notation problem and came through this problem. Can you tell me how could

$$O(n) = 1 + \Theta(1/n)$$

$O(n)$ is the set of all functions $f(n)$ such that, for sufficiently large $n$ and a positive constant $c$, $f(n) \le cn$.
$1+\Theta(\frac{1}{n})$ is an abuse of notation that denotes the set of all functions $h(n) = 1+g(n)$ such that, for sufficiently large $n$ and a two positive constants $c_1$, $c_2$, $\frac{c_1}{n} \le g(n) \le \frac{c_2}{n}$.
Then the claim is clearly false since, e.g., the function $h(n)=n$ belongs to $O(n)$ but it does not belong to $1+\Theta\left(\frac{1}{n}\right)$.


NP-hard or not: partition with irrational input or parameter See some related questions in Cont: NP-hard or not: partition with irrational input or parameter

  Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset $S\subseteq N$ such that $F(\sum_{i\in S} a_i;\alpha)$ is maxmized, where $F(\cdot;\alpha)$ is a known fixed function with parameter as $\alpha$.

Method 1.

To prove the complexity of the problem above, I set $\alpha=1$. Then $x_*=\textbf{argmax}_{0\le x\le 1} F(x;\alpha=1)$ can be calculated, which is an irrational number and $x_*\approx 0.52$.

Instance

  Given a set $N=\{a_1,...,a_{n+2}\}$ with $n+2$ numbers where

  $a_1,...,a_n$ are positive and rational,
  $\sum_{i=1}^n a_i = 0.02$,
  $a_{n+1}=x_*-0.01$, and
  $a_{n+2}=0.99-x_*$,

determine whether we can find a subset of $N$, such that the sum of the subset is $x_*$.

NP-complete

  Since $x_*$ is irrational, the desired subset cannot contain both of the last two numbers.
  Since the sum of any subset not containing the $(n+1)$th element is smaller than $x_∗$, the desired subset must contain the $(n+1)$th element.
  The remaining question is to find a subset of the first $n$ numbers whose sum is 0.01

So the original problem is NP-complete.

Criticism

Since $x_*$ is irrational, I can't store irrational numbers in a machine properly and my proof is not correct.

Method 2

Set $\alpha$ with some value which may be irrational, such that $\textbf{argmax}_{0\le x\le 1} F(x;\alpha)$ is rational. Then repeat the process in method 1 and the problem can be reduced from a subset sum problem. This proof does not have the issue of encoding irrational numbers.

The problem you have stated probably contains an error:

  Given a set $N$ with $n+2$ numbers, such that the first $n$ numbers are positive and rational with sum $1$, the $(n+1)$st number is $\sqrt{2}$, and the $(n+2)$nd number is $2 - \sqrt{2}$, determine whether there is a subset of $N$ such that the sum of the subset is $3/2$.

The answer is that there is never any such subset. Either the subset includes $\sqrt{2}$ and $2 - \sqrt{2}$, or neither. If it includes neither, then the sum is less than or equal to $1$. If it includes both, then the sum is greater than or equal to $2$. So the sum of the subset will never be $3/2$.


Should two DFAs be complete before making an intersection of them? In the slides given by my teacher, the third automaton is the product of the first two:

I tried to do the product myself by doing the transition table of both automata at the same time. I got stuck when I realised that the second automaton has no transition from state $2$ with $a$ as input symbol, thus the automaton should halt at that moment. In the third automaton, I can see there is no transition with input symbol $a$ in any of the states that have $2$ in (sorry for the bad expression, don't know how else to say it).

So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton? Or would it be wise to complete the automaton?

So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton?

If there is no transition in one of the automata, then that one won't accept the input word. Therefore, the automaton for the intersection should not accept either; not having a transition is one way to make sure of that.


Computability: Proving a predicate is not recursively enumerable Let P(p) <=>  for each x, comp(p,x) is defined.

Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?

Show that your predicate is coRE-hard, that is, every coRE predicate reduces to it. If your predicate were RE, then it would follow that RE=coRE, which is known to be false.

The rest of the answer assumes that "comp(p,x) is defined" is the same as "program $p$ halts on input $x$".

In order to show that your predicate is coRE-hard, you need to show that for every coRE predicate $Q$ there is a computable function $f$ such that $Q(z)$ iff $P(f(z))$. A predicate $Q$ is coRE if there is a computable function $q$ such that $Q(z)$ iff for all $x$, $q(z,x)$. Hence we need

  for all $x$, $q(z,x)$ iff for all $x$, $f(z)$ halts on $x$.

You take it from here.

(In fact, your predicate is $\Pi_2$-complete.)


Graphs that are connected vs strongly connected vs reachable What is the difference between "connected", "strongly connected", and "reachable" in a graph?

Connected: Usually associated with undirected graphs (two way edges): There is a path between every two nodes.

Strongly connected: Usually associated with directed graphs (one way edges): There is a route between every two nodes (route ~ path in each direction between each pair of vertices).

Reachable (from $A$ to $B$): A path exists in the graph between nodes $A$ and $B$. (Ability to get from one vertex to another)

Note: Got some terminology from:
https://mathoverflow.net/questions/6833/difference-between-connected-vs-strongly-connected-vs-complete-graphs


Size of the language accepted by a Turing Machine I want to figure out if the following language is Turing decidable, Turing acceptable but not turing decidable, or neither. The language is

{ρ(M) : |L(M)| ≤ 10}

My question for this problem is what does |L(M)| ≤ 10 mean? At first, I thought it meant that the language will only accept strings that are less than or equal to 10 in length, but I am not sure

... what does $|L(M)| \leq 10$ mean?

This means that the size of the language accepted by the TM $M$ is less than or equal to $10$. In other words, TM $M$ accepts no more than $10$ strings (inputs), while the length of any accepted input may be greater than $10$.


Where can I find a reasonable NLP CFG or CSG for English? I'm looking to do natural language parsing and looking for how the CFG (or CSG) should be defined for English.

Surely one'd expect to find one from the internet already, but do you know where?

It needs to be in "formal grammar" form, not an implementation (e.g. a Python library).

It has to allow for as wide range of sentences as possible to be parsed correctly.

Something that I could be looking at:

S -> NP VP | VP
NP -> D N | N | N NP
VP -> V | V NP | V PP | V NP PP
PP -> P NP

But how sufficient is this?

Related:
https://english.stackexchange.com/questions/32447/is-there-an-ebnf-that-covers-all-of-english

It is uncommon to use a "closed set" context free grammar because the number of production rules is staggeringly large. The typical approach is to recover a probabilistic context free grammar from a treebank (e.g., the Penn Treebank) in order to do statistical parsing (via probabilistic CKY, Earley, etc).

The only time you might want a "closed set" is when working with toy data in which case you may define an overly simplistic subset of English grammar dealing with sentences, noun phrases, verb phrases, and so on. Such miniature grammars can be found in standard NLP texts such as Jurafsky and Martin, and Manning and Schuetz.


intractable problem example? I have been doing some research into the limits of computation and I have come across the terms intractable and undecidable. Are these two terms the same thing?

What does intractable mean and what is an example of an intractable and undecidable problem?

Tractable usually means decidable in polynomial time.  Under that definition, NP-complete problems appear to be intractable, but they're still decidable.


It's necessary to replace all the population each generation in a genetic algorithm? I'm creating a timetable generator using GA's, and I'm stuck in the crossover part.

Each generation, I just basically copy the best individuals (the 50% fittest individuals inside the population), and perform my crossover operator between them.

I'm using a 2 point crossover. I represent all my TT courses as a List. Each course has an assigned teacher, and an assigned position. The position is the index inside a 2D array. The first dimension represents times and the second represents classrooms.

When I perform the crossover, I choose a middle point inside the Course's list of each parent. Then I create 2 individuals mixing this Course's. If there are overlaps or other constraint violation, I repair the new individual.

My question is this, How can I ensure an optimal offspring?

Sometimes after the crossover and/or after the repair, the new offspring is not better than his parents. This makes the population gets stuck in high fitness values (I'm minimizing the errors, so, a low fitness score means a good individual), so, the GA never reach an optimal solution.

I've been reading an article about copy the fittest individuals in to the next generation, then perform the crossover, but I don't know if this is correct.

GAs are heuristic algorithms. They don't guarantee optimality in any but the most trivial problems. Hence there are no strict rules how to implement them. What works and what doesn't depends your exact problem. Tuning the parameters of a GA is somewhat of a dark art and people turn to heuristics for tuning their heuristics.


Among $k$ unit vectors, find odd set with sum length less than 1 I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no such set exists?

As some motivation, if I have 3 vectors (so that $n=1$), the minimum value of their pairwise dot products if $-3/2$, given by them forming the corners of a triangle. This places all 3 vectors in the same two-dimensional plane. Anything out of that plane (so, more than 2 dimensions) will raise the minimum to some sum $>-3/2$. If I go to a fewer number of dimensions by constraining all the vectors to 1D, then my only possible sums are -1 or 3.

In general, if I have $2n+1$ vectors, then by putting them at corners of a $2n$-simplex, you get a sum of dot products of $-(2n+1)/2$. But by putting them in 1D, you get a minimum of $-n$. I'd like to find sets of vectors that "don't look very 1D" in the sense that they violate this bound.

This is equivalent to the question, "Find an odd-size set of vectors such that their sum has length less than 1" -- the equivalence can be shown by taking the norm of the sum. I think this is more natural, so I'll change the question title.

The latter problem feels similar to the Shortest Vector Problem (SVP) in integer lattices.

The Shortest Vector Problem is:

Input: vectors $v_1,\dots,v_k$
Goal: find a non-empty subset of vectors whose sum has length as short as possible

Your problem is:

Input: vectors $v_1,\dots,v_k$
Goal: find a non-empty subset of vectors whose sum has length $\le 1$, such that the number of vectors in the subset is odd

If we omit the "odd-size" constraint for the moment, the two are very similar: one asks for the sum to be as small as possible, the other asks for the sum to be $\le 1$.  Thus, any algorithm for SVP would immediately yield an algorithm for your problem (ignoring the odd-size constraint).  And solving your problem sounds like it might be about as hard as the SVP (if we replace $\le 1$ with $\le t$ where $t$ is an additional input, your problem becomes as hard as the SVP; reduction by binary search on $t$).

Unfortunately, the SVP is hard: roughly speaking, it's hard if $P \ne NP$ (this isn't quite right, but it's close).  This makes me think that your problem might be hard, too.

That said, there are approximation algorithms for the SVP.  You can use LLL lattice reduction to find a subset whose sum is not too much larger than the shortest possible.  Unfortunately the gap between "the true minimum" and "what LLL finds" is pretty large, so this might not be good enough in practice.  But it is something you could try and see if you get lucky.

I'm not sure how to accommodate the extra restriction that the subset be of odd size.  You could try solving with LLL reduction and hope the resulting subset has odd size (50% chance). I can't think of a better technique, unfortunately.


Question regarding Hoare's partitioning scheme and a slight modification to it This is the pseudocode on wikipedia for Hoare's partitioning scheme:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot   //Question here

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

This code finds an inversion and swaps it. Now, the problem of partitioning about a pivot is to divide an array such that all elements <= pivot fall in one partition, and all elements > pivot fall in the other.

My question is simple: why not use while a[i] <= pivot ?

As far as I can tell, it will work correctly, infact it would align better with the previous definition of partitioning.

If it does work, the big question is why wasn't it used in the original paper? It makes more sense and seems to be slightly faster as well (less number of swaps required).

Infact, while we're on the subject: would it be incorrect to also use while A[j] >= pivot that could further reduce the number of swaps.

I know that if I'm too worried about multiple elements repeating I should use 3 way partitioning, but I'm curious about how this algorithm would work nonetheless.

Why not use while a[i] <= pivot ?

You could.  It's arbitrary.  Either way will work fine.  We just have to choose one of those two choices.  They both have the same asymptotic running time.


Spinlock using cache coherence Have been trying to understand the image below which shows status of spinlock using cache coherence. Reference is Computer Architecture A Quantitative Approach------------------
Could anybody explain why there is a cache miss in step no.5 when P2 tries to execute swap.

In step 4 P2 tests the lock and sees the value is 0.  But testing the lock is just a read operation, so P2 has the cache line in state shared.  In step 5 P2 executes a swap operation, which is both a read and a write, so requires a coherence action (invalidate P1's shared copy) to acquire the cache line in state exclusive.  It's a "cache miss" in the sense that the required state in the cache is incorrect, not in the sense that the data is missing.


NL-Hardness of Target When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve:

$ TARGET = \{<G, t> : t\ is\ reachable\ from\ every\ other\ node\ in\ G\}$

Now we are allowed to use any standardly known problems that are NL-Hard in this part of the question. I considered between reducing from $REACH$ or $\overline{REACH}$, its complement - where $REACH$ is the standard NL-Complete problem. I thought perhaps $\overline{REACH}$ would reduce more naturally to $TARGET$ as the negation of $REACH$'s membership logical formula would be "$<G,s,t>$ where for all paths $P$ originating from $s$, $t$ is not on $P$".

However, I did not get very far from here. Then again, it is quite late in the evening and perhaps I am missing an obvious reduction here.

Many thanks for any hints and pointers!

Let us reduce REACH to TARGET. Given an instance $(G,s,t)$ of REACH, add edges from all nodes other than $s$ to $s$ to form a new graph $G'$. If $t$ is reachable from $s$ in $G$ then it is reachable from all other nodes in $G'$ using the new edges. Conversely, if $t$ is reachable from all other nodes in $G'$, then in particular it is reachable from $s$ in $G'$. Even if this path uses any of the new edges, all they can do is bring it back to the starting point, and so $t$ is reachable from $s$ already in $G$.

Altogether, we have shown that $(G,s,t)$ is a yes instance of REACH iff $(G',t)$ is a yes instance of TARGET.


Binary rooted tree isomorphism My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below:

How many isomorphism classes of trees with n vertices are there?
What are the classical algorithms to decide if two given trees are isomorphic?
Is there a nice (computable?) isomorphism invariant?

Of course, the answers may depend on the structure used to define the trees, but I guess the correct choice of structure is part of the answer I am seeking.

There is a classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman. The algorithm actually uses a simple isomorphism invariant. See for example lecture notes of Vikram Sharma. Using this, you can solve unrooted tree isomorphism in linear time, as described for example in Smal's slides. Another classic algorithm is due to Buss.


Why do I get really different results with my benchmarking code I made? I'm doing research work for my last year in high school. My work is about processors and for the experimental part i've coded an app that can mesure how many Floating Point Operation can a processor do in one second. My problem is that i get really different results depending when I execute my benchmark, I can get 5,6 GFlops and then 5 seconds later I can get 1,6 GFlops. How is this possible? Isn't measuring a processor aproximate speed with how many floating point operations per second can do useful? If not, what ways are useful to get an aproximate result of how fast is a CPU.

While benchmarking metal is mostly outside of the realms of computer science -- we usually don't want to worry about issues of materials and physics -- there are some general remarks here.
Tl;dr: benchmarks are inherently fickle.

Your benchmark process is not alone on the machine. Other processes and interrupts can cause your process to be stalled non-deterministically¹.
Therefore, if your benchmark is only a few seconds long (or less?), random events can dominate the measurement. You want to measure for long periods of time (so you get "average noise") on a machine where almost nothing else is running (so there's little noise) and compare with exactly the same system but the CPU (so the noise is the same).

Flops figures in the literature (or ad leaflets) are often theoretical peak figures. They just look at the CPU construction and say, okay, ideally (no pipeline stalls, no context switches, no memory delay, ...) at this frequency (which a store-bought, flawed chip may not be able to attain) the FP-ALU can compute this many operations per second.
This number is never attained. You can of course try to determine a "real" peak number by running different benchmarks and taking the maximum. Averages probably depend heavily on the benchmark.

Flops are only one type of operation. What about all the others?

Real computation performance depends on many factors that range from the architecture of the CPU to the design of the program being run on it. One notable example would be the length of the pipeline. All else being equal, a chip with a longer pipeline will outperform one with a shorter pipeline on long chains of operations without any conditional jumps -- and exactly the other way around if there are (many) such jumps!

If not, what ways are useful to get an aproximate result of how fast is a CPU.

I am not sure that there is a general measure for "CPU speed". Different CPUs excel at different things. Also, relative measures like "computation power" per Watt become increasingly relevant.

That said, I'm sure books have been written about all these issues. I can't recommend one, but doing some literature research may pay off -- especially at your level, since it'll point you towards many other great things to learn!

It's not really non-deterministally or random, of course. But when looking at a CPU as a black box, it might as well be.


When to use SAT vs Constraint Satisfaction? If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it.  Another standard approach is to express it as a constraint satisfaction problem, and try using a CSP solver.  The two feel somehow vaguely similar in what sorts of problems can be naturally expressed in their input format.

Are there any guidelines or rules of thumb for how to recognize, for a given problem, which approach is more likely to yield good results?  Is there any guidance anyone can offer about which sorts of problems can be handled better by SAT solvers than by CSP solvers, or vice versa?

(Obviously, there are some easy problems that can be solved by both approaches.  There are also some hard problems that can't be usefully solved by either approach.  Let's set those aside.  The case where guidance is most helpful are problems where either SAT solvers perform better than CSP solvers, or where CSP solvers perform better than SAT solvers.  How do I recognize when a SAT solver is likely to be a better fit than a CSP solver, or when a CSP solver is likely to be a better fit than a SAT solver -- i.e., which approach to try first?)

I think this is a very good question. You could also ask: when to use a SMT solver? I have a feeling it might be hard to determine before modeling the problem and actually running the CSP/SAT/SMT solvers and finding out. It is well known that even different solvers perform very differently on the same instances! My intuition also comes from the fact that there are potentially many ways of modeling a problem. Furthermore, there are many ways of doing search and inference, depending on what type of constraints is used (if the formalism in question allows different types).

Take for example the standard Sudoku puzzle. For the standard $8 \times 8$ puzzle, a modern SAT/CSP solver will solve any such puzzle in an instant. However, I would rather use a CSP solver because it is easier to express my intention. The mentioned puzzle needs $9+9+9=27$ alldiff constraints, and I'm done. There's actually quite a bit of research in the context of CSP solvers trying to solve Sudoku instances of different size. As far as I remember, they don't do any comparisons between SAT, but rather try to determine what kind of inference works the best, or what kind of Sudoku puzzles are hard. I don't know if for say $32 \times 32$ Sudoku puzzles, SAT solvers would be faster than CSP solvers.

Different formalisms are able to capture domain specific information and exploiting it better and in different ways. For a bit more on this, see the answer and the comments here.


Longest path on a full tree Given a full tree $\ T = (V, E, w) $ I need to find the path with maximum length from root $\\ s $ to any of the leaves.
I was thinking I could use some sort of BFS. Because I'm looking for maximum length path, I must go through all of the edges of the tree and I will start at the vertex $\ s $. So I'll use a dictionary $\ lengths = \{\} $ where each vertex in the $\ lengths $ dictionary is a key and its value is the total length from $\ s $ to that vertex. Then I'll just choose a the leaf with the highest value. From what I've seen online the solution to the problem is actually using Shortest path for DAG and multiply lengths by $\ -1 $ and the multiply back once algorithm finish. So not sure if my solution is ok?
Thanks,
EDIT: added proposed solution
 weights = {}

 def max_path(root, w):
     if root in weights:
        return weights[root]
     else:
        weights[root] = w + max(max_path(root.leftchild, root.weight), root.rightchild, root.weight))

Your solution will work and, if implemented properly, will require $O(n)$ time where $n$ is the number of vertices of $T$ (to achieve this complexity you cannot just use a BST or a hashmap as a dictionary though).
Notice that you're using the fact that there is a unique path from the root of $T$ to each of the leaves.
Also running any shortest-path algorithm for DAGs on the weighted version of $T$ in which each edge $e$ weighs $-w(e)$ will work in $O(n)$ time. However this is overcomplicated as it requires finding a topological order of $T$ (which requires a DFS). In other words you are not taking advantege of the fact that $T$ is a tree and not just a generic DAG.
A quick way to solve this problem in $O(n)$ time is performing a depth first search starting from the root of $T$ while keeping track of the weighted depth $d$ of the current vertex. Whenever you traverse an edge $e$ "forward" (i.e., from a vertex to one of its children) you increase $d$ by $w(e)$, whenever you traverse an edge $e$ "backwards" (from a vertex to its parent) you decrease $d$ by $w(e)$.
It is very easy to implement this recursively.


Closure of context-free languages under "removal of a regular language from the right" I have a homework that I can't solve can somebody help me?

If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \{\alpha\in\Sigma^*\mid \alpha\beta\in L\text{ for some }\beta\in R\}$$ context-free?

Let me prove that if $L$ is regular then so is $P$. The proof in your case is similar. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$ be a copy of the alphabet $\Sigma$. Let $s$ be the $\Sigma$-substitution $s(\sigma) = \{\sigma,\sigma'\}$, let $t$ be the $\Sigma$-homomorphism $t(\sigma) = \sigma'$, and let $d$ be the $\Sigma \cup \Sigma'$-homomorphism $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Then
$$
P = d(s(L) \cap \Sigma^* t(R)).
$$

As an aside, the class of languages obtained by dividing a context-free language by a context-free language consists of all r.e. languages. See for example The family of one-counter languages is closed under quotient by     Latteux, Leguy and Ratoandromanana.


Problem with my proof that NP = coNP? Is there a problem with this proof that NP = coNP?

It suffices to show that Satisfiability can be solved efficiently with at most a polynomial number of queries to an oracle for Tautology. The algorithm for a problem P is, pick a variable X in P and fix it to T to obtain a problem P'. Submit ~P' to the oracle for Tautology. If ~P' is a tautology, then X is a "no go" for the problem P. If the oracle accepts ~P', then fix X to T in the result, otherwise fix X to F. Then proceed to the next variable. This requires linear queries in the size of the problem. An analogous result reduces Tautology to Satisfiability. Therefore NP = coNP.

My only doubt is that maybe when you're using an oracle you only get to find out if it accepts, not if it rejects. That would block this proof.

You are confusing Turing reductions with mapping reduction, in a sense. The problem with your argument is that if you allow an oracle $O$ to an NP-complete (or coNP-complete) problem, you immediately get that $P^O=co-P^O$. That is, if you already have an oracle for coNP, then you cannot distinguish NP from coNP (but that does not mean that they are equal!).

Here is a shorter version of your argument, to make things clear: suppose we have an oracle for Tautology. It is true that $\phi$ is satisfiable iff $\neg \phi$ is not a tautology. Thus, in order to test if $\phi$ is satisfiable, just run the oracle on $\neg \phi$, and invert the answer. But this only shows that $NP\subseteq P^{coNP}$. Your assumption that $P^{coNP}=coNP$ is incorrect (or at least, it's an open question).


What is the type signature of a Turing Machine? Maybe my question is a bad question, but if it is, I want to know eactly how it is a bad question.

Suppose we have some Turing machien $M$ that takes as input a natural number $n$ in the form of a binary string, writes $n^2$ in binary on its output tape, and then halts.

What is the type signature of this machine? Here is why I am confused:

We can treat $M$ as a function: $M(\cdot)$ denotes the function that maps $n\mapsto n^2$, which suggests that it has type $\{0,1\}^*\to\{0,1 \}^*$
But $M$, intuitively speaking, is not a function, but a "device". This means that we can extract more information from it. e.g. potentially we could define $M_{235}(\cdot)$ to be the function that takes an input and outputs: "what is the string on the output tape after 235 steps, given this input?".
In the formal definition, a turing machine is a tuple $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ (with some properties on these elements). But I am confused about how this tuple relates to type theory. Is this the "type signature" of $M$? If so, what kind of type theory captures this kind of type?

Usually, Turing machines are presented using set theory rather than type theory.

There might be many ways to represent a TM in type theory, each one with its advantages and disadvantages. I would not represent it as a function $\{0,1\}^* \to\{0,1\}^*$ since the function implemented by a TM is a partial function, because the TM might fail to terminate, while in type theory functions are total.

If we wanted to follow the set theoretic definition, we might define a TM as a dependent tuple. This tuple would include:

$\Sigma:\sf Type$ a type representing the tape "alphabet"
$Q:\sf Type$ a type representing the states
$b:\Sigma$ the blank symbol
$q_0 : Q$ the initial state
$\delta : Q \to \Sigma \to (Q \times \Sigma \times 3)$ for the transition function (assuming a deterministic TM) where $3=1+1+1$ represents the directions
$F : Q \to 2$ with $2=1+1$ the halting states

Technically, this would be a huge dependent sum such as

$$
\sum_{\Sigma\sf Type}
\sum_{Q:\sf Type}
  \Sigma \times Q \times (Q\to \Sigma \to(Q\times \Sigma\times 3))\times(Q\to 2)
$$

The above would be a possible representation of a TM. (I'm unsure it would be a very good one, especially if we work without functional extensionality, but I'll neglect that.)

In a similar way one could define the type of the configurations of a TM ${\sf Conf}\ T$ and a step function $step: {\sf Conf}\ T \to 1 + {\sf Conf}\ T$
(the $1+$ is to report "no next step" when the TM halts).

One could even define a function to run $n$ steps, or a predicate for "the TM $T$ on input $x$ halts with output $y$".

$$
\begin{array}{l}
{\sf runTM} :
\prod_{T:TM} {\sf Conf}\ T \to \mathbb N \to 1+{\sf Conf}\ T
\\
{\sf semanticsTM} :
\prod_{T:TM} (\pi_{\Sigma} T)^* \to (\pi_{\Sigma} T)^* \to \sf Type
\end{array}
$$


Determine number of values less than mean in one pass through list The problem statement is as follows:

  Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A_1$ and ending at $A_n$) with only constant memory?

By "constant memory" I mean a constant number of $O(m \log_2 n)$ bit words where $m$ is the number of bits to represent the largest value in $A$. Some other things to consider:

Assume $m$ is non-constant and $m \geq \log_2 n$. If $m$ were constant, we could not even count $n$ as Yuval mentioned.
Assume values in $A$ are integers, but does it affect the problem if they are rational, or real valued?
Assume values in $A$ are uniform random. It helps if they are uniform random because we can get a tight confidence bound with a constant number of elements. How high of a confidence bound can we get?
Time complexity does not matter. You can spend as much time as you want on a particular $A_i$ if that helps, but once you move to $A_{i+1}$ you cannot go back unless you have stored $A_i$ in one of your constant memory words.
What if the values in $A$ are non-uniform random with distribution is unknown? What if the distribution is known?
What if we are not constrained to going from $A_1$ to $A_n$, perhaps we could randomly sample and get a tight confidence bound even if the distribution is non-uniform?
What if instead of mean, we wanted values less than median? Does this help at all?

It's clear with 2 passes through the array we can get this value precisely with no probability involved. With one pass through the array this seems not be possible, but I am not sure. You could create an adversary that waits until the last element to give it an extreme value and throw off all previous calculations. However, with a uniform distribution this is limited. Any thoughts on these variations or an answer under the assumptions provided would be appreciated.

Consider an algorithm for arrays of length $n$ consisting of entries from $0$ to $n$, and using space $S$ bits.

Suppose that the first half of the array consists of pairs $a,n-a$ (where $a \leq n/2$). By choosing the second half appropriately, we can make the average of the entire array anything from $n/4$ to $3n/4$ (discretized to multiples of $1/n$). In particular, the state of the memory after reading the first half should store the number of pairs with $n/4 \leq a \leq n/2$. For every non-empty subset of $\{n/4,\ldots,n/2\}$, we can construct a first half of the array which contains exactly these values of $a$. This shows that the number of first halves that are pairwise distinguishable is at least $2^{n/4}$, hence $S = \Omega(n)$.

A very similar construction establishes an $\Omega(n)$ lower bound even when replacing the mean with the median.


Positive term for "unnegated"? I read a paper which talks about "a logic formula in which each variable appears at most twice unnegated and once negated". The term "unnegated" is double-negative, which makes it slightly unclear. Is there a more positive term to denote a variable that is not negated?

I looked in an English thesaurus, but all suggestions seem out-of-context in logic.

You often see negative variables ($\neg x$) and positive variables ($x$). A literal is either a positive or a negative variable.


Edmonds-Karp Algorithm with both directed and undirected edges? How would this work and be implemented?

If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have those vertices in the middle linked by undirected edges, how would flow work and be maximized?

Replace each undirected edge $(u,v)$ by two directed edges, one in each direction: $u\to v$ and $v\to u$.  That gives you a graph with only directed edges.  Then the max-flow on that graph is the same as the max-flow on your original graph.


Complexity classes where $C^C = C$ One possible motivation for studying computational complexity classes is to understand the power of different kinds of computational resources (randomness, non-determinism, quantum effects, etc.).  If we look at it from this perspective, then it seems like we can obtain one plausible axiom for any attempt at characterizing which computations are feasible in some model:

Any feasible computation can always invoke another feasible computation as a subroutine.  In other words, suppose the programs $P,Q$ are considered feasible to execute.  Then if we construct a new program by hooking $P$ and $Q$ up, so that $P$ makes subroutine calls to $Q$, then this new program is also feasible.

Translated into the language of complexity classes, this axiom amounts to the following requirement:

If $C$ is a complexity class intended to capture which computations are feasible in some model, then we must have $C^C = C$.

(Here $C^C$ represents computations in $C$ that can invoke an oracle from $C$; that's an oracle complexity class.)  So, let's call a complexity class $C$ plausible if it satisfies $C^C=C$.

My question: What complexity classes do we know of, that are plausible (by this definition of plausible)?

For instance, $P$ is plausible, since $P^P=P$.  Do we have $BPP^{BPP} = BPP$?  What about $BQP^{BQP} = BQP$?  What are some other complexity classes that meet this criterion?

I suspect that $NP^{NP} \ne NP$ (or at least, that would be our best guess, even if we cannot prove it).  Is there a complexity class that captures non-deterministic computation and that is plausible, under this definition?  If we let $C$ denote the smallest complexity class such that $NP \subseteq C$ and $C^C \subseteq C$, is there any clean characterization of this $C$?

$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$ has been proved in Strengths and Weaknesses of Quantum Computing Bennett et al. (arXiv).

According to the complexity zoo, $\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$.


Alpha-Beta pruning in chess? How can alpha-beta pruning be made safe for a chess program? Pruning away a certain set of nodes is safe when the tree is complete and it is known that no other new nodes can be found deeper in the tree, but obviously this is not the case in chess. If my program prunes away a move that looks bad because it sacrifices valuable material that may just be the sacrificial move that would have checkmated the opponent in another few additional ply (or just gain a material and/or tactical advantage)?

What you are describing is unrelated to alpha-beta pruning.  The tendency of fixed-depth minimax searches to badly underestimate or overestimate positional scores in dynamic situations is known as the horizon effect.  The problem is due to static evaluation being used on positions unsuited to such evaluation.  Static evaluation scores a position based on things like material, pawn structure, and king mobility, properties that can be determined without extending the search tree.  But some positions are transitional, needing more search to identify their nature.

The standard way to deal with this problem is to recursively apply a quiescence function to all terminal nodes that extends the search an extra ply if there are checks, forced captures or promotions available at that node.  If no such moves are available, then the position is considered quiet and the usual static evaluation function is called.


Checking if sequence is almost strictly in ascending order This was part of my interview questions.

Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
For instance,
For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false
There is no one element in this array that can be removed in order to get a >strictly increasing sequence.
For sequence = [1, 3, 2] the output should be
almostIncreasingSequence(sequence) = true
We can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, we can remove 2 to get the strictly increasing sequence [1, 3].
The function must return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

The conceptual algorithm that the interviewer wanted was below with Java:
boolean almostIncreasingSequence(int[] sequence) {
    int seq1 = 0;
    int seq2 = 0;

    for(int i = 0; i < sequence.length - 1; i++){
        if(sequence[i] >= sequence[i + 1]) seq1++;
    }

    for(int k = 0; k < sequence.length - 2; k++){
        if(sequence[k] >= sequence[k + 2]) seq2++;
    }

    return !(seq1 + seq2 > 2);
}

but I didn't get the part comparing sequence[i] with sequence[i+1] andsequence[i+2] to increment the counter which are seq1 and seq2. How does this cover all the cases?

It does not cover all cases! Consider the sequence [2, 6, 4, 8, 7].
Before the return statement, the values of seq1 and seq2 are: $seq_1 = 2$, $seq_2 = 0$. So the function would return $True$. However, the sequence is not almost strictly increasing, because you need to remove at least two elements from it to obtain an increasing sequence.

So, either the Java implementation is not faithful to the conceptual algorithm, or the conceptual algorithm is wrong.

The problem can be solved by finding the length of the longest increasing subsequence (LIS) of the given sequence. Call $n$ the length of the original sequence. If the LIS has length $\ge n-1$, the sequence is almost increasing according to your definition. If the LIS has length $\le n-2$, the sequence is not almost increasing.


For given reduction f, can show "if f(x) in 4NAE then x in 3SAT", but not "if x is not in 3SAT then f(x) not in 4NAE" Claim: $3SAT \le_p 4NAE $, where reduction $f$ is defined as such: given a 3CNF formula $\varphi$, add to each clause a new literal $z$ (where $z$ is same literal for each clause), and return new formula $f(\varphi)$.

It seemed pretty easy to show that $\varphi\in 3SAT\Rightarrow f(\varphi)\in 4NAE$:

If $\varphi \in 3SAT$, then every clause in $\varphi$ contains at least one $T$ literal. In $f(\varphi)$, let the added literal $z=F$. Then every clause in $f(\varphi)$ contains at least one $T$ and one $F$ literal, so $f(\varphi)\in 4NAE$.

Here's where I'm confused: At first, I thought that if $\varphi \notin 3SAT \Rightarrow f(\varphi) \notin 4NAE$.

We know $\varphi \notin 3SAT$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $\varphi$ containing all true literals, then if $f(\varphi)$ adds $z=T$ to each clause, wouldn't $f(\varphi)$ belong to $4NAE$?

On the other hand, I thought of this argument to show that $  f(\varphi)\in 4NAE \Rightarrow \varphi\in 3SAT$:

Suppose $f(\varphi)\in 4NAE$, where $x_i$ represents original literals in $\varphi$ and $z$ is added literal from reduction. Let $Y$ represent a satisfying assigment of $f(\varphi)$.

If $z=F$, then for any clause $(x_1 \vee x_2 \vee x_3 \vee z)$ in $f(\varphi)$, we know that either
$x_1$ or $x_2$ or $x_3$  had to be true. Thus, the original clause $(x_1 \vee x_2 \vee x_3)$ in $\varphi$ would evaluate as true, and so $\varphi$ contains satisfiable assignment.
if $z=T$, then for any clause $(x_1 \vee x_2 \vee x_3 \vee z)$ in $f(\varphi)$, we know that either
$x_1$ or $x_2$ or $x_3$  had to be false. Now define the assignment $Y '$ to be identical to $Y$ except with every literal negated, and remove all $z$'s. Then $(\bar x_1 \vee \bar x_2 \vee \bar x_3)$ contains at least one true literal. So $Y'$ is a satisfiable assignment of $\varphi $, and  $\varphi \in 3SAT$.

Basic logic says if p then q should be equivalent to "if not q then not p". So obviously I'm making some mistakes or assumptions here. I just don't see where.

The error is in this paragraph:

  We know $\varphi \notin \mathsf{3SAT}$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $$ containing all true literals, then if $()$ adds $=$ to each clause, wouldn't $()$ belong to $\mathsf{4NAE}$?

Here's your argument, broken into steps:

Suppose $\varphi \notin \mathsf{3SAT}$. Thus, every assignment for $\varphi$ has at least one falsified clause.
Suppose there was some assignment in which each clause contains a falsified literal. Then $f(\varphi) \in \mathsf{4NAE}$, by choosing $z=T$.

I fail to see the contradiction here. Indeed, if there is some assignment in which each clause contains a falsified literal, then if you complement it, you get a satisfying assignment, as you show in your post. This means that if (1) holds, then (2) cannot possibly hold.

You argument is basically saying "what if I had an unsatisfiable $\varphi$ together with an assignment in which each clause contains a falsified literal". If such a $\varphi$ existed, then your reduction wouldn't have been sound. Fortunately, no such $\varphi$ exists. It's true that you have to rule out the existence of such $\varphi$, which you do by showing that if (2) holds then (1) doesn't hold.


Possible to get the Sum x with maximal two summands? Suppose we have $n$ different summands. Is it possible to get the sum x with a maximum of two of the $n$ summands (Below the m summands there can be several times the same one). For example you have the summands (2,4,6,7). So its possible to get the sum $2+4 =6$,$6=6$ but its impossible to get the sum $3$ or $1$ ect.

My idea of an algorithm would have the runtime $\mathcal{O}(n\log(n))$. Now I'm not sure if this is already aymptotically optimal ?

If the numbers have a limit on their value, i.e. all numbers are smaller than $m$, then you can get runtime of $O(n + m)$: in an array $t$ of size $m$, for each number $a$ in the set of summands, check if $t[x - a] > 0$: if yes, then the answer is $(a, x - a)$. If not, set $t[a] = 1$ and continue with the next number.

This can be slightly improved with assigning values in buckets, but the worst time complexity will be $O(nm)$.

Otherwise, $O(n \log n)$ is the optimal complexity.


Is C → A B C | A left-factorizable? $$C \to A B C \mid A$$

Obviously has the same FIRST(C) for the both productions.

But how can this be left-factorised?

Tried:

$$C \to A B C'$$
$$C' \to A C \mid \varepsilon$$

The FIRST sets are disjoint, but is this correct?

Should $B \to \varepsilon$ (or $C \to \varepsilon$) be added as well, so that it handles $A B A$?

Your proposed factoring won't work correctly because both productions start with the same nonterminal. Remember that for an LL(1) parser you cannot have two productions that start with the same nonterminal (usually) because if you see anything in the FIRST set for that nonterminal, you wouldn't know which production to pick.

To left-factor the grammar, try something like this:

  C → AX

  X → BC | ε

Notice that this gives you the same strings as before, but (assuming that at least one of B and C doesn't produce ε) is LL(1).


Shortest path in a matrix I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem:
Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each number in the matrix represents the costs and one can only move horizontal and vertical:

e.g.

M =

1, 50,50,50,50;
1, 50,1, 1, 1 ;
1, 1, 1, 50,1 ;
50,50,50,50,1 ;
50,50,50,50,1 ;

where the shortest path is: (1,1) , (2,1) , (3,1) , (3,2) , (3,3) , (2,3) , (2,4) , (2,5) , (3,5) , (4,5) , (5,5)

Initially i tried to solve this recursion using Dynamic Programming:

SP(i,j) = {
    M[i][j], if i=M and j=N
    min(SP(i+1,j), SP(i-1,j), SP(i,j+1), SP(i,j-1)) + M[i][j], otherwise
}

It however loops infinitely since it calls in every direction e.g. going right is dependent on going left and so on..

Can anyone help me solve this problem?

Treat the matrix as a weighted graph and use your favourite least-weight path algorithm.

To transform the matrix into a graph, say that the cost of going along the edge from $a$ to $b$ is the cost of visiting $b$. You'll need to separately add the cost of visiting the first node to the cost of any path the algorithm comes up with.


Number of different output labels in Local Binary Pattern I'm studying about Local Binary Pattern and I'm having trouble understanding the following part about the number of output labels for binary patterns from Computer Vision using Local Binary Patterns, by Pietikäinen et al. (2011):

  Another extension to the original operator uses so called uniform patterns [53]. For this, a uniformity measure of a pattern is used: $U$ ("pattern") is the number of bitwise transitions from 0 to 1 or vice versa when the bit pattern is considered circular. A local binary pattern is called uniform if its uniformity measure is at most 2. For example, the patterns 00000000 (0 transitions), 01110000 (2 transitions) and 11001111 (2 transitions) are uniform whereas the patterns 11001001 (4 transitions) and 01010011 (6 transitions) are not. In uniform LBP mapping there is a separate output label for each uniform pattern and all the non-uniform patterns are assigned to a single label. Thus, the number of different output labels for mapping for patterns of $P$ bits is $P(P-1)+3$. For instance, the uniform mapping produces 59 output labels for neighborhoods of 8 sampling points and 243 labels for neighborhoods of 16 sampling points.

I don't understand why the number of different LBP output labels is $P(P-1) + 3$. Could someone explain why?....

Thnx for any help =)

Update: I think I have some idea already :) I included an example from my book:

A pattern with uniformity measure exactly 2 is determined by: the value $b$ of bit 0, the position $i>0$ of the first bit that is different from bit 0 and the position $j$ of the first bit after the $i$th that is different from bit $i$.  (We may have $j=0$, for example in the pattern 00001111, which has $b=0$, $i=4$, $j=0$.)  How many choices are there for the triple $(b,i,j)$? Clearly, there are two choices for $b$.  For $i$ and $j$, there are  $\tfrac12(P-1)(P-2)$ choices with $i<j$ and $P-1$ choices where $j=0$. Thus, the total number of choices for $i$ and $j$ is
$$ \tfrac12(P-1)(P-2) + P-1 = \tfrac12P(P-1)\,.$$

To that, you need to add three more labels: all zeroes, all ones and the label for all patterns of uniformity measure strictly more than 2.


Worst-case prime sieve The Sieve of Eratosthenes bothers me because you have to specify an upper bound before you begin the algorithm.

Is there a prime sieve that doesn't require this?

More Formally:

Is it possible to write an iterator on which the i'th call to next() yields the prime number $p_i$ in only $O((p_i - p_{i-1})log(log(p_i)))$ time for all i > 1 ?

(Note: I'm looking for a worst-case solution, not amortized.  For amortized time, you can simply use Sieve of Eratosthenes and restart the algorithm doubling n each time you hit the previous upper bound)

Most fast sieves are segmented, so you can get this in efficient amortized time.  When you call to get the next segment, you may have to increase the auxiliary prime list, but that's a trivial amount of time.  Then you just sieve that segment, exactly how it would be done if you were sieving to some large known upper bound.  You can wrap all of that in a next() call.  I believe primesieve and primegen both have setups like this.  This is also how my forprimes and forcomposites work, as well as my iterator in Perl/ntheory.

This is likely faster than prime-by-prime extensible sieves.  I see in the Rosetta Code extensible prime generator task the C solution is a simple segmented generator like I mention above.  The first D solution is the rather horrible method you noted.  A number of the languages, including Go, implement O'Neill's lazy functional sieve which is more directly what you might be asking for.  Ben Tilly shows a lazy sieve using closures in Perl here that should meet your complexity goal.

Of course you can do primality tests, but that takes more time than sieving until your input is large (how large depends on your implementations of both sieve and primality test, but it would certainly be before 10^25).


Forward edges in undirected graph using BFS Introduction to Algorithms books claims BFS only classifies an edge for an undirected graph to be either tree or cross edge. But how about this simple example below where forward edges are naturally appearing?

Given graph with just 2 vertices A and B and 3 edges from A to B!

 exploring A adjacent vertices

(1) A->B (tree edge, A is now marked as an ancestor for B and B is A's descendant)

(2) A->B (forward edge? B is not yet processed (gray) and we found an edge to it from its ancestor(A))

(3) A->B forward edge using the same reasoning as in (2)!

What am I missing here?

My example was a multigraph (multiple edges between a given pair of vertices is allowed). And in multigraph BFS does "produce" forward edges!


Dynamic Programming Solution to 0,1 KnapSack Problem I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course and need to solve questions based on the classic knapsack problem.However unless I understand the classic problem clearly , I won't be able to make any headway to the advanced ones.Please help pointing me out in the right direction.

The recursive equation is way too confusing for me.

The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n.

We define $O(K,W)$ to be the optimal value for the first k items with a total weight W, we need to be able to define this in terms of subproblems now since without that, dynamic programming does not work. To add some quick definitions $W_k$ is the weight of the kth item and $V_K$ is its values.

So we define the recursive formula in 2 cases:

The first case is $O(K,W) = O(K-1,W) \quad \text{if $W_k$>W}$, meaning the k'th item weighs more then are target weight so it cannot be added even if nothing else was in the bag.

The second case is the decision case, $O(K,W) = MAX(O(K-1,W),O(K-1,W-W_k)+V_k)$ it means that either we don't add Item K to our set, in which case our best so far is $O(K-1,W)$, or we do add it, in which case we only have $W-W_k$ weight remaining to be filled with items 1 to k-1 and our total value is $O(K-1,W-W_k)+V_k$, which is our recursive value plus the value of the new Item.

The optimal solution is then $O(n,MaxWeight)$

Now for the dynamic programing part, the best way to start out is with our standard grid, we have our horizontal portion as k, so at any $i$ point we have the first $i$ items available, and our vertical as the total weight from zero to the weight the question was asking. The first row and columns will have a value of zero since with no weight or items, our bag has no value. Below I have put good walk through example. We walk through the algorithm by moving down each column, one column at a time. So at any grid location we check 3 other grid points which correspond to the values from the recursive definition, If we are at grid point $k,W$ and item k has a weight of$W_k$ and a value of $V_K$ we first check if $W<W_K$, if it is we use the square above it, since our item is too big, this is $O(K-1,W)$, if the item is not too big you check locations $k-1,W$ which is $O(K-1,W)$ and compare it to $K-1,W-W_k$ which is $O(K-1,W-W_k)+ V_k$, since we are going column by column from smallest to largest these are already calculated. If we keep doing this we will eventually get to the bottom right corner, which is the solution to the problem. The trick to this is we start at the smallest values and save the answers so for larger one the recursion is only a quick lookup instead of a full call.