Proving formula for derivative of Kleene star Prove that for any symbol $a$ and regular expression $r$ it is true that:

  $$\partial a(r^* ) =  \partial .a(r)(r^* )$$

My attempt:

Induction on regular expression $r$

Base cases:

1) $\emptyset $

$\partial a(\emptyset^* ) =  \partial a(\varepsilon) = \emptyset$

$\partial a(\emptyset) (\emptyset^* ) =  \emptyset \emptyset^* = \emptyset \varepsilon = \emptyset$

2) $\varepsilon $

$\partial a(\varepsilon^* ) =  \partial a(\varepsilon)$ = $\emptyset$

$\partial a(\varepsilon) (\varepsilon^* ) =  \emptyset \varepsilon^* = \emptyset \varepsilon = \emptyset$

3) $a\in\Sigma$

Case $a=b$:

$\partial a(a^* ) =  $

$\partial a(a) (a^* ) = \varepsilon (a^*) = a^*$

Case $a \neq b$:

$\partial a(b^* ) =  $

$\partial a(b) (b^* ) = \emptyset (b^*) = \emptyset$

But how to prove for Inductive Step when regular expression $r$ is:

1) Concatenation: $r=\alpha\beta$

2) Union: $r=\alpha + \beta$

3) Kleene Star: $r=\alpha^*$

Using structural induction seems like overkill, or, which is more likely in your case, overly formal in a way which complete obstructs what is going on.

Here is a simple proof that explains why $\partial_a(r^*) = \partial_a(r)r^*$. We consider two cases:

$\epsilon \notin L[r]$. This implies that $\partial_a(r^{n+1}) = \partial_a(r)r^n$. Since $\partial_a(\epsilon) = \emptyset$, we get
$$
\partial_a(r^*) = \bigcup_{n \geq 0} \partial_a(r^n) = \bigcup_{n \geq 1} \partial_a(r)r^{n-1} = \partial_a(r) \bigcup_{n \geq 1} r^{n-1} = \partial_a(r) r^*.
$$
$\epsilon \in L[r]$. Write $r = \epsilon + s$, where $\epsilon \notin L[s]$. Then $r^* = s^*$, and so using the preceding case applied to $s$, we get
$$
\partial_a(r^*) = \partial_a(s^*) = \partial_a(s)s^* = \partial_a(r)r^*,
$$
since $\partial_a(r) = \partial_a(\epsilon) \cup \partial_a(s) = \partial_a(s)$.

If you did want to use a proof by structural induction, then you would need to let us know what identities of the Brzozowski derivative and of regular expressions you are allowed to use.

For example, if you are allowed to use $\partial_a(L_1 \cup L_2) = \partial_a(L_1) \cup \partial_a(L_2)$, then you immediately get the inductive step for union.

As another example, for the base case $r = b$, you can use the fact that every word in $b^*$ is either empty or starts with a $b$, and consequently $\partial_a(b^*) = \emptyset$. Since also $\partial_a(b) = \emptyset$, you would deduce this base case. Perhaps the identities you are allowed to use can implement this argument.


Given a path of 2d points and a maximum distance, find the minimum number of line segments needed to "connect" all points I have an array of 2 dimensional points describing a path. I want to reduce the number of points needed to describe this path by using line segments that connect multiple points on the same line, allowing for some minimal deviations.

For example, given the points (0,0)-(50,50)-(100,100), the path can be optimized by only specifying (0,0)-(100,100) which will also cover the center point. In case of (0,0)-(49,49)-(100,100) I still want to allow the same line segment of (0,0)-(100,100), as the distance (e.g. euclidian) from the point to the line is small (by a user defined parameter).

What is the minimum number of line segments needed that satisfies the distance condition and how can the segments be determined. Is there a "good" heuristic which is simpler or more efficient while providing comparable results?

Try polyline simplification.
For heuristics or other simplifications you might want to treat segments as resizeable, but for now objective is not that clear.
Here is demo of RDP.
Try it, merge your answer into question and then explain objective.

There is tradeoff between polyline complexity reduction and number of remaining points. Number of removed points depends on data and $\epsilon$.

If you want to find minimum, you have $N-1$ segments on $N$ points, and exact reduction depends on colinearity of points. Otherwise it is only approximation.


Data structures and algorithms for bridge game play? In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There are 28561 possible non repeated 4 card groups.

What is the best method of generating and storing all possible trick combinations (played according to the bridge rules just for one session) to be further processed by a computer program (i.e., data structures such as game trees, and any open source algorithms written for any computer language if any).

All resources to read to get the theory behind or any references are welcome.
Thank you.

If the data is really a tree graph, then maybe a Prüfer code?


Can a Turing machine decide if a LOOP program stops for the integer input 0 This is a question I found in a practice exam while I am preparing for my mid term exam.

The answer needs justification, either a pseudo code or a logical explanation why not.

What puzzled me about that question is that we already know that all LOOP programs terminate at some point, the question seems odd to me.

Any references about LOOP and/or WHILE programs are  welcome. Our professor didn't give much.

If all LOOP programs terminate that there is a Turing machine that decides whether a LOOP program stops on input 0: it just always accepts. For WHILE programs the picture is rather different - I'll let you find out yourself. (Perhaps your professor really meant WHILE programs.)


Algorithm for placing circles of Diameter d around the edge of another circle with diameter D Hi i'm struggling with what i think may be simple maths. I need to place circles of a small size around the edge of larger circle.. is there an algorithm to calculate the angle for each small circle from the x-axis, counter clockwise? then using this angle i can find the Cartesian coordinates (x,y) of the enter of each circle.

Circles centers form isosceles triangle with base of length $2r$ and arms of length $R+r$, so
$ \tan (\frac{\beta}{2}) = \frac { r}{ r+R} $ hance $\beta = 2\arctan(\frac{r}{r+R}) $


Finite subsets of the Halting problem are decidable. Can I prove the correctness of Turing machines computing these subsets? I am trying to wrap my hand around the undecidability proof of the Halting problem, and to me it really seems to be more of a proof about representation than decidability. Namely, the proof that some languages are undecidable by Turing machines seems to simply state that I cannot find finite representations for arbitrary countably infinite sets. So far so good. However, I do not see how this might ever be a problem in practice.

If I fix some machine $M$ and consider the language $L_M = \{M \mid \textrm{$M$ halts on empty input}\}$. Clearly, $L_M$ is decidable, because it either denotes the singleton set $\{ M \}$ or the empty set, but:

(1.) Can I always prove the correctness of some machine that decides $L_M$?

(2.) Suppose I cannot always find a proof. Can I find some specific machine $M$, for which I can find a proof that I cannot prove or disprove whether it halts on a specific input?

My first question can also be seen from another viewpoint: If I was to formulate the Halting problem in natural language, it would state

"Does there exist a fixed strategy, so I can decide for every TM whether it halts or not."

But I am interested in the problem:

"Given some TM, can I come up with a strategy to decide whether it halts or not."

I guess that that this question is more about provability than decidability, but unfortunately I know very little about the former.

You cannot always prove the correctness of the true value of $L_M$ (unless your proof system is inconsistent). Indeed, if you could, then given $M$, you could search for proofs that $L_M = \emptyset$ and for proofs that $L_M = \{M\}$, and eventually you'll find one, thus solving the halting problem.

Gödel's incompleteness theorem gives you a specific such machine. Suppose that your proof system is $P$ (for example, ZFC), and consider the machine $M$ that goes over all possible proofs in $P$, searching for a proof of contradiction, and halting if it finds one. Assuming that $P$ is consistent, we have $L_M = \emptyset$, but if $P$ could prove that, then it follows that $P$ proves its own consistency, which is ruled out by Gödel's second incompleteness theorem (assuming $P$ is not too weak).


Complexity for nested #P? Consider a problem such as weighted model counting for propositional logic. The problem of enumerating all models M of a logic formula f and summing their weights w(M) is #P. What happens if the weight is a function of the model and the task of computing the weight w(M) given M is in itself #P? Whats the complexity of the total problem?

The result is in #P.  Suppose there are 50 states, and each state has 10 cities.  Then how many cities are there in total?

Now suppose we have a polytime verifier for states: $S(x)$ outputs 1 iff $x$ is a state.  We also have a polytime verifier for cities: $C(x,y)$ outputs 1 iff $y$ is a city in state $x$.  Then counting the number of states is in #P: it's the number of $x$ such that $S(x)=1$.  If you think a bit, you can see that counting the number of cities is also in #P: it's the number of pairs $(x,y)$ such that $S(x)=1 \land C(x,y)=1$.  Can you come up with a polytime verifier $V$ such that $V(x,y)=1$ iff $x$ is a state and $y$ is a cities in that state?  I bet you can.  Consequently, counting the number of such pairs (i.e., counting the number of cities) is in #P.

Now apply the same idea to your problem, and you should be able to figure out the answer.


What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently? I was thinking about how nature can efficiently compute ridiculous (i.e. NP) problems with ease. For example, a quantum system requires a $2^n$ element vector to represent the state, where $n$ is just the number of particles. Nature doesn't need any extra time despite the exponential nature of "solving" this $n$-particle system.

This may not be a wholly valid assumption, but the action principle in physics makes me think that nature always wants to do things the easiest way. If that's not true, then this question is probably moot.

If we found that nature was NOT capable of solving some problems efficiently, does this mean we are doomed in terms of being able to solve NP problems in polynomial time? Are the laws of physics a strong enough weapon for tackling P vs. NP? Is the converse of the first question/assertion also true (if nature can do it, then there must be a way for us to as well)?

Here are five remarks that might be helpful to you:

