Time complexity of linear program? I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of nodes $N_{k+1} \leq 0.5N_{k}$.

I think this means that the overall complexity should be order $\log N \times T(N)$ where $T(N)$ is the complexity of the FIRST linear relaxation. since the problem size gets at least cut in half each iteration. But there's two issues.

1) The complexity of the inner problem is reduced each iteration, so we're not doing $\log N$ iterations of $T(N)$ complexity, but something like $\sum_{i=0}^{\log N} T(N/2^i)$ or something. But is this the same as $\log N \times  T(N)$ asymptotically or can I tighten my bound?

2) How do I find the complexity of my linear program? I've heard the figure $O(n^{3.5})$ where $n = $ number of variables for interior point methods and $n^3$ for average case Simplex, but I can't find a good source.

Answering your first question, whether you can tighten the analysis depends on the function $T$. If $T$ is constant, for example, then the analysis is tight; if $T$ is a polynomial, then the analysis is not tight, and in fact you can remove the logarithmic factor: the answer is simply $O(T(N))$.

Answering your second question, the best known time complexity for solving linear programming is given in Yin Tat Lee and Aaron Sidford's recent paper, top of page 43:
$$
\tilde{O}\left(\sqrt{\operatorname{rank}(A)}(\operatorname{nnz}(A)+\operatorname{rank}(A)^\omega)L\right).
$$
Here:

$\tilde{O}$ hides logarithmic factors.
$A$ is the constraint matrix.
$\operatorname{rank}(A)$ is the rank of $A$.
$\operatorname{nnz}(A)$ is the number of non-zero entries in $A$.
$\omega$ is the matrix multiplication constant. The best known value currently, due to Le Gall, is $\omega < 2.3728639$, but it is suspected that $\omega = 2$.
$L$ is the bit complexity of the LP, roughly the number of bits in the encoding of the LP (see footnote 2 on page 2 for the exact definition).

The smoothed complexity of the simplex algorithm might be better, but unless your instance is random, smoothed complexity isn't going to help you.


Why does A* fail to find the fastest path when it reaches the goal? I'm trying to understand how A* works on some simple examples, and something struck me as odd. I could fairly easily come up with situations in which A* "failed". Here is an example:

