Artificial Intelligence: Condition for BFS being optimal It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that:

  breadth-first search is optimal if the path cost is a nondecreasing function of the
  depth of the node. The most common such scenario is that all actions have the same cost.

From that I understand that if the path cost is non decreasing function of depth, the BFS algorithm returns an optimal solution, i.e., the only condition is the cost function being nondecreasing. But I think the only way for BFS to be optimal is the scenario in which all the path costs are identical, therefore a node found in a certain level is necessarily the optimal solution, as, if they exist, the others are. Therefore I think for BFS to be optimal, cost function should be non decreasing AND the costs of nodes should be identical. However, the book says only one of the conditions (former one) makes BFS optimal.

Is there a situation in which the costs are not identical, the cost function is nondecreasing and the solution returned by BFS is guaranteed to be optimal?

¡Nice question really!

The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because the most obvious one consists just of considering all grounded actions to have the same cost.

Thus, let me try to start with the first statement (that it just suffices for the path cost to be a nondecreasing function of the depth of the node) with a theoretical example. Let $c(n,n')$ denote the cost of traversing the edge from node $n$ to node $n'$ and let us define it as:

$$
c(n,n')=2^{g^*(s,n)}
$$

where $g^*(s,n)$ is the minimum number of actions required to reach node $n$ from the start node $s$. I am certainly defining the cost of the edge as a function of the depth of the source node but it seems to be that this is absolutely okay with the statement in the book. Think of this as an attractive force exercised from the start state $s$ so that the farer you get, the more costly it is to progress. This function is clearly non-decreasing as it progresses as follows: 1, 2, 4, 8, ..., the total cost paths progressing as: 1, 3, 7, 15, ...

Now, let me show that Breadth First Search would certainly find an optimal solution. I will make it by induction:

Base case: the queue is seeded with the start state $s$. In the first iteration of BFS it is extracted from the queue and its children are generated, all of them with cost $2^0=1$. These nodes have been certainly reached through an optimal path so this satisfies the base case.

Induction step: let us assume that all nodes of depth $(d-1)$ have been already generated through optimal paths with a path cost $\sum\limits_{i=0}^{d-2}2^i=2^{d-1}-1$. In the induction step all nodes generated at depth $(d-1)$ are expanded to generate nodes at depth $d$ from the start state $s$. Obviously, all these nodes are generated through optimal paths as well since their cost corresponds to paths of minimum length from the start state (in other words, would there be a shorter path in terms of length instead of cost, it would have been discovered in a previous layer of the search tree traversed by BFS with a lower cost).

It seems to me that you would agree with this but it might not satisfy you because all nodes in the same level would have exactly the same path cost (and nodes at depth $d$ would have a total cost equal to $\sum\limits_{i=0}^{d-1}=2^d-1$), but the previous proof was necessary in order to consider the following case now:

Let us re-define the cost function as:

$$
c(n,n')=\left\{\begin{array}{l}
2^{g^*(s,n)}, \mbox{in some cases, whichever}\\
2^{g^*(s,n)}+\delta, \mbox{otherwise}\end{array}\right.
$$

where $delta$ is just a small number, say $\frac{1}{2}$, such that it is smaller than the smallest of all costs $2^0=1$. Now you have a lot of different ways to get different path costs of nodes lying at the same level. In this particular case, the path cost of a node at depth $d$ ranges in the interval $[2^{d+1}-1, 2^{d+1}+\delta\times d-1]$.

However, the optimality condition of BFS still applies because the maximum difference ($\delta\times d$) is not enough to shift any node at depth $d$ after nodes that lie at depth $(d+1)$ in the queue the reason being that the path cost of those nodes ranges in the interval $[2^{d+2}-1, 2^{d+2}+\delta(d+1)-1]$. For a value of $\delta$ small enough nodes with different costs (even if they lie at the same depth) are found through optimal paths. However, note that I am assuming here $\delta$ to be small enough. If it is not, then BFS could be easily fooled and sub-optimal paths would be easily found by BFS.

Nice question, really! Hope this contributes somehow,


what is the relationship between entropy and variance? Consider a simple Bernoulli variable X
X = 1 with probability p
X = 0 with probability (1-p)

The variance is simply p(1-p). The entropy is -p*ln(p)-(1-p)*ln(1-p) Both are measures of uncertainty. What is the advantage of entropy then?
Thanks!

They measure different things.  Given the variance, you can solve for $p$ and compute the entropy, and vice versa, but they have different interpretations and different applications.  You can learn a bit about the meaning and applications of these notions in the corresponding Wikipedia articles: https://en.wikipedia.org/wiki/Entropy_(information_theory), https://en.wikipedia.org/wiki/Variance.
Analogy: if we have a sphere, I could measure its radius, or I could measure its volume.  They both reflect the size of the sphere, so you could as, what is the advantage of radius, or of volume?  Answer: they measure different things, so depending on what you want to do, one or the other might be more useful.


Big O vs Big $\Theta$ during coding interview Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$.
From the book "Cracking the coding interview":

  "In industry (and therefore in interviews), people seem to have merge Θ
   and
   together. Industry's meaning of big O is closer to what academics mean by
  Θ
  , in that would be seen as incorrect to describe printing an array as $O(n^2)$. Industry would just say this is O(N)"

In an interview context, would it be considered ok to say $\Theta$ instead of O?
If the interviewer is asking : "What's the Big O of this algorithm?", is it alright to answer :"The time complexity of this algorithm is $\Theta$(n)"?
I'm wondering if most interviewers would think I'm trying to outsmart them by saying that. But I don't feel comfortable by replacing O by $\Theta$ since they don't have the same meaning.

I think its fine. It just shows the interviewer you actually know what the real meaning of big-O and theta are. Just make sure its actually true (the $\Omega$ part) when you have a complicated algorithm and you have used some inequality for big-O complexity proof.


Modified topological sort I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways.
Let's define a "task" $T_k$ to be a tuple $(a_k, b_k, C)$, where $a_k$ is the amount of active time spent on a task, $b_k$ the inactive time, and $C$ a set of child tasks that cannot begin until this task is fully complete. For a given task, while I'm actively working on it I cannot do anything else. However, during the inactive period the task continues without my supervision and I can go do some other non-dependent task.
A good example is washing clothes: I might need $a_k = 5$ to load a washing machine, but then while the cycle runs ($b_k = 40$) I can go do something else with those 40 minutes. However, the tasks listed in $C$ cannot start until both the active and inactive parts have completed. So, using my existing example, I cannot run the dry cycle on my clothes until I've both loaded the washing machine and waited for the cycle to end.
So, given a set of tasks $T$ a question you could ask is: "What's the fastest I could complete a set of tasks?". In a way this is a topological sort, but there's also some weighting in there that I'm not sure how to navigate with existing topological sort algorithms. Perhaps there is a greedy way to pick the next node?
My question is this:

Is there an algorithm to solve this problem (that isn't brute-force enumeration of course)
Does this problem fall into an exist realm of research that I could investigate? Are there any introductory articles you could point me to?

Topological sorting would work if all $b_k$'s were zero.  Here is a way that takes into account the $b_k$'s.  Build a dag where each vertex is a task and there are edges from each task to its child tasks.  Then, use the following algorithm:

Out of all sinks (vertices with out-degree zero), find the one whose $b_k$ value is smallest.  Output it, then delete it and all edges into it.

Repeat, until all vertices have been output.

I believe this will output an optimal schedule, in reverse order (last task first).


Obtain all possible Turing Machines from a Universal Turing Machine Knowing how a Universal Turing Machines works and its capabilities, is it possible to obtain the collection M = {M0 , M1 , M2 , M3, … } of all possible Turing Machines?

If so, can we prove that a language L = {wj |wj not accepted by Mj } is not accepted by the Universal Turing Machine?

Enumerating all the possible TMs is a boring programming exercise. We do not need to use the UTM at all here -- we only have to generate the representation of all TMs and output it, using the chosen encoding of TMs as words.

The UTM does not accept your language $L$ since it accepts another language, namely $\{\langle M,w\rangle \ |\ \mbox{$M$ accepts $w$}\}$.


Randomly construct linear combination that is within bounds over two basis Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that:

$0 \le x_{j} \le 1$
$0 \le b_{j} \le 1$ where $\vec{b} = A\vec{x}$

Matrix $A$ is about 10 x 15. I want to generate $10^{5}$ $\vec{x}$ as an initial guess in each iteration of a solver.

Below is my attempts.

Least square and rejection

Generate $\vec{y}$ with entries between 0 and 1.
Generate $\vec{b}$ with entries between 0 and 1.
Minimize $(\vec{y} - \vec{x})^{2}$ subjected to constraint $A\vec{x} = \vec{b}$.
Reject $\vec{x}$ that are out of bounds.

Problem: the rejection rate is very high. Very impractical even for a 10 x 15 matrix $A$.

Step 2 is equivalent to solving

$\begin{bmatrix}
A & 0\\
I & A^{T}
\end{bmatrix}
\begin{bmatrix}
\vec{x}\\
\vec{\lambda}\\
\end{bmatrix}
=
\begin{bmatrix}
\vec{b}\\
\vec{y}\\
\end{bmatrix}
$

Constrained Optimization

Generate random $\vec{y}$ within bounds.
Objective: $(\vec{x} - \vec{y})^2$.
Constraint: $A\vec{x} = b$
Bounds: between 0 and 1.

Problem: Optimization is too slow and often gives result out of bounds. Impractical.

Other ideas

Null space
Simplex, random planes, and projection
Hit and run sampling

Using barycentric coordinate and keeping sum of coordinate equal to 1 do not sample a convex polytope uniformly.

import numpy as np
import matplotlib.pyplot as plt

N = 1000000  # Number of samples
V = 5 # Generate points within a V-gon

# generate columns that each sum to 1
s = np.exp(-np.random.uniform(0, 1, size=(V, N)))
s /= s.sum(axis=0)

# generate vertex of regular polygon
r = 2
theta = np.linspace(0, 2*np.pi, V+1)[1:]
v_x = r*np.cos(theta)
v_y = r*np.sin(theta)

# generate random points within the polygon
# by linear combination of coordinates of
# vetex where the coefficients sum to 1.
x = (v_x[:, np.newaxis] * s).sum(axis=0)
y = (v_y[:, np.newaxis] * s).sum(axis=0)

# plot density
heatmap, xedges, yedges = np.histogram2d(x, y, bins=50)
extent = [-r, r, -r, r]

plt.clf()
plt.imshow(heatmap.T, extent=extent, origin='lower')
plt.plot(v_x, v_y, color='r')
plt.show()


Running time of heap sort, when all number are identical Given n numbers that all are identical, then what would be the running time of heap sort?
Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?

It would be $O(n)$, because each call to a siftdown or siftup procedure would be executed in $O(1)$ if well implemented.
Indeed, in a maxheap, the siftdown procedure is called in the heapify procedure, or to extract a node from the tree, and is defined as follow:
siftdown(x):
   while x is not a leaf and x is strictly smaller than its two children:
      swap x and its largest child

Since you consider an array of $n$ equal values, the test x is strictly smaller than its two children will never be true, so the loop will never be executed and the complexity is $O(1)$.
Now, the heapsort procedure in an array of size $n$ is defined as follow:

heapify the array ($n$ siftdown from last to first element);
extract each value ($n$ siftdown).

The total complexity is indeed $O(n)$. Please note that one can prove that the heapify procedure can be executed in $O(n)$ in all cases (and not only with equal values).


Reservoir Sampling vs Round Robin You are given a List of numbers (length unknown).

Let's say the length is 10.

GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned.

GetRandom(List) is called 100 times. If implemented correctly, each number will appear 10 times in the result.

Fine?

You now have to do the same for a Stream of numbers.

GetRandom(Stream, 5) is called. This adds 5 to the Stream. Stream is of length N=1, then 5 is returned (probability = 1/N = 1)

GetRandom(Stream, 3) is called. 3 is added to stream. N=2. Either 3 or 5 is returned (prob = 1/2).

How will this be tested for correctness?
If GetRandom(Stream) (without adding any more numbers) is called 10 times when length of list is 2, each number (3 & 5) should be returned ~5 times.

GetRandom(Stream, 7) is called.  7 is added to Stream. N = 3. One of the 3 numbers (5, 3, 7) is returned (probability = 1/3).

But how will this be tested for correctness?
If GetRandom(Stream) is called 10 times when N = 3, each number is returned ~3 times.

So far, so good ?

Alright, here is my algorithm:

N = 0
Pointer = 0

GetRandom(Stream, Number = NULL):
    Pointer += 1

    if Number is NOT NULL:
        N += 1
    else:
        if Pointer == N:
            Pointer = 1    # Reset

    return Stream[Pointer]    # Assume 1-based indexes

This simply cycles through all numbers in order / round-robin fashion.

If GetRandom(Stream) is called on a Stream with 100 numbers, 1000 times, each number will appear exactly 10 times.

If GetRandom(Stream, 77) is called on a Stream with 100 numbers (77 is the 101st number), while Pointer got reset to initial location 1. Then when GetRandom(Stream) is called 101 times, then on the 101st call, 77 will be output, which satisfies the required probability of 1/101. If it's called 202 times, then on the 202th call, 77 will be output, which satisfies 2/202.

Why bother with Reservoir Sampling k/k+1, Why bother with a random number generator?

it seems that you're asking why bother with reservoir sampling when you're capable of tricking the test that you wrote?

Round robin doesn't return random numbers. It returns numbers deterministically. Well much more deterministic seeming than reservoir/other methods.

Your tests should be better. If you need the result to seem random and not deterministic, make a test which captures that instead of one which is based on empirical probability.

EDIT to add a test example:
another test for randomness (one that round robin would fail) is that you run the same process many times and don't get the same result every time. For uniform random sampling of a stream (the output of reservoir sampling) for a set/list/stream of a fixed size the probability to get one specific subset of size k should be 1/(n choose k) . You can run your method once then another 10000 (or any number of times) and see that you get the first result approximately only 1/(n choose k) times.


Can we have a poly time reduction from 2-SAT to 2-Coloring problem? I know that given a 2-Coloring instance we can easily convert it into a 2-Sat instance in polynomial time . Is the reverse possible? i.e given a 2-sat instance can we convert it into an 2-Coloring instance in poly time?

As rotia mentions in their comment, to make the question meaningful we must restrict the power of the allowable reductions. The two most obvious choices are to allow only logspace reductions or only AC0 reductions.

Since 2SAT is NL-complete (with respect to logspace reductions) whereas 2COL (2-colorability) is in L (this is a non-trivial result which follows from Reingold's theorem), if there is a logspace reduction from 2SAT to 2COL then L=NL, which is considered unlikely. Hence we do not expect such a reduction to exist; a fortiori we do not expect an AC0 reduction to exist.


What is minimization (μ-function) in layman tems? In Computer Science μ-function is used to extend set of primitively recursive functions to generally recursive functions, and I can't understand what this function does.
There is a lot of formulae, but I can't understand what is is. Let's say I'm writing in Python (or any other general purpose language). What are examples of μ-function IRL?

This is minimization in Python:
def mu(p):
    n = 0
    while not p(n):
        n += 1
    return n

It is a slightly more complicated exercise to convert a while to $\mu$, but essentially, $\mu$ performs a search for the first (minimal) number satisfying a given condition, where there is no guarantee that the search will succeed.


Can someone give me the definition of #Monotone-2SAT? In the decision problem, I set all variables to true and see if the formula is satisfiable.

My question is because I do not understand how there can be multiple solutions, though all variables are true.

Satisfiability problems are about making the formula true, not necessarily the variables. Counting satisfiability problems ask how many different assignments to the variables make the formula true.

In $\#\text{Monotone-2SAT}$, the formula is in 2-CNF (conjunctive normal form with at most two literals per clause) and is monotone (there are no negations). So, certainly, making all the variables true satisfies the formula, but there are plenty of other ways.  Just consider the formula $x\lor y$, which is monotone and in 2-CNF. It has three satisfying assignments.


Proving van Emde Boas recurrence I have tried to solve the following question:

  van Emde Boas Bounds Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. Hint: consider the binary representation of $u$.

In CLRS (Introduction to Algorithms), they make use of the master method case 2. They let $m = \log_2u$ so we have $T(2^m) = T(2^{m/2}) +O(1)$. Then they substitute $T(2^m) = S(m)$ and the recurrence looks as follows:

$$S(m) = S(m/2) + O(1).$$

The above confuses me, because I don't see how $S(m/2)$ is the same as $T(2^{m/2})$. Taking half of $m$ is not the same as taking half of the exponent $m$.

The idea is to define a new function $S(m)$ by $S(m) = T(2^m)$. Then by definition we have $S(m/2) = T(2^{m/2}) = T(\sqrt{2^m})$.


Double-nested loop with bitwise operation I have this little exercise:

for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      foo ();

(j <<= 1 means j = (j << 1), where << is the bitwise left shift operator. & is the bitwise and operator.)

I am supposed to determine how many times will the foo function be called for some n. The result should be both an exact number (or the most accurate approximation possible) and asymptotic (like O(n)).

The number of foo() calls is the number of 1 bits in all numbers from 0 to $n$ (or all even numbers between $0$ and $2n$ - same thing). Asymptotically, it's $O(n \log n)$, because the number of 1 bits is around $\log_2(n)/2$.

I don't have an exact function. It won't be a smooth function - for example, $f(1023)-f(1022)=10$, but $f(1024)-f(1023)=1.$


How to generate response variable during machine learning? I am analyzing data of insurance companies and for some reasons the data that was provided doesn't have any response variable of whether an insurance claim is legit or suspicious.

Are there any ways to generate the required response variable from the data that is available to us. I can think of clustering (hierarchical or K-means) as a means to identify clusters. But I am not sure if the clusters developed are true representation of my unreported response variable.

Also, Let me know of any other methods to generate response variable when there is none.

No.  You can't.  You need ground truth.  You're asking "if I don't know which claims are fraudulent, can an algorithm somehow determine that for me?"  The answer of course is no: the algorithm doesn't know anything more than you do about insurance fraud -- if anything, it knows even less.

This is one of the challenges with using machine learning.  You typically need a lot of labelled data: data that has been labelled with ground truth (e.g., whether the insurance claim is legit or fraudulent).  Supervised learning is data-driven: given some instances where we know the correct answer, it tries to figure out some rules to use to classify other instances where we don't know the answer.  For this to work, it needs a training set of instances where we do know the correct answer.

Now there are some techniques that can be helpful.  You might be able to use active learning to try to figure out claims to manually label, to try to reduce the number of examples you need to label.  You might be able to use clustering to cluster the instances, and then hand-label a few instances from each cluster.  But ultimately, you'll need some labelled instances to train on and evaluate the accuracy of your method.

See also How to identify labels in unsupervised learning? and Why is automatically labeling data in unsupervised learning hard? and
What exactly is the difference between supervised and unsupervised learning? and
What would be a decent threshold for classification problem?


Splicing squares on a Turing Machine finite tape Trying to explain a problem, I thought of a variant of Turing
Machines. It is unlikely to be new, but I do not recall ever seing it
before, and I wonder whether it has been used or has a name. The idea
is that the TM uses a "linked list" rather than a tape, so that the
head can splice a new symbol position between two existing ones (one
could also think of removing some, but I had no use for it :). Of
course, that requires having a new item in the description of a
transition to specify whether a new square should be spliced in, on the left or on the right of the head (both are needed).

The final point is that it does start with a finite tape. I did not
give all the details, but I do not think the rest matters much.

I have not done any proof, but I conjecture its computing power is
that of usual TM :) .

As I said I thought of it as a convenient way of explaining some other
problem. Then it hit me that, while TM are finitely defined, they are
stuck with their infinite tape from the very beginning. It never
bothered me very much, until some physicist started explaining that TM
are not realistic because of their infinite tape (which I only saw as
a convenient mathematical shorthand). I could fight that technically
in various ways. But this splicing idea should just do away with such
silly objections using no mathematics at all.

So my question is: where has this model, or some similar one, been considered before,  by whom and under what name?

Yes, it has the same computing power as an ordinary TM.

It's a standard exercise in computation theory/complexity theory textbooks that the ability to insert characters into the tape (and delete them from it) can be simulated by a standard Turing machine with a quadratic loss of efficiency. For example, this is Exercise 2.8.8 of Papadimitriou's book (Computational Complexity, Addison Wesley, 1994); he doesn't give a name to this extension of the standard Turing machine or attribute it to anyone which suggests to me that it's folklore – he's pretty good at citing and attributing.
Since you can insert characters at will, reaching the end of the initially finite tape makes no difference: you can just use insertion to extend the tape. A halting computation will only need to do this a finite number of times.
The infinite tape of an ordinary TM is just a definitional convenience: it suffices to have a finite tape that gets extended any time the head reaches the end.


Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0 Suppose you have a system that consists of $m$ slow machines and $k$ fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now you are given a set of n jobs; job $i$ takes time $t_i$ to process on a slow machine and time $\frac{1}{2} t_i$ to process on a fast machine. The goal is to minimize the makespan — the maximum, over all machines, of the total processing time of jobs assigned to that machine.

Algorithm: When each job arrives, we put it on the machine that currently ends the soonest(machine with smallest current load before the job is assigned). (Note that this determination involves taking into account the speeds of the machines.) This is a 3-approximation algorithm.

I want to find an example for which the algorithm is not a $(3 - x)$-approximation algorithm for any $x > 0$.

Condering that the makespan of the resulting algorithm is $T$, to do that I thought that, since the algorithm is a $(3-x)$-approximation if $T \leq (3-x)OPT$, I would just have to find an example for which $T > (3-x)OPT$. But I cannot seem to be able to find one, all the examples I find yield $T \leq (3-x)OPT$.

I just found a very basic example, where I have 4 jobs and 2 machines, one fast and one slow. The jobs: 4, 4, 1, 2

The algorithm would  first assign job 1 to the fast machine, then job 2 to the second machine, then jobs 3 and 4 to the fast machine. This yields a makespan $T$ of $4$.

The optimal makespan $OPT$ would be assigning jobs 1, 2 and 3 to the fast machine and job 4 to the slow machine, so $OPT = \frac{9}{4}$.

But then $4 < 9 (4\frac{9}{4})$

What am I doing wrong?

Suppose that you have one fast machine and one small machine, and consider jobs of the following durations: $t_1=t_2=\epsilon$, $t_3=1$, $t_4=2$.

The greedy algorithm first puts a job taking time $\epsilon$ on each machine (immaterial of tie-breaking rules). It then puts the third job on the fast machine (since it ends in $\epsilon/2$ rather than $\epsilon$), and then the fourth job on the slow machine. The makespan is $2+\epsilon$.

In contrast, if we put jobs 1,2,4 on the fast machine and job 3 on the slow machine, then the makespan is $1+\epsilon$.

This shows that your algorithm is not a $(2-\delta)$-approximation for any $\delta > 0$.

Indeed, suppose, for the sake of contradiction, that the algorithm was a $(2-\delta)$-approximation for some $\delta > 0$. Find $\epsilon > 0$ small enough so that $(1+\epsilon)(2-\delta) < 2+\epsilon$ (exercise: show that this is always possible), and consider the corresponding example.

Since the optimal makespan is at most $1+\epsilon$ and the algorithm is a $(2-\delta)$-approximation, it must produce a solution whose makespan is at most $(1+\epsilon)(2-\delta)$. However, the algorithm produces a solution with makespan $2+\epsilon > (1+\epsilon)(2-\delta)$, and we reach a contradiction.

You might be able to give an even worse example. This is just to demonstrate the proof technique.

I suggest looking at the proof that the algorithm is a $k$-approximation algorithm, and try to find an example for which the analysis is tight. This will show that the algorithm is not a $(k-\delta)$-approximation for any $\delta > 0$.


Is bounded waiting ensured in given version of Dekker's solution for critical section problem? William Stallings discuss various step by step process in developing Dekker's algorithm in his Operating Systems book. In process, he reaches to following version of algorithm (which is incomplete as it results in livelock):

1
2    /*    PROCESS 0    */
3    .
4    .
5    flag[0] = true;
6    while (flag[1])
7    {
8       flag[0] = false;
9       /* delay */ ;
10       flag[0] = true;
11    }
12    /* critical section*/;
13    flag[0] = false;.
14
15    .
16
17    /*    PROCESS 1   */
18    .
19    .
20    flag[1] = true;
21    while (flag[0])
22    {
23       flag[1] = false;
24       /* do */ ;
25       flag[1] = true;
26    }
27    /* critical section*/;
28    flag[1] = false;.
29
30    .
31
32

I want to know whether above algorithm satisfies the "bounded waiting" requirement of critical section solution.

My current opinion is that, if process 0 fails on lines 6,7,8,11,12,13,14,15, that is all lines where flag[0] is already set to true, then process 1 will be blocked and hence will result in unbounded waiting. Am I correct?

Also is there easy way to find whether given/proposed algorithm for critical section problem solution satisfies "bounded waiting" requirement?

A reasonable definition of bounded waiting is:

  After a process made a request to enter its critical section and before it is granted the permission to enter, there exists a bound on the number of turns that other processes are allowed to enter.  [1]

In your case each process makes its request to enter by setting its flag (line 5 for Process 0, line 20 for Process 1.  The granting of permission is the test of the other process' flag (flag[1] false on line 6 grants permission to Process 0, flag[0] false on line 21 grants permission to Process 1).

So the only way to test the bounded waiting requirement here is to consider the case that Process 0 has just tested flag[1] on line 6, and found it true, and ask, "how many times can Process 1 leave and reenter the critical section while Process 0 is stuck in the loop?"  (Hint: consider the case where Process 0 has really bad luck, and Process 1 is able to leave and reenter the critical section during Process 0's delay on line 9).

[1] source: http://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf


Algorithms that achieve better compression for more data I'm interested in compression algorithms where the compression ratio increases as the amount of data to be compressed increases. Let's call this "super compression".  Could super compression be achieved through recursive compression algorithms?

Here's the kind of algorithm I'm contemplating.  The binary file is first scanned, to identify patterns. After this, the file is rewritten such that the patterns are encoded, e.g., if there is a sequence of 100 $0$'s, it could be represented as $xxx 0$ where $xxx$ represents that the $0$ occurs 100 times.

After this is done, the algorithm is then called on the generated compression file, until a file with no patterns is produced. The header of the file will contain how many times the algorithm was run, so the file can be decompressed.  Will this work to achieve super compression?

Compressing compressed data only benefits you if the original compression wasn't very good. Good compression essentially removes all the patterns, leaving very little for any future round of compression to exploit.

There is a fundamental limit as to how well any particular lossless compression scheme can compress. In particular, if a compression scheme could make every file smaller, you could indeed run it repeatedly and you could keep going until the file you started with had become one bit long. Since there are only two compressed files and the decompression program is deterministic, the decompression program can only have two possible outputs, but it's supposed to be able to produce whatever file was actually compressed.

In fact, you can't even compress all files once. There are $2^n$ $n$-bit files, but only $\sum_{i=0}^{n-1}=2^n-1$ files of length strictly less than $n$.  So, if you had an algorithm that could make every file of length $n$ strictly smaller, there would have to be two different files that compress to the same thing, by the pigeonhole principle. But now the decompresser doesn't know how to decompress that file.

And it gets worse. Any fixed lossless compression scheme can't compress half of the possible files by even one bit. When we talked about compressing $n$-bit files in the previous paragraph, we didn't mention that there are also files of length less than $n$, which need to be compressed, too. There are $2^{n+1}-1$ possible files whose length is in the range $0$–$n$ bits. If we could compress all of those by even one bit, we'd have to be able to write $2^{n+1}-1$ different files of length at most $n-1$ bits, but there are only half that number of $(n-1)$-bit files, so it simply cannot be done.

Note that you can't get around this by saying "If algorithm A compresses the file, I'll use that and, otherwise, I'll use algorithm B." Even if it were guaranteed that every file could be compressed by one of those two algorithms, you'd have to write a header to the file to say which one was used. So, now you need to compress by at least two bits so that the compressed file plus the header is shorter than the original file. But no single algorithm can compress more than a quarter of files by two bits, so your combination of A and B still can't compressed half your files.

You can't get around it by using multiple files because the total length of those files will still obey the same rules that we already discussed. Since, in reality, files on disks are stored in blocks so storing $k$ files means you need to allocate at least $k$ blocks, which isn't efficient when the files are small. Multiple files does allow you to cheat slightly, since it means you don't need any delimiter between your metadata in one file and the data in the second. However, that data still has to be stored in the directory entry so you're not really saving any space.

Note that everything above applies to all possible compression algorithms. It doesn't use any properties of whatever algorithm you could think of: the argument is just about the number of files of different lengths.  The scheme you're thinking of – looking for patterns and representing them using some language – is no different. It cannot win because nothing can win. Taken to the ultimate degree, you're moving towards Kolmogorov complexity, which essentially compresses a file into the shortest program that will output that file when it's run. Still, this doesn't let you get around the fundamental bounds. Indeed, it's the tool that's used to prove a lot of the more interesting fundamental bounds. And it turns out that, for most files, the shortest program is print "[literal string containing the file contents]";, which is, essentially, one bit longer than the file you started with.


Progressive discrete multifunction optimization I have a set of functions $F$.

The functions effectively take a set $S$ that is always a subset of a global set of all possible values $G$, where $|G|>1000$. (alternatively, they could take a $|G|$tuple of booleans, if that's easier). The functions return a real result. I want to minimize over $S$ the average value of these functions if all of them are given the same parameter $S$.

$$\min_{S\,\subset\, G}\left(\sum_{f\,\in\,F}f(S)\right)$$

Now here's the catch:

The functions take a fantastic amount of time to run (say, a few hours), and I intend to have a huge collection of such functions (say $|F|>1000$ to start). Every so often, a new function will be created and be added to the set. There is no bound to the size of $F$.

Obviously, I can't just use closed form optimization (I'll be dead before it'll finish), so I'm interested in an algorithm that can find an approximate solution and progressively refine it over time as new function results and new functions come in (and hopefully converge faster than brute force).

We can have a better-than-brute-force because the functions $F$ behave similarly. Namely, $f(S) \approx f(T)$ when $S\approx T$ and $k_aF_a(S) \approx k_bF_b(S)$ for all $S$ ($k$ is constant). There are, of course, many exceptions.

Now, I am new in the CS field so I have no idea what things are called. AFAIK I haven't learned how to do this in Into to ML, but it has the feel of a Genetic Algorithm problem. If anyone could point me to a technique or a name, I'd be very happy.

There are two techniques that I suspect might be worth trying in this context:

Simulated annealing. Simulated annealing is a heuristic for optimization that works well when the objective function varies smoothly as a function of its parameters, based loosely upon some structure in the parameter space.  You can find a good discussion of how to use simulated annealing, in Steven Skiena's The Algorithm Design Manual.

In your context, you'll need some operations that tweak $S$ by a little bit.  Basically, you start from a specific choice of $S$ and then make small modifications, seeing which modifications increase the value of $\Phi(S)$, where $\Phi$ is the objective function.  When you find a $S'$ that increases the objective function, you keep that one and start modifying it.  This is basically hillclimbing.  Simulated annealing improves on that by doing random jumps to get out of local optima.

In your context, the objective function is

$$\Phi(S) = \sum_{f \in F} f(S).$$

There are many candidates for how to tweak $S$.  You could try adding a random element of $G$ to $S$ (or adding $k$ randomly chosen elements of $G$ to $S$) as one operation; removing a random element (or removing $k$ elements) as another operation; and so on.  Typically you take advantage of your domain knowledge to select a set of operations that might potentially make sense as "sensible" ways to vary $S$ by a little bit.  Then, you let the simulated annealing algorithm take over from there.

The useful thing about your context is that when you've found an optimal value of $S$ for functions $f_1,\dots,f_n$ (i.e., for objective function $\Psi(S) = f_1(S) + \dots + f_n(S)$), and then you later get an additional function $f_{n+1}$ to add to the set, now $S$ is a reasonable starting point to start the optimization process for $f_1,\dots,f_{n+1}$ (i.e., for objective function $\Psi'(S) = f_1(S) + \dots + f_{n+1}(S)$).  In particular, given your structure, we might expect that the optimum for $\Psi'$ might be "close" or "similar" to an optimum for $\Psi$, so the optimum for $\Psi$ is a good place to start the hill-climbing/simulated annealing for $\Psi'$.

To extend on that idea, you might also try remembering multiple values of $S$ from the previous round: say, sets $S_1,\dots,S_m$ that give the $m$ largest values of $\Phi(\cdot)$ that you encountered during your optimization with the objective function $\Psi$.  Now, when you add another function in the next round
and want to find an optimum for $\Psi'$, you could try starting from each of $S_1,\dots,S_m$ as candidate starting values for the hill-climbing / simulated annealing.  This might be effective in practice -- you'd have to try it out to see.
Memoization. Since computing $f(S)$ is very expensive, you might use memoization to ensure you never compute it more than once.  In particular, you might keep a hashtable with mappings $(f,S) \mapsto f(S)$, so that you never need to compute $f(S)$ for any particular combination of a function $f$ and a set $S$ more than once.  This might help you out.

Also, when starting the optimization process for the objective function $\Psi'$, you might try computing $\Psi'(S)$ for each $S$ such that you computed $\Psi(S)$ in the previous round. Since $\Psi'(S) = \Psi(S) + f_{n+1}(S)$, the memoization will ensure that (if you computed $\Psi(S)$ previously) $\Psi'(S)$ can be computed relatively efficiently: it only requires evaluating $f_{n+1}(S)$, since $f_1(S),\dots,f_n(S)$ will already be in the memoization table.

Finally, if you know anything more about the structure of the $f$'s, you might try looking into branch-and-bound style techniques.

Again, these are just ideas.  You are in the space of heuristics, so there are no guarantees.  You'll have to try out these techniques in your particular application domain to see how well they work.  In practice often you may need to try out different parameter settings and make some application-specific tweaks to these general techniques, so be prepared to experiment and try out different stuff.


What if P implies Q is false when both P and Q are false? This is actually a problem that our professor gave us, and I'm clueless of how to answer this. I browsed through various sources, but none were helpful regarding this question.

The question is,

  In the definition of semantics of logic, P implies Q is defined as
  true under the assignment of both P and Q are false. Although this is
  rather unusual at a glance, explain what would be the issue with
  logic, if the definition is differently.

Any helpful answer is highly appreciated.

This question is a soft question IMO, it assumes there's common ground about what "should be true" independent of definitions but it doesn't clarify what those assumptions are. If I were to break it down, I'd say it's looking for a particular bit of reasoning (e.g. a proof or an inference rule) to hold and then asking you to show that that reasoning would be invalid if we defined the semantics of implication differently. In essence it's asking if there exists a proof that, under this new model, would be invalid.

Consider $\neg (Q \vee \neg Q) \to \neg (Q \vee \neg Q)$ which is provable, and should be valid in all models (no matter what we assign to $Q$ that is). As a general rule of reasoning it should always hold that $P \to P$ no matter what. I posit this is sufficiently fundamental common ground of "what should be true". So if we find this reasoning invalid, we have our soft contradiction. We can construct instances of $P$ for which $P$ is certainly false as shown above. So despite the very reasonable proof of $\neg (Q \vee \neg Q) \to \neg (Q \vee \neg Q)$ that would actually be false under the model...in fact it's negation would be valid in the model!


Question in coreset construction fro K-median clustering I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that $A$ is an $[α, β]$-bicriteria approximation for K-median clustering for some $α, β=O(1)$. I am wondering if the construction still work if $A$ is an arbitrary set of $αk$ centers?
Can anyone help prove the correctness of my suggestion?

Of course not. Otherwise the construction would be "pick an arbitrary set of centers".
You can follows the proof and see that the size of the coreset depends polynomially on $\beta$ and $\alpha$.
If they are $O(1)$ they can be hidden in the $O()$ notation. Otherwise, someone needs to  pay.  See more details in Section 6 here:
https://arxiv.org/abs/2011.09384


Context-free grammar for tautologies in one variable Construct a context-free grammar for the set of tautologies in $p$ - that is, the set of formulae in $\{p, \text{true}, \text{false}, \land, \lor, \lnot, (, )\}$ which evaluate to $\text{true}$ for any assignment to $p$.

My first step is to construct a CFG for all propositional formulae:
$$ S \rightarrow S \land S \mid S \lor S \mid ( S ) \mid \lnot S\mid p \mid \text{true } \mid \text{ false} $$

What can I do from here?

Every formula in $p$ is equivalent to one of four formulas: true, false, $p$, $\lnot p$. This suggests having four different nonterminals, which generate exactly formulas which have this truth values. Calling these $T,F,P,N$, we have, for example,
$$
T \to T \land T \mid T \lor S \mid S \lor T \mid P \lor N \mid N \lor P \mid (T) \mid \lnot F \mid \mathrm{true},
$$
where $S \to T \mid F \mid P \mid N$; this additional nonterminal is only used as shorthand.

In the same way, you can write rules that generate all tautologies over any fixed number of variables.


Hash table collision probability For an open-addressing hash table, what is the average time complexity to find an item with a given key:

if the hash table uses linear probing for collision resolution?
if the hash table uses double probing for collision resolution?

From my understanding my answer to the first question would be $O(n)$
but I'm not sure about the double probing question.

What are the odds of a collision given a fixed hash table size?

Size of hashtable
When hashing $k$ items into a hash table with $n$ slots, the expected number of collisions is

$n - k + k(1-{\frac{1}{k}})^n$

The main statistic for a hash table is the load factor: $\alpha = \frac{n}{k}$
For a perfect hash the load factor also happens to be the probability that a collision will occur.

Open addressing
Back to the question:

  average time complexity to find an item with a given key if the hash table uses linear probing for collision resolution?

The length of probe sequence is proportional to $\frac{\alpha}{(1 - \alpha)}$. As the load factor $\alpha$ approaches 1, probe times goes to infinite.

The following graph shows the benefits and drawbacks of open addressing quite clearly.

Because of locality of reference open addressing is fast up to 70% load factor, after that running time deteriorates quickly.
Note that the graph only shows cache locality issues. Its for this reason that the chaining times do not go up much. In reality the chaining time goes up exponentially as well when the hash table fills up, albeit slower than the linear probing time.

Let $\alpha$ be the load factor

Double hashing has a time complexity of $O(2 * \frac{1}{2}(\dfrac{\alpha}{(1-\alpha)}))$

Linear probing has a time complexity of $O(1 * (\dfrac{\alpha}{(1-\alpha)}))$

So the time complexities are the same, but the constants are different.
Double hashing takes more time, but linear probing goes into pathological running time sooner as the fill factor goes up.


Kleene positive closure - help in proofing this claim I just started a course called 'Automata and Formal Languages'.
I'm having difficulty in proofing\disproofing this equality.

$ (L_{1} \circ L_{2})^{+} = L_{1}^{+} \circ L_{2}^{+}
 $

Where:

$ L_{1} $, $L_{2}$ are Languages.

$\circ$ is the concatenation operation between two languages.

$+$ is the Kleene plus closure defined by $\bigcup  _{i = 1}^{\infty }L^{i} $

I tried finding a counter example and also tried to formally proof but had no luck.
Can someone please point me in the correct direction?

Let's use $A$ for $L_1$ and $B$ for $L_2$.
If you unpack both sides, you get
$$
(AB)^+ = AB + ABAB + ABABAB + \cdots \\
A^+B^+ = AB + AAB + ABB + AABB + \cdots
$$
Perhaps this can give you some ideas.


Algorithm for splitting array into subarrays with sums close to the target value I have an array of positive integers, $A = (a_1, a_2, ..., a_n)$.
Let $s(A)$ denote the sum of elements of array $A$.
I also have an integer $t$, such that $1 < t \le s(A)$.

I want to split the array $A$ into $m$ contiguous subarrays $(A_1, ..., A_m)$, for which I'll get a minimum of function $f$, defined as

$$
f(A_1, ..., A_m) = \sum_{1 \le i \le m}{(s(A_i) - t)^2}.
$$

Please note that I'm talking specifically about arrays, so the order of elements does matter.

Here is a simple example.

Let $t = 13$ and
$$
A = (1, 6, 7, 10, 3, 2, 10).
$$
With the following subarrays
$$
A_1 = (1, 6, 7)\\
A_2 = (10, 3) \\
A_3 = (2, 10) \\
$$
the value of $f(A_1, A_2, A_3) = (14-13)^2 + (13 - 13)^2 + (12 - 13)^2 = 2$.

I don't need an exact solution. Good heuristic would be sufficient.

You can solve it exactly using dynamic programming, though that might be too slow or might require too much memory. Calculate an array $B(\ell,k)$, which is the minimal error obtained by dividing $a_1,\ldots,a_k$ into $\ell$ parts. This can be implemented in time and space $O(mn)$ by calculating (in advance) the running sums $\sum_{i \leq t} a_i$.


How come correctness proofs aren't tautological? Consider the following function on binary trees, which is supposed to tell whether a given int is a member of a binary tree t:

type tree = Leaf | Node of int * tree * tree;;

let rec tmember (t:tree) (x:int) : bool =
  match t with
      Leaf -> false
    | Node (j,left,right) -> j = x || tmember left x || tmember right x
;;

If one wants to prove that this function is correct, one would need to define first what tree membership actually means, but then I can find no formal way of doing this except for saying that x is a member of t if and only if it is either equal to the root of t, or it is a member of the left or right subtree of t. This is essentially saying that x is a member of t if and only if  tmember t x outputs true.

What am I missing here?

Membership is much more general than this recursive definition you give. At a higher level you could define membership as follows:

A tree can be defined as a collection of nodes, $V$, and edges $E$ where those edges and nodes satisfy particular constraints.
We say a value $x$ is a member of the tree if and only if there is a node $v$ in $V$ such that the value of $v$ is equivalent to $x$.

You then prove (probably with induction since it's recursive) that your function is equivalent to this definition. That is to say, your function returns true on value $x$ if and only if there is a node $v$ in $V$ such that the value of $v$ is equivalent to $x$.


Why/how does the definition of PCP use randomness? I am confused by the definition of probabilistic checkable proofs.

Language $L$ has an $(r(n),q(n))$ - PCP verifier, if there is a PPA V satisfying:

Efficiency: $V$ uses at most $r(n)$ random coins and makes at most $q(n)$ nonadaptive queries to location of $\pi$.

Completeness: $x \in L, \exists \pi \in \{0,1\}^*, Pr[V^{\pi}(x)=1]=1$

Soundness: $x \notin L, \forall \pi \in \{0,1\}^*, Pr[V^{\pi}(x)=1]\leq\frac{1}{2}$

The main question:

Why does PCP need randomness?
How exactly are random coins  used in the PCP?
And what happens when these random coins are actually deterministic?
Where does the effective proof length bound of $2^{r(n)}q(n)$ come from?

The way a PCP works is like so: in order to verify some property, the prover presents a proof P which is "easily testable". The way to test it is to query the proof at a small number $q(n)$ of points. We want the PCP to satisfy two properties:

If the property actually holds, the verifier should always (or almost always) accept.
If the property doesn't hold, then the verifier would notice with some constant probability.

Now if the proof is long and the verifier only looks at a small number $q(n)$ of them, then they better be random! Otherwise it's very easy to fool the verifier. That should answer your first and third questions.

How are the random coins used? In an arbitrary way. The verifier chooses $r(n)$ random coins, and based on them queries the proof at $q(n)$ points. Then she applies a test which always succeeds in YES instances (the property holds), but fails with constant probability (over the coin tosses) in NO instances (the property doesn't hold). That should answer the second question.

Since there are $r(n)$ coins, there are $2^{r(n)}$ different outcomes for the coins, and so the verifier in total queries the proof in at most $2^{r(n)}q(n)$ different places. That answers your fourth question.

What's the point of a PCP? We can encode the verifier as a CNF whose variables are the bits of the proof: for each of the $2^{r(n)}$ coin tosses, there are clauses encoding that the $q(n)$ bits sampled pass the verifier's test. If it's a YES instance, then this CNF is satisfiable. If it's a NO instance, then the verifier fails with some constant probability, and so a constant fraction of the clauses in the CNF are always unsatisfied.

The PCP theorem gives a PCP for 3SAT with $q(n) = O(\log n)$ and $r(n) = O(1)$. That means that given a 3CNF, we can come construct a new CNF of length $O(2^{q(n)}) = n^{O(1)}$ using the construction outlined in the preceding paragraph such that (i) if the original 3CNF formula is satisfiable, so is the new one, (ii) otherwise, at most $1-\epsilon$ fraction of the clauses can ever be satisfied in the new CNF. That gives a hardness of approximation result for 3SAT.

Using Raz's parallel repetition theorem, Håstad obtained a construct in which in case (ii), at most $7/8+\epsilon$ of the clauses can be satisfied, thus obtaining an optimal inapproximability result. (It's optimal since a random assignment satisfies $7/8$ of the clauses; this algorithm can be derandomized using the method of conditional expectations.)


Computational complexity of coefficients I have some recurrence relationships I use to compute some coefficients of a series. I want to know what the time complexity of computing these is. Suppose I know the coefficients $a_0,...,a_n$, and I want to compute $c_0,...,c_n$ as follows

$ c_{n}=\begin{cases}
e^{b_{0}}, & n=0\\
\frac{1}{n}\sum_{k=1}^{n}kb_{k}c_{n-k}, & n\geq1
\end{cases}$

where

$b_{n}=\begin{cases}
\frac{1}{a_{0}}, & n=0\\
-\frac{1}{a_{0}}\sum_{i=1}^{n}a_{i}b_{n-i}, & n\geq1
\end{cases}$

So far this is what I have. If we know $b_0,...,b_{k-1}$ then $b_k$ can be computed in $O(k)$ time, so to compute $b_0,...,b_{n}$ takes $\sum_{k=0}^{n}O(k)=O(n^2)$ time.

Now suppose that we know $b_0,...,b_{k}$ and $c_0,...,c_{k-1}$ then it takes  $O(k)$ time to compute $c_k$. Thus to compute $c_0,...,c_{n}$ it takes $\sum_{k=0}^{n}O(k)=O(n^2)$. Ofcourse we have to take into account the time it takes to compute  $b_0,...,b_{n}$ which is $O(n^2)$.

So can I conclude that the time it takes to compute $c_0,...,c_{n}$ is

$O(n^2)+O(n^2)=O(n^2)$??

You also need to take into account the size of the coefficients. Adding integer coefficients of bit-length $\ell$ takes time $O(\ell)$, and multiplying them takes time $\tilde{O}(\ell)$, i.e. $O(\ell (\log \ell)^k)$ for some $k$ (any $k > 1$ will do). Your case is slightly more complicated, since the answer is rational and uses the "indefinite" value $e^{1/a_0}$, so in general it is going to be a polynomial in $e^{1/a_0}$ with rational coefficients. This further increases the running time.


Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is? Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

My attempt:

Lets $f(n)=g(n)=n$, then $f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$

But given answer is $O(n)$. Now sure where I have have committed mistake or if I am missing something. How it can be $O(n)$?

You have a fault in $f(n).g(n) = \Omega(n^2)$. Because, $g(n) = O(n)$ and you can't say $g(n)$ is $n$ or $\frac{1}{n^2}$ for example. Hence, we can't say nothing about $f(n).g(n)$. For more example:
$$g(n) = \frac{1}{n}, f(n) = n \Rightarrow f(n).g(n) = \Theta(1)$$
$$g(n) = 1, f(n) = n \Rightarrow f(n).g(n) = \Theta(n)$$
$$g(n) = \frac{1}{n^2}, f(n) = n \Rightarrow f(n).g(n) = o(1) (\text{little-o})$$
$$g(n) = n, f(n) = n \Rightarrow f(n).g(n) = \Theta(n^2)$$

As we don't know about $f(n).g(n)$. However, we can say $f(n).g(n) + h(n) = \Omega(n)$ as $h(n) = \Theta(n)$ and $f(n).g(n) \geq 0$.


NP-Completeness reduction, using a same input We have problem X and Y that we know is NP-Complete. Problem X uses graph G as an input and Problem Y uses graph G and constant k as an input.

Problem we are trying to reduce to, which I will call Z, is reasoning whether given a graph G and constant k, does G have X or Y.

I have been trying to solve this problem and an idea I came up with is to use an input G and k which can serve as an input for both X and Y, and reduce it to G' and k' where G=G' and k=k' for problem Z

Is it a valid thing to reduce without changing an input?

You can do whatever you want as long as you satisfy the definitions.

For example, a polynomial time reduction from a language $A$ to a language $B$ is a function $f$ satisfying the following two properties:

$f$ can be computed in polynomial time.
For every $x$, we have $x \in A$ iff $f(x) \in B$.

Any function $f$ satisfying these conditions is a polynomial time reduction from $A$ to $B$.

In particular, if $A$ is NP-hard and there exists a function $f$ satisfying these two conditions, then $B$ is also NP-hard.

The definition doesn't specify anything beyond these two properties. In mathematics nothing is left unsaid; everything which is not forbidden is actually allowed. All the cards are open. The rules of the game are public, and there is no need to ask a judge about any of them.


Creating regular expression with sub sequences of strings I am creating a program which searches for particular  types of strings. The alphabet of these strings are in $\{a, b, c\}$, for which every sub string of length 3 contains exactly $c$. Some strings that follow these constraints are:

$cabcbbca$, $cbb$ and $acaacb$

And strings that don't follow the constraints are:

$aaac$, $ccc$ and $cbcaac$

From this, I can see that a regular expression might need to be made to search for strings that follow the constraints.

I have tried hard coding some regular expressions such as:

$((a \cup b)(a \cup b)c)^*$, which would cover strings like $abcabcabc$, but will obviously not work for all strings, as their are many combinations the strings could be in.

I'm not sure how I could create a general regular expression that could strictly follow any sub string of length 3 to contain exactly one $c$. Any help would be appreciated.

The following regular language should match your specification. I've used a slightly different notation than yours, denoting $(a \cup b)$ as $\{a,b\}$.

$\mathcal{L} = c \cup c \{a,b\} \cup c \{a,b\} \{a,b\} \cup \{a,b\} \cup \{a,b\}\{a,b\} \cup \left( ((\{a,b\}c) \cup c)? (\{a,b\}\{a,b\}c)*\right)$

$?$ denotes repetition  zero or one time, and $*$ repetition zero or more times.

It can be written in a more compact representation as:
$\mathcal{L} = c\{a,b\}\{a,b\} \cup \{a,b\}?c?\{a,b\}? \cup (\{a,b\}?\{a,b\}?c)?(\{a,b\}\{a,b\}c)* $


Combining merge sort with insertion sort - Time complexity I am learning algorithms from the CLRS book on my own, without any help. It has an exercise which combines merge sort {O(n log n)} with insertion sort {O($ n^{2} $)}. It says that when the sub-arrays in the merge-sorting reach a certain size "k", then it is better to use insertion sort for those sub-arrays instead of merge sort. The reason given is that the constant factors in insertion sort make it fast for small n. Can someone please explain this ?

It asks us to show that (n/k) sublists, each of length k, can be sorted by insertion sort in O(nk) worst-case time. I found from somewhere that the solution for this is O($ nk^{2}/n $) = O(nk). How do we get this part O($ nk^{2}/n $) ?

Thanks !

For your first question:
O(n logn) might be 4nlogn or 13nlogn or 0.1nlogn etc.

If you compare 4n^2 and 100nlogn you will see that for n < about 200 the O(n^2) is faster. Big O is an asymptotic measure. It says what happens when n approaches infinity, but does not say anything about “smaller” inputs.

For your second question:
You have n/k sublists. Each sublist has length k and needs k^2 to be sorted with insertion sort. So multiply and you get n/k * k^2 = nk worst case. This is a way of parametrizing your algorithm’s complexity. If you choose k to be a constant c ex. k = 3 then you have n/3 sublists of length 3. Each one needs 3^2 = 9 execution steps and the overall amount of work is n/3 * 9 = 3n. You can also choose k to be a function of n, ex. k = f(n) = n/5. Then you have n/(n/5) = 5 sublists of length n/5. Each sublist needs (n/5)^2 = n^2/25 execution steps and the overall amount of work is 5 * n^2 /25 = n^2 / 5. Again, don’t assume that the one is faster than the other. n^2 / 5 and 3n describe “the same thing” written differently.

Finally, keep in mind that big O describes neither time nor space. It describes amount of work it needs to be done. If you take account the parallelization then for example assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.

Some algorithms can be parallelized and some others can’t. Insertion sort for example is CPU favorable when the input size is comparable to the “block size” of the CPU. Divide and conquer algorithms are not fast for small inputs because the cpu must populate the code recursively. This means lot of memory to be allocated, lot of stacks, etc

The approach you are describing is a hybrid algorithm.


dynamic programming: longest palindromic subsequence, recurrence relation question Moving from top left down the column then over to the right column, taking ideas from here: https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/
I want to restate the question at the top of the Excel table.
Why do I need to max from T(i,j-1) and T(i+1,j)?  Can't you just take what's in T(i,j-1)?
I changed the input slightly and I still get the right answer just taking T(i,j-1) when T(i,0) != T(0,j)
Edited:

A counterexample would be nice to see.

Let T(i,j) = T(i,j-1) when L(i) != L(j)
You could be wrong if you take T[0, n-1] as the final answer as in the article on GeeksforGeeks. For example, let X = "abb". Then T[0, n-1] = 1 while the longest palindromic subsequence is bb with length 2.
You are right if you take the maximum of T[i,n-1] as the final answer, where i goes through all valid indices, i.e., from 0 to n-1 and n is the length of the given string X.
What is happening?
We need to understand/specify the meaning of T(i,j). We can let T(i,j) denote the length of the longest one among all subsequences that start at index i and end no later than index j, where i <= j. Then it is correct that T(i,j) = T(i,j-1) when X(i) != X(j), since any palindromic subsequence that start at index i cannot end at index j, i.e., it must end no later than index j-1.
Exercise

Describe the meaning of L(i,j) in that GeeksforGeeks article.

Suppose we let T(i,j) denote the length of the longest one among all subsequences that start at index i and end at index j, where i <= j.

What will be the recurrence relations?
Suppose we have computed all T(i,j). What would be the final answer, i.e., the length of the longest palindromic subsequence overall?


Converting connected graph to disconnected graph by removing minimum vertices How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?

The minimum number of vertices that have to be removed in order to disconnect the graph is known at the connectivity of the graph. Wikipedia outlines an algorithm for finding the connectivity of a graph. More efficient algorithms might exist.

A related problem is the vertex separator problem, in which we want to disconnect two specific vertices by removing the minimal number of vertices.


Do one way function exist? I was recently going through the Wiki page List of unsolved Problems in Computer Science.

There was a problem which I do not understand

  Do one-way functions exist ? [Is public-key cryptography possible ?]

A one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input.

A one-way function that comes to mind is a Cryptographic hash function which is used to create message digests. Where size of the message digest is relatively small as compared to the size of the message and hence it becomes very hard to reconstruct message from the message digest.

So, why does the above problem say that these functions do not exist?

No known cryptographic hash functions are provably secure. It might seem to be hard to reconstruct an input hashing to a given hash value, but we can't prove that it is indeed very hard. We can just say that no one was able to find an algorithm accomplishing that so far, but there is no guarantee that tomorrow such an algorithm won't be found.

In cryptography there is a very exact definition of one-way functions, which implies, among else, that P$\neq$NP. While there are several specific functions which are conjectured to satisfy the definition, no one knows how to prove this. We don't even know how to prove that one-way functions exist assuming P$\neq$NP.


Is the open question NP=co-NP the same as P=NP? I'm wondering this based on several places online that call $\sf NP=$ co-$\sf NP$ a major open problem... but I can't find any indication as to whether or not this is the same as $\sf P=NP$ problem...

No. It is another open problem and certainly related, but different. The complexity class co-$\mathsf{NP}$ is the set of languages whose complements are in $\mathsf{NP}$; that is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier. So for example, the question "Is this SAT formula unsatisfiable?" If the answer is "no", then there is some satisfying assignment of the variables that proves this; that's the certificate for the verifier.

It is possible that $\mathsf{P} \neq \mathsf{NP}$, yet $\mathsf{NP} = $co-$\mathsf{NP}$.

But on the other hand, if $\mathsf{P} = \mathsf{NP}$, then $\mathsf{NP} = $co-$\mathsf{NP}$ for sure. This is because if a language is in $\mathsf{P}$, then its complement is also in $\mathsf{P}$, so if $\mathsf{P} = \mathsf{NP}$, then that goes for every language in $\mathsf{NP}$ as well.


Concatenation among different language types I am trying to figure out the result of the concatenation among different language types (regular, context free, ...). I think the result strongly depends on the nature of the languages which will be concatenated, but I have some doubts on determining the category the result belongs to. Maybe troughout an example it will be easier to solve all my doubts and let you understand better the nature of my question. For instance, let $L = \left \{ 0^{n}\cdot 1^{n} \mid n \geq 0 \right \}$ and $L^{R} = \left \{ 1^{n}\cdot 0^{n} \mid n \geq 0 \right \}$

Those two languages are obviosly not regular (it's easy to apply the Pumping Lemma here)
but what happens if I define this result language $L{}' = L \cdot \left \{ 0, 1 \right \}^{*} \cdot L^{R}$

I think it should be still not regular, since we can apply again the pumping lemma by letting be $p$ the length of the pumping and $w=0^{p}1^{2p}0^{p}$, w is in $L'$. The contination is easily.

But is it good to consider that w of $L'$?

The language $L'$ contains all possible strings, and so it is in particular regular. This is because the empty word is in $L$, and so $L\cdot \{0,1\}^* \cdot L^R$ contains $\{0,1\}^*$. If you "proved" that it's not regular using the pumping lemma, you have made a mistake applying it. Try to find it; this will lead to better understanding of the pumping lemma.


Maximizing sum of numbers within a sequence Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except for first and last number in seq, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example:
[2, 1, 5, 3, 4], sum = 0
[2, 1, 5, 3, 4], sum = 1 + 2 + 5 = 8, 1 removed
[2, 5, 3, 4], sum = 8 + 3 + 5 + 4 = 20, 3 removed
[2, 5, 4], sum = 20 + 5 + 2 + 4 = 31, 5 removed
[2, 4] only 2 numbers left so algorithm ends

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

My question is, is there more efficient algorithm solving this problem?

I'll explain the Dynamic Programming approach to your problem using your sample sequence $[2,1,5,3,4]$. This approach is based on analysis of sub-problems - in your case each sub-problem is simply a task to find the maximal value (in the sense you described in your question) for some sub-sequence. These sub-problems are related to each other - this reducibility relation means that one sub-problem can be reduced to another one in a single step. For example, the sub-problem $[2,1,5,3,4]$ can be reduced to sub-problems $[2,5,3,4]$, $[2,1,3,4]$ and $[2,1,5,4]$ by removing a single number from the sequence.

The graph of sub-problems with this reducibility relationship is below. It's easy to see that our problem is equivalent to a problem of finding a path from the vertex $[2,1,5,3,4]$ to the vertex $[2,4]$ (or vice versa), which will give us the maximal value for the vertex $[2,1,5,3,4]$ (see the path, marked by red color).

Not every problem can be solved by decomposition into sub-problems - such a problem must have Optimal Substructure for that. In our case it means that all the sub-problems along the optimal reducibility path must also have optimal solution. For example, the value of the vertex $[2,5,3,4]$ can be calculated along two paths, so we need to choose the maximal value (23) along the red path and forget about another path.

This local optimization is the reason why the Dynamic Programming method works so well for large problems. It often allows us to reduce exponential time complexity to polynomial one.

There are two ways to solve our problem using Dynamic Programming - "top-to-bottom" and "bottom-up". In our case they are equivalent to traversing our graph from the vertex $[2,1,5,3,4]$ to the vertex $[2,4]$ or vice versa.

The top-to-bottom way involves developing a recursive function with two arguments - a sub-problem description (sub-sequence in our case), and mapping from the sub-problem description to the values space. This mapping will gather information about already solved sub-problems, so we will never solve the same problem again. The function will need to reduce (in one step!) the given sub-problem to all the possible sub-sub-problems and find the maximum of calculated values. Using such a mapping is often called Memoization.
The bottom-up way starts from the simplest sub-problem ($[2,4]$ with value = 0) and assigns values to all the sub-problems going up layer by layer, again maximizing the value of each sub-problem, calculated over its sub-sub-problems. Here we don't need recursion, however multiple nested loops will be needed, and it's not easy to program that correctly right away.

Now - it's your job to choose a way you want and solve your problem in general case.

ADDITION. We can make our graph oriented (each arc is oriented from top to bottom) and weighted (each arc weight is equal to the portion of value, given by its beginning) - then the described above "bottom-up" approach becomes equivalent to the Longest Path in Acyclical Digraph Problem.


Maximal class for which function equivalence is decidable I previously asked if it's decidable whether two primitive recursive functions are equivalent: "primitive recursive functional equivalence". The answer was no.

Here is my followup. What is the most powerful class of functions where it can generally be decided if two functions are equivalent? That is, a function can be written such as areEqual :: fun1 -> fun2 -> Bool. By equivalent I do not mean the same algorithm but the same relation between domain and codomain.

In another question I asked if lower elementary recursion was equivalent to deterministic push down automata: "Relation of deterministic push down automata and lower elementary recursion". The answer was no, and that my thought process was wrong. My hope was that this would show that polynomial time functions (lower elementary) could be proven equivalent.

This question is in relation to what class of recursion, not machine. As such deterministic pushdown automata is not what I am looking for. If I understand the answers to my second question correctly the automata do not necessarily translate to a class of recursive functions.

I have been poking at this question for a while in a round about way probing for an answer.

The problem is intuitively solvable for simple problems. For example the even? function could be implemented in a mutual recursive manner with odd? or from mod 2. These two ways do the same thing. The question is in relation to the highest class of functions where this is possible.

There is no such maximal class.

Proof: suppose that there is a class $C$ of representations of total functions for which function equivalence is decidable. If $C$ is finite, then $C$ augmented with the constant function that returns $\max\{\overline{f_i}(0)\} + 1$ (which by construction is not in $C$) has decidable function equivalence (test the function at $0$ then apply the postulated decision algorithm). If $C$ is infinite, it is denumerable (because representations of functions are denumerable¹), so let $(f_i)_{i\in\mathbb{N}}$ be an enumeration of all function representations in $C$. Let $G(i) = \overline{f_i}(i) + 1$ (a classic diagonal construction). By construction, $G$ does not have a representation in $C$ (because $\forall i, g_i(i) \ne h(i)$). Let $g$ be a representation of a function that calculates $G$ (this is doable in any Turing-equivalent framework). The algorithm that reports that $g$ is distinct from any member of $C$, and otherwise applies the existing decision algorithm for $C$, is an equivalence decision procedure for $C \cup \{g\}$.

Any class of function representations with decidable equivalence can be augmented to a larger such class. Therefore there is no maximal class.

Intuitively speaking, if you have two classes of functions with decidable equivalence, you can apply the two decision algorithms inside each class, but it's not necessarily possible to compare two functions from different classes. And if you have an infinite set of classes, with a decision procedure for each, then even calculating which decision procedure to use is not necessarily doable.

¹  The set of all functions is not denumerable, but whatever representation of functions you choose (e.g. source code in some language), the set of inputs for your decision algorithm is denumerable.


A problem with the greedy approach to finding a maximal matching Suppose I have an undirected graph with four vertices $a,b,c,d$ which are connected as in a simple path from $a$ to $d$, i.e. the edge set $\{(a,b), (b,c), (c,d)\}$. Then I have seen the following proposed as a greedy algorithm to find a maximal matching here (page 2, middle of the page)

Maximal Matching (G, V, E):
M = []
While (no more edges can be added)
     Select an edge which does not have any vertex in common with edges in M
     M.append(e)
end while
return M

It seems that this algorithm is entirely dependent on the order chosen for which edge is chosen first. For instance in my example if you choose edge $(b,c)$ first, then the you will have a matching that consists only of $(b,c)$.

Whereas if you choose $(a,b)$ as your starting edge, then the next edge chosen will be $(c,d)$ and you have a matching of cardinality 2.

Am I missing something, as this seems wrong? I have also seen this described as an algorithm for finding a maximal matching in the context of proving that the vertex cover approximation algorithm selects a vertex cover by choosing edges according to a maximal matching. Any insights appreciated.

You're correct, you're not missing anything -- except that the algorithm is not wrong.  The task is to choose a maximal matching, not a maximum matching.  There may be many possible maximal matchings, many of which are not maximum matchings.  It's the difference between a local optimum vs a global optimum.


Encoding set of At-Most-One constraints as a MAX-SAT problem Assume a set of variable $V$ = $\{v_1,...,v_m\}$.
Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$,
$$ AMO \, (v_1, v_4, \neg v_6, v_{10}) \\ ... \\  AMO \, (v_2, \neg v_3, v_7)$$
Problem: Find an assignment to $V$ that maximize
         the number of satisfiable AMO constraint set.

I'm unable to represent it as MAX-SAT problem.
Tried so far (Attempt 1): Using hard constraint for each of At-Most-One constraint. This will not work as encoding of $AMO (v_i,...,v_w)$ will have multiple clauses for each $AMO$ and all of them have assigned same weight (top weight). A solution to this set may not be the maximal one.
Attempt (2): To fix the above problem, I tried relative clause weight; i.e., for each clause assign weight proportional to size of the clause. This will give preference of assigning satisfying shorter clause. But this do not work in extreme situations like if all clause have same length.
I have experience with SAT solvers but this is my first MAX-SAT problem attempt.

The standard way to create soft constraints in MaxSAT is to use label variables:

For each $AMO_j$ constraint, create a new variable $l_j$. Then create an unit clause $(\lnot l_j)$ with weight $1$ and add the literal $l_j$ to every clause of the standard $AMO_j$ encoding that contains only hard (infinite weight) clauses.

Now the label variable $l_j$ acts as a switch: setting $l_j = true$ will "turn off" the $AMO_j$ hard constraint, but does not satisfy the unit clause $(\lnot l_j)$.


dining metaphysicians problem Here is a problem vaguely related to the dining philosophers problem. Three metaphysicians go to a restaurant for dinner. When it is time to pay the bill, they decide that they want one of them to pay the entire bill, but without the other two knowing who paid the bill. Ideally, they'd put three tokens in a bag, one white and two black, and secretly draw a token at random. But this is not allowed. They each have a random generator (coin, dice), and they are limited to exchanging information between each other, either publicly or in private between two of them. For example, all three of them may flip a coin, take note of their coin flip (H or T) and inform their left neighbour of the result. Then the metaphysician whose coin flip equals the coin flip of his right neighbour pays, and the other two don't pay (and don't know who paid). This only works, however, for THH, TTH, HTT, HHT, HTH, and THT; but not for HHH and TTT (since in those cases, all three of them would be paying the entire bill).

Here is my attempt at a solution. Let $R$ be a finite event space for the random generator, ${r_1,...,r_n}$, let $S$ be $\{0,1\}$, and $T$ be a suitable set. Let $f$ be a mapping from $R$ to $S$ and $g$ be a mapping from $R$ to $T$. $f$ maps the outcome $r_i$ to heads or tails as in the coin flipping example. $g$ is a function that masks the $r_i$ while providing enough information to decide whether the procedure needs to be repeated (because the $f$ results are of the HHH or TTT type). The metaphysicians reveal their outcome $f(r_i)$ only to their left neighbour and announce $g(r_i)$ publicly. Here is what $f$ and $g$ need to be able to do: (i) knowing all $g$ values determines whether $f(r_1)=f(r_2)=f(r_3)$ or not; in the former case repeat the procedure. In the latter case apply the coin flipping example to determine who pays. (ii) the probability of $f(r_L)=f(r_\mbox{me})$ conditional on knowing $(g(r_L),g(r_{\mbox{me}}),g(r_R))$ and $f(r_\mbox{me})x≠f(r_R)$ is $0.5$ so that I don't know who pays the bill if my coin flip differs from the coin flip of my right neighbour. $r_L$ is my left neighbour's outcome, $r_R$ my right neighbour's outcome. If I had functions $f$ and $g$ fulfilling these constraints, I'd have a solution for my problem, but I don't know what $f$ and $g$ might look like. $g(r_i)$ could be something like an md5sum, not allowing me to infer $f(r_i)$ which determines the payor.

Using secure multi-party computation, there exists a polynomial-time protocol for this problem.

The functionality is

$$F_i(r_1,r_2,r_3)=((r_1 \ne r_2) \lor (r_2 \ne r_3) \lor (r_1 \ne r_3), (r_i = r_{i+1}) \land (r_i \ne r_{i-1})).$$

In other words, in the ideal world, participant $i$ flips a coin to get $r_i \in \{0,1\}$ and sends it to the trusted third party; they receive $F_i(r_1,r_2,r_3)$ back, and the first bit of the result indicates whether to repeat or not and the second bit indicates whether to pay.

It's a powerful theorem from the cryptographic literature that there exists a protocol for any functionality, with computational security and running in polynomial time.  Thus, there exists a protocol for this problem, too.  It will be secure as long as no more than 1 of the 3 participants are malicious.

See https://en.wikipedia.org/wiki/Secure_multi-party_computation and a good textbook on theoretical cryptography.


How to master Dynamic Programming? I am having hard times learning Dynamic Programming.

I looked around the web and found many tutorials with examples.

Each time I tried to figure out how to solve a new problem before looking at the solution my mind locked up and I could not continue trying...

I do not where to start!! For example, in divide and conquer I know how to start but In dynamic programming there is no a fixed starting point or at least (technique).

Last try I moved forward but I found that the solution was in a completely different direction.

Not sure why I can't just comment.  All I want to do is share a link:

http://people.csail.mit.edu/bdean/6.046/dp/

Or better yet:  Deciding on Sub-Problems for Dynamic Programming

This is a duplicate.


How to calculate an accurate estimated reading time of text? I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the difficulty of the used vocabulary with some kind of text analysis.

I suppose it would be something like this:

totalWordCount / (avgReadTimePerWord * textDifficulty)

Also I read somewhere that the average reading speed is 120 words per minute. But I have some questions regarding that:

Are people known wich existing algorithms that are capable of doing such accurate calculations considering those factors?
Is the average reading time equal in all languages and if not, how to add language as a factor also? What study shows average reading times per language?
Is it possible to add age as a factor? Or are there known studies on those factors?
If someone has dyslexia. Is their some research that suggest for example they take 30% longer to read? And can we just increase it by 30% in such case or are there other factors in such case?

Goal is to implement this as a function in a programming language like Python or PHP and to use the (personalised) result for creating an output like "this article can be read in approximately 12-14 minutes".

It would be nice if such information is publicly available.

There is a similar question, so I will add a bit over the answer.

There are too many factors independent of language but solely based on individual reading abilities that such estimate would not be possible.
I assume perfect text without spelling errors and unclear grammar.

Giving it a try:
People can read 20, 50, 200, 2000... pages per hour, it depends on reading skills - only prescreening test will give you answer to that: give 2 pages, measure time, or use eye tracker and do the same.

This depends on language used, but the reading speed is measured in native language, so the differences are in the next point as for language (or decrease the speed for non-native by... proficiency at that language).

People use Cohorts imagine that the dictionary forms trie, and the speed of recognizing given word depends on amount of words with the same prefix.
Cognitive Psychology: A Student's Handbook, fifth edition by Michael W. Eysenck,Mark T. Keane, page 347.

For example: "Av..." What are possible words?
Average, Avalanche... Avengers if someone seen the movie, comics or ads.
"Ave.." - word on it's own, Average fits, Avengers also.
If person reads about statistics, "average" is already good choice, about Roman Empire - Ave it is, about movies played - Avengers.
But reading continues to the next syllabe.

It depends on mood, recent readings, coherence of text, familiarity with topic, recent topics seen (not only read).

About topic: reading novel is faster than technical text. Technical text for someone proficient will not decrease reading speed.
So the task given is important, if someone is checked for understanding text, reading speed decreases.

The language itself is not a factor, you should not take mean reading speed but median of your target group.
Yes age is factor, but not that usable as it gives fraction of other factors.

With dyslexia the decrease also vary per person, $30%$ decrease is very optimistic case.

Theory and Research in Learning Disabilities by J.P. Das, R.F. Mulcahy and A.E. Wall, page 179.

I would take into account understanding of text, with dyslexia simple, short statements are easier to cope than longer sentences.

In any case taking syllabes count, average sentence length, topic, statistical occurence of word in e.g. books, magazines, movies, spoken language, difficulty of text (taken as topic and uncommon words).

There are a lot more factors, but giving the general idea that it is not sufficient to just calculate it from text is presented.

The best estimate for personalised result - measure per person and store the result, honestly the best you can do.

You can try The Psychology of Reading by K. Rayner and A. Pollatsek.


Is there a research name for "systems that steadily grow in complexity as they are computed"? I have an intuitive concept of systems that grows in complexity steadily as it computes. I can think in some examples:

Nature. Given the physical laws, some initial conditions (say, the Earth planet at the beginning of life) and enough time, the system eventually evolves in complexity, all the way from dinosaurs fighting over territory to humans building castles.
Cellular automatas. Given a set of automata rules, some initial conditions (a grid with specific cells set) and enough time, some automatas eventually evolve complex structures.
AI applications such as genetic programming (to some extent). The issue is that most of those evolve towards a specific goal and often reach a tipping point and stop.

The kind of system I'm talking about is supposed to grow in complexity indefinitely. That is, one can expect that, given enough time, such system will eventually develop complex structures such as "lifeforms" that defend their own existence. It is also not goal oriented, it is supposed to grow in complexity because their own internal structures are more stable when they are more complex. We know nature/physical laws satisfy that criteria, but I'm not sure about cellular automatas and genetic programming. That is a very vague concept and hard to define (there is no accepted definition of complexity, after all). Yet, is there any name/formalization for this kind of system? Do we know any examples of systems/specific automatas that, as far as our observation goes, never reach a "tipping point" where they stop becoming more complex?

Hypothesis could be :

The time is discrete, let $s_i$ be the state of your system at $t=i$.
Your system is deterministic and  its transition function $f$ is computable.
Its complexity $c : \mathbb{N} \to \mathbb{N}$ is the Kolmogorov complexity, $c(i)$ is the length of the shortest C++ program which prints $s_i$.

Then you have a bound : $$c(i) \leq O^+(1) + c_0 + |f| + |i| = O^+(1) + |i| $$

($O^+(1)$ is a notation for a positive constant, |x| is the Kolmogorov complexity of x)

And more generally for any computable function $g$ : $$c(g(i)) \leq O^+(1) + c_0 + |f| +|g| + |i| = O^+(1) + |i| $$

The system complexity grows more slowly that any computable function !

Conclusion :

You should look at systems which are not deterministic or whose transition function is not computable. Or use an other definition for complexity (like this one : Chaos Theory).
With Kolmogorov complexity, chaotic states are more complex than states with lifeforms defending themselves, but may be one can define a physical macroscopic Kolmogorov Complexity where the  unbreakable basic components for describe the world are quite big and their internal features are negligible. Then it becomes more complex to describe tangle of life and vacuum than homogeneous chaos.


Upper bound derivation of expected time for finding a large cut Given an undirected graph $G$ with $n$ vertices and $m$ edges, we build a cut as following. Initially sets (of vertices) $A$ and $B$ are empty. For each vertex $v$ we flip a fair coin and according to outcome we put $v$ either in $A$ or $B$.

Let $X$ be a r.v. denoting the cut size, i.e. the number of edges between sets $A$ and $B$. A simple calculation produces $$E[X] = \frac{m}{2}$$
(see Probability and Computing by M.Mitzenmacher & E. Upfal, pg 130).

Now, let $p = \Pr\left(X \geq \frac{m}{2}\right)$. Then
$$ \frac{m}{2} = E[X] = \sum_{i \leq m/2 -1}{i\Pr(X=i)} + \sum_{i \geq m/2}{i\Pr(X=i)}$$
$$ \leq (1-p)\left(\frac{m}{2}-1 \right) + pm.$$

I understand that for $i < m/2 -1$, $\Pr(X=i) \leq \Pr(X < m/2)$ and for $i \geq m/2$, $\Pr(X=i) \leq \Pr(X \geq m/2)$, but I don't understand how the last upper bound is derived.

Can anyone give me a hint or explain the derivation?

We can upper bound the first summand by
$$
\sum_{i \leq m/2-1} i \Pr(X=i) \leq
\sum_{i \leq m/2-1} (m/2-1) Pr(X=i) =
(m/2-1) \sum_{i \leq m/2-1} Pr(X=i) =
(m/2-1) Pr(X \leq m/2-1) = (1-Pr(X \geq m/2))(m/2-1) = (1-p)(m/2-1).
$$
Similarly, we can upper bound the second summand by
$$
\sum_{i \geq m/2} i \Pr(X=i) \leq
\sum_{i \geq m/2} m Pr(X=i) =
m \sum_{i \geq m/2} Pr(X=i) =
m Pr(X \geq m/2) = pm.
$$


Implementation of QuickSort to handle duplicates I have this past year question based on the following scenario:

When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we recursively QuickSort those values on the left and those values on the right. Make the necessary changes to the partition method to achieve that.

Here is the implementation of Quicksort, written in Java. I will not include the code in the main page because it seems that this site requests for description of pseudocode rather than actual code, even if the code is very “simple”.

In particular, this quicksort implementation is similar to the typical one, but choses its pivot on the left of the array.

I have some basic understanding of the quicksort algorithm based on the actual code, but a lot of times I have to break down the code myself to understand it. Whenever I am given pseudocode hints to understand the algorithm[and to be honest I don’t know sometimes whether a hint is a very obvious one or a rather implicit one], I somehow cannot appreciate the “magic” behind the pseudocode.

My understanding of this implementation of quicksort is that the array has to be iterated to make 2 regions of low and high values, while we dynamically decide on where to put the pivot, call it position X, which in this implementation is chosen to be the leftmost element of the input array. If this position X is dynamically decided, how exactly do you “group elements equal to pivot” to middle, and how exactly does it adhere to the principles behind the typical algorithm?

Do inform me if more information is required or the formatting of the question doesn't adhere to the standards here.

The simple implementation idea is to separate the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot.

In pseudocode, the algorithm looks like the following.

algorithm quicksort(A, lo, hi):
    if lo < hi then
        p ← pivot(A, lo, hi)
        left, right ← three-way-partition(A, p, lo, hi)

        quicksort(A, lo, left - 1)
        quicksort(A, right, hi)

The partition procedure looks like the following.

procedure three-way-partition(A, pivot, lo, hi):
    l ← lo
    r ← lo
    u ← hi

    while r ≤ u:
        if A[r] < pivot:
            swap A[l] and A[r]
            l ← l + 1
            r ← r + 1
        else if A[r] > pivot:
            swap A[r] and A[u]
            u ← u - 1
        else: // the element is equal to pivot
            r ← r + 1
    return l, r

It uses three indices l, r and u (left, right, and upper bound), maintaining the following invariant in the while loop.

lo ≤ l ≤ r ≤ u ≤ hi
the elements with index in [lo, l) are smaller to the pivot.
the elements with index in [l, r) are equal to the pivot.
the elements with index in [r, u] are not examined yet.
the elements with index in (u, hi] are greater than the pivot.

There are a few minor variants. The above should be enough for you to understand what is going on.


Perceptron learning rule doesn't work i'm a little bit lost ... can you help me ?

So I have this table of date (each row give a point with its group)

So i took a random weight let's say : [1, -2]
H = 1 if n =< 0
    0 otherwise

a= H([1,-2][6,3]) = H(0) = 1 but the target output is 0 ... so we have to update the weight:
w -> w - p = [5 , -5] .
Next :

a= H([5,-5][3,3]= H(0)=1 the problem is : there the target output is 1 so we don't have to update the weight , but that's strange because the [5 -5] vector doesn't draw a linear separation between the 2 groups ...

Thanks for your help ? :)

I think you're mixing up the weight vector $w$ and the actual hyperplane defining the decision boundary. The way to interpret $w$ is as a vector which is orthogonal to any vector lying on the hyperplane. See these slides for some visualization.

As you've said, the decision is defined by $1$ if $w_1 x + w_2 y > 0$ and $0$ otherwise. So to find the actual hyperplane (decision boundary) we can just solve for the place where the decision changes, which is at $0$. Using your $w$ we have
$$
\begin{align*}
w_1 x + w_2 y &= 0\\
\implies 5 x + -5y &= 0\\
\implies x &= y.
\end{align*}
$$
So the decision boundary is given by the line $y = x$. Plotting this with your points we see that this $w$ does indeed define a separating hyperplane.


What is the relation between functors in SML and Category theory? Along the same thinking as this statement by Andrej Bauer in this answer

  The Haskell community has developed a number of techniques inspired by
  category theory, of which monads are best known but should not be
  confused with monads.

What is the relation between functors in SML and functors in Category theory?

Since I don't know about the details of functors in other languages such as Haskell or OCaml, if there is info of value then please also add sections for other languages.

Categories form a (large) category whose objects are the (small) categories and whose morphisms are functors between small categories. In this sense functors in category theory are "higher size morphisms".

ML functors are not functors in the categorical sense of the word. But they are "higher size functions" in a type-theoretic sense.

Think of concrete datatypes in a typical programming language as "small". Thus int, bool, int -> int, etc are small, classes in java are small, as well structs in C.
We may collect all the datatypes into a large collection called Type. A type constructor, such as list or array is a function from Type to Type. So it is a "large" function.
An ML functor is just a slightly more complicated large function: it accepts as an argument several small things and it returns several small things. "Several small things put together" is known as structure in ML. In terms of Martin-Löf type theory we have a universe Type of small types. The large types are usually called kinds. So we have:

values are elements of types (example: 42 : int)
types are elements of Type (example: int : Type)
ML signatures are kinds (example: OrderedType)
type constructors are elements of kinds (example: list : Type -> Type)
ML stuctures are elements of kinds (example: String : OrderedType)
ML functors are functions between kinds (example: Map.Make : Map.OrderedType -> Make.S)

Now we can draw an analogy between ML and categories, under which functors correspond to functors. But we also notice that datatypes in ML are like "small categories without morphisms", in other words they are like sets more than they are like categories. We could use an analogy between ML and set theory then:

datatypes are like sets
kinds are like set-theoretic classes
functors are like class-sized functions


How to compute Gabor feature vector? I'm working on semi automatic texture segmentation using level set and gabor feature vector described by Manjunath und Ma [1]. I consider their feature representation is better than others since I can get good result on several images but somehow performs really bad on other images data. So I guess there's something wrong with my understanding.

They describe that the feature vectors consist of $\mu_{mn}$ (mean) and $\sigma_{mn}$ (standard deviation). I use scale $S = 4$ and orientation $K = 6$, thus my feature vector will be 48 dimension (4 * 6 * 2 = 48):

$f = \{  \mu_{00}, \sigma_{00}, \mu_{01}, \sigma_{01}, \mu_{02}...\mu_{35}, \sigma_{35}  \} \tag1$

I am confused with their equation:

$W(x, y) = \int I(x_1,y_1)g_{mn} * (x - x_1, y - y_1) dx_1 dy_1 \tag2$

$\mu_{mn} = \int \int |W_{mn}(x,y)|dxdy \tag3$

$\sigma_{mn} = \sqrt{ \int \int (|W_{mn}(x,y) - \mu_{mn}|)^2 dxdy } \tag4$

So my first question is: are $\mu$ and $\sigma$ simply mean and average? So far, I just average every pixel value of the magnitude to obtain $\mu$ and compute the standard deviation to obtain $\sigma$.

After I compute the feature vector, I need to do distance measure between two vectors $f_i$ and $f_j$

$d(i, j) = \sum_{}^{m}\sum_{}^{n} d_{mn}(i, j) \tag5$

$d_{mn}(i, j) = |\frac{\mu_{mn}^i - \mu_{mn}^j}{\alpha(\mu_{mn})}|  + |\frac{\sigma_{mn}^i - \sigma_{mn}^j}{\alpha(\sigma_{mn})}| \tag6$

I'm really puzzled with $\alpha(\mu_{mn})$ and $\alpha(\sigma_{mn})$ ? What are they? I have tried to calculate 48 standard deviations from $ (1)$

$\alpha = \{ \alpha(\mu_{00}), \alpha(\sigma_{00}), \alpha(\mu_{01}), \alpha(\sigma_{01}), \alpha(\mu_{02})...\alpha(\mu_{35}), \alpha(\sigma_{35}) )\} \tag7$

and use it to calculate the distance function but I'm not convinced with my calculation since it seems not better than simple euclidean distance.

Texture Features for Browsing and Retrieval of Image Data by B.S. Manjunath and W.Y. Ma (1996)

$\mu$ and $\sigma$ are simply mean and standard deviation. I assume there is also a normalizing coefficient out there. Or the normalization as you mentioned comes from $\alpha$, since it $\alpha$s are vectors composed of the standard deviation and mean.