The current belief is that, despite the exponentiality of the wavefunction, quantum mechanics will not let us solve NP-complete problems in polynomial time (though it famously does let us solve certain "special" NP problems, like factoring and discrete logarithms).  The basic difficulty is that, even if a solution to an NP problem is "somewhere" in the wavefunction, that isn't useful if a measurement will only reveal that solution with exponentially-small probability.  To get a useful quantum algorithm, you need to use quantum interference to make the correct answer observed with high probability, and it's only known how to get an exponential speedup that way (compared to the best-known classical algorithm) for a few special problems like factoring.
The action principle doesn't imply that Nature has any magical minimization powers.  The easiest way to see that is that any physical law formulated in terms of the action principle, can also be formulated in terms of the ordinary time-evolution of a state, without reference to anything being minimized.
If P=NP, then certainly NP-complete problems can be solved in polynomial time in the physical universe, since universal Turing computers exist (you're using one now).  However, the converse direction is far from obvious!  For example, even if you assume P≠NP, it's still logically possible (if very unlikely) that quantum computers could solve NP-complete problems in polynomial time.
The mere assumption that there are some problems that we can't solve efficiently, certainly doesn't imply that NP-complete problems have to be among those problems!  (Maybe it will turn out that quantum gravity lets us solve NP-complete problems in linear time, but the PSPACE-complete problems still take exponential time... :-D )
For whatever it's worth, my money is firmly on the conjecture not only that P≠NP, but also that NP-complete problems are intractable in the physical universe---using quantum computers, analog computers, "black hole computers," or any other resource.  For more about my reasons why, you might enjoy my old survey article NP-complete Problems and Physical Reality


Prove that an infinite set is semidecidible I have been asked to prove that:

Being C an infinite set. Prove that C is semidecidable if and only if exists a total computable function that is injective and whose image is C.

I've read the wikipedia articles of computable function and recursively enumerable set and I saw these properties are true. But I have no idea how to start the proof.

Could you please help me?

Thanks in advance.

Here is a rough sketch.

If $M$ recognizes $C$, we can exploit $M$ to craft $N$ which enumerates the language of $M$, writing all its words on an output tape, clearly separated, in infinite time. For that, it suffices to exploit dovetailing to generate all the pairs $(w,k)$, where $w$ is a word and $k$ a natural. For each such pair, we run $M$ on $w$ for $k$ steps -- if $M$ accepts, we add $w$ to the output tape, otherwise we try the next pair.

Exploiting $N$ is then possible to define a total computable $f$ whose image is $C$.

For the other direction, given a total computable $f$, we can craft $M$ such that on input $w$ compares it to $f(0),f(1),f(2),\ldots$. In this way we can make $M$ recognize the image of $f$, i.e. $C$.


How many words loaded on a cache miss Regarding Processor Direct Cache, what is the proper mathematical technique for discovering how many words are loaded on a cache miss?

For example if you have a direct mapped cache with a total data cache size of 32 words and a direct mapped cache of 4-word blocks. I believe I have a cache index of 8 cache blocks:

32/4 = 8

Example: Finding a block in python:

var1 = 56
print ((var1 / 8)% 8)

The answer: 7

So finding where to store the blocks is simple enough but I'm uncertain on a miss exactly how MANY words will be loaded?

In a typical cache design an entire block is loaded (in your example 4 words). While it is possible to include separate valid bits for smaller chunks (sometimes called sectors, though Intel uses sector to designate the larger group and line for the smaller unit), making it unnecessary to load the entire block, even in that case typically the entire block is loaded on a miss.


Efficient algorithm for a modified stack to pop the smallest element I was practicing the following problem :

  There are a total of $N$ operations.
  At each operation, you can either add an element to the top or remove several elements as described below.

  Inputs are integers. An input other than $-1$ indicates that we have to add the elements in last in first out fashion (LIFO). If the input is $-1$, then we have to remove (pop) all the elements that lie above the current minimum element of the stack, and then pop that minimum element.

  For each $-1$ in the inputs, print $(m,p)$ where $m$ is the minimum element on the stack and $p$ counts how many total elements we popped from the stack.

Example :

N=14 (Total 4 operations)
9
6
8
-1
2
0
6
-1
3
1
2
10
5
-1

In above example : First three operation is inserting operation ,
that is we need to insert them in LIFO Fashion.
So the stack after third operation is : [9  6   8*]
    PLEASE NOTE * represent the element at the top  of the stack.
Fourth Operation is -1 , that is we have to remove all elements
(including the minimum ) , that lie above the minimun elements.
The Minimum Element is 6 ,so we remove 8 and 6 and Hence the stack now is :
[9*]
So answer for fourth operation is (6,2)
6 - the minimum element in the stack and 2 ,as we removed
total 2 elements from the stack.

Operation 5 th ,6 th and 7th are Inserting operations.
After 4 th operation , the stack was [9*]
After 7th operation , the stack looks like [9 2 0 6*]
8th operation is -1 . Minimum element is 0 ,so we should remove 0,6
    from the stack
Hence Answer is (0,2)
As the minimum element is "0" and we removed total "2" elements from
    the stack.

The  stack at the end of eighth operation is:
[9 2]

Operation 9 ,10 ,11 12,13  are inserting operations
So Stack after 13th operation is:
[9 2 3 1 2 10 5* ]
operation 14 is -1.
The minimum element  in the stack is 2. However 2 lies at two
    different positions in the stack .
But we should remove that  2 , which is nearest to the top of the stack
(In order word ,if the minimum lies at more than two positions in the
    stack ,then the one which is closer to the top of the
stack is considered).
So remove 2 at Index 5 (as it is closer to the top of stack) and element
that lies above it in stack.
So after removing 2(the minimum element ) and 10,5 (the elements above
    the min element)
The stack looks like:
[9 2 3 1*]
    Answer is (2,3) //As 2 is the min element and we popped "3" elements

PLEASE NOTE * represent the element at the top  of the stack.

My approach

I am using a simple stack for the above problem. But the constraint is high: $1 \le N \le 10^6$. There are many $-1$'s in the input, so a simple stack will work very slowly. The time limit for the problem is just 1 second.

You can simply push elements to the stack only if they are smaller than the element on the top of the stack.If they are bigger you will count them in different counter in order to know how much elements were pushed and keep those counters in another stack. When you have to pop you will pop only the top element.

Here is sample pseudo code (some check for empty stacks and initial values are omitted):

    input: element
    // stack.peak() - gets top element without popping it
    if (element == -1)
        top = stack.pop()
        print(top, (counter_stack.pop() +1))

    if (element > stack.peak())
        count = counter_stack.pop()
        counter_stack.push(count+1)
    else
        stack.push(element)
        counter_stack.push(0)

Here is what should this look for your example:

9
stack: [9*]
counter_stack: [0]
6
stack: [9 6*]
counter_stack: [0 0]
8
stack: [9 6*]
counter_stack: [0 1*]
-1
stack: [9 6*]
counter_stack: [0]

print : 6(the popped value), 2 (counter_stack popped +1)

2
stack: [9*]
counter_stack: [0 0]
0
stack: [9 2 0*]
counter_stack: [0 0 0]
6
stack: [9 2 0*]
counter_stack: [0 0 1]
-1
stack: [9 2*]
counter_stack: [0 0]
print : 0(the popped value), 2 (counter_stack popped +1)

3
stack: [9 2*]
counter_stack: [0 0 1*]
1
stack: [9 2 1*]
counter_stack: [0 1 0*]
2
stack: [9 2 1*]
counter_stack: [0 1 1*]
10
stack: [9 2 1*]
counter_stack: [0 1 2*]
5
stack: [9 2 1*]
counter_stack: [0 1 3*]

-1
stack: [9 2*]
counter_stack: [0 1]
print : 1(the popped value), 4 (counter_stack popped +1)

and so on.


NP hardness of unique Puzzle Generation Introduction

For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on circular matrix shift of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1, Here-2, Here-3 and algorithm in python

Decision Problem

Before reading make sure the links are read first.

Given an n^2 x n^2 grid G does there exist a mapping of a puzzle that will allow only one solution?

Here I test to see if my problem is in NP

g = grid

p = mapped puzzle

The certificate (g, p) is accepted by the checker

run backtracker....

print "analyzing puzzle to check possible solutions"

       if p == one solution

       print "valid shift-L puzzle"
else:
       print "false"

Proof that Puzzle completion is NP-Complete

It is already proven by Colborn with a reduction from a NP-complete problem known as Triangle Partition of tripartite graphs. Explained here

Question

With a pre-existing proof that latin square completion is NP-complete, is it safe for me to firmly say my puzzle generation (or puzzles) is at least NP-hard?

Your problem is in NP.
Generalized Sudoku is NP-Complete, but your mapper is in P. Check whether given grid is generated by mapper runs in $\mathcal O(n^2)$ time.
Your mapper is not NP-Complete and your decision problem is not NP-hard.

On the other hand decision version of Sudoku is NP-hard.

The main problem is that you have not provided anything about checking uniqeness of solution, but since your mapper resolves only one solution from family of solutions it can't decide it.

If you insist on proving NP-hardness please provide valid reduction (hint, it will not run in polytime, so answer is no).


ML to approximate a dampened harmonic oscillator from a related curve I want to approximate the output of a Monte Carlo simulation that takes a probability density function sampled at x-axis points $0,1,2,3,\ldots,n$ and outputs what tends to look like a dampened harmonic oscillator.

Four examples appear below.  The blue dots are the sampled pdf (or pmf), and the heights of the black lines give the curves I want to approximate.

My inclination is that I would be able to use Machine Learning to either (a) provide second-order differential equations that approximate the output of the Monte Carlo simulation, or (b) bypass the dampened harmonic idea and approximate the output of the MC simulation directly.

Needless to say, I can generate tons of learning data using the MC simulation.  I should also mention that once the ML has done its training, it needs to perform much faster than the MC simulation!

I'm hoping this will be a good introduction to ML algorithms for me, but I'm not sure where I would start.  Hints about learning resources and software frameworks to do my research in are welcome.

Can this be solved with ML?
If so, would I bother with the oscillator stuff?

I would suggest that you try to learn the function $f$ that maps the parameters of the pmf to the parameters of the dampened harmonic.

For each example, you can presumably derive the parameters of the Weibull distribution for the pmf.  You can also presumably derive the parameters of the dampened harmonic (by curve-fitting, or other means).  So, each example gives you one input-output pair for $f$.

Now, try to learn $f$ from these input-output pairs.  You should start by visualizing the function $f$, to try to understand how each output of $f$ depends on the inputs of $f$, and then you can probably select an appropriate (nonlinear) regression model.  k-nearest neighbors regression might be worth a try in this context.


Asymptotic analysis of a summation I was calculating the time complexity of one of the phases of my proposed algorithm, but unfortunately, I faced a problem about solving that and providing an understandable running-time. This phase of the algorithm indeed iterates a task $t$ times where $t$ is that iteration in which the algorithm achieves the desire result (optimal value). Each iteration $i$, where $0\leq i\leq t$, runs in $O\big((Y-iy)(\log(Y-iy)+D-id)\big)$ such that $y$ is the expected amount by which $Y$ decreases and $d$ is also the expected amount by which $D$ decrease at each iteration $i$. Therefore the total time complexity of this phase is as follows:

$$\sum_{i=0}^t O\big((Y-iy)(\log(Y-iy)+D-id)\big)\,.$$

Now I would like to find a nice solution for that. Can you help me approximate this in order to obtain a better solution?
Any help will be appreciated. Thank you in advance.

Assuming all the quantities are positive, just use $\log(Y-iy)\leq \log Y$, expand the brackets and use the standard identities for $\sum_i i$ and $\sum_i i^2$.  The $\log$ term disappears anyway since, asymptotically, it's dominated by the terms polynomial in $i$.


How to simulate a k tape non deterministic turing machine with 2 tapes? The only thing I found online about this is the following blog: http://blog.computationalcomplexity.org/2005/03/tape-reduction.html

where they write:

  Roughly the simulation guesses every step of the transition function
  on one tape and uses the other tape to verify the transition function
  on each tape of the original machine one tape at a time.

How exactly do you guess the transition function? And if you guess it, then why do you need to verify it? Isn't the guess in non deterministic turing machines always correct?

I think the idea is that we can run with just the first tape of the original machine while pretend other $k-1$ tapes exist. We pretend knowing states of other tapes by guessing every possible ones.

After the first tape executed, for those machines stopped in accept state, run with the second tape to see whether the guesses with respect to that tape were correct. Reject all wrong guesses. Repeat until all $k$ tapes are executed.

  Isn't the guess in non deterministic turing machines always correct?

For NDTMs, "correct guess" is that guess which will lead the machine into accept state.  We need to reject all incorrect guesses by verifying them to make only the correct guesses (for our problem) correct (for NDTM).


A directed graph colored path problem? Given: A rooted, directed, a-cyclic graph $G$. Let $r_0$ be the root node and $t_0$ be another target node. Each node in $G$ is assigned a non unique id/color ($ID_i),\ 1<i<N$ for some integer N.

Problem: Is there a directed path from $r_0$ to $t_0$, such that for some $ID_x$ there is no node in that path with $ID_x$ as its $ID$. In other words, the nodes in the path do-not cover all the $IDs$.

Comments: Clearly the problem is in $NP$ since if we are given such a path we can easily verify it. I suspect the problem is also in $P$ and can be solved in polynomial time. But, I am struggling to find an algorithm for the same.

Can someone please help with this?

Simple approach: for each $1 \le i \le N$ (I assume that the $<$ in the question are typos) run depth-first or breadth-first search ignoring nodes coloured $i$.

Slightly more advanced approach: use a matrix-based all-pairs reachability algorithm, but rather than record a Boolean isReachable or a numeric shortestDistance record a bitmap of which colours can be avoided.


What does a polynomial time reduction mean? I am having a little trouble understanding what is meant by a poly-time reduction.
Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean that the algorithm that solves $A$ using $B$ as a helper runs in $O(n^k)$ for some $k$?

So for example suppose:

$A$ is an algorithm that takes as input a list of numbers and returns whether there is a sublist whose sum is $0$.

$B$ is an algorithm that takes as input a list of numbers, and an integer $k$, and returns whether there is a sublist of length $k$ whose sum is $0$.

Then

def A(L):
     for i in range (1, len(L)+1)"
           if B(L, i):
                return true
     return false

Since this $A$ calling $B$ as a helper runs in $O(n)$ so can this be described as a polytime reduction from $A$ to $B$?

Be careful, you probably mean a reduction from a problem to another, and not a reduction from an algorithm to another.

When a problem $A$ is polynomial time reducible to a problem $B$, it means that given an instance of $A$, there is an algorithm for transforming instances of $A$ into instances of $B$. This is often done to derive hardness results: if there was a fast algorithm for some problem, there would also be a fast algorithm for some other problem. The Wikipedia article on reductions gives as an example problem pair multiplication and squaring. Both of these happen to be rather easy problems, of course.

It doesn't matter what your problems look like and how the transformation actually works, as long as it is both correct and polynomial time.


What do you call a data structure containing multiple lists? I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know such a data structure must exist out there already, and I would like to find articles about its performance, but I don't know what it's called. The closest thing I've found so far is a skip list, but that seems to be more like a binary search tree and isn't just for dumping elements in.
I thought of implementing it something like this - the data structure L starts out containing an empty doubly-linked list of arrays.
[]

Then, when an array or other list-like data structure is added to it, it becomes the first element.
Add [100, -4, 2] to L
Head -> [100, -4, 2] <- Tail

The next array added becomes its second element, and so on.
Add [2, 6, 1] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <- Tail

Add [4, 5] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <-> [4, 5] <- Tail

L will only expose methods to iterate over it one at a time (in order), so it can be treated as a normal list.

If you don't care about the order of elements (e.g. you can deal with sets instead of lists) then the union-find structure gives an (amortized) constant time union operation.
There's also the unrolled linked list but the idea is to unroll a list for better cache performance rather than better performance when concatenating lists. For this reason, the number of elements at each node is generally bounded.
I don't think the data structure you describe has a name. It will act like a linked list in the worst case e.g. O(1) to add at the front/back and O(n) to search but you get the added bonus of O(1) concatenation that would be O(k) (for k new elements) with linked lists.
If that's all you're doing with your list then there doesn't seem to be any need to rearrange your list at any point e.g. by coalescing or splitting up nodes.
Update: An example of a specific data structure that seems to behave in the way you want is the Quicklist in Redis. It is described as a 'linked list of ziplists' where a ziplist is a contiguous bit of memory.


Typical NP-complete/hard problems in machine learning I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with constraints, etc.

I was wondering, is there any problem in ML that is NP-hard for which there are only approximations or small attempts of trying to solve them? I would like to look at them to see if my work can be applied there.

I am only interested in discrete optimization (so over integers/Booleans). Something that one could typically solve with constraint programming. Examples of such problems are scheduling tasks, finding paths in a graph given some weird constraints, TSP, vehicle routing...
My research is on constraint programming applied to graphs, so if the problem can be modelled as a graph problem, that is a plus.
My knowledge of ML is limited. I know the high-level concepts such as what regression, classification or supervised/unsupervised mean. Never actually implemented one of this ML things. I am watching a coursera class form Stanford on ML, but it is portrayed in a way that doesn't let me really see what are the NP-hard challenges.

Many theoretical problems in ML are NP-hard.

I think the famous AlphaGo is trying to solve a NP-hard problem.
Contextual bandit problem and its combinatorial variants are np-hard.
In social network analysis, the famous influence maximization problem is a NP-hard problem.
There are many others. You can search in google. Also you can find related papers in two famous ML conferences: NIPS and ICML.


Can a method be written if the language is undecidable? If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and false otherwise.

If a language is undecidable, what does that mean? Does it mean:

a.) We cannot write a method; we cannot even conceive of a method.