Take a 2x2 grid, in which you can only move in one of 4 (orthogonal) directions (no diagonal movement). Denote the node at (0, 0) by A, the node at (1, 0) by B, the node at (0, 1) by C, and the node at (1, 1) by D (so that it looks like

C D
A B

The weight going from A to B is 3, the weight going from A to C is 2, the weight from B to D is 1, and the weight from C to D is 3. Let the start node be A and the goal be D. Let our heuristic simply be Euclidean distance (or Manhattan distance, both produce the same result in this instance).

So, if my understanding of A* is correct, we start with an open set containing only A, so we pop A. It's neighbours are B and C, which have g values g(B) = 3, g(C) = 2, and h values h(B) = 1, h(C) = 1. So the f-values are f(B) = 3 + 1 = 4, f(C) = 2 + 1 = 3. Add these to the open set.

Now the open set is {B, C}. Since C has the lowest f-value, we pop it. C's only neighbour is D, which is the goal. So we stop, having found "the best path" from A to D.

This is clearly wrong. The algorithm should output the path A->B->D, which has total weight 4, but instead it stopped prematurely.

Now, if we were to have a larger graph, then after exploring the path A->C->D we would go back to B (which is still in the open set), notice that the path A->B->D to D gives D a lower f-value than A->C->D, so we update D's f-value, giving the correct fastest path. Alternatively, we could simply continue running A* until the open set is empty, rather than ending prematurely as soon as we've found the goal (however, this doesn't agree with Wikipedia's pseudocode implementation of A*).

Are my ideas correct, or am I missing something about how A* is typically implemented?

Your misunderstanding is that A* doesn't return success until it pops a goal node, in your terminology.

So, in your example, when it pops $C$, it puts $D$ in the open list, with quite a high value. It then pops $B$ and puts $D$ in the open list again, with a lower value. So the first time that $D$ is popped will be from the route $A\to B\to D$, as it should be.


BPP search: what does boosting correctness entail? It is not really clear to me, how and if I can do boosting for correctness (or error reduction) on a BPP (bounded-error probabilistic polynomial-time) search problem. Can anyone of you explain me how it works?

With BPP search, I mean a problem that can have false positive-negative, correct solution, and no-solution. Here's a definition:

A probabilistic polynomial-time algorithm $A$ solves the search problem of the relation $R$ if

for every $x ∈ S$, $Pr[A(x) ∈ R(x)] > 1 - μ(|x|)$
for every $x ∉ SR$, $Pr[A(x) = \text{no-solution}] > 1 - μ(|x|)$

were $R(x)$ is the set of solution for the problem and $μ(|x|)$ is a negligible function (it is rare that it fails).

So now I would like to increase my probability of getting a good answer, how can I do it?

~ ".. boosting for correctness.." : a way to increase the probability of the algorithm (generally by multile runs of the probabilistic algorithm), i.e., when the problem have a solution then the algorithm likely return a valid one.

If the relation $R$ lies in the complexity class P (or even BPP), then boosting works by running your algorithm many times, and testing whether its output satisfies $R$. When $x \in S$, this fails with probability $\mu^N$, where $N$ is the number of times you run $A$. When $x \notin S$, this never fails. This way you can boost $\mu$ from $1-1/\mathrm{poly}(n)$ to $2^{-\mathrm{poly}(n)}$.

Edit: if $R$ is in BPP rather than P, with constant error probability $\mu$, then this approach doesn't work. You can decide whether $x \in S$ or not using the usual majority trick, but if $x \in S$, it's not clear how you'd find a correct witness whp.


Is the kernel loaded into memory for every user simultaneously using a Multi-User O.S. system? I have a doubt about loading kernel for every user using a Multi-User system. Every user's processes and programs are scheduled to CPU in a time-sharing fashion. But, do every user on the multi-user system have their individual kernel loaded in the main memory, or is there only one kernel loaded which is sort of distributed amongst the users?

The shell (or window manager) which provides a visual interface is not part of the kernel. It's a simple user process and it runs in userspace without elevated privileges. In order for the user to "log in", which involves associating their terminal with the shell (or window manager), a login manager is needed. This program does run with elevated privileges, but it is also not part of the kernel. And there is only one instance of it.
Almost all user processes interact at some point with the kernel, usually by triggering a software interrupt which is caught by the kernel and triggers some kind of kernel request handler. There is only one copy of the executable image which contains kernel functions, but each handler needs to run independently and normally requires some transient storage. This would most naturally be stored on a stack, as with the transient storage for any ordinary procedure. However the "kernel stack" for a process is provided, it will by unique to the process. But it's usually not very big at all.


NP-hardness and FPTAS I have a problem in understanding how to prove the following question.

Let $Q = \langle\max,f,L\rangle$ be an NPO-Problem, where $f$ only supports integers.
Define $$L_Q^* =\{(x_0,1^k) : \exists x . L(x_0,x) \land f(x_0,x) \geq k\}.$$
The instance of $x_0$ is binary coded, while the numerical parameter $k$ is unary coded. Show that if $L_Q^*$ is NP-complete, then there is no FPTAS for $Q$.
It can be assumed that $P \neq NP$.

Normally I have some ideas, but this time I am really stumped. My only idea was to use the fact that if $L_Q^*$ has an approximation scheme, then $f$ must run in time polynomial in $|x_0|+|x|$.

Hint: Show that an FPTAS for $Q$ implies a polytime algorithm for $L_Q^*$. This contradicts the assumption $P \neq NP$, which is missing from your question but seems to be tacitly assumed.


Is it possible to get Nth Fibonacci number in sublinear time? I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I've decided to check out if you agree with my explanation.

The naive algorithms runs in $O(n)$, if we ignore the cost of addition.
The Binet's formula or matrix exponentiation method should both theoretically run in $O(\lg(n))$ (since exponentiation of both matrices and real numbers takes $O(\lg(n))$ steps)

The problem arises when you analyze the size of Nth Fibonacci number by assuming that after first few members of the sequence, the ratio between two numbers is at least 1.5 (picked randomly, I assume it can be easily proved by induction).

We can then bound the number to be at least as big as: $c_1*(1.5)^n$.
Its logarithm gives us the number of digits the Nth Fibonacci number has ($c_2*n$).
Am I right to assume that you can't print out (or calculate) linear number of digits in sublinear time?

My explanation of this "paradox" is that I forgot to add multiplication costs in 2nd algorithm (Binet/matrix), making its complexity $n*\lg(n)$.
I've found out that naive algorithm (1st) runs better for very small inputs, and 2nd algorithm runs better for bigger ones (python3).

Is my explanation of complexity correct, and should the naive algorithm get better running time at even larger inputs ($n>10^9$ or such)?

I do not consider this to be a duplicate question, since it adresses the problem of arbitary values and arbitary integer aritmetic.

Let's assume that you could store such large Fibonacci numbers. In that case, the  length of $n^{th}$ Fibonacci number is $\lfloor n \log_{10}\phi+1\rfloor$. That is the length of the $n^{th}$ Fibonacci number is $\Theta(n)$.

If you go by the naive method, then calculating the $n^{th}$ Fibonacci number would cost you $\Theta(n^2)$ time.

In comparison, matrix exponentiation will take $O(n^2\log n)$ time, assuming you use schoolbook long multiplication to multiply numbers.  (A slightly more refined analysis shows that it is in fact $\Theta(n^2)$, by summing a geometric series.) But if instead we use Karatsuba multiplication , the running time to compute the $n$th Fibonacci number using matrix exponentiation becomes $O(n^{1.585}\log n)$.  (Analogous to before, a slightly more refined analysis shows that the running time is in fact $\Theta(n^{1.585})$.) Thus, if you use sophisticated multiplication algorithms, matrix exponentiation would be better for large $n$ compared to the naive algorithm.

In short: which method is better depends on which multiplication algorithm used.


Closure of Deterministic context-free languages under prefix For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be:

$\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$

ie. the set of all (not necessarily proper) prefixes of words in $L$. I know that if $L$ is context-free then pref(L) is context-free but if $L$ is deterministic context-free then is pref(L) deterministic context-free?

I am sure this is known but I cannot find the answer anywhere and it's not in Hopcroft and Ullman.

DCFL are known to be closed under quotient with regular languages, but the quotient of $L$ with $\Sigma^{*}$ is precisely $\text{pref}(L)$ so yes, if $L$ is a DCFL then $\text{pref}(L)$ is a DCFL.


What subfields in computer sciences may one study without learning Object Oriented Programming? What subfields in computer sciences may one study without learning Object Oriented Programming or is there some kind of degree in Computer Science without the OOP knowledge requirement?
Is there a language without OOP?
Does one need to know OOP to simulate a CPU?
I wanted to earn a CS degree without ever learning OOP. Is there a name for that?
My guess what that Computer science without OOP is simply applied Statistics or Machine Learning using SKlearn and packages.

Depending on where you study, you might be able to get a CS degree without Object Oriented Programming, but the chances are slim. Most degrees would require you to take some programming courses using some general purpose languages along the way, and that will often be Java, C++ or similar, and there you have OOP. Hard to avoid.
But that's good for you, because if you want any job outside university, and you have not a clue about OOP, your chances are practically zero to get any job.


When did commercial Speech Recognition first begin using grammar (sentence structure) for prediction? It seems as though modern speech recognition (e.g., through Android, iOS phones) make use of grammar or sentence structure. (e.g., it might have a tough time distinguishing between "grammar" and "grandma" but can distinguish between "I'm going to see grandma" and "I'm reading a book on english grammar". (yes, I just tried it with my Android phone with vLingo app)

That is much improved (with Speaker Independent SR (i.e., no training)) over what I experienced with Dragon Dictate even using Speaker Dependent SR (with 30m of training).

So, I'm wondering whether my guess is right: When did the commercially available SR software start using grammar and sentence structure to "guess" the right speech?

As far as I know, much of the speech recognition software is build using Hidden Markov Models (HMM) where observations are individual sound phonemes, and the states correspond to words (or some partitions of the words).

I don't think the systems take into account grammar or sentence structure in the sense that they encode rules of English so much as they naturally pick up common structure from training. Because inferring the state in an HMM is based on both the observation (the sound) and the previous state, by adding more training sequences it is possible to capture typical phrases.

For example, there are likely several instances in the training data where the word "English" is followed by the word "grammar", whereas there are very few where it is followed by "grandma", thus the dynamic aspect of the model will capture these connections naturally.


Is it possible to prove $\mathsf{BPP = NP}$ statistically? Assuming that someone will find poly-time algorithm that statistically is wrong on ~1% of total (already runned) instances (which are very different), will it be a proof for $\mathsf{BPP = NP}$?

One way to interpret your statement is:

  Suppose that $\mathsf{L\in NP}$, and there exists a polynomial time deterministic algorithm $A$ such that for all $n$: $\Pr\limits_{x\sim U_n}\left[ A(x) = L(x)\right]\ge 0.99$, where $U_n$ is the uniform distribution over $\{0,1\}^n$, does this imply $\mathsf{L\in BPP}$?

As Yuval mentioned, the question (at heart) relates to the difference between randomized complexity and distributional (average case) complexity. Randomized complexity is the time required to correctly decide the membership of all inputs with high probability (where the probability is over the inner randomness of the algoirthm), whereas average case complexity is the time required for a deterministic algorithm to correctly decide "most" instances (relative to some distribution $\mathcal{D}$ over possible inputs).

This means that the question translates to whether the worst case hardness of an NP problem implies its average case hardness (the opposite direction is a result of Yao's principle, see this question for details). To the best of my knowledge, this is an open problem. There are many works on the subject, e.g.
On Worst-Case to Average-Case Reductions for NP Problems by Andrej Bogdanov and Luca Trevisan. The paper defines what it means for a language to have a worst to average case reduction, and shows that unless the polynomial hierarchy collapses, such reductions cannot exist for NP complete problems (the implication might still hold, but not through their form of reduction).


Sample K representative frames within a video I have an image-based processing module that takes photos for some computer vision processing. I have many videos, but I need to sample representative frames as its inputs, preferably those frames with higher attention.

What are some good and effective algorithms or approaches to take K sample frames in a video? Interesting feature is that usually camera doesn't move much in successive frames with higher attention. So basically we have more stable scenes when a person is focusing on something important. Is there any ways to take this into account for our sampling?

The question misses a lot of detail, so I will try to make an educated guess.

I don't know of any specific algorithm for the task you are trying to achieve, but the first step towards your solution would be perhaps the computation of the average of the magnitude of the optical flow throughout the whole duration of a video. Why: you said that an interesting feature in your videos is the fact that the camera moves less while filming something interesting. Then, the magnitude of optical flow vectors will be expectedly smaller. If you plot the average magnitude of optical flow throughout time of the video, you could start to see parts where there is potentially something interesting here and there.

Edit: look-up at the algorithm used by Youtube for "smart" thumbnail selection. E.g. https://stackoverflow.com/questions/28263511/smart-video-thumbnail-generator-algorithm


Emergent complexity and Turing Completeness Is there some link between the concept of emergence and Turing Completeness?  The ideas feel intuitively like they might be linked, but I can find nothing online.

The idea came to me because I was exploring Conway's Game of Life, and it was hard not to suppose a link between these two properties.

Edit: In response to Raphael's point, I have a clarification to the question (which I thought was implied, but in hindsight, it really wasn't)

Must it be the case that systems that exhibit weak emergent complexity are also Turing Complete?

I suggest you  to give  a look to S. Wolfram's book "A New Kind Of Science" (that is also available online).

The centeral ideas are:

Computation is everywhere
Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication (Principle of Computational Equivalence)
Computation irreducibility: while many computations admit shortcuts that allow them to be performed more rapidly, others cannot be sped up.

Though these ideas are probably not new, they are exposed in a fascinating way (to be honest, a rather informal and non-mathematical "way").


Why does functional map() operation not permit operating on two elements of a list at a time? Mathematically it seems so easy to use two elements of a vector as two arguments to a function.
$$f(\boldsymbol{x_{i+1}},\boldsymbol{x_{i}})$$
In functional programming however a map (function) allows to work with one element at a time only, so one would need to create vector of pairwise 2-tuples from a single initial vector fisrt. Why is that? Is it also more proper mathematically?

Conceptually, 1-argument map should be able to work on unordered collections, because each application of a mapping function doesn't know anything about the element's index.

Your proposed version does know something about the elements' indices, so treats its argument as an ordered sequence of elements. That's the difference.

For regular lists, we can recover the indices by zipping the list with the (infinite, unbounded) sequence [1..]. So, the ability to zip assumes the sequence is ordered - not in values, but positionally.

Mathematicians can have some specific terminology for this, but I think that's the gist of it.

Such sequences you can always split into a special so-called head i.e. "first" element, and the rest of them, deterministically. But e.g. for truly non-deterministic sequences this is not possible, yet mapping is still a well-defined operation.


first order logic resolution unification Assuming I have shown part of the knowledge base in the clausal format:

[1] p1(banana).

[2] not p1(X) or p2(Y).
[3] p1(X) or not p3(F).

... and more rules.

Most of the books, would do something like this:

[1,2] {X=banana} p2(Y).

and more steps.

First question: is it equally correct to do something like follows:

[2,3] {X=X} p2(Y) or not p3(F).

and then continue with resolution.

Second question: What if different variables were used in each clause, could I do the same as above, for example we had:

[2] not p1(X1) or p2(Y1).
[3] p1(X2) or not p3(F2).

[2,3] {X1=X2} p2(Y) or not p3(F2).

Thank you in advance

Assuming $X$ here is a variable, rather than an atomic proposition, then first you must specify what is the quantification for 2 and 3. I assume that it should be

$\forall X,Y \neg p1(X)\vee p2(Y)$, and similarly for 3.
In this case, what can be done is to replace $X$ and $Y$ with each atomic proposition available, in order to obtain a propositional knowledge base, and work on that.

What you suggest to do with 2,3 is sound only under universal quantification, but if you have only universal quantification, it is useful indeed.

For your second question: the name of the variable means nothing, so your substitution is sound also there. Indeed, the claim $\forall Y, P(Y)$ is equivalent to $\forall Z, P(Z)$. You can first change the names, if it makes you happy :)

I'll remark that usually, in resolution-guided proofs, it is more useful to resolve a concrete expression with a quantified rule. For example, resolving $P(a)$ with $\forall X P(X)\to Q(X)$ in order to obtain $Q(a)$. This is more likely (heuristically) to get you towards the proof of a claim.


Prove that $1^\text{nan} = 1.00$ I know that for most computation involve nan (not a number) the result is a nan itself except for some cases.
For example, $1^{\text{nan}} = 1.00$ which proven by mathematicians to be true.
I tried to find a proof but failed
so my question is how to prove that $1^{\text{nan}} = 1.00$?

The fact that $1^{\text{nan}}= 1.0$ is by definition, and not by proof, more specifically, it is by definition of the standard IEEE 754, IEEE Standard for Floating-Point Arithmetic.
From the definition of floating-point arithmetic, as specified in IEEE 754 revision 2008, 9.2.1 Special values:

pow(+1, y) is 1 for any y (even a quiet NaN).

Here is the full list of special values for pow:

For the pow function (integral exponents get special treatment):

pow(x, ±0) is 1 for any x (even a zero, quiet NaN, or infinity)
pow(±0, y) is ±∞s and signals the divideByZero exception for y an odd integer < 0
pow(±0, −∞) is +∞ with no exception
pow(±0, +∞) is +0 with no exception
pow(±0, y) is +∞ and signals the divideByZero exception for finite y < 0 and not an odd integer
pow(±0, y) is ±0 for finite y > 0 an odd integer
pow(±0, y) is +0 for finite y > 0 and not an odd integer
pow(−1, ±∞) is 1 with no exception
pow(+1, y) is 1 for any y (even a quiet NaN)
pow(x, y) signals the invalid operation exception for finite x < 0 and finite non-integer y.


Compare Hidden Markov Model's sample with ground truth data I have a time-serie and I fit different HMMs on it, each with a different number of hidden states.
Now after sampling from the models , I'd like to compare the results with the ground truth data and find the model that gets closer to the real world data in the original time-serie.
For now I simply compared visually the distribution of the values generated by the HMMs and the distribution of values in the time-serie, but I'd like to compute a number indicating which model generates better samples.

Compute the likelihood of the observed data, for each model.  Then higher the likelihood, the better the fit.  The likelihood is just the probability that the model assigns to the observed data, which for HMMs can be computed using dynamic programming.
Be prepared that the more complex the model, the higher the likelihood will be, but that doesn't necessarily mean the model is "better" -- you run the risk of overfitting.  Larger HMMs may fit the training data better, but if the HMM is too large, it might perform poorly on new data because of overfitting.


Avoiding overflow in computing the ratio of two large numbers Is there a trick for computing the expression
$x + (exp(x)-x)/(exp(2*x) + 1)$ while avoiding an overflow?
Currently, computation seems to fail for any $x \geq 710$, presumably because computing $exp(2*x)$ leads to an overflow. The expression as such never produces particularly large numbers, but exponentiation seems to cause problems.

I'm working in R, but the same problem occurs in C++ as well.

If there is no trick for computing it, I'd be just as happy using another non-negative monotonic function which is nearly linear for $x > 10$.

Yes, when $x\ge355$, computing $e^{2x}$ as a double-precision float in IEEE 754-1985 standard, leads to an overflow.

$$x + \frac{e^x-x}{e^{2x} + 1}= x + e^{-x} - \frac{x+e^{-x}}{e^{2x} + 1}\approx x+ e^{-x}$$

The difference between the two sides of the approximate sign is smaller than the minimal positive number in IEEE 754-1985 standard, $2^{−1022} \approx 2.225×10^{−308}$, when $x>367.2$.

So, once $x>367.2$, you can just use $x+e^{-x}$ instead.


For a given certain situation how to prove that the system will never get into the state of Deadlock The situation is as follows

  'm' process shares 'n' resources of same type. The maximum need of
  each process does not exceed 'n' and the sum all their maximum needs
  is always less than m+n. In this set up will deadlock ever occur

This is a question from Operating System Concepts by Silberschatz, Gagne and Galvin.

I tried to prove this using using Banker's Algorithm. Initially, I assumed that the Allocated Matrix for 'm' processes is a zero matrix. And Maximum Matrix of 'm' process is 'n'. Since Need matrix is difference of Allocated Matrix and Max Matrix therefore, Need Martix is equilavent of Maximum Matrix. And at last Available Matrix is equal to 'n'.

At this point I feel stuck and not able to find a way to proceed. Looking forward for help from you guys.
Thanks in advance.

The question in the given situation is equivalent to the question: is it possible to create or to design a system such that m processes sharing n resources of the same type may enter a deadlock state subject to the following: each process needs less than or equal to n resources, and the total number of needed resources is less than or equal to m+n (“For a given certain situation”, 2015)?

Assumptions. Processes run on a single processor. The processor can execute a statement from one and only one process at a time. In other words every statement in a process is an atomic operation. After ending a statement and before executing the next statement of a process, the processor can switch to another process and execute the other process’ next statement.

Consider using a Petri Net for the system design. In terms of Petri Nets a deadlock is a situation when no transition is enabled. Figure 1 is an example of a system that may enter a deadlock state. In this example, m=2 and n=2.
For the same number of processes and resource needs per process (m=2 and n=2), it is also possible to create a system that does not enter a deadlock state. Each of Figure 2 and Figure 3 is an example of two systems that will never reach a deadlock state.

Figure 1: A System with Deadlock

Figure 2: A System without Deadlock

Figure 3: Another System without Deadlock

Notes

For Figure 1, the transitions related to Process 1 (Process 2) are:

T0 (T4) – get 1 resource unit.
T1 (T5) – get 1 resource unit.
T2 (T6) – process critical section.
T3 (T7) – return 2 resource units.

For Figure 2, the transitions related to Process 1 (Process 2) are:

T0 (T4) – get 1 resource unit.
T1 (T5) – get 1 resource unit.
T2 (T6) – process critical section.
T3 (T7) – return 2 resource units.
T8 (T9) – return 1 resource unit.

For Figure 3, the transitions related to Process 1 (Process 2) are:

T0 (T3) – get 2 resource units.
T1 (T4) – process critical section.
T2 (T5) – return 2 resource units.

For the PDF version of this reply, Figure 1, Figure 2 and Figure 3 are interactive, dynamic diagrams.

References

Chionglo, J. F (2015). "A Reply to "For a given certain situation how to prove that the system will never get into the state of deadlock" at Computer Science Stack Exchange". Available at http://www.aespen.ca/AEnswers/OnMWQ1449933168.pdf

“For a given certain situation how to prove that the system will never get into the state of Deadlock” (2015). Mathematics Stack Exchange. Retrieved on Dec. 2, 2015 at For a given certain situation how to prove that the system will never get into the state of Deadlock.


Finding Shortest Paths of weighted graph using stacks I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall algorithm it is kinda of possible, but unfortunately I'm only allowed to use stacks (instead of matrices). I also looked for Dijkstra's algorithm but I could not get the relationship with my problem.

Clearly my aim is to get all shortest paths from one point to another one. As I mentioned I will just output the solution from my stack in a vector string. I guess I have to visit each node and what I am most afraid is of getting stacked in a loop or even loosing the track during the search.
Also note that this is not a directed graph. If  Dijkstra's algorithm is applicable here I would be very grateful if anyone of you would guide me and I would really appreciate any help, suggestion, idea or even a vision for not getting stacked in a loop or loosing the track while searching.

Thanks in advance.

As with most graph searching algorithms, you have to keep the state of each node during the searching. The state would have following values: white, gray, black with following interpretation:

white = node has not yet been discovered during the current search, or it is unreachable.
gray = node that was discovered, but not yet processed by the search algorithm.
black = reachable nodes in your graph, that the search algorithm has discovered and also processed.

This labeling ensures that you do not search in endless loops.

To get all shortest paths from a node s to another node e:

mark all nodes nodes as white.
then as you visit nodes you label them gray and put them on the stack.
If you processed all neighbours of a node, you label it black.
To recover all the shortest paths from s to e, you need to maintain an array, call it parents, i.e. parents(v) = u, meaning v was visited from u.

After you searched the whole graph, you proceed backwards from the end node e via the parents array, to get all the shortest paths from the starting node s.


How do i simplify this SOP expression? Hi i have derived the following SoP (Sum of Products) expression , by analyzing the truth table of a 3 bit , binary to gray code converter. I ask for verification, because i feel as though this answer may not be correct or complete.

  X = a'bc' + a'bc + ab'c' + ab'c

which, using k-maps, was simplified to

  X = ab' + a'b

Is this correct  ?

You can verify that the two expressions are equivalent by using some logical equivalences. Below I'm using 1 to represent true.
$$\begin{align}
a'bc'+a'bc + ab'c'+ab'c &= (a'bc'+a'bc) + (ab'c'+ab'c) &\text{associativity of } +\\
 &= a'b(c'+c) + ab'(c'+c) &\text{distributivity, twice}\\
 &= a'b(1) + ab'(1) &\text{inverse for }+\\
 &= a'b + ab' &\text{identity for }\cdot
\end{align}$$


lw and sw hazards example MIPS The below example confused me:

lw $r0, 4($r0)
sw $r0, 4($r0)
add $r0, $r0, $r0

Using MIPS 5 stage execution what are the hazards we have 1) without forwarding 2) with forwarding only in the stage of execution (exe or alu) 3) with forwarding. Add nops to eliminate hazards.

The hazard stems from the fact that the lw instruction updates register \$r0 at the 5th stage of the pipe (write-back) while the sw and the add instructions require the updated data at the 2nd stage of the pipe (decode/read).

Putting everything on a single time line (assuming the lw execution begins at time $t=1$), the correct value of \$r0 will be available not before $t=4$ and the other instructions must be stalled (at the decoding phase) until this data is available. After $t=4$ a forwarding unit can be used to forward the data to the correct place, e.g., to the execution stage for the sw or to the decoding stage for the add (if needed).


SIMD computational model Flynn's taxonomy contains three interesting computer architectures: SISD, SIMD, MIMD.

For the SISD architecture, we have RAM computational model that simulate real SISD systems very well;
For the MIMD architecture, there is PRAM computation model that is capable to highlight main benefits of the parallel processing units that operate on the different part of a dataset (though, this model can't cope with the complexity of the real world parallel programs).

Are there any nice computational model for SIMD architecture?

I've found that Blelloch writes a book about data-parallelism: Vector models for data-parallel computing. In this work, he introduces a vector memory model (V-RAM). This model extends simple RAM with additional vector memory, that available to store an unlimited amount of homogeneous simple data types. Also, there is a vector processor that is capable to perform some "simple" operations with the vectors. Blelloch has a nice definition of the simple operation: he allows to use operations, that can be implemented in $O(n)$ time on RAM and also these operations must be contained in the $NC^1$ class of the boolean circuits.

This model is a very high level, but I think that it depicts the structure of SIMD processing more deeply than PRAM. Also, this model quite interesting by itself, because it wraps almost all parallel interaction of algorithm in the primitives and description of algorithms is purely sequential.

Does anyone know about the future of this model? Does it evolve or just stuck and no progress in done in this direction?


Proving correctness of the Newton's Method for finding the square root of a number I'm trying to prove the correctness of this simple square root calculation algorithm using SPARK:

Y := X / 2.0;
while abs (X - Y ** 2) > Tol * X loop
    Y := 0.5 * (Y + X / Y);
end loop;
return Y;

The preconditions are that both X and Tol are greater then zero and the postcondition is simply the opposite of the while loop's condition.

Are there any invariants of the loop above that may help? Or maybe a different algorithm (eg. bisection) would be a better choice? So far I've tried showing that the value of the square root is always between Y and X / Y but that didn't get me anywhere.

I suggest you take some example values and see the pattern how Y actually changes. Observe that at the first iteration of the loop, Y may be too small, but only on the first iteration. Then you should see how Y changes after that.

With that, you should find a much stronger loop invariant that lets you actually prove convergence (if TOL is small enough and we ignore arithmetic overflow).


Using integer programming to find a solution without optimizing it Oftentimes I find myself wanting to use integer programming to find a solution to a particular problem, without caring about optimizing a certain variable at all.

I've found that most packages that offer integer programming do not provide this feature.

Is it then correct to assume that maximizing/minimizing a solution is no harder than just finding any solution?

If yes, does it matter what variable you choose to optimize for (considering you really do not care either way)?

If not, why do packages almost never offer to only solve rather than optimize?

There is at most a pseudo-logarithmic gap between the complexity of optimization and simply finding a feasible solution.
We can turn any optimization problem into a feasibility problem by simply adding the optimality expression to the inequalities with some value $C$, and using binary search to find the optimal $C$.


Why does making a seemingly insignificant edit to an executable's machine code return errors? First of all, I would like to apologize if this question is in the wrong section. For all I know, it could be placed in Super User, Reverse Engineering, or Stack Overflow.

Now lets get back the experiment I tried:

What I did was took an executable file and changed its file type to a text document type. Then I opened this file in a text editor and changed a single character. This character was just part of some descriptive copyright information. After this I changed the file type back to an executable file type and tried running it. Why does the Windows operating system return the error, "The version of this file is not compatible with the version of Windows you're running...", when attempting to run the executable?

What is happening underneath the hood when an executable runs?

When you open an executable in a text editor then the editor reads the contents in some lossy way - even if you haven't changed anything then the file would be different. Binary files contain non-printable characters (those with ASCII codes from 0 to 31), and these could be deleted by the text editor (other than CR/LF), especially the 0 character. Also, Windows text editors would convert CR (the UNIX new line convention; 0D) to CR/LF (the Windows convention; 0D 0A).

If you're curious what went wrong in your case, try to compare the files byte by byte and see where the differ. You could use a "hex editor", which is what you should have used to modify your file in the first place. These editors don't mishandle your files.


Showing a language is context free. Use PDA or CFG? I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it.

Show language $L$ is context free, where $L = \{\text{all strings where middle two symbols are the same}\}$

For this problem, it's easier to come up with a CFG than it is to invent a PDA. First, notice that the strings should all be of even length, otherwise it's not clear what "middle two symbols" should mean. Here are some hints to get you going.

Hint 1. Could you have grammar rules $T\rightarrow (something)$ which would generate all strings $xx$, where $x$ is a symbol from your alphabet?

Hint 2. If you had a start variable $S$, could you make productions of the form $S\rightarrow (symbol_1)\; S\; (symbol_2)$ that would generate all sentential forms $\alpha\;S\;\beta$ where $\alpha$ and $\beta$ can be any strings over your alphabet and have the same length?

If you can do these two tasks, the CFG is easy.


Questions about amortised analysis As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the concept of amortised analysis. What is amortised analysis and how to do it? In our lecture notes, it is stated that "amortised analysis gives bounds for the "average time" needed for certain operation and it can also give a bound for the worst case". That sounds really useful but when it comes to examples, I have no idea what I have to do and even after having read the sample solution, I have no idea what they are doing.

  Let's add up 1 in base 2, i.e. 0, 1, 10, 11, 100, 101, 110, 111, 1000, ... Using amortised analysis, show that in each step only amortised constantly many bits need to be changed.

(the exercise originally is in German, so I apologise for my maybe not perfectly accurate translation)

Now the standard solution first defines $\phi(i) := c \cdot \# \{\text{1-bits in the binary representation}\}$ for some constant $c > 0$. I think this is what is called the potential function which somehow corresponds to the excessive units of time (but I have no idea why I would come up with this particular definition). Assuming that we have to change $m$ bits in the $i$-th step. Such a step always is of the form

$$\dots \underbrace{0 1 \dots 1}_m \to \dots \underbrace{1 0 \dots 0}_m.$$

This statement is understandable to me, however again I fail to see the motivation behind it. Then, out of nowhere, they come up with what they call an "estimate"

$$a(i) = m + c(\phi(i) - \phi(i-1)) = m + c(-m + 2)$$

and they state that for $c=1$, we get $a(i)=2$ which is what we had to show.

What just happened? What is $a(i)$? Why can we choose $c=1$? In general, if I have to show that in each step only amortised constantly many "units of time" are needed, does that mean that I have to show that $a(i)$ is constant?

There are a few other exercises regarding amortised analysis and I don't understand them either. I thought if someone could help me out with this one, I could give the other exercises another try and maybe that'll help me really grasp the concept.

Thanks a lot in advance for any help.

Let $a_i$ be the amortized costs of operation $i$, $c_i$ be the actual costs of operation $i$, and $D_i$ the data structure after operation $i$. The amortized costs of an operation  are defined as
$$a_i:=c_ i+ \Phi(D_i) -\Phi(D_{i-1}).$$
You usually assume the following

The potential is always positive, that is $\forall\colon i \Phi(D_i)\ge 0$,
In the beginning the potential is 0, that is $\Phi(D_0)=0$.

These two assumptions are not always necessary but they are commonly used and make the life easier. Now you can consider the potential at costs that have already been paid by previous operations.

To justify this definition consider the accumulated costs of all operations. We get the following telescoping sum
$$
\sum_{i=1}^n a_i = \sum_{i=1}^n (c_i +\Phi(D_i) -\Phi(D_{i-1})) = \Phi(D_n) -\Phi(D_{0}) + \sum_{i=1}^n c_i \ge \sum_{i=1}^n c_i.
$$
So you see that the sum of the amortized costs exceeds the total actual costs. Hence the amortized costs give an upper bound.

I have not seen the use of the $c$ in your formula. But the $c$ can be simply added to the potential function $\Phi$. So think of the $c$ as a factor that weights the potential, and be redefining the function $\Phi$ you can get rid of it.

So to answer your concrete questions. $a(i)$ denotes the amortized costs for the $i$th operation, that is the actual costs in a sequence of operation charged to operation $i$. The $c$ is some positive factor you can pick. And the $a(i)$s are not constant in general (they are in your example) - you don't have to show anything for the $a(i)$ costs, the values $a(i)$ are the result of your analysis.

Since you seem to speak German, you might also have a look at my German class notes to the potential function.


What is partial expansion in Monte Carlo Tree Search? I'm trying to understand the modification to the MCTS algorithm called Partial Expansion.

From what I've been reading it enables one to not require all child nodes to have been expanded before expanding grandchild nodes.

However, I'm having a hard time conceptually understanding this process and its potential benefits. Can anybody please help me out?

Partial expansion is a pruning/reduction strategy. Instead of requiring all children to be explored in selection you could set a threshold like done in "Move Count Pruning" (MCP) based on only expanding the first 10 children only. Usually you call ucb_sample if all children are explored depending on your weights.

Another example could be based on the rollout. Even rollouts need full expansion and odd rollouts need only MCP. This way the tree gets explored in a different way.

Benefits usually come in reducing time and favouring early moves. Early moves get more time and those nodes get better statistics. With backpropogation grandchildren help update their parents because statistics exist.


Is this problem NP-Complete (Bin packing with seperable items and penalty)? The problem is a bit like bin-packing, so I'll describe it with similar naming:

You have $N$ bins, with the same size, $V$, where $V$ is a positive integer
This problem has items, and also "pieces" of items: each item is considered a piece, and each piece must always have a "valid size": size must be a positive integer
You have a set, $S_1$, of items that must all be placed into bins, but can be seperated into "pieces" of any valid sizes (ie. the sum of the sizes of the pieces of an item must always equal the original size of the item)
You have a second set, $S_2$, with non-seperable items of all the same size, $F$, where the cardinality of this set is sufficiently large / unbounded
If you place any piece from $S_1$ into a bin you must also place exactly one item from $S_2$ into the same bin

Given an instance is it possible to place all elements from $S_1$ into the bins without exceeding the capacity of the bins?

More simply put: Is bin-packing still NP-Complete if you allow for items to be separated into pieces, but there is a "penalty" for having more pieces in each bin, where you're forced to place a "filler" between each piece in a bin?

I've considered trying to reduce from bin-packing, scheduling, 3-partition, 3-col, 3-SAT, TSP, but I can't think of a way to do it. Also, in trying to solve the problem in poly time. I can only think of approximation algorithms such as greedily placing the largest item in the bin with the largest remaining capacity.

Any answers or observations on this would be very appreciated.

We can reduce from 3-Partition. In 3-Partition instance we have:

A set, $S = \{ s_1, s_2, ..., s_n \}, n = 3m$, where $m$ in a
positive integer
$B = \sum_{ i = 1 }^{ n } \frac { s_i } { 3 }$
$\frac { B } { 4 } < s_k < \frac { B } { 2 }$, $\forall k
   \in \{ 1, ..., n \}$

Where the problem is whether $S$ be partitioned into m triples such that they all have the same sum, $B$.

To reduce from my problem, let:

$N = m$
$F$ may be set to anything
$V = B + 3F$
$S_1 = S$, ie. the values from the 3-Partition instance become the item sizes in the new problem

In the reduced problem the total space available is:

size of each bin $\times$ number of bins

$ = (B + 3F) m $

$ = Bm + 3mF $ (1)

And the total space that the items will occupy is at least:

Sum of item sizes from $S_1 +$ number of pieces, $p$, from items $S_1 \times$ size of items in $S_2$

$ = Bm + pF $ (2)

We know that:

$ p \geq n = 3m $ (3)

and

total space occupied $\leq$ total space available:

(1),(2) $\Rightarrow Bm + pF \leq Bm + 3mF $

$\Rightarrow p \leq 3m $

(3) $\Rightarrow p = 3m $

Implies that for the reduced problem to be satisfiable then all the available bin space is occupied by the items, and that it's not possible to separate any of the items from $S_1$ into smaller pieces. (4)

It's clear now that this is equivalent to the 3-partition problem, but I've shown it below:

If a 3-partition problem is satisfiable then there exists corresponding triplets in the reduced problem that can be placed into each of the separate bins with exactly $3F$ remaining in each to allow for the required items from $S_2$. Hence 3-partition $\Rightarrow$ reduced problem. (5)

Because $\frac {B}{4} < s_k$ from the original 3-particiation problem, and item sizes in $S_1$ correspond to the values in $S$ (from 3-partition), we know that if we place more than 3 items in a bin that we exceed the capacity of the bin:

$s_{1,k} > \frac {B}{4}$

If we place $x$ items into a bin, where $s_{min}$ is the size of the smallest item:

total size of bin used for $x$ items $ = x ( s_{min} + F )$ (6)

Because $\frac {B}{4} < s_k$ from the original 3-particiation problem, and item sizes in $S_1$ correspond to the values in $S$ (from 3-partition):

$ s_{min} > \frac {B}{4} $ (7)

(5), (6) $ \Rightarrow$ total size of bin used for $x$ items $ > x ( \frac {B}{4} + F )$

$\Rightarrow$ total size of bin used for $x$ items $>$ total capacity of bins $ = B + 3F $, $ \forall x > 3 $

$\Rightarrow$ A satisfiable solution to the reduced problem has no more than 3 items in any bin. (8)

Likewise, because $s_k < \frac {B}{2}$ from the original 3-particiation problem:

$ s_{max} < \frac {B}{2} $

$ \Rightarrow$ total size of bin used for $x$ items $ < x ( \frac {B}{2} + F )$

$\Rightarrow$ total size of bin used for $x$ items $<$ total capacity of bins $ = B + 3F $, $ \forall x < 3 $

(4) $\Rightarrow$ A satisfiable solution to the reduced problem has no fewer than 3 items in any bin. (9)

(8), (9) $\Rightarrow$ A satisfiable solution to the reduced problem has exactly 3 items in each bin. (10)

If any reduced problem is satisfiable: We know from (4) that the items cannot be separated; we know from (10) that each bin contains exactly 3 items.

$\Rightarrow$ The triples from each bin (items from $S_1$) have sizes that sum to $B$, and that the sizes for each item in $S_1$ have a one-to-one correspondence to the values in the set $S$. Therefore there is a partition of the $S$ set into triples, where each of the triples sums to $B$. Hence reduced problem $\Rightarrow$ corresponding 3-partition problem. (11)

So long as we accept that the problem from the question is in NP (I'm not going to prove this!) (5), (11) $\Rightarrow$ the problem from the question is in NP-Complete.


Finding the regular expression equivalent for the given finite automaton This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression.

On inspecting the given automata, I started deducing the expressions that it accepts and tried to find a pattern, and this is what I was able to figure out -

The automata makes the following transitions to a final state upon said input -

$q_1 to \ q_3$ on input of a single symbol $b$, $a^*b$, $ba^*$, or $a^*ba^*$.
Traversing through the cycle $q_1,q_3,q_2$ (and so on repeating) on input of  $(a^*b^4a^*)^*$, a  $((a^*b)^4)^*$.

Now the equivalent regular expression must be the sum of all these expressions,

R = $b + (a^*b) + (ba^*) + (a^*ba^*) + (a^*b^4a^*)^* + ((a^*b)^4)^*$.

Is there a better, concise expression for this or am I missing something? If not, How do I approach the simplification process of this expression?

Your DFA accepts the language of all words over $\{a,b\}$ in which the number of $b$s is of the form $3n+1$ (i.e., it is equivalent to 1 modulo 3). More generally, upon reading a word $w$, the DFA will be in state $q_1$ if it read a number of $b$s which is a multiple of 3; in state $q_3$ if it read a number of $b$s which is equivalent to 1 modulo 3; and in state $q_2$ if it read a number of $b$s which is equivalent to 2 modulo 3.

Using this description, it is easy to come up with a regular expression equivalent to your DFA. Rather than do that, let me give regular expressions for the language $L_{even}$ of words over $\{a,b\}$ containing an even number of $a$s, and for the language $L_{odd}$ of words over $\{a,b\}$ containing an odd number of $a$s:

$L_{even}$: $b^*(ab^*ab^*)^*$.
$L_{odd}$: $b^*ab^*(ab^*ab^*)^*$.

These examples should enable you to solve your specific problem.


What is the difference between "information model" and "conceptual model"? I am trying to figure out the difference between information and conceptual models. For me, both terms seem to mean be the same, but I cannot find a reference where this is established. They are never used together; maybe because they are from different domains?

My question is: What is the difference between information model and conceptual model?

Definitions

Conceptual model:

  A domain consists of objects, relationships, and concepts we commit
  ourselves to a specific way of viewing domains. [...] In the field of
  information systems, this commitment to viewing domains in a
  particular way is called the conceptual model. [Antoni Olivé. 2007.
  Conceptual Modeling of Information Systems. Springer-Verlag, Berlin,
  Heidelberg.]

Information model:

  An information model is a representation of concepts, relationships,
  constraints, rules, and operations to specify data semantics for a
  chosen domain of discourse. The advantage of using an information
  model is that it can provide shareable, stable, and organized
  structure of information requirements for the domain context. [Y. Tina
  Lee, Charles R. McLean and Yan Luo, Information Modeling and Model
  Implementation. In: Proceedings of the International Simulation
  Conference, Italy, 2006]

Conceptual Modeling, Information Modeling and Data Modeling are all terms that more or less specify the same. I do not believe there is a common consensus about these terms.

When reading the articles of the authors you refer to, I get the impression that (for these authors) Conceptual Modeling is broader than Information Modeling.

A Conceptual Model can contain actors other than only computers (e.g. humans), can contain time aspects (e.g. events, and the required reaction to these events, called Behavioral Modeling by Olivé) and can contain concepts that will not necessarily translate into a data model (“we use the name conceptual modeling for the activity that elicits and describes the general knowledge a particular information system needs to know”).

An Information Model, as used by Lee et. al., has a more narrow scope (“The initial phase for developing an information model starts with the definition of the scope of the model’s applicability. The scope specifies the domain of discourse and the processes that are to be supported by the information model. It is a bounded collection of processes, information, and constraints that satisfy some industry need”) and his modeling seems to limit itself to a subset of the conceptual model. Lee et. al. also write their article with a particular industry in mind, manufacturing, where Olivé does not limit himself to an industry.

For example, a Conceptual Model could model a company including less tangible processes such as Strategy development an Marketing, and an Information Model could model some key process of the company derived from the conceptual model, for example purchasing and logistics.

I did not read their full article. I just did a scan to find where they apparently seem to differ and, as said, there is to my knowledge no clear consensus about what each term exactly means.


DFA for $L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv 0$ $(mod$ $5) \}$ There is a language:
$L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv  0$ $(mod$ $5) \}$. My idea for DFA is - we count number of $a$$\pmod{5}$ and separately we count number of $b$$\pmod{5}$. So we end up with $5*5=25$ states, because each state have to keep track for both number of $a$ and $b$$\pmod{5}$. Is there any better aproach to this DFA ? Because for example when we have$\pmod{10}$ we end up with 100 states. I would appreciate any sugestions.