b.) We can write a method that returns true for each string that is an element of the language; for strings that are not an element of the language, the method may return false or it may loop indefinitely.

c.) Other (what?)

(c) If a language is undecidable, we can write a method that returns true for some strings that are an element of the language and false for some strings that are not an element of the language. But such methods will always return an incorrect result or not terminate on at least some elements of in the language.

(b) describes a particular kind of undecidable languages: the languages that are semi-decidable. A semi-decidable language is one such that there is a way to enumerate all the elements of the language with a Turing machine (or other equivalent computation method). So the method can go on enumerating the language until it finds its argument; this method loops indefinitely if the argument isn't in the language.

An example of a semi-decidable language which isn't decidable is the set of provable statements in any reasonable foundation of mathematics. (Note that I wrote provable, not true. The opposite of a provable statement is a statement that admits no proof; this statement might not be false: there may be no way to prove its opposite either.) Given a potential proof, you can easily verify that it's correct, and thus provable statements can always be recognized as such. However, it can happen that neither the statement nor its negation is provable, in which case the search for a proof would loop forever.

An example of a language that isn't semi-decidable, and whose complement isn't semi-decidable either is the set of programs in a Turing-complete programming language that take an argument and return true for all arguments. This is the halting problem. For a language that isn't semi-decidable, (b) doesn't apply: it is impossible to write a function that returns true for all programs that terminate on all arguments and loops forever (or returns false) on all programs that loop on at least one input.


Translating the in-order index of a node in a complete, balanced binary tree into the level-order index Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here.
As highlighted by the lack of a 7*2^64/8 term it is not necessarily full, but it is always complete. The nodes are stored in numerical order (in-order) in a list of which I know the size, and I have the index (call it the in-order index) of a node in that sorted list.
I'm trying to get the index (call it level-order index) of that same node if the array was stored according to the breadth-first traversal order (level-order) of the tree instead. In the example, the tree root would have level-order index 0 and in-order index 3.
What I've found already is that the level-order index consists of two parts:

A base part which is the amount of nodes contained in the perfect tree above the level in which the node resides.
An offset part which is the amount of nodes to the left of this node in the level in which it is contained.

Summed together, they produce the level-order index.
I have no idea how to find either of these parts from the in-order index. Of course, it is possible by iterating the tree programmatically, but since the exact layout and contents of the entire tree are known simply from the amount of nodes that it contains, I was wondering whether a mathematical relation between these two indices holds. Does anyone have an idea?

I think it is possible by rescaling the in-order index to what it would be in a complete and full (perfect) tree, i.e. $perfect\_index = index*\frac{ceil_2(size + 1)}{size}$ where $ceil_2(arg)$ computes the next power of two of $arg$.
Then, the level at which this perfect-tree in-order index sits is given as follows: $level = \left \lfloor{log_2(size)}\right \rfloor - nr\_divisible_2(perfect\_index + 1)$ where $nr\_divisible_2(arg)$ computes the number of times $arg$ is divisible by 2.
This works because it seems like in a perfect tree, the number of times the $index + 1$ of a node is divisible by 2 corresponds to the inverse zero-indexed level number of the level it is contained in. $1 + \left \lfloor{log_2(size)}\right \rfloor$ represents the total number of levels ($nr\_levels$) in a complete tree, so that minus the inverse level index minus 1 should give the zero-indexed level index in narrow-to-wide (top to bottom) tree orientation.
Then, the numerical spacing between in-order node indices in zero-indexed top-to-bottom level $L$ is 2 for the bottom level, 4 one up, 8 one up etc, in other words: $spacing = 2^{nr\_levels - L}$. For a 1-indexed in-order index, there is an additional spacing of $\frac{spacing}{2}$ at the beginning of the level. The horizontal offset of the node into the level is therefore given by $h\_offset = \frac{perfect\_index + 1 - \frac{spacing}{2}}{spacing}$.
Lastly, the amount of nodes preceeding the level this index is contained in is given by the size of a perfect tree of depth $nr\_levels - 1$, which is $base = 2^{nr\_levels}−1$.
The zero-indexed level-order index into the perfect tree should now be $base + h\_offset$. Since the level-order index of the first $size$ (counted in breadth-first traversal order) nodes is the same whether the tree is perfect or complete, I think this index will also be the level-order index into the complete tree.
Note that I have no proof of any of this, and have not tested it yet. Specifically, what worries me most is the rescaling at the beginning and if that is allowed/will work at all. The rest might contain errors but is not fundamentally flawed I think.