The minimal DFA for $L$ contains 25 states, as can easily be shown using Myhill–Nerode theory.

Indeed, consider the 25 words $\{a^ib^j : 0 \leq i,j < 5\}$. I will show that when a DFA reads any two different words from this list, it cannot end up in the same state. To show this, for any two different words $x,y$ from the list, I will give a word $z$ such that $xz \in L$ but $yz \notin L$.

Let $x = a^i b^j$ and $y = a^k b^\ell$ be two different words from the list. Since $x \neq y$, either $i \neq k$ or $j \neq \ell$ (or both). Assume without loss of generality that $i \neq k$. Take $z = a^{5-i} b^{5-j}$. Then $|xz|_a = |xz|_b = 5$, and so $xz \in L$. In contrast, $|yz|_a = 5-i+k \not\equiv 0 \pmod{5}$, since $i \not\equiv k \pmod{5}$ by assumption, showing that $yz \notin L$.


Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most There are $n$ elements in a hash table of size $m \geq 2n$ which uses open addressing to avoid collisions.

The hash function was chosen randomly among a set of uniform functions. A set $H$ of hash-functions $h:U\to\{0,\dots,m-1\}$ is called uniform, if for every tuple of different keys $x,y \in U$ the number of hash-functions $h \in H$ with $h(x) = h(y)$ is $\frac{|H|}{m}$ at most.

Show that the propability that for $i = 1, 2, \dots,n$ the $i$-th insert operation needs more than $k$ attempts, is $2^{-k}$ at most.

This is an assignment, which I got as homework. What I already worked out:

The propability $p_1$ for a collision is 0 of course for an empty table.

The propability $p_i$ for a collision after k attempts should be $\frac{i - 1}{2n}\cdot k$ assuming that the table is filled with $i-1$ elements to this point and the tables size is $2n$ as worst case.

So I have
$$
p_i= \frac{i-1}{2n} \cdot k \leq 2^{-k},
$$

but I don't know where to go from here.

The method of open hashing used here simply iterates over different hash-functions until a free place is found (for example $h(x) = (x \bmod j) \bmod n$ with increasing prime numbers for $j$.

Hint: Show that at a given value of $i$, the probability of failure of the $l$th attempt is at most $i/m \leq 1/2$ (perhaps using a union bound), and the events are independent for different attempts.


Overflow safe summation Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$.

It seems to me that we can always permute the numbers to $b_1, b_2, \dots b_n$ such that each prefix sum $S_i = b_1 + b_2 + \dots + b_i$ also fits in a register of width $w$.

Basically, the motivation is to compute the sum $S = S_n$ on fixed width register machines without having to worry about integer overflows at any intermediate stage.

Is there a fast (preferably linear time) algorithm to find such a permutation (assuming the $a_i$ are given as an input array)? (or say if such a permutation does not exist).

Strategy
The following linear-time algorithm adopts the strategy of hovering around $0$, by choosing either positive or negative numbers based on the sign of the partial sum. It preprocesses the list of numbers; it computes the permutation of the input on-the-fly, while performing the addition.

Algorithm

Partition $a_1, \ldots, a_n$ into a two lists, the positive elements $P$ and the negative elements $M$. Zeros can be filtered out.
Let $Sum=0$.
While both lists are non-empty
$~~~~~~$If $Sum>0$ { $Sum:=Sum+\text{head}(M)$; $M:=\text{tail}(M)$; }
$~~~~~~$else { $Sum:=Sum+\text{head}(P)$; $P:=\text{tail}(P)$; }
When one of the two lists becomes empty, add the rest of the remaining list to $S$.

Correctness
Correctness can be established using a straightforward inductive argument on the length of the list of numbers.

First, prove that if $a_1, \ldots, a_n$ are all positive (or all negative), and their sum does not cause overflow, then nor do the prefix sums. This is straightforward.

Second, prove that $Sum$ is within bounds is an invariant of the loop of the algorithm. Clearly, this is true upon entry into the loop, as $Sum=0$. Now, if $Sum>0$, adding a negative number that is within bounds to $Sum$ does not cause $Sum$ to go out of bounds. Similarly, when $Sum\le0$ adding a positive number that is within bounds to sum does not cause $Sum$ to go out of bounds. Thus upon exiting the loop, $Sum$ is within bounds.

Now, the first result can be applied, and together these are sufficient to prove that the sum never goes out of bounds.


Finding the most frequent element assuming $\Theta(n)$ frequency We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(n \log(n))$ time to find the most frequent element (assuming the domain of the array elements is not small).
But what happens when you know that there's an element with frequency at least $\alpha \cdot n$? Can you then decide the problem, or determine what the element is, in linear time (in $n$, not necessarily in $1/\alpha$) and deterministically?

Here is an algorithm for all $0<\alpha\leq 1$. I'm assuming your data can be ordered and that comparing two elements is done in constant time.
Run a few levels of the quick-sort recursion (choosing the pivot optimally in linear time with the Median of Medians algorithm) until you have partitioned the elements into "buckets" $B_1,\ldots, B_m$ each of size $\frac{\alpha n}{4} \leq |B_i| \leq \frac{\alpha n}{2}$, where all elements in $B_i$ are smaller or equal to all elements in $B_{i+1}$.
This will take $O(n\log(1/\alpha))$ time.
Now notice that because the relative majority element $e$ is present at least $\alpha n$ times and each bucket has at most $\frac{\alpha n}{2}$ elements, the majority element needs to fill at least one of the buckets completely. Thus $e$ is also  the first element in some bucket.
Notice also that there are at most $4/\alpha$ buckets as each bucket contains at least $\frac{\alpha n}{4}$ elements. Thus you can pick the first element in each bucket, and choose the element with maximum frequency among those in $O(n/\alpha)$ time.
Thus, you can find that relative majority element $e$ in $O(n\log(1/\alpha) + n/\alpha) = O(n/\alpha)$ time.


Two-way finite automaton: How does the automaton remember the state I have been going through a theory of Two-way finite automatons and I did not understand the given example when there were a DFA A = (Q, Σ, δ, q1, F). the 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#}, δ|, q0, {qF}) and a following language  L = { #u# | uu ∈ L(A)}. In following paragraph  I will describe how would it works, if we are reading a word that belongs to the language. In the first procedure automaton B follows the states of automaton A, when it reach right '#', it stops, remember the accepting state and starts to move back through the copied states of automaton A: Q| as long as it come to right '#'. Afterwards it starts moving on through the copied states Q|| of automaton A, and once it reaches out the right '#' checks if it is the saved accepting state. Image below shows the movements where qN is a failing/non-accepting state and +1 movement of head to right and -1 movement of the head to left.

Question

How does the 2-DFA remember that it reached out during first walk through the states of automaton A the accepting state for the second walk?

Here is a simpler example, for NFAs.

We will show that if $L_1,L_2$ are regular languages over disjoint alphabets $\Sigma_1,\Sigma_2$, then so is the following language over $\Sigma = \Sigma_1 \cup \Sigma_2$:
$$
L = \{ xyz : x,z \in \Sigma_1^*, y \in \Sigma_2^*, xz \in L_1, y \in L_2 \}.
$$
Here is the idea. Start with DFAs $A_1,A_2$ for $L_1,L_2$. We will construct a DFA for $L$ which acts as follows. It starts by simulating $A_1$. When it encounters a symbol from $\Sigma_2$, it remembers the state that $A_1$ is in, and switches to $A_2$. When it encounters a symbol from $\Sigma_1$, it switches back to $A_1$, assuming that $A_2$ is at an accepting state. It goes to a failure state if it encounters a letter from $\Sigma_2$ again.

Here are the details, showing how we implement remembering the state of $A_1$.

Let $A_1 = \langle Q_1,\Sigma_1,q_{01},\delta_1,F_1 \rangle$ and let $A_2 = \langle Q_2,\Sigma_2,q_{02},\delta_2,F_2 \rangle$. We construct a new DFA $A = \langle Q,\Sigma,q_0,\delta,F \rangle$ as follows:

The set of states is $Q = (Q_1 \times \{1\}) \cup (Q_1 \times Q_2) \cup (Q_1 \times \{2\}) \cup \{q_f\}$. States in the first part will be used to simulate $A_1$ before a symbol from $\Sigma_2$ is ever encountered. States in the second part will be used to simulate $A_2$ while remembering the state of $A_1$. States in the third part will be used to simulate $A_1$ after reading the $y$ part. The final state will handle various modes of failure.
The initial state is $(q_{01},1)$.
The transition function is defined as follows:

If $\sigma \in \Sigma_1$ then $\delta((q,1),\sigma) = (\delta_1(q,\sigma),1)$: we just advance $A_1$.
If $\sigma \in \Sigma_2$ then $\delta((q,1),\sigma) = (q,\delta_2(q_{02},\sigma))$: we remember the state of $A_1$, and advance $A_2$.
If $\sigma \in \Sigma_2$ then $\delta((q_1,q_2),\sigma) = (q_1,\delta_2(q_2,\sigma))$: we advance $A_2$, while keeping the state of $A_1$ intact.
If $\sigma \in \Sigma_1$ and $q_2 \notin F_2$ then $\delta((q_1,q_2),\sigma) = q_f$: the $y$ part is not in $L_2$, so we signal failure.
If $\sigma \in \Sigma_1$ and $q_2 \in F_2$ then $\delta((q_1,q_2),\sigma) = (\delta_1(q_1,\sigma),2)$: we go back to simulating $A_1$.
If $\sigma \in \Sigma_1$ then $\delta((q_1,2),\sigma) = (\delta_1(q_1,\sigma),2)$: we just advance $A_1$.
If $\sigma \in \Sigma_2$ then $\delta((q_1,2),\sigma) = q_f$: the input is malformed, so we signal failure.
For all $\sigma$, $\delta(q_f,\sigma) = q_f$.

The final states are $(F_1 \times \{1\}) \cup (F_1 \times F_2) \cup (F_1 \times \{2\})$. The first part handles the case $y=z=\epsilon$, the second handles the case $y\neq\epsilon$ and $z=\epsilon$, the third handles the case $y,z \neq \epsilon$.

Hopefully this explains how a DFA can commit a piece of information to memory. Since a DFA has only finitely many states, it can only store a constant amount of information.


Does Turing machine have no shift? In a Turing machine I read that it can go only right or to left. But in my book [elements of theory of computation, Book by Christos Papadimitriou and Harry R. Lewis ] it says that Turing machine operates in two discrete steps
1) put the control unit in new state.
2)Either: replace the symbol already there by the symbol currently scanned. Or
Move read/write head one tape square left or right