Does Kernighan-Lin algorithm guarantee its partitions to be a connected graph? Currently I am experimenting with Kernighan-Lin algorithm to produce coarse representation of navigation mesh for hierarchical pathfinding.

Based on the use case, my requirement is that partitions produced are a connected graph on its own.

For example, a bisection of the below grid

x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x

Should produce something along the lines of

a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b

where all nodes in partition A can be reached from a node in partition A without crossing a node in partition B.

However in quite a number of tests, I am getting disconnected partitions such as.

a--b--b--b--a--a
|  |  |  |  |  |
a--b--b--b--a--a
|  |  |  |  |  |
b--b--b--a--a--a

I am not able to judge if this is a bug in my code or whether the Kernighan-Lin algorithm by nature does not guarantee connected partitions.

I know that KL algorithm works towards a locally optimal solution for minimum cut, but does the algorithm not guarantee connected partitions?

The Kernighan-Lin algorithm tries to find a partition.  As far as I can tell, the partition it finds might or might not be connected; I don't see any guarantee that it will output a connected partition.  There is also no guarantee that it finds the optimal partition.  Even if the optimal partition is connected, I don't think there is any guarantee that the Kernighan-Lin algorithm will output a connected partition.


Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2) The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach:

Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this as follows: The machine has an infinite array A that is initialized to all blanks. It accesses this array as follows. One of the machine's work tapes is designated as the address tape. Also the machine has two special alphabet symbols denoted by R and W and an additional state we denote by q_access. Whenever the machine enters q_access, if its address tape contains 'i'R (where 'i' denotes the binary representation of i) then the value A[i] is written in the cell next to the R symbol. If its tape contains 'i'Wa (where a is some symbol in the machine's alphabet) then A[i] is set to the value a.

Show that if a Boolean function $f$ is computable within time $T(n)$ (for some time constructible $T$) by a RAM TM, then is is in $\mathrm{DTIME}(T(n)^2)$.

The trivial solution by using an additional tape recording pairs (address,value) turns out to be in $\mathrm{DTIME}(T(n)^3)$, since that tape can be of size $O(T(n)^2)$ with $O(T(n))$ pairs while the address of each pair can be of size $O(T(n))$.

You write in the comments:

  Since the address should be written in the tape by a $T(n)$-time Turing Machine, the size (i.e. string length) of the address can not exceed $O(T(n))$.

Can you use a similar argument to improve the bounds

  [The] tape can be of size $O(T(n)^2)$ with $O(T(n))$ pairs while the address of each pair can be of size $O(T(n))$.

you mention in the question? You may need to remember what operations are possible in constant time on the RAM, that is using the precise definition the authors use.


Can you specify a programming language without implementation? Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to execute a given program in that language on a given input to the output of the function corresponding to the program on that input.

What is are the minimal requirements of such a language?

Usually, implementing a programming language is at least giving a interpreter in a language (or a compiler to a language) that is no more than Turing-complete.

Using this "definition" we can specify a programming language like this:

there only one possible program that is HALT;
specification of HALT: it is a function that solve the halting problem.

Implementing this programming language requires solving the halting problem with the implementation. (Which is impossible since our implementation should not be more powerful than a Turing machine).

Specification handles logic and thus can ask for a lot more. Another specification that will be impossible to implement is "false". (Or any contradictory sentence in the specification) But this does not feels like a specification, which is why I used the halting problem example.


How is equation 1 simplified to equation 2 as shown below In CLRS (Intro to algorithms) on page 362, it says eqn(1) :

can be simplified to this equation(2):

I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal proof but one that makes logical and intuitive sense. (General arguments or assumptions that lead to this simplification are also welcome). Any effort is much appreciated. (Thanks)
Update
I want to know how the second equation is valid if we are not considering the optimal revenues on both sides but only the optimal revenue of the right-hand piece as suggested by the second equation. I.e. in the second equation, we use the price of the left piece and then add it to the optimal revenue of the right-hand piece.

I feel like this is basically paraphrasing the explantion in CLRS but maybe it will help.
Let $j$ be the length of the leftmost rod piece in an optimal solution. This piece has a cost of $p_j$ and so it contributes exactly that much to the total revenue. It is easy to see that the remaining part of the rod (of length $n-j$) must be divided up in an optimal manner as well for the whole thing to be optimal
(and thus leads to a revenue of $r_{n-j}$).
Thus, we have $r_n = p_j +r_{n-j} $. Because $r_n$ is the optimal revenue, $r_n \geq \max_{1\leq i \leq n}\{p_i+r_{n-i}\}$. But we also have $r_n = p_j +r_{n-j} \leq \max_{1\leq i\leq n}\{p_i+r_{n-i}\}$.
Putting both ineqalities together gives $r_n = \max_{1\leq i \leq n}\{p_i+r_{n-i}\}$.


Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters? Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?

An asynchronous multiplier is much bigger than an adder. It's about 18*n^2 NOR gates where n is the number of bits. An adder is about 15*n NOR gates. But for a 32-bits multiplication, a multiplier with successive additions will need 32 clock cycles, while an asynchronous mutliplier only 1. I think it's a big performance gain.

The same is for BCD to binary converter.

Last time I checked (more than 15 years ago), Wallace trees (and variants such as Dadda trees) were still the state of the art ($O(N^2)$ number of gates, but $O(\log N)$ latency; if you are naive in the way you do the additions, the latency may be $O(N)$).

Note that multipliers may be pipelined so you can still achieve a throughput of one multiplication per cycle but with a latency of more than one cycle if the latency of the multiplier is too big for your target clock rate.


Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice? Sanjeev Arora and Boaz Barak show the following :

  $P/poly = \cup_{c,d} DTIME (n^c)/n^d$

where $DTIME(n^c)/n^d$ is a Turing machine which is given an advice of length $O(n^d)$  and runs in $O(n^c)$ time. I do follow the proof. But I feel the  proof only holds if we assume that  $\forall n$ the advice given to any two $n$ length strings $x$ and $y$ is same.

But I am unable to see if the theorem still holds if the above condition if not applicable ?

Since $P/Poly$ talks about circuit families for languages (different circuit $C_n$ for length $n$ inputs), it is natural to talk about an advice which is a function of the input's length alone.
Different advice for each string will make the class too big. For any $L\subseteq \Sigma^*$, your advice for some $x\in\Sigma ^*$ can be 1 if $x\in L$ and 0 otherwise.


Regular expression for language that does not accept x string (3 letters, |x|=3) The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not contain "$ca$" at the end nor "$cab$" anywhere$\}$, $X_2=$"$bac$" and $X_3=\{w∈\{a,b,c\}^*| w$ does not contain "$ab$" at the start nor "$cab$" anywhere$\}$. What I find difficult to express is that "$cab$" does not appear anywhere in $X_1, X_3$ (the situation for "ca" and "ab" is simple because they consist only of 2 letters, we can split $X_1, X_3$ so that the "cab" problem remains). I have tried creating a NFA for this purpose but the automata needs to have quite a few loops (thus it is hard to find the regular expression). My question is whether there is a clever way to find the representation of non-existance of "cab", other than counting all the possibilities in the NFA that accepts such strings. If there is no such way, how can I find the regular expression of L from the start?

You can create a complete DFA (with all transitions populated) and then just invert the set of start and end states. In your case, using grammar notation, this accepts all strings with the sequence $cab$:

$$\begin{align*}
S & \rightarrow Q_0 \\
Q_0 & \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\\
Q_1 & \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\\
Q_2 & \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\\
Q_3 & \rightarrow a Q_3\,|\,b Q_3\,|\,c Q_3\,|\,\epsilon
\end{align*}$$

So this accepts all strings without the sequence $cab$:

$$\begin{align*}
S & \rightarrow Q_0 \\
Q_0 & \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\
Q_1 & \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\
Q_2 & \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\,|\,\epsilon\\
Q_3 & \rightarrow a Q_3\,|\,b Q_3\,|\,c Q_3
\end{align*}$$

Now you just have to convert that into a regular expression. Whether or not that's easier is up to you.

You can also directly construct a DFA which accepts $(a|b|c)^*bac(a|b|c)^* \setminus (a|b|c)^*cab(a|b|c)^*$ using Brzozowski's method, but that's a bit tricky to do by hand for this example.


Multi-dimensional Knapsack with added one-per-group constraint I have some sets (A, B, ...) each containing some vectors (e.g. [1, 0, -1]). How can I pick exactly one vector per set such that they sum to a specified target vector?

For example:

A: { [1, 0, -1], [3, 0, 0], ... }
B: { [0, -1, -1], [2, -1, 0], ... }

Target: [3, -1, -1]

Solutions:

1) A=[1, 0, -1], B=[2, -1, 0]
2) A=[3, 0, 0], B=[0, -1, -1]

I think this is a variation of the multi-dimensional knapsack problem with the added 'one-per set' constraint. Has this been written about anywhere?

For my domain, there are 30 sets each containing 50 vectors with 30 dimensions. These vectors are sparse with ~80% zeroes. There is at most one negative number per vector.

Any pointers to research papers or proposed algorithms would be hugely appreciated.

Thanks.

One reasonable starting point is to try formulating it as an instance of integer linear programming, and apply an ILP solver.  This might not be the best possible algorithm, but it is simple and easy to try.

Let $A_{i,j}$ be the $j$th vector in the $i$th set.  Define zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means you have picked the $j$th vector from the $i$th set.  Then you have constraints of the form

$$\sum_{i,j} A_{i,j} x_{i,j} = t$$