In many online tutorials they say you must move read/write head right/left but you may not change state

Can someone please clear the doubt

There are a lot of slightly different definitions of Turing machines out there! They usually differ in small but subtle ways. For example, some authors say that a Turing machine's head moves left or right, and writes the symbol; some authors say that it can also stay still. You have seen that Papadimitriou and Lewis allow either replacing the character on the tape, or moving left or right, which is slightly different than both replacing the character on the tape and moving left or right.

That sounds like bad news, but the good news is that you can prove that all of these different definitions are equivalent. Your textbook will have some exercises related to that. For example, we can prove:

That Turing Machines that can move left, right, or stay still are equivalent to ones that just move left or right.

Proof Idea: The Turing Machine that can only move left or right can "mimic" staying still by first moving one step to the right, then moving one step to the left. It takes $2$ steps instead of $1$, but it does the same thing.
That Turing Machines that move the head OR write a symbol are equivalent to those that move the head AND write a symbol at each step.

Proof Idea: the one that moves-or-writes can simulate the behavior of the one that moves-and-writes by first writing, then moving. So it takes $2$ steps instead of $1$, but it does the same thing. On the other hand, the one that moves-and-writes can simulate the behavior of the moves-or-writes one as follows: in order to move without writing, it should write the same symbol that is already on the tape (so that the write has no effect). And in order to write without moving, it should move left and then right, so that there is no net effect.


How do Hard Drives Send and Recieve Data? Ok. I know this is probably a commonly asked question. Before you refer me to a site or answer this yourself, I ask for you to please read this through. I have been into computers and electronics for quite a while. I have a pretty good understanding of electronics, and would like to become a computer hardware engineer eventually. For quite a while now, I have been searching for an answer to my question: How to hard drives send and recieve data, and in general, how do they work? Every site I find, simply explains the basics, of which I already am quite familiar with.

An example of what I am trying to figure out: Suppose you want to save a very small file (less than 1KB for simplicity) to a hard drive. Is there a site that explains exactly what information is exchanged between the hard drive and the rest of the computer? I would like to understand what is sent, and when it is sent ( down to ones and zeros ). I would eventually like to know enough information that, in theory, I could build a small storage device compatible with a modern computer. The more information, the better.

As it stands, this isn't a Computer Science question. Actually, it's several questions, some of which could be phrased of as computer science questions.

Disk-like devices (these days we'd include flash memory) do not understand the concept of a "file" or "directory". You can think of a disk as a big array of fixed-size blocks. The two basic operations are "read a block" and "write a block". Files are an abstraction on top of this implemented by the operating system.

All of this is explained in any operating systems course. But if you just want the short version, I recommend Maurice Bach's classic book The Design of the UNIX Operating System. It doesn't reflect modern operating systems or filesystems that well, but it will give you a good idea about what operating systems do and what they expect of a disk device. If that wasn't enough for you, Practical File System Design by Dominic Giampaolo is a whole book which gives an in-depth look at a more modern filesystem design.

The hardware that sits between there and the disk is a topic all by itself. On a modern system, disks can be connected to a computer using a variety of different hardware connection (e.g. USB, SATA, SCSI), and a modern operating system needs to both be able to talk to the host controller for this bus, but also be able to tell what is attached to the bus. For some busses (e.g. USB) there may be a complex topology for the operating system to discover; the disk may be connected via a hub, for example.

The final link in the chain is what lies between the bus and the storage medium itself, and this is presumably what you're interested in.

My suggestion, if hardware engineering is what you're most interested in, is to hook a simple computer (e.g. a microcontroller) up to a simple storage device (e.g. MMC) and see what you can do. You will learn a lot this way.

As a final comment, there is a book by Jan Axelson called USB Mass Storage: Designing and Programming Devices and Embedded Hosts. I can't recommend it because I haven't read it, but it looks like the sort of thing you might want to know. If I'm reading the table of contents correctly, it looks like it gives you everything you need to know to build a USB flash drive. That sounds like a fun project to me.


Find Length of longest substring with all 1's in a binary string with k queries Given a string of size n consisting of 0s and/or 1s.you have to perform k queries and there are two types of queries possible.

"1"(without quotes): Print length of the longest substring with all '1'.
"2 X"(without quotes): where X is an Integer between 1 to n.In this query, you will change character at Xth position to '1' (it is possible that the      character at ith position was already '1')

Input Format:

First Line of input contains n and k, where n is string length and k is the number of queries.
Next line contains a string of 0's and/or 1's of length n.
Each of next k lines contains query of any one type (i.e 1 or 2).

Output Format: For each query of type 1, print in new line the maximum size of subarray
       with all 1's.

     Example Input:                        Example Output:
     5 7                                   0
     00000                                 1
     1                                     1
     2 3                                   3
     1
     2 5
     1
     2 4
     1

My Solution: O(k*n) (if most of the queries of type 1)

 if(type==1){
        int count=0, ans=0;
        for(int i=0;i<str.size();i++){  //longest len substring
            if(str[i]=='1'){
                count++;
            }else{
               ans=max(ans,count);
               count=0;
            }
        }

        printf("%d\n",ans);
 }else{
        int xth;
        scanf("%d",&xth);
        str[xth-1]='1';   //update
 }

I am not able to figure out an efficient solution, as for 'type 1' query only solution I could think of is to iterate through string every time and maintain a "count" variable with all 1's consecutively and finally update "ans" variable when ith str becomes '0'.

I am thinking of using segment tree but don't know how to do. As required good solution should be O(k*log(n)) (doing "type1" query in log(n) time)

Observation: Type 2 query can only make the longest substring of 1 longer.

Let's call a substring of 1's a component. For example, there are 3 components in this string

1 1 1 0 0 1 0 1 1 1 1 0

When a 0 is changed to 1, only the components to its immediate left and right will be affected. The length of the other components remains the same.

string: 1 1 1 0 0 1 0 1 1 1 1 0
size  : 3 3 3 0 0 1 0 4 4 4 4 0

update position 7 to 1 (1-index)
string: 1 1 1 0 0 1 1 1 1 1 1 0
size  : 3 3 3 0 0 6 6 6 6 6 6 0

Hence, all you need to do is to keep track of the size of each component and merge them when necessary. You can do so using a Union-Find Disjoint Set data structure. You can have a variable to keep track of the size of the largest component and update its value if, after the merge, you get a larger component.


How to extract randomness from a file? I have a generator of files with approximately 7 bits /byte entropy. The files are about 30KB each in length. I'd like to use these as sources of entropy to generate random numbers. Theoretically I should be able to achieve about 26 KB (max) of randomness per file.

This is a hobby and I know about hashes, but they're primarily checksums.  I'm looking for more sophisticated methods of extraction designed specifically for that purpose. I'm hoping to use this as a true random number generator.

Supplemental:

Following comments, and in order to solicit non hash based responses, I'm evaluating the following architecture...

It works like this:-

The entropy is the 30KB file

The compressor reduces the entropy to a target size of 26KB

A seed is derived from all of the bytes of the entropy

Some PRNG implementation produces 26KB of pseudo random output

The two outputs are xored together to produce true random numbers

So in summary, a 30KB file of 86% entropy is manipulated into a 26KB file of 100% entropy.  Entropy is preserved throughout the extraction process, and all the output is totally dependant on the input.  26KB of full entropy goes in, and 26KB of full entropy comes out.

I suggest that this is a good method to extract entropy from complete files.  Or not.

In practice, in about 95% of cases, the correct answer is probably going to be: forget about those files, use /dev/urandom or CryptGenRandom() (or equivalent).  They provide very high quality random numbers -- That's what they're designed for.  So this is the most pragmatic answer, and it will provide excellent quality randomness.

Let's say you can't do that, maybe because it's a headless embedded device with no access to entropy, or you want your random numbers to be a repeatable deterministic function of the files.  Then in that case the best answer is likely to be -- guess what? -- hashing.  In particular: concatenate all the files, take the SHA256 hash of the concatenation, and then use that as a key for AES-256-CTR; then use AES-256-CTR to generate as much output as you want.  This is basically using a cryptographic hash to generate a seed for a cryptographic-quality pseudorandom generator, and it satisfies all your requirements.  This is a solid answer, from the perspective of robust engineering and high quality random numbers.

OK, let's say you are a theorist.  If you are a theorist, you won't like the last answer, because it relies upon cryptographic assumptions that have not been mathematically proven to hold.  Pragmatically, you probably shouldn't worry about that -- you rely upon those assumptions every day (e.g., when doing e-commerce or entering your password into a website), and other issues are far more likely to affect you in practice -- but let's say you are a theorist.

From a theoretical perspective, the cryptographic solution is potentially unsatisfying, because it relies upon an unproven assumption, and that is... inelegant.  So, it's interesting to ask what can be achieved that will provably work.  If that's what you're interested in, you'll want to read about randomness extractors.

If you care about pragmatics, randomness extractors are probably not the best possible solution: extractors need stronger assumptions about the distribution of the data in your files, they are more limited in how much random output they can produce, and they are more fragile.  But they do come with provably good properties, and they are mathematically elegant and beautiful.


Concluding $SPACE(n^2) \neq SPACE(n^7)$ from universal turing machine running time Let $M_U$ be an universal Turing machine which fulfills the following condition:

  If $M$ running $x$ takes $f(x)$ space, then $M_U$ running on $\langle \langle M\rangle,x\rangle$ takes $(f(|x|))^3+2\cdot|x|+|\langle M\rangle|$ space.

Why can we conclude from the above that ${\sf Space}(n^2) \neq {\sf Space}(n^7)$?

I assume with ${\sf SPACE}$ you mean ${\sf DSpace}$. As usual for these types of hierarchy question you can use a diagonalization argument.

So build a machine $D$ that takes its input $w$ and then executes $M_u(\langle  w ,w \rangle)$. While executing $M_u$ it checks also how much space is used and how many steps the machine $M_u$ has done. Then the result of $D$ is the following:

if $D$ used more than $n^2$ space than reject,
if $D$ does more than $2^{cn^2}$ steps then accept (in this case the simulation detected a cycle if $\langle w \rangle$ would be a $n^2$ space bounded TM),
if none of the above occurred, then accept if $M_u$ rejected, and reject if $M_u$ accepted.

You can say that $D(w)$ anti-simulates the machine $M_u(\langle w ,w \rangle)$, if $\langle w \rangle$ is in ${\sf DSpace}(n^2)$. Clearly, $\langle D\rangle$ is in ${\sf DSpace}(n^7)$. However, it cannot be in ${\sf DSpace}(n^2)$. If it would be then you get a contradiction at $D(\langle D \rangle)$.


Object qualification algorithm I need to develop algorithm for one task.

I have 500 types of object, each type is represented by a group of qualifiers (about 20 for each type, the same qualifier can be used for different types), where qualifier is a simple predicate (but calculation of the predicate can take some time, as you have to check data in data base). When all qualifiers for particular type return true then object has such type.

For now I just came up with idea to use cache and go through all types trying to do qualification. For each type firstly I go through predicates without calculation and check that no of them failed before if some failed I skip the type, otherwise I go through qualifiers and do calculations (for each predicate I take data from cache if I did the same qualifier before).

I think may be there are some data structures for such task, or common approaches how to do that better.

A small update to the question. The classification data I have, has special structure, like not all attributes of the object mentioned for each class.

For example
Type European transaction:

Country one of DE, FR, ES
Color : Blue
Serial type: 2
Currency : EUR

Type UK transaction:

Country: UK
Serial type: 1

It just example out of my head, each object has much more attributes. The main point here that some attributes can present for some objects but not for others. So if we create data set on the objects to build qualification tree, the value of such attributes could be marked as ANY value, that way it's impossible to do qualification, since we can get to the branch where we have two ways to go.

Thanks.

Sure.  Caching is a standard optimization that can be applied in many situations.  I'm not sure there's much more to say there.

The other optimization that might be useful here is to choose the order in which you test the predicates.  I would suggest using ID3 to construct a decision tree that identifies which predicates you test, and in what order.  This may reduce the number of predicate computations you need to do, to determine the type of an object.


How to convert this DFA with multiple final states to a regular expression? (State elimination method) So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4.

I want to convert this into a regular expression using State elimination, and I know that I need to first create a new state call it 's' which replaces q0 as the start state, and then create another new state (call it 'f') which will be the new final state, and make q1, q2, q3, and q4 non-accepting states, and make epsilon transitions from the former accepting states to the new final state.

My question is, when I eliminate say q1, I don't know what the regular expression will be as a result. Now since q1 has 2 outgoing transitions 'a' to a2 and epsilon to f, what would be that regular expression? I know that for q2 it would be a(ba)a(ba) ... then q0 to f will be a(ba)*.. so far it doesn't make sense to me how this will end up becoming the correct regular expression. Am I on the right track?

When I eliminate say $q_1$, ..., now since $q_1$ has 2 outgoing transitions, '$a$' to $q_2$ and $\epsilon$ to $f$, what would be that regular expression?

Here are the transitions among the neighbors of $q_1$, which are $q_0, q_2$ and $f$ when $q_1$ is eliminated.

$\delta(q_0, ab)=q_0$
$\delta(q_0, aa)=q_2$
$\delta(q_0, a)=f$
$\delta(q_2, a+bb)=q_0$
$\delta(q_2, ba)=q_2$
$\delta(q_2, \epsilon+b)=f$

  $a(ba)^* + a(ba)^*a(ba)^*(aa(ba)^*a(ba)^*)^* + b(ab)^* + b(ab)^*b(ab)^*(bb(ab)^*b(ab)^*)*$

I am afraid the above is not correct since it does not include $abbaa$ nor $abbab$


Terminology needed for the computational solution to the Rubik's Cube I apologize if this question is out of the guidelines of this forum. If it is please let me know and I will abstain from requesting definitions and terminology.

Hello!  I am currently writing a program to find the shortest path solution in a randomised Rubik's Cube. There is a certain language/search based methodology that has caught my attention, and which I would like to apply to the solution, but I am unaware of what kind of terminology I should be looking up.

THE METHODOLOGY:

The methodology is one where different languages are developed to satisfy different aspects of the cubes solution. For instance, we might find a language/grammar which appropriately describes/generates all transformations which move one block of the cube to some position we want it to be. We may then find another language which satisfies the movement of another block to some position we want it to be. The language which satisfies both of these languages is the one which generates transformations which will move BOTH blocks to where they are supposed to be.

WHAT I WOULD LIKE TO LEARN MORE ABOUT:

It is in this sense that I am interested in learning more about how languages can be tested against each other in order to CONSTRAIN the otherwise unweildly "search tree" that would be required to be derived and searched in order to find the solution.

At the same time I would like to build a symbolic vocabulary which would allow me to compare the different pertinent variables (runtime, memory size, etc.) of different tree search constraint methodologies, particularly language based methods (as I have poorly defined them).

I am also particularly interested in the methodologies that can be used to detect patterns in the strings which are satisfying two seperate languages so that a third language which satisfies both can be developed.

Also, I would like to learn more about how we can show that one language is mutually exclusive to another language.

I am particularly interested in terminology so that I might do research on the Internet, however I would also greatly appreciate any book recommendations. Thank You!

Kociemba wrote very nice algorithm, which is the fastest working algorithm returning optimal or almost optimal solution very efficiently.

If you want to derive your own system, try in steps:
0) invent notation for the cube, do not try to optimize it.
1) try BFS or something like A* (this one will be harder, with heuristics).
2) try some kind of memoization, and state precomputation.
3) if something is not efficient step back to 0 and change type of notation.

Why should you not optimize your notation?
Because a few bytes overhead is nothing in compare to smooth transitions between states.

Honestly, pure BFS will do the job, but without any help or reductions it will be very slow. You can make encoding relative to color and put your reference point (one corner or the cross), it will decrease hashing time.
To check your approach just take several thousands of permuted cubes, count turns per cube and time it took per cube to solve.
If you are interested in AI, solving cube is doable, but guaranteed least moves will take some time.

There is Rubik Group but language induced solvers in contrary to graph or group solvers are not common, so there might be some hidden treasure there. Look at Kociemba algorithm, he does not use Rubik Cube group per se, but changes it so he has smaller number of instances.


Properties of self-dual code Let $C $ be a self-dual binary $[n,k,d]$ code.

I want to show that if $ c=(c_1, \dots, c_n) \in C $ then $ \sum_{i=1}^n c_i=0$ and that all the words of the code have an even weight.

We know that $ x \in C^{\perp} \Leftrightarrow Gx=0$ where $ G $ is the generator matrix.

Since $ C=C^{\perp}$ we have that  $ G=H $ where $ H$ is the parity matrix of the code.

So we have that $ c=(c_1, \dots, c_n) \in C \Rightarrow c \in C^{\perp} \Rightarrow Gx=0 \Rightarrow Hx=0 $

Do we get from that,  that $ \sum_{i=1}^n c_i=0$?

If so how?