where $t$ is the target vector.  (Notice that this is a sum of vectors, so it actually turns into 30 different equations, one per dimension.)  Also to ensure that you pick exactly one element from each set, we have

$$\sum_j x_{i,j} = 1$$

for every $i$.  Then send that to an ILP solver.


How do global variables and automatic variables with the same name interact? Suppose I define a global variable and I define an automatic variable within a function definition with the same name as the aforementioned global variable.

What would happen to the global variable if I altered the automatic variable within the function body?

In most programming languages, especially imperative languages, a “variable” is actually two things: a name and a storage location. The storage location is a block of memory where a value can be stored and retrieved. The variable's name is often called an identifier. An identifier is a way to refer to some object in the program, in this case a storage location. A variable has a scope, which is the part of the program where the variable's name refers to the variable.

For example, consider the following C snippet.

int foo;
void myfunction(void) {
    float foo;
    … /* Here the identifier foo refers to the variable that's of type float. */
}
/* Here the identifier foo refers to the variable that's of type int. */

This snippets declares two variables. The two variables happen to have the same name: both are called foo. They're distinct variables, refering to distinct storage location, same as if they'd been called by different names. The scope of the foo variable that's of type float is the function myfunction: inside the code of myfunction, the identifier foo refers to this variable; outside the code of myfunction, the identifier foo refers to some other variable, or none at all. The scope of the foo variable that's of type int is the file where it's declared; the identifier foo refers to this variable everywhere is the whole file, except for the functions (or more generally blocks¹) which declare another variable that's also called foo. The local variable foo is said to shadow the global variable foo.

A variable whose scope is a whole file is usually said to be global. A variable whose scope is a function, method, block, etc. is usually said to be local. In the example above, the int-typed foo is a global variable and the float-typed foo is a local variable, local to the function myfunction.

The scope of a variable is the part of a program where its name refers to that variable. This is not always the same thing as the part of the program where the storage location exists. There is some correlation between the two, because it's usually undesirable to have a name for a storage location that doesn't exist, and it's often desirable to have a name for storage locations that do exist.

In C, the time during which a storage location exists is called its duration. The duration of a global variable is the whole program execution (“static duration” in C jargon, but that jargon doesn't extend to other languages, unlike most of the terms I used in this answer). (That's in C and some other langauges; in many other languages the duration of a global variable starts when the variable is defined.) The duration of a local automatic variable is the time during which the block containing it is executing. Note that “automatic” refers to the duration, not to the scope; “automatic” is not the opposite of “global”, “local” is. In C, you can't have automatic duration at a global scope, but you can have static duration at a local scope, with a variable that's declared static or extern.

void myfunction(void) {
    static int s;
    extern int e;
}
/* Here s and e are not defined */

The duration of both s and e is the whole program execution, but their scope is only the function myfunction: the names e and s are not valid outside that function. The difference between static and extern is that the variable s cannot be accessed from another scope, whereas e is the same variable as any other extern e in any scope.

Coming back to the foo example above, since two variables in different scopes have no relation, altering foo in myfunction has no impact on the global foo. They're unrelated variables, they just happen to have the same name.

It would be possible to rename the local variable foo to avoid having a name conflict. If you change all occurrences of foo in the code of myfunction to a different name that isn't used elsewhere in the program, you get an equivalent function.² This renaming process is known as alpha conversion in programming language theory.

The main reason programming languages allow programmers to pick the same name for different variables is that doing otherwise makes it difficult to write large programs and especially to write programs in pieces. If adding a library to your program meant that you had to rename some of your local variables in unrelated parts of your program to avoid conflicts, it would be a nightmare. (As it is, C only has global names for functions, which can be troublesome.)

Basically all languages allow variables in unrelated scopes to have the same name. C also allows shadowing: defining a variable in a scope hides any variable by the same name in a surrounding scope. This is common, but not univeral. For example, in Java, if you define a variable in a block, you can't define another variable by the same name in a nested block. The advantage of this restriction is that it prevents a source of confusion: a programmer might inadvertently use the name to refer to the variable from the outer scope, and not realize it instead refers to the variable in the inner scope. The downside of this restriction is that it makes some program transformations impossible without renaming the variable.

void myfunction(void) {
    int x = 1;
    if (…) {
        int x = 2;  // allowed in C, forbidden in Java
        printf("%d\n", x); // prints 2
    }
    printf("%d\n", x); // prints 1
}

Some languages have a way to refer to a variable that's shadowed, but it's uncommon. C has no such way, but you can refer to the storage location of the outer variable if you have a pointer to it.

¹  More precisely, the scope of a variable defined in a block runs from the variable definition to the end of the block. If there is an outer scope with a variable of the same name, it's that same part which is excluded from that outer scope.
²  This only works in languages where variable names are not significant. Actually, I lied here, because C can make variable names significant via the preprocessor. C is quite a complex language… If that preprocessor feature isn't used, variable names are not significant.


Counting elements that are greater than the median of medians Short version: I want to know where the $-2$ comes from in the formula on p. 221 of CLRS 3rd edition.

Long version: CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers.  The algorithm is roughly:

  Input: an array of $n$ elements and $i$, the number of the order statistic to return from the elements.

  Divide the $n$ elements into $\lfloor n/5 \rfloor$ groups of 5 elements each along with an optional group containing $n\mod{5}$ elements (resulting in $\lceil n/5 \rceil$ groups.)
  Find the median of each of the groups by sorting.
  Recurse, using the $\lceil n/5 \rceil$ medians as the array and $\lfloor\lceil n/5 \rceil/2\rfloor$ as the order statistic, resulting in the median-of-medians.
  Partition the $n$ elements around the median-of-medians (using a quicksort-like $O(n)$ partitioning algorithm.
  Letting $k-1$ be the number of elements less than the median-of-medians, if $i = k$, return the median-of-medians.  Otherwise recurse: if $i < k$ then recurse finding the $i$th order statistic of the $k-1$ elements less than the median-of-medians; if $i > k$,  then recurse finding the $i-k$th order statistic of the $n-k$ elements greater than the median-of-medians.

  Output: the $i$th order statistic of the $n$ numbers.

In the proof of the runtime, CLRS argue that the number of elements greater than the median-of-medians is at least:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg)
$$

The reasoning is that half of the medians are greater than the median-of-medians, and each of those medians' groups has at least three elements greater than the median-of-medians (the median itself plus the two elements greater than the median.)  That would result in

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg)
$$

for the lower bound on the number of elements greater than the median-of-medians.

But we must account for two things: the group containing the median-of-medians (the median-of-medians is not greater than itself) and the group that contains the modulo leftovers.  To account for the group containing the median-of-medians, we subtract 1, resulting in:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 1
$$

and I think that for the modulo leftovers group, we should subtract 4, because the least number of elements in the group is 1.  So that would give:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5
$$

which can be transformed into

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) + 1
$$

Why does my analysis lead to a lower-bound 1 greater than that given in CLRS?

In

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg)
$$

we are subtracting 2 in order to discard the group containing the median of medians and the group of leftovers. So, 2 is the number of groups we are discarding.