By definition, the dual code $C^\perp$ consists of all words $x$ such that $\langle x,y \rangle = 0$ for all $y \in C$. If $C = C^\perp$ then in particular $\langle x,x \rangle = 0$ for all $x \in C$, which implies that $x$ has even weight.


How to prove that  $n(\log_3(n))^5 = O(n^{1.2})$? This a homework question from Udi Manber's book. Any hint would be nice :)

I must show that:

  $n(\log_3(n))^5 = O(n^{1.2})$

I tried using Theorem 3.1 of book:

  $f(n)^c = O(a^{f(n)})$ (for $c > 0$, $a > 1$)

Substituing:

$(\log_3(n))^5 = O(3^{\log_3(n)}) = O(n) $

but $n(\log_3(n))^5 = O(n\cdot n) = O(n^2) \ne O(n^{1.2})$

Thank you for any help.

Do what you did, but let $a = (3^{0.2})$... that should do it, right?

The reason that what you did didn't work is as follows. The big-oh bound is not tight; while the logarithm to the fifth is indeed big-oh of linear functions, it is also big oh of the fifth root function. You need this stronger result (which you can also get from the theorem) to do what you're doing.


Sufficient condition for simple graph isomorphism? Say I have two simple graphs, $A$ and $B$

In $A$, I know:

one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
etc.

In $B$, I know:

one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
etc.

Can I derive that graph $A$ and $B$ are isomorphic to each other? Or is there a counter-example where two graphs look the same from this distance point of view, but are not isomorphic?

It is a necessary condition, so if these simple graphs are isomorphic, they will share these distances. I am wondering if this is a sufficient condition as well.

There are two non-isomorphic graphs with 16 vertices in which each vertex has 6 neighbors and 9 vertices at distance 2: the Shrikhande graph and the $4\times 4$ rook's graph.


How to simulate natural number in Pi Calculus I have some questions about Pi Calculus:
How to simulate the natural numbers only with its primitives?
It's possible simulate the if else clauses without the sum (+)?
A minimal and standart example would be interesting.

You can encode natural numbers in π-calculus in a way that is a variant on encodings of natural numbers in untyped λ-calculus, see (1). Milner, Parrow & Walker explain how to do this in the paper (2) that introduced  π-calculus. Note that such encodings are not efficient (they are essentally unary encodings of numbers, so give rise to large terms). You only do such encodings to gauge expressive power of the untyped π-calculus. In any real implementation, you'd add numbers as a basic data-type.

Wikipedia, Church encoding.

R. Milner, J. Parrow, D. Walker, A Calculus of Mobile Processes, Part I.


How does hardware interrupt work on a physical layer I'm a newbie in computer science and would to understand how hardware interrupts work at the physical layer. I ask my question considering a specific example. When packet arrives at the network adapter, a hardware interrupt is raised. Wikipedia says that

  an interrupt is a signal to the processor emitted by hardware or software indicating
  an event that needs immediate attention.

I know that the OS will invoke a corresponding interrupt handler when
the interrupt's type is detected. But I don't understand how the CPU detects and distinguishes incoming interrupts.

First, why CPU does know that the interrupt is coming from the network adapter and not from some other device?

Second, where are interrupt handlers registered in the CPU? Are there specific areas of the CPU that contain addresses for handlers registered by the OS?

The CPU has specific pins on the outside to detect hardware interrupts.

Take for instance the 6502 used in the Apple II and c64 it has two interrupt pins:
IRQ on pin 4 and  (can be ignored)
NMI on pin 6  (cannot be ignored)

If the signal on pin 6 falls from high voltage to low voltage the CPU will perform a call to the non-maskable-interrupt handler.
It will read the contents of address $FFFE and jump to the 16-bit location contained in that address.
After it's done it will return to where execution was before and resume operation as if nothing happened.

In the interrupt handler the CPU will query its peripherals to find out which one generated the interrupt.
Usually a specific chip is connected to the interrupt pin and that chip can be queried using an INput/OUTput instruction to get the relevant info quickly. On the c64 the CIA 6526 was used.

  Are there specific areas of the CPU that contain addresses for handlers registered by the OS?

You set up the CPU so that it calls a predetermined address when it receives an interrupt.
In early CPU's this address has hardcoded in the chip. In newer chips the system kernel can change the interrupt address using a privileged instruction.

On modern processors this works the same but things are complicated because everything is virtualised.


k-means clustering with efficient point lookup? What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still efficiently lookup a point $p$ and classify it into a cluster ID (an integer)?

Obviously standard $k$-means alone is not sufficient.   Would putting the centroids of each cluster into a BSP or $k'$D-tree do the trick?  I used $k'$ there because that $k'$ has nothing to do with $k$.

Instead of the classical $k$-means algorithm where you

classify all points and then
update the center of each cluster to be the average of all points of that cluster,

you could use the sequential variant of $k$-means:

centers = random(k)
while True:
    p = next_point(points)
    c = find_center(centers, p)
    c = c + a * (p - c)

next_point iterates all the points and maybe prefers new points (online) for example by using deque and putting new points front.

find_center classifies a point. This takes $O(k)$ naive and $O(\log k)$ using a spacial datastructure like a k-d tree.

$a \in [0,1]$ says how much a center moves in the direction of the given point. Usually this is time dependent and gets lower with time, i.e. $a(t) = \lambda_1 e^{-\lambda_2 t}$. Maybe one could boost the weight of new points though.


List count of occurrences pairs, triplets, etc. from sets A receipt is an array of products. I have an array of receipts.

I need to generate a report in where I can find the products often bought together.

For instance, for a single receipt where the products bought are [A, A, B, B, B, C], a report would look like

Pair - count
A&B - 2
A&A - 1
B&B - 1
A&C - 1
B&C - 1

Notice that pair B&A is no longer counted because this is the same as A&B, and similar occurrences. It also has to be sorted by count, decreasing. Also notice that this is just from one receipt rather than multiple, which is what is required.

I also need the algorithm to scale to triples and quadruples, not just pairs.

How would I create an algorithm like this?

There are no set time efficiency constraints. In fact, a more readable solution is preferred over more efficient solutions although efficiency is also appreciated. A python solution is also appreciated, but any language or pseudocode will do.

This is the itemset mining problem.  Use any standard algorithm for that problem.  Follow the links to learn more about standard algorithms for that task.


What is known about the sets enumerated by primitive recursive functions? Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, we can enumerate $S$ by calculating $\{f(0), f(1) \ldots \}$.

What is known about this class of sets? Where does it stand in terms of computability? I suspect that it contains sets that are not context free, and that it does not contain all recursive sets.

Has this been studied? Does anyone have a reference for this?

In "Extensions of some theorems of Gödel and Church" it's shown by Barkley Rosser that these sets are exactly the recursive sets:

  Corollary I. If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function.

Note that the crux here is repetitions. Since you constructed sets, and comparing them with other sets, any repetitions do not violate their equality.


Closure against right quotient with a fixed language I'd really love your help with the following:

For any fixed $L_2$ I need to decide whether there is closure under the following operators:

$A_r(L)=\{x \mid \exists  y \in L_2 : xy \in L\}$
$A_l(L)=\{x \mid \exists  y \in L : xy \in L_2\}$.

The relevant options are:

Regular languages are closed under $A_l$ resp. $A_r$, for any language $L_2$
For some languages $L_2$, regular languages are closed under $A_l$ resp. $A_r$, and for some languages $L_2$, regular languages are not closed under $A_l$ resp. $A_r$.

I believed that the answer for (1) should be (2), because when I get a word in $w \in L$ and $w=xy$ I can build an automaton that can guess where $x$ turning to $y$, but then it needs to verify that $y$ belongs to $L_2$ and if it won't be regular, how would it do that?
The answer for that is (1).

What should I do in order to analyze those operators correctly and to determine if the regular languages are closed under them or not?

To answer these question, we need allow any $L_2$. So let's think that $L_2$ is a very complex language (say, some undecidable language.)

Lets start from the easy question: $A_l(L)$  (question part 2). Take $L_2$ to be undecidable, and $L=\{\varepsilon\}$. What happens?

(moral: Always check the "extremes": empty $L$, $L=\{\varepsilon\}$ and $L=\Sigma^*$...)

Now for $A_r$. This is a great question (usually bonus question in Final/Homeworks). Indeed, regular languages are closed under $A_r$ for any language $L_2$. Even undecidable $L_2$. Cool, right?

So how can we build an automaton for $A_r(L)$ if there is no machine that accepts $L_2$?

Here comes the magic of "abstract thinking",i.e., existential proof. If someone gives us $L_2$ we can use this information to show that there exists some automaton to solve $A(L)$. Now the details.

We start from the automaton of $L$ (call is $DFA_L$).
Assume that after processing $x$ we end up in a state $q$. We need to accept if there exists $y\in L_2$ such that if we continue from $q$ processing $y$ we will end up in a final state of $DFA_L$. There is no machine that can tell us if $y$ is in $L_2$, but we can make $q$ a final state of $DFA_{A_L}$ if the above condition holds, i.e., if there exists some $y\in L_2$ such that if we start at $q$ and process $y$ we end up in a final state of $DFA_L$.

so to build $DFA_{A_L}$ we examine each one of the states of $DFA_L$ and make each state $q$ an accepting state if we can take some $y\in L_2$ and this $y$ will lead us from $q$ to an accepting state of $DFA_L$.

So ok, $L_2$ is infinite, and we might have no computer to list all the words in $L_2$, but all of this doesn't matter... the above automaton is well-defined, even if I can't draw it to you state by state. Magic.


Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s Like the title says, we have the alphabet $\Sigma = \{a,b,c\}$ and the question is asking for the regular expression of the language $L$ that has the property that all strings in $L$ have at least two consecutive $a$'s but no consecutive $b$'s.

By attempt at a solution was this, where $aaa^+$ stands for $aaa(aaa)^*$:

$$(a+c)^*aaa^+(a+c)^*b(a+c)^* + (a+c)^*b(a+c)^*aaa^+(a+c)^*$$

but I know this is wrong since we never get an instance of consecutive $b$'s. Can someone point me in the right direction?

You'll need to guarantee the following:

at some place, you have $aa$
whenever there is a $b$, then there is a different letter between it and any further $b$

So one part of your regular expression will be $aa$, and that'll be need to be "in the middle" since we don't want to exclude the word $bcaab$ for example. The other part needs to take care of the restriction for $b$s.

One way to make ensure the restriction with regard to $b$ is to put at least one letter before every $b$ except for the first $b$ before and the first $b$ after $aa$. So you could do:

$(b + \epsilon)((a+c)^+b)^*(a+c)^*aa(b + \epsilon)((a+c)^+b)^*(a+c)^*$

where $\epsilon$ is the empty word. If you don't want to use $\epsilon$, you can split that expression up into 4 expressions without epsilon and sum them up.