First of all, note that there may not be a group of leftover elements: if $n$ is an exact multiple of 5 there will be no leftover group. We are interested in bounding from below the number of elements greater than the median-of-medians in the worst case, so suppose that a leftover group exists. Therefore, it will contain  at least an element and no more than 4 elements. If you want to reason in terms of elements to be discarded and not in terms of groups, then we must discard exactly 3 elements for the group containing the median of medians (including the median of the medians), and at most 2 element from the leftovers group (if this group contains 1 or 2 elements you do not discard any element; if this group contains 3 or 4 elements, then you discard respectively 1 or 2 elements which are greater than the group's median). So, you discard in the worst case (leftover group with 4 elements) 3 + 2 elements:

$$
3 \bigg(\bigg\lceil  \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5
$$


How does a recurrent connection in a neural network work? I am reading a very interesting paper on genetic algorithms which define neural networks.  I am familiar with how a feedforward neural network operates, but then I came across this:

Where node #4 goes back to connect to #5.  I was wondering how this is handled?  Does the state of node 4 get kept from the last timestep and applied to node 5 when it is time to calculate its activation?

When a recurrent network is calculated you can imagine the network is 'unrolled' out through time.

When visualized this way, you can see activation and loss can be calculated using the same method as a typical network.

So to clarify using the example you provided. Yes, the input to node #5 is the output from node #1, node #2, and the previous time steps node #4.

It is important to note; Typically the input and output to RNN's are expected to be time dependent. That is, for each time step t there is input t and output t. This makes RNN especially good at things like evaluating sequences. Although it is possible to keep the input and output equal throughout time.


Hoare-Logic: Requirements for imperfect data types Theoretically, Hoare-Logic let's one prove the correctness of an algorithm, given pre- and post-condition.

However, as far as I've seen it so far, one idealizes his data-types to a mathematical set like $\mathbb{N}$ or $\mathbb{R}$.

So, even though the logic might be sound in Hoare-calculus, the discrepancies between the data types used and the data types modeled can still fail the result (e.g. Overflow for Integers).

Therefore, the question is:
Which additional conditions have to be met (after each step of the algorithm?) to accomodate for the imperfect data types actually used?

No, when using Hoare logic properly, you make sure to account for integer overflow etc. and model the full semantics of the programming language.

It is possible to use Hoare logic along the lines you suggest, but the problem with that is that it invalidates all guarantees you might have hoped for.  Since the whole point of Hoare logic is to obtain guarantees, that seems rather counterproductive.

So if you are using Hoare logic for serious verification, you make sure that the Hoare triples accurately represent all elements of the language semantics, including integer overflow (if relevant).  For instance, part of the verification task might be to prove that integer overflow cannot happen; if you don't do that, then the Hoare triples need to account for that possibility.


Higher order empirical entropy is not the entropy of the empirical distribution? Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $x$ of length $n$ equals the entropy of the empirical distribution on the set of all words of length $n$ (the conditional probabilities are taken from the observed occurrences in $x$). Until today, I was totally sure that this is true, but it seems to be wrong for very easy examples (e.g. for $x=1011$).

To be more accurate, consider $\Sigma=\{0,1\}$, $x=1011$ and $k=1$ such that $$n\cdot H_k(x)=4\cdot H_1(x)=2.$$
On the other hand, the corresponding empirical distribution is a First-order Markov source described by

$P(\text{The first letter is }0)=0$
$P(\text{The first letter is }1)=1$
$P(\text{Letter }0 \text{ immediately follows after letter }0)=0$
$P(\text{Letter }1 \text{ immediately follows after letter }0)=1$
$P(\text{Letter }0 \text{ immediately follows after letter }1)=0.5$
$P(\text{Letter }1 \text{ immediately follows after letter }1)=0.5$

Now this probabilities yield a random variable $X$ on words of length $n=4$, where the Shannon entropy is
$$H(X)=-\sum_{w\in\Sigma^4}P(w)\log P(w)=\frac{9}{4}.$$
(You only need to consider words of length $4$ which start with $1$ and do not contain $00$.)

But shouldn't be both measures intuitively give the same value?
I did the calculations more than once, so I am pretty sure the mistake is in my understanding, not in the calculation.
Or did I always thought something wrong? But it seems so clear that the empirical entropy is the entropy of the empirical distribution (also for higher order Markov sources).

$ $

$ $
Backround
For a given string $x\in\Sigma^n$ over an alphabet of size $k$, the ($0$-th order) empirical entropy is defined as
$$H_0(x)=\frac{1}{n}\sum_{i=1}^{k}n_i\cdot\log \frac{n}{n_i},$$
where $n_i$ is the number of occurrences of the $i$th alphabet symbol.
The $k$-order empirical entropy ($k\ge 1$) is then defined as
$$H_k(x)=\frac{1}{n}\sum_{|w|=k}|S_w|H_0(S_w),$$
where $S_w$ is the string obtained by concatenating the characters immediately following occurrences of $w$ in $x$.

No, as your counterexample shows, it is not true.  I don't understand why you previously thought it was true, either, so it's hard to say what might have gone wrong with your previous intuition.

We can say that

$$H(X) = H(X_1) + H(X_2 | X_1) + H(X_3 | X_1,X_2) + H(X_4 | X_1,X_2,X_3),$$

where $X_i$ denotes the $i$th character in $X$.  that much is true.

In the example you gave, $H(X_1) = 0$, $H(X_2|X_1) = 1$, $H(X_3|X_1,X_2) = 0.5$, $H(X_4 | X_1,X_2,X_3) = 0.75$ (see footnote * for explanation).  Thus $H(X) = 1 + 0.5 + 0.75 = 2.25$.

Do notice that $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ both depend on $i$.  This might be important.

Also, notice that $H(X_{i+1}|X_1,\dots,X_i)$ is unrelated to $H_1(x)$.

Perhaps you were expecting $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ to be the same for all $i$?  If that were true, there might be a relationship between $H_1(x)$ and $\Pr[X_i=1]$ and $H(X_{i+1}|X_1,\dots,X_i)$ (or something similar to them)... but it's not.

Footnote *: How did I calculate those?  I used the formula

$$H(X_{i+1}|X_1,\dots,X_i) = \sum_v \Pr[(X_1,\dots,X_i) = v] \times H(X_{i+1}|(X_1,\dots,X_i) = v).$$

For $i=1,2$, we only need to consider two values of $v$; for $i=3$, we only need to consider three values of $v$.


Why does floating point modulus exactness matters? Most Smalltalk dialects currently implement a naive inexact floating modulus (fmod/remainder).
I just changed this to improve Squeak/Pharo and eventually other Smalltalk adherence to standards (IEEE 754, ISO/IEC 10967), as I already did for other state of the art floating point operations.

However for adoption of those changes, I anticipate that adhering to standard will not be enough to convince my peers, so explaining in which circumstances this exactness would really matter would help me a lot. I could not find a good example by myself so far.

Does any one here knows why/when/where (IOW in which algorithm) such exactness of modulus would matter?

Note that inexact floating point implementation affect the weather.

There have been tests running weather predictions with the same inputs on different hardware and the predictions diverged. If you are running iterative algorithm then a small rounding difference here or there can result in a butterfly effect changing sunshine into rain.

The rounding rules in standards (IEEE 754, ISO/IEC 10967) have been carefully thought out so numeric algorithms behave predictable with the most accuracy and reproduce the same result every time. By not following the standard numerical algorithms designed for those rounding rules will break and iterative algorithms like weather predictions can even give a random result.

(and doesn't that say something about weather predictions? :)


PCP when upper and lower words have different length The Post correspondence problem (PCP) asks, given two sets of words $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ over the same alphabet, whether there are indices $i_1,\ldots,i_s \in \{1,\ldots,n\}$ and $j_1,\ldots,j_t \in \{1,\ldots,m\}$ such that
$$
a_{i_1} \ldots a_{i_s} = b_{j_1} \ldots b_{j_t}.
$$
It is well-known that PCP is undecidable.
What happens if we restrict $s \neq t$? Does the problem become any easier?

The problem doesn't become any easier.
Suppose we are given an instance $a_1,\ldots,a_n,b_1,\ldots,b_m$ of PCP.
Let $\sigma$ be a new symbol. Add to the first list the words $a'_1 = \sigma a_1,\ldots,a'_n = \sigma a_n$, and to the second list the word $b'_0 = \sigma$.
If the new PCP instance has a solution, then we can obtain a solution of the original PCP instance by removing all occurrences of $\sigma$. Now suppose that the original PCP instance has a solution
$$ a_{i_1} \ldots a_{i_s} = b_{j_1} \ldots b_{j_t}. $$
If $s \neq t$ then this is a solution of the new PCP instance in which $s \neq t$. If $s = t$, then consider the following solution instead:
$$ a'_{i_1} \ldots a_{i_s} = b'_0 b_{j_1} \ldots b_{j_t}. $$


Has anyone seen a NP graph problem like this before? I have a following graph-based problem:

Input: positive integers K and L, undirected graph G
I have to choose K vertices from this graph
In the path between each pair of chosen K vertices there has to be at least L vertices, i. e. there has to be a "space between" each two of chosen vertices made of at least L vertices.

The above of course may not be possible for a given instance of a problem, then I have to check that. I'm quite sure that this problem is NP or even NP-complete, since it has to do with paths with length constraint. Have you ever met a similar problem? Do you have an idea how to reduce it to some more well-known problem, possibly NP, e. g. vertex cover or graph coloring?

Also, note that my graph is a grid graph, which might not be "full" but a subgraph of a full rectangular grid.

This is known as the distance-$d$ independent set, i.e., you are looking for an independent set of size $k$ where the distance between every two elements in the solution is at least $d$.

The problem is NP-complete even on planar graphs according to [1], but I don't know about its complexity on partial grids.

Regarding reductions, you can probably take the $d$'th power of the graph and find a (distance-1) independent set in that. The claim is that any solution here is a distance-$d$ independent set in the original, but you need to verify this.

[1] Eto, Hiroshi, Fengrui Guo, and Eiji Miyano. "Distance-$d$ independent set problems for bipartite and chordal graphs." Journal of Combinatorial Optimization 27, no. 1 (2014): 88-99.


What is a self-delimiting program? I came across the term self-delimiting program, referring to the paper "Laws of information (nongrowth) and aspects of the foundation of probability theory" by Levin, 1974.
Unfortunately this paper is not available afaik, and I couldn't find any definition anywhere. What is the definition? or what is a resource stating the definition and explaining the idea?

While a specific program could be self-delimiting, in this context what we usually mean is a self-delimiting encoding of programs. An encoding of programs is self-delimiting if it forms a prefix code, that is, no program is a prefix of another program. Intuitively, programs are self-delimiting, so there is no ambiguity in where a program ends.
Why do we care? Consider the chain rule in Kolmogorov complexity, which expresses the idea that if there are short programs that generate $x$ and $y$, then there is a short program that generates the concatenation $xy$. If programs are self-delimiting, then a program for generating $xy$ could look as follows:

Run the following two programs in sequence.
Program for generating $x$.
Program for generating $y$.

Denoting the Kolmogorov complexity of a string $w$ by $C(w)$, this shows that $$ C(xy) \leq C(x) + C(y) + O(1). $$
(The $O(1)$ takes care of the first bit.)
In contrast, if programs are not self-delimiting, then it is impossible to tell where the program for generating $x$ ends. Therefore the chain rule for non-self-delimiting Kolmogorov complexity takes the more complicated form $$ K(xy) \leq K(x) + K(y) + O(\log K(x) + 1), $$
where $O(\log K(x))$ is needed to delimit the first program.
Self-delimiting programs are also useful for defining the universal distribution, which is a distribution on programs useful for understanding average-case complexity. The probability that the program $P$ comes up is $2^{-|P|}$. Since the valid programs form a prefix code, Kraft's inequality states that $\sum_P 2^{-|P|} \leq 1$, so this is a (sub-)probability distribution.
So far the advantages of prefix-free Kolmogorov complexity. The disadvantage is that whereas $K(w) \leq |w|$, this no longer holds for $C(w)$; instead we only have $C(w) \leq |w| + O(\log |w|+1)$.
You can read a lot more on these issues in the excellent monograph of Li and Vitanyi on Kolmogorov complexity.


Reduction from Vertex Cover to Polygon Cover Polygon Cover:

Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$.

Output: True if and only if there exists a subset in $S$ of at most $k$ (not necessarily convex) polygons such that every point in $P$ lie inside some polygon in the subset.

I am trying to give a polynomial reduction from Vertex Cover to Polygon Cover.  However, I am struggling slightly.  My idea is that to construct the set of points $P$, I figured that I should map each $uv \in E$ with ($u < v$) to a point $(u, v)$.  For the set of polygons $S$, I was thinking to define some type of non-convex polygon in order to cover the rows and columns.

Let $(G,k)$ be an instance of Dominating Set where $G$ is drawn on the plane with any drawing.  Construct for each vertex $v$ a polygon $S_v$ which covers all of $N[v]$ and no other vertices, where $N[v]$ is the set containing $v$ and all its neighbors.  Let $S = \bigcup_{v \in V(G)} S_v$ and the points $P$ be the points where the vertices are drawn.  The instance for Polygon Cover is $P, S, k$.  This reduction is a Karp-reduction from Dominating Set which is NP-complete, and hence Polygon Cover is NP-complete as well.

To formally prove that the above reduction works, you need to prove that selecting a set of $k$ polygons $S' \subseteq S$ which covers all the points corresponds to picking a set of vertices whose neighborhoods contain all the vertices of the graph.

If you want to prove it for convex polygons, you can use the fact that Dominating Set is NP-complete on planar graphs and that planar graphs are equivalent to kissing graphs.


Propositional formula in DNF can be decided in polynomial time? For a given propositional formula f in DNF, one can decide in polynomial time, if the formula is satisfiable:
Just walk through all subformulas (l_1 and ... and l_k) and check, wheter it has NO complementary pair of literals. Formula f is satisfiable iff such subformula exists.

Is my approach above correct ?

If yes, I'm wondering why all modern SAT solvers get a CNF as input format, and don't just use DNF.

The conversion from CNF to DNF can come at an exponential cost. For example $(a_1 \lor b_1) \land \cdots \land (a_n \lor b_n)$ expands to $2^n$ many terms. As you comment, for DNF satisfiability is easy - it is falsifiability which is hard. If the problem is trivial, you don't input it to a SAT solver, and that's why SAT solvers accept CNFs instead of DNFs.

If you believe that P is different from NP, then this implies that there is no polynomial time way to convert CNF satisfiability to DNF satisfiability, since the former is NP-complete while the latter is in P.


Highest possible value of combinations of 5 According to https://www.heroescounters.com/teampicker a Hero has a synergy value with another hero, Heroes of the Storm have 60+ heroes each one with a synergy value for example:

HeroID  Synergy.With.HeroID      Synergy.Points
1               2                       97
1               3                       95
1               4                       94
45              1                       2
45              2                       11

A Team in heroes of the storm have 5 heroes, and the full synergy of a team is calculated by the formula:

Team_total_synergy = Synergy_Points(Hero1 with Hero2) +
mean(Synergy_Points(Hero3 + Hero1) + Synergy_Points(Hero3 + Hero2)) +

mean(Synergy_Points(Hero4 + Hero1) + Synergy_Points(Hero4 + Hero2) + Synergy_Points(Hero4 + Hero3)

[And so on... till Hero5]

Explaining the formula: Each Synergy Value after the synergy of Hero 1 and Hero 2 is calculated by the Mean of that Hero with the rest of the team, When Hero5 is added up i got the synergy of the team summing all the values.

My Answer is, How can I find the Team with the greatest possible synergy given that formula, and how can I write the code to find it given the possibility there are 64 Heroes(approximately) without brute-forcing all all 64^5 combinations of heroes.

I suggest you solve it with integer programming (you can download gusek for free for not too complicated computations).

Define a graph $G=(V,E)$, where $V$ is the set of heroes, and $E$ a link between two heroes, with their synergy value $s_{i,j}$
 for $(i,j) \in E$.

Define, for $i \in V$, $X_i$ the boolean variable equal to 1 iff you take hero $i$

Define additional real positive variables $Y_{i,j}$ for the cost, which are equal to 1 in the final solution iff heroes $i$ and $j$ are selected.

You want to solve

$\max \sum_{(i,j) \in E} Y_{i,j}s_{i,j}$

such that $\sum_{i \in V}X_i = 5$

$\forall (i,j) \in E, Y_{i,j} \leq X_i $

$\forall (i,j) \in E, Y_{i,j} \leq X_j $

other formulations are possible. I like this one, since it only has $|V|$ boolean variables

If that does not work (too much computation time), try to modify some already existing algorithms to find cliques, such as the one from Tarjan and Trojanowski.

Sidenote, you are lucky that the number of heroes is limited by 5. Otherwise, it would be a maximum clique problem, which is NP-complete.


Which research languages have a stronger typesystem than Haskell and why? Here I read that:

  Haskell definitely does not have the most advanced type system (not
  even close if you count research languages) but out of all languages
  that are actually used in production Haskell is probably at the top.

So I am asking two things:

which research languages have more powerful type systems  than Haskell;
what do they improve.

I am just a programmer, so I don't know many mathematical objects used in type theory, please provide gentle explanations if you can.

The question is somewhat problematic, since it relies on a subjective definition of "better."
Dependently-typed languages such as Agda, Idris, and Coq have a stronger type system than Haskell. This means, you can use the types in these languages to prove strictly more properties about your code than in Haskell. That is, there are more incorrect programs that will be caught.
However, this comes at a price: type inference, and testing whether any values of a given type exist, are no longer possible. This means for these languages, you need to explicitly annotate your code with types. Essentially this boils down to writing your own correctness proofs for your code.
So are these languages "better" than Haskell? They can check advanced proofs of correctness for your code, but they can't automatically prove properties about your code the way Haskell can.
Another research language that is "better" than Haskell is LiquidHaskell. This is basically Haskell with refinement types bolted on top, parsed from special comments.
Refinement types allow you you refine types with properties. For example, instead of having an Int, you can specify {i : Int | i > 0}, giving the type of all positive integers. Type inference is decidable with refinement types, but you can't prove nearly as many correctness properties with them as you can with dependent types.
There are other refinement type systems out there, but I'm not terribly familiar with any of them.


Why do we still use a Von Neumann Architecture in modern computers? The Von Neumann architecture was first created in the mid 40s for use in a computing system known as ENIAC for research into the feasibility of thermonuclear weapons.

To this day the Von Neumann architeture is still primary foundation in the majority of modern computers. I have listened to a few historians and scientists mention that there is likely more efficient architectures and that Von Neumann himself didn't believe in its universal capability(unfortunately cannot remember enough to find a link).

So why do we still use this architecture in the majority of modern computing?

So why do we still use this architecture in the majority of modern
  computing?

The assumption itself, first clause: Modern Computer <= Von Neumann

Firstly, do note that the Von Neumann architecture is not used exclusively: almost any current "Von Neumann" machine except for very small microcontrollers (which are occasionally Harvard machines) features several important extensions to the original architecture, from DMA to MMUs.

Specialized coprocessors are very popular - most notably, GPUs.

Those work very well in conjunction to a Von Neumann machine.

The assumption itself, second clause:  Von Neumann <= Modern Computers

The limitations of the Von Neumann architecture and the need for non-Von Neumann architectures for certain applications is well recognized in the scientific community, most importantly whenever "[general] artificial intelligence" of interest, see for example this very recent paper, which continues the line of work started by Carver Mead, who envisioned one of the most radical departures from "classical" architectures in 1989, in the form of analog, time-continuous, highly parallel "neuromorphic" chips.

Your premise is thus, in a way, flawed, unless it is implied that you're referring purely to industrial applications (read on for that part).

On the notion of efficiency

Note that Mead himself had envisioned his architecture as complementary to a traditional Von Neumann machine.

Why?

This brings us to another important point: you mention "more efficient architectures", but efficient for which sort of workload?

Sontag and Siegelmann have famously proved that a feed forward neural network is Turing-complete, as is, of course, the Von Neumann architecture, and if we accept Church's thesis (which has never been seriously challenged in quite a while) that this amounts to the ability to compute all computable functions, they're theoretically interchangeable and unsurpassed in their abilities.

However, leaving aside for a moment the issue of practicality, they are not as efficient for the same applications.

I'm guessing that a neuromorphic chip such as Carver Mead's would make for a terrible Excel machine.

So why mostly Von Neumann in industrial applications?

But yes: even if research has branched in other directions and has gotten to the status of prototypes and early industrial devices Von Neumann architectures are still the bread and butter of industrial applications (and a good foundation to extend with coprocessors and specialized optimizations).

It's safe to assume that the reason is practical:

They're universal -- i.e. "good enough" in the broadest possible sense: they are Turing complete and sufficiently close to some theoretical models such as the TM itself or the URM; it is safe to assume that the ubiquity of the Von Neumann machine has influenced developement of theory as well.
They're tolerably easy to reason about and very well understood by engineers and developers
They work very well for existing industrial workloads that drive the demand for hardware R&D; there is 60 years' worth of algorithms and software for Von Neumann machines.

Von Neumann closed under copper cable?

Finally - and only partly tongue-in-cheek: do note that it is very easy to obtain a decidedly non-Von Neumann machine from off-the-shelf parts: just buy two laptops and connect them with an UTP cable and you have a very strange machine where you don't have uniform, synchronized access to a single mutable storage or a single clock.


Running algorithms in parallel I'm doing a course in Computational Number Theory and am currently looking at algorithms such as Euclid's algorithm, Square-roots modulo a prime, LLL reduction algorithm, McKee's method, Pollard's $p-1$ method, the elliptic curve method and a couple of others.

In an assignment, I'm asked the following question: Which of the algorithms can be run easily using several computers in parallel?

Here are my questions which I hope can shed some light on my above question:

What is the alternative to running computers in parallel (if such an alternative exists)? What are the differences?
What criterion determines whether running computers in parallel is an advantage?

I'll start by giving an example which can be easily run in parallel: the elliptic curve method (ECM). In this method, we choose a random elliptic curve $E$, and run Pollard's $p-1$ method on this curve up to a certain point. The idea is that with probability $\alpha$, Pollard's $p-1$ method terminates within $T$ iterations. We optimize over $T/\alpha$, the end result being that $\alpha$ is quite small.

Here is how you would run ECM in parallel. Each processor (or core) runs the algorithm just described, until one of them succeeds in factoring the integer. Having $N \ll 1/\alpha$ processors (or cores) cuts the running time by a factor of $N$. An algorithm where a similar approach is possible is called embarrassingly parallel.

A slightly different example is the quadratic sieve. In this algorithm, we need to find a certain number of smooth integers and factor them. If we aim at finding $n$ such integers and there are $N$ processors available, we can assign each of them to find $n/N$ integers. A more complicated approach would be to have one central processor assign "jobs" (integers) to processors: each time a processor finishes factoring a smooth integer, it receives a new one. (In practice, since the algorithm sieve for smooth integers, each processor will get a range of potential smooth integers.) This scheme is also embarrassingly parallel.

In contrast, consider the simple Pollard's $p-1$ method. The algorithm is iterative in nature and there doesn't seem to be a simple way to run it in parallel; we can perhaps run the FFTs associated with modular exponentiation using a sophisticated parallel scheme, but this is no longer embarrassingly parallel.

At this point you should be able to answer the question on your own. The question is asking you to determine which of the algorithms are embarrassingly parallel.


shortest path in color-weighted graphs I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum of the weights of the colors used. If we have for example a path A->B->C where A and C are red colored and B is blue colored, its length should count the weight of red only once (and the weight of the blue node)! I'm struggling to find an (efficient) algorithm that can do this. Dijkstra's algorithm or any greedy algorithm cannot work, because they require that a local optimum must be also a global optimum. Here, this is not the case because the weight of a vertex depends on the path to it. You could add vertecies for each combination of colors but this would add exponantially many vertecies.
It would be enough for me to find such an algorithm for DAGs.
Thank you very much for your help!

This problem seems to be NP-hard.  A reduction from 3-SAT is left as an exercise, but here is a hint.  The empty nodes are free, and then create a color for each literal and its negation.  The cost is 1 for each.  You can then visit a "clause" for free if and only if one of its literals is selected.  Now, the cheapest s-t-path costs $n$ if and only if the formula is satisfiable.


Why are there $2^{2^{n}}$ possible boolean functions of n inputs? Why are there $2^{2^{n}}$ possible boolean functions of n inputs? How to derive that?

For 3,
I can only write down 16 and cannot go further.

8 of

$f(x_{1},x_{2},x_{3})=0$

000 = 0

001 = 0

010 = 0

110 = 0

111 = 0

110 = 0

101 = 0

011 = 0

and

8 of

$f(x_{1},x_{2},x_{3})=1$

000 = 1

001 = 1

010 = 1

110 = 1

111 = 1

110 = 1

101 = 1

011 = 1

That's the maximum I can go. How do I proceed?

Hint:
let $f$ be a boolean function with $n$ inputs  i.e $f(b_{1},b_{2},b_{3}...b_{n})$
For example, when $n=3$,   $(1,0,1)$ and $(1,1,0)$ are  different inputs to $f$.
Each input maps to an answer. Also there are limited values that  $f(b_{1},b_{2},...,b_{n})$ can take.

Now consider the definition of a function: $f\colon A \to B$

Define  the size of both  sets $A$ and $B$ and you will arrive at your answer.


Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences Given inorder and preorder (or postorder) traversal sequences of a

binary tree
balanced binary tree
binary search tree

of n nodes, what is the time complexity of creating the respective unique tree.

Assuming inorder and preorder sequences are given -

1. For binary tree : Starting with the root node, traverse the preorder sequence and for each node, binary search on the given inorder sequence, separating the left and right subtrees. Recurse on the next node with the new piece of the inorder sequence. Time complexity in worst case : T(n) = T(1) + T(n-1) + O(logn) = O(nlogn)

2. For balanced binary tree : Follow the same procedure as in 1. But, since the tree is balanced, the time complexity in worst case is different: T(n) = 2T(n/2) + O(logn) = O(n)

3. For binary search tree : Traverse the preorder sequence and at each node, keep a flag (=key of the parent node). If the next node in the sequence is less than the flag, then the node gets to be the left or right child of the current node. Else, we go back to the parent recursively and apply the same procedure to it. Time complexity = O(n) since we are creating nodes in the preorder sequence.


Trouble finding what this recurrence solves to I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$

I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.

Hint: can you solve it for $n = 2^k$ where we replace $O(1)$ with constant $c$ and let $f(1) = c$? Then you have:

$$f(2^k) = 2f(2^{k-1}) + c$$

Then the pattern starts $f(1) = c$, $f(2) = 3c$, $f(4) = 7c$, $f(8) = 15c$... any guesses?


The halting problem of Turing machines in view of enumeration of initial tape configurations As far as I know, presentations of the (general) halting problem (cmp. Wikipedia) are referring explicitly to an ennumeration of (applicable) programs. For the purpose of my questions let's consider specificly any programs for one-head, two-symbol Turing machines with sufficient memory to store the instructions prescribed by the program and any (internal) state reached in the course of executing the program.

Such an enumeration of applicable programs could be symbolically written as

$$ p : \{ \mathsf{TM_{\text{(1 head, 2 symbols)}}} \} \leftrightarrow \mathbb N.$$

(The mapping is one-to-one since enumeration is supposed to be without gaps, and there are infinitely many Turing machine programs to be enumerated. For definiteness, the set $\mathbb N$ here denotes the whole numbers, including $0$.)

I am interested in the consequences of the input (i.e. specificly the contents of the tape, in reference to the machine head, at the start of program execution) being explicitly encoded through an enumeration as well; symbolically

$$ s : \{ \text{ starting tape configurations } \} \leftrightarrow \mathbb N;$$

specificly for instance, for input $\text{ tape contents }$ with non-blank fields on positions $1 \le a \lt b \lt c ... \lt l$ to the left of the Turing machine head  and on positions $0 \le z \lt y \lt x ... \lt r$ to the right of the head (and if applicable on position $0$ directly under the head in starting position) then

$$ s[~\text{tape contents}~] := (4^a + 4^b + 4^c ... +~4^l)/2 + 4^z + 4^y + 4^x ... +~4^r.$$

(The completely blank tape is accordingly encoded as number $0$.)

My question:
Given the above description, can the non-existence of a halting program ("DoesItHalt?") be proven regardless of the specific enumeration $p$ of Turing machine programs?
And if so, how exactly?

As an illustration of possible difficulties in trying to argue that a Turing machine program "DoesItHalt?" doesn't exist one might perhaps consider the composition

BadH := EncodeInput | DuplicateArgument | DoesItHalt? | ContrarianActor

which should have the value $p[$ BadH $]$ in the enumeration of programs,
running on input "BadI" which would be selected exactly such that

$p[$ BadH $] = s[$ BadI $]$;

where

EncodeInput is supposed to be a specific program implementing the enumeration $s$,
DuplicateArgument is a simple program to prepare the two arguments required for a (meaningful) subsequent execution of DoesItHalt?, and
ContrarianActor is a simple program whose action is just the opposite of the intended meaning of DoesItHalt?'s result.

Then it would be premature to conclude a contradiction; that program DoesItHalt? didn't function as correct halting program because the program BadH, being run on the inital tape configuration BadI, is thought to act eventually just contrary to the intended meaning of the presumed result of program DoesItHalt? evaluating (running on) the two argument values $p[$ BadH $]$ and $s[$ BadI $]$. Because:

Already the (apparently necessary) program part "EncodeInput" is questionable: It is supposed to terminate when starting on any initial tape configuration with a finite number of non-blank fields (in order to return its enumeration value). But therefore it also returns the exact same result when starting on any "suitably extended" initial tape configuration with some (still finite) additional non-blank fields "sufficiently further out". The correct enumeration values of any such "suitably extended" initial tape configuration cannot be returned by the specific "EncodeInput" program.

Then why not enumerate the specific "BadH" program of the example above precisely by such an "inaccessible" value (which obviously is not being calculated by program part DuplicateArgument either); thus defeating the attempt of arriving at a contradiction in this specific case. (Obviously, this would have to be accomodated by a suitable enumeration of all programs.)

The Halting problem is stated in terms of any admissible numbering. There are effective (i.e. Turing-computable) compilers between all such numberings, so the Halting problems are all the same. That is, in particular not decidable.

There are numberings of all partially-recursive functions for which the Halting problem is decidable -- of course. For instance, give all "yes"-instances even and all "no"-instances odd numbers. Such a numbering would certainly not be admissible; in this case because it would not be partially recursive.

Thus, it comes down for you to show that your numbering is admissible or not. If not, the Halting problem may be decidable but the numbering would be ... not very useful.


Variations of Omega and Omega infinity Some authors define $\Omega$  in a slightly different way: let’s use
$ \overset{\infty}{\Omega}$
(read “omega infinity”) for this alternative definition. We say that $f(n) = \overset{\infty}{\Omega}(g(n))$
if there exists a positive constant $c$ such that $f(n) \geq c\cdot g(n) \geq   0$ for infinitely many integers $n$, whereas the usual $\Omega$ requires that this holds for all integers greater than a certain $n_0$.

Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative,
either $f(n) = O(g(n))$ or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$.

I am trying learn Algorithms. But I am unable to prove this. Can the experts help me ?

Hint: If $f(n) \notin \overset{\infty}{\Omega}(g(n))$ and $g(n)$ is asymptotically non-negative, then for all positive constants $c$, $f(n) \leq c \cdot g(n)$ for large enough $n$. This follows by ignoring the condition $c \cdot g(n) \geq 0$ and negating the definition of $f(n) \in \overset{\infty}{\Omega}(g(n))$. In fact, this way you get the stronger result that either $f(n) \in \overset{\infty}{\Omega}(g(n))$ or $f(n) \in o(g(n))$ (but not both).

Further hint: You can start by showing that the negation of "$P(n)$ for infinitely many $n$" is "$\lnot P(n)$ for large enough $n$".


Pumping lemma occurrence of c > d I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it.

The alphabet is:

$$ \Sigma = \{c, d\} $$

The language is:

$$ A = \{z \in \Sigma^* \mid c(z) > d(z)\} , \text{where $c(w)$ and $d(w)$ means occurrences of $c$ or $d\in z$  }$$

I tried to define a string like so:

Pumping length = P

$$ s = c^{(P+1)}d^P $$

Here is how I tried to solve it:

If we select P = 5. Then s = ccccccddddd and split it in 3 parts. Where x = ccccccd, y = ddd and z = d. (Is that even allowed though as |xy| <= P, but now |xy|=10 and 10>5). If I then do y^2. Then I get s = ccccccdddddddd, so now d>c which proves the string is not in the language. Does this then prove that the language is not regular?

You need to show that with that arbitrary pumping length $P$, for any partition $c^{(P+1)}d^P = xyz$ such that $|y|>0$ and $|xy|\leq P$, there is some $i$ such that $xy^iz \not\in A$.

Since for any partition we require that $|xy|\leq P$, then $x$ and $y$ necessarily consist only of $c$'s. Also, you know that $|y| >0$ (it's also a requirement). Can you find an $i\in\mathbb{N}$ such that the amount of $c$'s in $xy^iz$ is less than or equal to the amount of $d$'s?


Construct a grammar over {$a,b$} whose language is {${a^mb^ia^n | i = m+n}$} I am a little confused on how to approach this problem. I am unsure how to construct both parts of the grammar using a context-free grammar.

This is as far as I got, but this will end up producing a's inside of the group of b's and a's. I'm not sure how to add the second group of a's to the right of the b's.

$S \rightarrow aSb \ | \ A$

$A \rightarrow bAa \ | \ λ$

This language should produce strings like

$abba, aabbba, aaaabbbbbbaa$

You must handle aXb and bYa sequences seperately.
$\\S \rightarrow \  XY\ |\ \epsilon \ \\ X\rightarrow \ aXb\ | \ \epsilon \\ Y\rightarrow  \ bYa\ | \ \epsilon$