Can we find a computable function which cannot be calculated faster for any given time? Define $T\colon \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ by:

$T(k,n) = 2^{T(k-1,n)}$

$T(0,n) = 1$

$T(1,n) = 2^n$

$T(2,n) = 2^{2^n}$

And denote the W.C. (worst case) time of computing $f(n)$ as $WC(f(n))$

Can we find computable functions $f_i\colon \mathbb{N} \rightarrow \mathbb{N}$ such that computing $f_i(n)$ takes $\Omega(T(i,n))$ W.C. and such that for every other computable function $f \equiv f_i$ (I mean $f(n) = f_i(n) \forall n \in \mathbb{N}$), we have $\lim_{n \rightarrow \infty} \frac{WC(f_i(n))}{WC(f(n))} \neq 0$?

I am in a sense trying to find a concrete example of functions that takes at least X time to compute, where X can be as large (asymptotically) as we want.

I was thinking maybe $f_i(n) =$ the $T(i,n)$'th digit of $\pi$,
but not quite sure this fulfills the second condition.

The "$f$-bounded halting problem" takes time at least (roughly) $f$ (for infinitely many $n$). The $f$-bounded halting problem asks whether a Turing machine halts on the input $0^n$ within time $f(n)$. Suppose we could solve this problem in time $g(n)$. Consider the following machine:

  On input $0^n$, ask whether the $n$th Turing machine halts within time $f(n)$ on the input $0^n$. If so, go into an infinite loop, and otherwise, halt.

This takes time $g(n) + Cn$ for some constant $C$. If $g(n) + Cn \leq f(n)$ then we obtain a contradiction by taking $n$ to be the code of this machine. Hence the $f$-bounded halting problem cannot be solved in time $f(n) - Cn$.

This argument only shows that we need time $f(n) - Cn$ for some $n$. But we could consider an infinite sequence of Turing machines equivalent to the one described above, and so obtain an "infinitely often" version of this statement.

It is possible that through trickery we can improve this to all $n$ (for reasonable functions $f$), and leave this for the reader to ponder.


Quadratic residue and integer factoring I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime).

I am looking at the following special case of this problem: Let $p$ and $q$ be two different prime numbers and $n:=pq$. Given $r$ between $1$ and $n$. Decide if there exists an $x\in\mathbb{Z}/n\mathbb{Z}$ such that $x^2\equiv r\pmod{n}$.

My question is: The functional version of this problem i.e. "Find such an $x$ as above" yields an randomized algorithm for integer factoring. So it is very interesting for practical reasons like "breaking RSA". Is there any such result for the decision version of this problem? If not, what are typical problems that let us think that deciding quadratic residuosity it is a hard problem?

And furthermore, is the special case I'm looking at really a special case? Or can I solve the general case with an arbitrary $n$ with an oracle for the decision problem above?

Tibor Jager and Jörg Schwenk show in The Generic Hardness of Subset Membership Problems under the Factoring Assumption that factoring reduces to distinguishing quadratic residues from numbers with Jacobi symbol 1, for generic ring algorithms. These are algorithms whose only "API" to integers are ring operations (addition, multiplication, subtraction, division), equality comparisons and generating a random element. They also show that the Jacobi symbol, which can be efficiently computed in polynomial time, has no efficient generic ring algorithm. So their result doesn't answer your question, other than implying that the answer isn't known.


Simple pathes in an acyclic graph How to answer on many requests by type:

  Count amount simple paths passing through chosen edge in an acyclic undirected graph using dynamic programming?

Since the graph is acyclic, we know that it is a forest - which means that, there is at most $1$ simple path between two nodes. Now, simply root the graph at one vertex of the edge, remove the edge, and run a dynamic programming algorithm to find the number of vertices in the subgraph, call it $v_a$. Similarly, do the same for the other vertex of the edge, call it $v_b$. The answer is $v_a*v_b$, since the simple path between every $2$ nodes is a different simple path.

Proof: Clearly every simple path we consider passses through the chosen edge. The only other simple paths are the ones where both the nodes are chosen in the same subgraph, which clearly does not pass through this edge.


Is there a standard recently-used algorithm based on time and usage count? Everyone is familiar with most recently used files lists in software and in OSs like Windows.

Some programs just sort by time. I've always been fairly annoyed at this. Others like Windows take usage count into consideration. Some move the item halfway to the top each time it is used, which seems to make sense.

Rather than me blindly guessing at what combination of calculations might be nicest for my end users, is there some well-known most helpful standard for end-user recently-used lists?

(My searches turn up information about MRU caching, but I can't tell how applicable any of that is; it's server efficiency facing vs user efficiency facing.)

This concept is indeed known in data structures as self-adjusting/-organizing lists. Possible strategies include

move the accessed element to the front,
maintain a sorted list by (potentially degrading) counts, and
move the accessed element one step towards the front.

Many more strategies are possible; which is most suitable depends a lot on the specific situation.


Local variables get assigned global addresses based upon call tree When working with certain low-powered / embedded CPUs that are bad at using the stack, I need to avoid putting local variables there, instead opting to make them static variables. But this can waste a lot of address spaces since not every local in every function needs their own unique address. Rather, by looking at the call tree, functions that do call each other can share memory space.

For example, given code such as this:

void A() {
    int x;
    // ...
    B();
    C();
    // ...
}

void B() {
    int y;
    // ...
}

void C() {
    int z;
    // ...
}

The variables y and z can be assigned the same address, while x should be unique so that calls to B() and C() don't clobber it.

Obviously this breaks recursion and multi-threading, but neither of those are a problem for the use cases I'm working in.

Is there a name for this algorithm? I'm assuming that it's well known, but it's very hard to search for information about this specific problem.

This sounds similar to register allocation.  Normally, register allocation is done at the scope of a single function, but it can also be done globally (interprocedurally).  If you ignore all recursive and mutually recursive calls, you might be able to apply standard algorithms for register allocation to your situation.


Question about the formal proof of the inorder traversing In Don Knuth's famous series of books, The Art of Computer Programming, section 2.3.1, he describes an algorithm to traverse binary tree in inorder, making use of an auxiliary stack:

T1 [Initialize.] Set stack $\rm A$ empty and set the link variable $\rm P\gets T$
T2 [$\rm P=\Lambda$?] If $\rm P=\Lambda$, go to step T4.
T3 [Stack$\rm \;\Leftarrow P$] (Now $\rm P$ points to a nonempty binary tree that is to be traversed.) push the value of $\rm P$ onto stack $\rm A$, then set $\rm P\gets LLINK(P)$
T4 [$\rm P\Leftarrow Stack$] If stack $\rm A$ is empty, the algorithm terminates; otherwise pop the top of $\rm A$ to $\rm P$.
T5 [Visit $\rm P$] Visit $\rm NODE(P)$. Then set $\rm P\gets RLINK(P)$ and return to step T2.

We can plot a flow chart of the algorithm. In the succeeding paragraph, he gives a formal proof of the algorithm:

Starting at step T2 with $\rm P$ a pointer to a binary tree of $n$ nodes and with the stack $\rm A$ containing $\rm A[1]\dotsc A[m]$ for some $m\ge 0$, the procedure of steps T2-T5 will traverse the binary tree in question, in inorder, and will then arrive at step T4 with stack $\rm A$ returned to its original value $\rm A[1]\dotsc A[m]$.

However, as far as I know, such a formal proof is quite different from the general method described in section 1.2.1:

for each box in the flow chart, that if an assertion attached to any arrow leading into the box is true before the operation in that box is performed, then all of the assertions on relevant arrows leading away from the box are true after the operation.

In fact, such a method is somewhat equivalent to Hoare logic, which is used to formally check the validity of algorithms.
Can we turn the statement mentioned to prove the traversing algorithm into a schema of Hoare logic, or the assertion-attachment of a flow chart?
Thanks!

It is definitely possible to analyze this algorithm using Hoare triples. The first step would be to replace the VISIT procedure calls with some more reasonable accounting mechanism, say a list that lists the visited nodes in order. You then define formally what a binary tree is and what an inorder traversal is, something along the following lines:

Tree = Leaf N | Node N LTree RTree
Inorder(Leaf N) = N
Inorder(Node N LTree RTree) = Inorder(LTree) || N || Inorder(RTree)

Here N is the "name" of the node, and || is list concatenation. Armed with these notions, it is an exercise to construct the required Hoare triples. You will probably need to come up with even more notions (for example, you will need to explain what the contents of the stack are when a node P is popped).

What do we gain from this exercise? Do we understand the algorithm any better? Probably not. But we understand how to reason precisely about algorithms, something which is useful if you plan on doing software verification or programming language theory, areas forming the so called "Theory B". If you're more of a "Theory A" type (algorithms and complexity) then, like me, you will find such exercises somewhat beside the point.


How to read out a double negation in propositional logic How would one verbally say ~~R where R = my program is correct? The tildes are negation symbols. I'm not sure if it just cancels out and comes out as 'my program is correct' or if it's something else.

Thank you!

The answer by @D.W. is valid in classical logic, however if you are on the intuitionistic side, then you can't eliminate double negation (~~).

I'd read the formula as 'It is not true that my program is not correct'.


How can I produce a summation function from this set of production rules for a grammar? I am not entirely sure if the title is the correct way to phrase what is occurring. There is a recurring process which I decided to attempt to model using production rules similar to those used in a context-free grammar.

The real world process is a production line. It takes 1 unit, after 2 weeks, produces 1 unit, after 4 weeks, that unit will produce another unit - and also 2 of the starting units. After 4 weeks the "another unit" will produce "that unit" - and also 3 of the starting units. This continues semi indefinitely, but the range I am looking at is roughly 52 weeks.

I came up with this model of production rules

$S\rightarrow A$

$A\rightarrow S^2B$

$B\rightarrow S^3A$

I attempted to expand this so that I could formulate a generating function and solve for n=52 (52 being the 1 year mark).

$S$,$A$,$S^2B$,$S^5A$,$S^7B$, ...

However, I was unable to determine if I was taking the correct approach to solving this situation. I believe that an error here lies in the fact that the duration of time is ignored. Namely that from $S\rightarrow A$ 2 weeks elapse, from $A\rightarrow S^2B$ 4 weeks elapse, and from $B\rightarrow S^3A$ 4 weeks elapse.

In order to better understand this situation, I decided to code an example so I could at least see the totals. However, it did not lend itself to producing a summation function.

So, given all this, how is it possible to come up with a summation function instead of having to manually iterate through it like this c# approach does? Or, is there a similar/alternate approach to modeling this which will allow an easier summation process?

Please feel free to correct any misunderstandings I may have.

edits

For example:

Week 1: We have 1 unit (S). It sits for 2 weeks until it is ready to become 1 of the next type(A).

Week 3: The first unit is now here. It sits for 4 weeks until it is ready to become 1 of the next type(A). At that time, it also becomes 2 of the first type(S).

Week 7: The unit from Week 3 has now become 2 of the first type of unit(S). It also created 1 of the second type(A). The 2 units of type S will now sit for 2 weeks until they make 2 units of type A. The 1 unit of type A will now sit for 4 weeks until it makes 1 unit of type B and 2 units of type S.

Week 9: The 2 units of type S from week 7 have now sat for 2 weeks. Now they have become 2 units of type A. These two units of type A will sit for 4 weeks and produce 4 units of type S and 2 units of type B.

Week 11: The 1 unit of type A from week 7 has now sat for 4 weeks and has now made 1 unit of type B and 2 units of type S. The 1 unit of type B will sit for 4 weeks and then make 1 unit of type A and 3 units of type S. The 2 units of type S will now sit for 2 weeks and make 2 units of type A.

Also, the 2 units of type S from week 9 have now sat for 2 weeks and become 2 units of type A. These two units will sit for 4 weeks and become 2 units of type B and will also become 6 units of type S.

etc.

This can perhaps be represented by a series of recurring relations

$s(n) = a(n) + b(n) + c(n)$

$a(n) = 2*b(n-4) + 3*c(n-4)$

$b(n) = a(n-2) + c(n-4)$

$c(n) = b(n-4)$

where

$s(n) = a(n) = b(n) = c(n) = 0$ for $n < 1$

$a(1) = 1$

OK, so the question now has a set of recurrence relations.  To solve these, you can plug them in to each other until you get a single recurrence relation.  First, substitute $c(n)=b(n-4)$ to get rid of all of the $c$'s:
$$a(n) = 2 b(n-4) + 3 b(n-8)$$
$$b(n) = a(n-2) + b(n-8).$$

Now substitute in to get rid of the $a$'s:

$$b(n) = 2 b(n-6) + 3 b(n-10) + b(n-8).$$

So, you've gotten down to a single recurrence relation for the $b$'s.  Solve this using standard methods; see Solving or approximating recurrence relations for sequences of numbers for details.  Then, once you have a solution for the $b$'s, you can reverse the substitutions and obtain a solution for the $a$'s, $c$'s, and finally $s$'s.

If you want to find an exact equation for the $b$'s (rather than an asymptotic estimate), the method of generating functions will probably be useful.  You'll have to find the roots of a 10th-degree polynomial ($x^{10} - 2 x^4 - x^2 - 3$, I think), and the solution will likely be an expression of the form $c_1 r_1^n + \dots + c_{10} r_{10}^n$ where $r_1,\dots,r_{10}$ are the roots and $c_1,\dots,c_{10}$ are the appropriate constants.  This might get a bit messy, but it should be doable.

Or: You can ask Wolfram Alpha to solve the recurrence relation for you.  Sometimes it is able.  Unfortunately, for this one it seems to have failed: output.


Common idea in Karatsuba, Gauss and Strassen multiplication The identities used in multiplication algorithms by

Karatsuba (integers)
Gauss (complex numbers)
Strassen (matrices)

seem very closely related. Is there a common abstract framework/generalization?

A partial answer to your question is the group-theoretic approach first developed by Cohn and Umans and further developed by Cohn, Kleinberg, Szegedy and Umans. It can "sort of" capture Strassen and Coppersmith-Winograd for matrix multiplication.


Sorting the number sequence I have

$4$ variables $n_1, n_2, n_3, n_4 \in \mathbb N$ that sum to $N$.
$4$ positive real constants $c_1 < c_2 < c_3 < c_4$.

Given a particular tuple $(k_1,k_2,k_3,k_4)$, how do I find the partial sum of the ordered (w.r.t. the sum $c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4$ in an increasing manner) sequence

$$\sum_{n}^{(k_1,k_2,k_3,k_4)} (c_1 n_1 + c_2 n_2 + c_3 n_3 + c_4 n_4)$$

from the minimum to the given $(k_1,k_2,k_3,k_4)$?

I think this problem involves some sorting algorithm. This should already be studied in some linear programming problem but I am just not aware of how to do this efficiently (e.g. using Python).

There's a simple $O(N^3 \log N)$ algorithm, though you might be able to do much better. First, compute all $N^3$ quadruples, and the corresponding linear combinations $\sum_i c_i n_i$. Then sort them. Then find the location of the given quadruple. Then compute the running sum.


Artificial Intelligence: theory vs processing power It is common to see articles praising the advances in AI (here is one example).
There is no doubt that significant progress has occurred on all kinds of automation, hard games like chess, etc.
The question is, how much of that progress is due to conceptual proogress, as opposed to increase in processing power? Or, to phrase it in a different way: if today's best AI would be shown to a computer scientist from the 60s, would they be impressed by the algorithms? Or just by the raw power of the hardware?

AI spans many different areas.  If you are actually asking about machine learning, the conventional wisdom is probably that it's a combination of new ideas (e.g., neural networks, architectures, methods for training them), computation power (e.g., GPUs), and data (large labelled datasets).
See, e.g.,
https://qz.com/1307091/the-inside-story-of-how-ai-got-good-enough-to-dominate-silicon-valley/,
https://towardsdatascience.com/the-state-of-ai-in-2020-1f95df336eb0, and probably many more (I didn't spend much time looking).


How does the equation for min heap array indexing work? I've been reading about min heaps, currently looking at this article, and I am very confused by something.

The article makes the following statement:

  If a given node is located at index 'x' in the array, its left child
  exists at index = 2x, and its right child exists at index = 2x + 1.
  Each node's parent exists at index = x / 2 (rounded down).

It gives this example:

This min heap is represented in the array [100, 19, 36, 17, 3, 25, 1, 2, 7].

But this doesn't jive with the preceding statement about indexing. 36 can be found at index 2, and 2 * 2 is 4. But index 4 is 3-- the right child of the 19 node, not the left child of the 36 node.

What am I missing here?

Start indexing at $1$, then everything will be fine.

Want to start at $0$? That is no problem, but one has to adjust the formula's. Children of $x$ can be found at $2x+1$ and $2x+2$.


How to analyze the worst case of weighted quick-union method on union-find Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne.

  Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial coefficients. Compute the average depth of a node in a worst-case tree with $k = 2^n$ nodes.

Here are my questions:

1) What is the worst-case tree for weighted quick union?

2) How I compute the average depth of a node in this worst-case tree with $2^n$ nodes?

I tried to show through induction that the number of nodes at each level for the worst-case tree in weighted quick-union are binomial coefficients (the first level has $\frac{1!}{0!(1-0)!} = 1$ node). From there I tried to think about how, generally, there are at most $\frac{n!}{r!(n-r)!}$ nodes at the next level. However, I'm unable to think of reasons as to how this makes sense.

Any help with this question is appreciated.

This is just a note for myself in the future, in case anyone else out their ends up getting stumped by this problem. This answer expands off of @Apass.Jack's answer.

To prove that each level has a binomial coefficient, we use induction.
The base case of $n=1$ is ${1 \choose 0}$ is 1. $n$ represents the height of the nodes while the $0$ is just an arbitrary level of the tree.
Now, assume that at each level the number of nodes is ${n \choose i}$ where $0 \le i < n$ for a tree $T_n$. When we combine 2 trees of size $2^n$ (let's call them $T_1$ or $T_2$), then one of them is chosen to point to the root and the other is chosen to become the root. Let's say that the root of $T_1$ is chosen to point to $T_2$. If this is the case, the depth of each nodes increases by 1. That means, in a sense, each node is "pushed" down the tree to the next level below. Now, if, by the inductive hypothesis, we have ${n \choose i}$ nodes at each level of $T_2$. However, for each level $i$ in the $T_1$, the number of nodes at is equivalent to the previous level in $T_1$, $i-1$. Therefore, for each level $i$ in $T_1$ connected to $T_2$, the number of nodes is ${n \choose i-1}$. So, if we count the number of nodes on each level, it's just the sum of the number of nodes at each level of $T_2$ and then the number of nodes at each level of $T_1$ connected to $T_2$. So, the number of nodes is ${n \choose i} + {n \choose i-1} = {n+1 \choose i}$. This fits the form of the inductive hypothesis; therefore it is proven.


Dwarves color their houses The dwarves of the Black Forest live in houses that are each painted either red or blue. Some dwarves are friends, and some aren’t. Every so often, a dwarf will think about repainting his house. To decide whether to repaint, he looks at the colors of his friends’ houses. If his house is red, but more of his friends live in blue houses than in red houses, then he will paint his own house blue. On the other hand, if his house is blue, but more of his friends live in red houses than in blue houses, then he will paint his own house red.
Prove that after some point in time, no dwarf ever paints his house again.

Here is my attempt:  This problem can be modeled by a graph. The vertices of the graph represent the houses and there is an edge between two vertices if the dwarves of the houses represented by the vertices are friend with each other. The problem then translate to coloring the vertices with two colors. If the graph has no cycle then it is a tree, then we can look at the leaves of the tree and color them and go one layer up and color the nodes according to how many children node has the majority of colors and so on. However, what happen when there is cycle in the graph?

Your problem is known as majority dynamics. It is known that under rather general conditions, the behavior converges to a fixed point or to a cycle of length 2. Presumably in your case the rules are such that cycles of length 2 cannot happen. Try adapting the proof method in Goles and Olivos.


Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$? According to this statement:

Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular language and its complement are a pair of complementary context-free languages.

$\{a^n b^n c^n \mid n\ge0\}$ is not deterministic context-free language so is $\Sigma^* \setminus \{ a^n b^n c^n \mid  n \ge 0\}$ a deterministic context-free language?
If it is, how does it look like?
($\Sigma^*$ means every possible string that can be generated with $\{a,b,c\}$.)

The complement of a deterministic context-free language is also deterministic context-free. Since $\{a^nb^nc^n \mid n \geq 0\}$ is not context-free, its complement cannot be deterministic context-free. However, the complement is context-free, since it can be written as follows:
$$
\overline{a^*b^*c^*} \cup \{a^{n+k} b^n c^m, a^n b^{n+k} c^m, a^{n+k} b^m c^n, a^n b^m c^{n+k}, a^m b^{n+k} c^n, a^m b^n c^{n+k} \mid n,m \ge 0, k \ge 1 \}
$$


Huffman encoding: why is there no need for a separator? Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Original text:

  Eerie eyes seen near lake

Encoded:
0000101100000110011100010101101101001111101011111100011001111110100100101

Why is there no need for a separator in the Huffman encoding?

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword.  For example, the codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10.

This means that you can decode greedily by reading the encoded string from left to right and outputting a character as soon as you've seen a codeword.  For example, 0, 00 and 000 don't code anything so you keep reading bits.  When you read 0000, that encodes "E" and, because the code is prefix-free, you know there's no other codeword 0000x, so you can now output "E" and start to read the next codeword. Again, 1 doesn't encode anything but 10 encodes "e".  No other codewords begins with "10", so you can output "e".  And so on.


Examples of difficult Hamiltonian Cycle Problems I am working on implementing algorithms to solve Hamiltonian Cycle Problem. I need difficult problem graphs to test my implementations but my google-fu is weak and am unable to find any.
Please advise where I might find a set of difficult graphs for the Hamiltonian Cycle, or how to generate such graphs for testing.

TSPLIB contains some instances of Hamiltonian Cycle. Haythorpe [1] proposes a set of around a thousand instances which are claimed to be "structurally difficult" (not necessarily large).

Haythorpe, Michael. "FHCP Challenge Set: The first set of structurally difficult instances of the Hamiltonian cycle problem." arXiv preprint arXiv:1902.10352 (2019).


Compute context free grammars for twice the amount $$\{ a^{k}b^{j} : k = 2j , k \geq 0\}$$

I'm trying to wrap my head around CFG's but I am having trouble. From this language, there should be twice as many a's than b's. Here is my attempt.

$$S \to aSb \ | \ a Sa \ | \ \epsilon $$

$$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSabb \Rightarrow aaaabb $$

But, I can also have this arise, which I don't want:
$$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb $$

How can I force the CFG to put twice as many a's as b's? Is there any general approach to solving these?

One general approach would be to try writing some initial strings and try to figure out a pattern. In my minimal experience, a lot of the times the strings I miss are of smaller lengths.

The initial strings for this would be:

$(\epsilon, aab, aaaabb, aaaaaabbb, ...)$ and so on.

Here we notice that: a) The string always has to start with an $a$ and b) Every time we generate an $b$, there should be two $a$'s corresponding to it.

So, we can write it as:

$$S \rightarrow \epsilon \  | \ aaSb$$


Subset of nodes such that all nodes of a graph are adjacent We have been given a graph $G$, we need to find a subset of nodes $S$ such that each node of the graph is in $S$ or is adjacent to a node from $S$. Additionally, the elements of the subset $S$ should not be adjacent to each other neither should they share a common neighbour node.
This is an example of the given problem:
In the given graph, the subset $S = $ {2, 4} is a valid solution as $3$ and $5$ are adjacent to 2 while $1$ and $6$ are adjacent to $4$. Further, $2$ and $4$ are not adjacent neither do they share a common neighbour.
The subset $S = $ {4, 5} is NOT valid as $4$ and $5$ have a common neighbour $1$.

I have been looking for an efficient way to do this; my attempt at an algorithm gives an exponential time complexity.
Any hints are appreciated, thanks in advance.

In the literature, such a subset is called a perfect code.
As it is NP-complete to determine if a given graph has a perfect code, even on some very restricted inputs, your exponential-time algorithm is probably about as good as it gets.


What is the name of this combinator? I've recently started casually reading into combinatorial logic, and I noticed that a higher-order function that I regularly use is a combinator. This combinator is actually pretty useful (you can use it to define addition on polynomial equations, for example), but I never gave it a decent name. Does anyone recognise this combinator? (ignoring differences in function currying)

unknown = function (h, f, g)
    function (x) h( f(x), g(x) )
}

In lambda calculus, the fully curried implementation would be
$\lambda h. \lambda f. \lambda g. \lambda x. h (f x) (g x)$. In other words, if $M$ is this mystery combinator, then its defining equation is $M \, h \, f \, g \, x = h \, (f \, x) \, (g \, x)$.

If more information is needed, or my question is lacking key information please leave a comment and I will edit my question.

This isn't probably a standard name, but in The Implementation of Functional Programming Languages in Section 16.2.4 Simon Peyton Jones calls it S'. It is defined as an optimization combinator

S (B x y) z = S' x y z

The following example is from the mentioned section. Consider

λx_n...λx_1.PQ

where P and Q are complicated expression that both use all the variables.
Eliminating lambda abstractions leads to quadratic increase of term sizes in n:

P Q
S P1 Q1
S (B S P2) Q2
S (B S (B (B S) P3)) Q3
S (B S (B (B S) (B (B (B S)) P4))) Q4

etc., where Pi and Qi are some terms. With the help of S' this gets only linear:

P Q
S P1 Q1
S' S P2 Q2
S (S' S) P3 Q3
S (S' (S' S)) P4 Q4


Array segmenting algorithm I have a sorted array of integers [x, ..., n, ..., y] so that
x > 0
n - x = random positive integer

The array might look something like this:
[1, 2, 3, 15, 16, 17, 120, 121, 122, 123, 124, 125, 126, 127, 210, 211, 212, 213, 214, 215]

I want to divide this array into segments so that,
1) The difference between last and first element of a segment < 125
2) The number of segments is equal to k (predefined positive integer)
3) Sum of differences between first and last element of all segments is minimal

The end result should be a list of segments with their start and end values.
The minimum size of a segment is 1.

Suppose k = 2, then the given example array could be divided into two such segments:
Option 1) [(1, 125), (126, 215)]
Option 2) [(1, 17), (120, 215)]
Both satisfy requirements 1 and 2.

Sum of differences between first and last element of all segments:
Option 1) (125-1) + (215 - 126) = 213
Option 2) (17 - 1) + (215 - 120) = 111
Therefore option 2 is the preferred solution.

Python is the used language.

Any suggestions on how to approach this problem are welcome.

From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$  into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,j)=0$ for any $j \ge 0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1)  + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1 (representing +infinity);

for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>=125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];

return delta[n][k];


Is UNIQUE-X3C a US-complete problem? The problem: Exact Cover by 3-Sets (X3C)

The definition: Given a set X, with |X| = 3q (so, the size of X is a multiple of 3), and a collection C of 3-element subsets of X.  Can we find a subset C’ of C where every element of X occurs in exactly one member of C’?  (So, C’ is an “exact cover” of X).

The class US (Unique Polynomial-Time) is the class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.

UNIQUE-3SAT is the problem of deciding whether the 3CNF Boolean formulas have a unique solution. UNIQUE-3SAT is a known US-complete problem.

Is the version of problem Exact Cover by 3-Sets(UNIQUE-X3C) when the instances have a unique solution a US-complete problem? (which means there is a unique subset C’ as solution)

Thanks in advance!!!

Yes, it is.

This scanned chapter 3 from Garey-Johnson classic book describe a parsimonious reduction from 3SAT to 3DM. And X3C is a generalization of 3DM. So, the same reduction can be used to parsimoniously reduce 3SAT to 3DM.

Thus, $\mathrm{UNIQUE-3SAT}$ many-one reduces to $\mathrm{UNIQUE-X3C}$. As a consequence, $\mathrm{UNIQUE-X3C}$ is $\mathrm{US}$-complete.


Time complexity of kruskal using array data structure I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps:

Sort the edges as per there edge weights. O(ElogE)
And then select edges one by an check by the union and find algorithm if they form a cycle or not. Time for this step for the single edge will be O(logv) so for E edges it will be O(ElogV).

Time complexity according to this implementation is O(ElogE)+O(ElogV)

For Desnse graph E=O(V^2) so time is O(ElogV^2) + O(Elogv) = O(Elogv)

But now the question is How to implement Kruskal using array data structure.
From above algorithm step, 1 will remain the same So time for sorting edges will be O(ElogE)

But how to implement the second step using array data structure without using Disjoint-set data structure?

If I store each set of disjoint set in an array then the second step will take O(V) time for each edge. So total time will O(EV) for the second step.
So total time for Kruskal using array data structure will be O(ElogE)+O(EV).

But questions in the below link does not have this option where I am wrong in above steps?

https://gateoverflow.in/92864/kruskals-mst

Here is the original question encountered by the OP, quoted here so that readers do not have to register to that website just to take a look at the question.

  Consider a graph with V vertices and e edges,What is the worst case time complexity for kruskal's algorithm when implemented using array data structure?
  a.) E+ElogV
  b.)VlogV
  c.)V^2
  d.)Vlog^2V

The only correct answer as I see is, the original question is ill-posed. It is ill-posed because of its unconventional, ambiguous, almost meaningless use of "using array data structure".

Array is such a fundamental data structure, it usually converys little information when you say an algorithm is implemented using array data structure. Especially in the current case of Kruskal's algorithm, we usually refer to the disjoint-set data structure used in the algorithm to keep track of which vertices are in which connected components and to determine whether an edge will join two different connected components. In fact, the whole page about Kruskal's algorithm in wikipedia does not mention "array" even once. Although well versed regarding to minimal spanning tree and Kruskal's algorithm[1], I am confused by this "using array data structure".

Let us also take a look at other aspects of the original question. It has bad capitalization, bad punctuation, and inconsistent white spacing. It introduces "$e$ edges" but use $E$ in the choices. When it lists the time complexities, it should apply the big $O$ notation such as $O(E+E\log V)$. It skips the basic description of the graph as connected edge-weighted.

All in all, it is fair to say the original question is of such a low quality, you should just ignore it. Try not to learn from it.


Relation between Signals and Events There are POSIX signals (linux man), and various event-based operating systems (such as TinyOS, most seem to be targeted at embedded systems). But the mechanisms seem very similar.

Are the terms 'signal' and 'event' interchangeable? Or are signals a sub-set of events? Or are they two fundamentally different for some reason that I am completely missing?

As general concepts, the words signal, notification and event are mostly interchangeable, though they carry different connotations and some words wouldn't be used to denote some specific mechanisms. A particular operating system or other concurrency framework may use these terms for different mechanisms.

Some differences to watch for (with signals, events or whatever they're called) include:

Synchronous vs asynchronous: does the sender block until the recipient receives the signal?
Stacking: if multiple identical signals are generated before the recipient acknowledges any of them, will the recipient receive that many signals, or can they be merged?
Associated information: is the signal just “hey, wake up”, or does it have an associated tag, or does it have a payload (which could be a pointer to a larger data structure)?
Destinations: does the signal target a specific task (unicast), or a set of recipients (multicast), or all tasks that care (broadcast)? In the multicast case, will all the specified targets receive the signal, or is the signal cleared as soon as one task acknowledges it (this may be termed unicast rather than multicast)?

For example, POSIX signals are asynchronous, unicast (multicast if sent to a process group), they stack, and have a tag which is a small integer. I'm not familiar with TinyOS; from a quick read of the tutorial I think they are asynchronous, unicast (perhaps with other possibilities), non-stacking, and have a payload (and, incidentally, sending an event is called signalling it; receiption is called triggering, because the event in TinyOS terminology is the handler instance rather than not the message).

I think the word event wouldn't be used if there is no associated information at all. The word signal wouldn't be used if there's a rich payload: with a rich payload, it's a message, possibly an event or a notification. GUI frameworks often call notifications of user input events; GUI events have a payload (e.g. to identify which key was pressed) and don't stack.

The use of the word event tends to promote event-driven architectures, where programs are structured as event callbacks rather than as a thread that checks for notifications periodically, but it isn't limited to this use.


Algorithm to identify if a string of numbers is a lottery sequence Suppose that a valid lottery ticket consists of a sequence of 7 numbers drawn from the set $\{1,2,\ldots,59\}$. Given a string like "$12345678$", I want to efficiently print all the lottery sequences using every digit in the input string.

In the example above, a couple of possible sequences are:
${1,2,3,4,56,7,8}$ or ${1,2,3,45,6,7,8}$ which both satisfy lottery number conditions.

I thought of a combinatorial solution like this:

Let $n$ be the number of characters in the input string. If $n<7$ or $n>14$ then there is no solution possible. For valid input strings of length $n$, where $n\in [7,14]$, the problem reduces to the following:

In a string of length $n$ there are $n-1$ locations to put a comma. We have to put $6$ commas in $n - 1$ spaces such that no two consecutive spaces are empty (Otherwise, a number will be consist of three digits or be greater than $59$). This simply means arrange six ones like this:

  111111

and then put $n-7$ $0$'s (representing emptiness) in the 7 slots. So, for example, if the input string is of length $8$ ("$12345678$") then we have to put $8-7 = 1$ zero in $7$ slots. So there are $7$ places where a zero can go and the strings generated are:

  0111111, 1011111, 1101111, 1110111, 1111011, 1111101, 1111110

which correspond to $\{12,3,4,5,6,7,8\}$, $\{1,23,4,5,6,7,8\}$ etc.

So the problem reduces to computing $\binom{7}{k}$ and for each arrangement like above, put the corresponding commas in the appropriate place in the input string. So $0111111$ maps to $12,3,4,5,6,7,8$ (the space between 1 and 2 is left empty while the commans occupy the remaining 6 slots).

Is this algorithm a bad choice or can I do better?


What makes a language "optimized" for a specific task? Often there are programming languages that are specialized for specific tasks. Some programming languages are excellent at array arithmetic (such as matrices and the use of multidimensional arrays), yet some are much better at higher-level mathematics that is hard to reproduce in other languages (yet still possible all the same).

What about a language makes it better for a specific task or end-goal than other languages, given that most simply compile down to assembly anyways?

I am talking about Turing complete languages, ones that are Turing equivalent.

There are a few things to consider:

Abstraction: what does the language treat as "special"? Are matrices first-class values, like in Matlab, or do you encode them using simpler types like arrays, as in C? C makes you think about how matrices are implemented, Matlab doesn't.
Likewise, if you've got a complicated system of asynchronous communications, you probably want first-class functions so that you can do callbacks.
The more features that are added, the more complex the language gets. So while there are some "multi-paradigm" languages like C++ and D, most languages pick a niche, choose the things that are important to that niche, and prioritize those as their main abstractions.

Performance: all abstraction comes with a cost, whether it be compile-time or run-time. Some languages limit themselves in a way that makes them less abstract but more performant.
Early Fortran didn't allow for pointers or recursion, so it was great at number crunching, faster than a language like C, where you were running lots of loops. But it was terrible at encoding large data structures, like trees, where you needed pointers for indirection. (Note that I don't know much about modern Fortran.)

Essentially, there are always tradeoffs. More abstract means either slower runtime or more complexity at compile-time. More features means a more complex language. Some features make certain things fast and others slow, like pointers and recursion. There's no perfect language, so each language will reach a sort of local maximum in the space of language qualities.


shortest paths algorithm - why backtrack from the end node instead of starting from the starting node? I was watching a dynamic programming video by Erik Demaine . He says here https://youtu.be/OQ5jsbhAv_M?t=2133 , finding the shortest paths from S to V for all V, by guessing the node after the starting node is not the right approach, and instead should guess the node before the last node. I didn't understand his explanation. Can someone explain better why find the path backwards? It seems to me that you should get the same answer either way and both approaches are equally good.

You want to find the shortest paths $S(s,v)$ to all nodes $v$ (31:30 in the video). In other words, we are interested in computing a function $f(v) = S(s,v)$, and, as explained in lecture, you can write it as $f(v) = \min_{(u,v) \in E} f(u) + w(u,v)$. In the end, it allows you to compute all such values in one go.
If you instead consider an equation $S(s,v) = \min_{(s,u) \in E} w(s,u) + S(u,v)$, you do can find $S(s,v)$ this way. However, you won't be able to find $S(s,u)$ for all other $u$ in the process, and you'll have to run the same algorithm again for other end vertices.


Extremal related question regarding Intersection of neighbourhood of vertices What is the maximum number of edges that a simple directed graph on $n$ vertices can have, if the graph has the following restriction.

Size of Intersection of Neighbourhood of any pair of vertices is at most $k$?

Neighbourhood is defined as follows.
If a vertex $v$ has directed edges towards exactly three vertices $a$, $b$ and $c$, then $\{a,b,c\}$ constitutes the neighbourhood of $v$.

My hunch is $O(kn)$ but I am not able to prove it?
Its easy to create such a graph which has $O(kn)$ edges, and has maximum intersection of neighbourhood to be at most k.

Simply create an empty graph on $n$ vertices say $v_1,v_2\ldots v_n$. Then for each $v_i$ give their neighbourhood to be $v_{i+1}$ to $v_{i+k}$.
This gives a graph $O(kn)$ edges.

Can you show that this is the best which can be done?

This problem has been solved in the undirected case by Füredi, New asymptotics for bipartite Turán numbers, who showed that for constant $k$, the optimal bound is
$$
\frac{1}{2} \sqrt{k} n^{3/2} + O(n^{4/3}),
$$
when counting undirected edges. When counting directed edges, you have to double the number. The lower bound also holds in the directed case — it is given by an explicit construction based on finite fields.

Following Füredi's footsteps, we can generalize the upper bound to the directed case. Denote by $P_2$ a path consisting of two directed edges pointing at the central cases. The number of copies of $P_2$ in your graph is at most $k \binom{n}{2}$, since for every choice of the outer vertices there are at most $k$ choices of the inner vertex. On the other hand, the number of copies of $P_2$ is also $\sum_v \binom{d_{in}(v)}{2}$, where $d_{in}$ is the in-degree of $v$, since for every $v$, we can choose any two vertices in its incoming neighborhood to create a copy of $P_2$. Convexity now shows that $\sum_v \binom{d_{in}(v)}{2}$ is minimized when all in-degrees are the same. If the graph contains $m$ edges, then the total in-degree is $m$, and so
$$
k \binom{n}{2} \geq n \binom{m/n}{2},
$$
from which we can deduce $m < \sqrt{k} n^{3/2} + n/2$.


Numerical problem on Access time in Cache memory For a system with two levels of cache, define:

$T_{c_1}$ is the first-level cache access time
$T_{c_2}$  is the second-level cache access time
$T_m$ is the memory access time
$H_1$ is the first-level cache hit ratio
$H_2$ is the combined first/second level cache hit ratio

Provide an equation for the average access time $T_a$ of a read operation.

Here is the algorithm for a read operation:

Check if the cell is in the first-level cache.
If not, check if it is in the second-level cache.
If not, access it from main memory.

The data you are given allow you to calculate how much time each operation takes, and what is the probability that each of the steps is being taken. Using this, you can calculate the average time of a read operation.


minimum number of states in cross product of two minimum DFAs If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of states in cross product DFA = num of states in FA1 x Num of states in FA2). How to think on this?

You probably know that if $\cal A$ and $\cal B$ are DFA, then their product recognizes the language $L({\cal A}) \cap L({\cal B})$. Now if ${\cal A} = {\cal B}$, then $L({\cal A}) \cap L({\cal B}) = L({\cal A})$. Thus if $\cal A$ is a minimal DFA with at least two states, ${\cal A} \times {\cal A}$ is never minimal.


Why is the set of perfect squares in P? I am reading an article by Cook [1]. In it he writes:

  The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots.

I can see how to use Newton's method to decide whether a natural number is a
perfect square or not, but it seems tricky to analyse.

Is there an easier way to see that the set of perfect squares is in P?

S. Cook, The P versus NP problem, Online

A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $m∗m=n$. If so, terminate. Otherwise, if $m∗m>n$ reduce the upper bound to $m$, else increase the lower bound to $m$. If the upper bound and the lower bound become the same and the midpoint squared is not equal to $n$, then $n$ is not a perfect square. This terminates in $\log n$ steps, which is polynomial in the bit size of $n$, i.e., the length of the input. Each iteration runs in polynomial time as well, so the overall algorithm runs in polytime.


How to design a Turing Enumerator which either ends with 011 or is of odd length? This question was asked by my professor in optional brain teaser section, I have tried to solve it for last 48 hours, I am not able to construct a deterministic Turing Machine, Can someone provide hint or something because this seems like impossible to me :( ..

I'm assuming you're looking for a Turing machine that decides the language $L$ consisting of all words ending with 011 or of odd length.

Hint: You're lucky since $L$ is regular. Construct a DFA for $L$ and rephrase it as a Turing machine.


Google's Deep Dreamer I was just wondering on a more technical side, if anyone could explain what Google does to create these amazing images from it's deep dream system.

Could anyone explain to me in a step by step way, what the program does and how it does it.

Google's Deep Dream project is research being done to visualize neural networks' learning to understand more about them.

First, you have to understand a Deep Belief Network on a high level. In short, it's a way for machines to 'learn' about data (images, in this case). That works, essentially, by transforming an input by several matrices (layers) through the network to get an output. Deep Belief Networks are trained to reconstruct their original image. All of the images are generally of some type, like animals. After some training, they begin to recognize basic features that are common between members of the training set, such as edges or colors.

The images published for the Deep Dream project are different ways of visualizing the data from trained networks. For some of the images, they observe the state of the image in layers between the input and output, resulting in artistic looking sketches of the original. For other images, they start with one image that is not related to the training set, send it through the network, then send the output through the network repeatedly to accentuate features that the network found in the image.


Prove if a property of a Turing Machine is decidable or not, how can I do it? I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not.

For example, if a have this:

(1.1) "M always halts within 100 steps"

or this

(1.2) "M recognizes all words with an ‘a’ in them"

what do I do to prove if it's decidable or not? I know I should use reduction or diagonalization, halting problem and so on, but I don't know how to apply them.

Thanks for the help.

To show that a language is decidable, you need to provide a description of a total Turing machine, i.e, on all input, the Turing machine should halt and accept or halt and reject.
Take the example of the first problem, we can build a total Turing machine, that on input $M$(where $M$ is a Turing machine) runs it all inputs of length at most 100. Note that if $M$ halts on all inputs within 100 steps, then it must halt on all inputs of length at most 100 within those many number of steps. If $M$ does so, our constructed Turing machine halts and accepts, else halts and rejects. Since  we have to check only on a finite number of input strings, the constructed machine always halts and hence is total.
As for the second problem, the property of accepting all strings with an 'a' in them is a non-trivial one for recursively enumerable sets($L(M)$ or the language recognized by a Turing machine $M$ is an R.E set) and hence from Rice's theorem, the language of deciding recursively enumerable sets with this very property is undecidable.


Word factorization in $O(n^2 \log n)$ time Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a string, we can use this notation to 'compress' it, i.e. $AABAAB$ may be written as $((A)^2 B)^2$. Let's call the weight of a compression the number of characters appearing in it, so the weight of $((A)^2 B^2)$ is two, and the weight of $(AB)^2 A$ (a compression of $ABABA$) is three (separate $A$s are counted separately).

Now consider the problem of computing the 'lightest' compression of a given string $S$ with $|S|=n$. After some thinking there is an obvious dynamic programming approach which runs in $O(n^3 \log n)$ or $O(n^3)$ depending on the exact approach.

However, I have been told this problem can be solved in $O(n^2 \log n)$ time, though I cannot find any sources on how to do this. Specifically, this problem was given in a recent programming contest (problem K here, last two pages). During the analysis an $O(n^3 \log n)$ algorithm was presented, and at the end the pseudo quadratic bound was mentioned (here at the four minute mark). Sadly the presenter only referred to 'a complicated word combinatorics lemma', so now I have come here to ask for the solution :-)

If I'm not misunderstanding you, I think the minimum cost factorization can be calculated in $O(n^2)$ time as follows.

For each index i, we will calculate a bunch of values $(p_i^\ell, r_i^\ell)$ for $\ell=1,2,\ldots$ as follows. Let $p_i^1\ge 1$ be the smallest integer such that there is an integer $r\ge 2$ satisfying $$S[i-rp_i^1+1, i-p_i^1] = S[i-(r-1)p_i^1+1, i].$$ For this particular $p_i^1$, let $r_i^1$ be the largest $r$ with this property.
If no such $p_i$ exists, set $L_i=0$ so we know there are zero $(p_i^\ell,r_i^\ell)$ values for this index.

Let $p_i^2$ be the smallest integer strictly bigger than $(r_i^1-1)p_i^1$ satisfying, likewise,
$$S[i-r_i^2p_i^2+1, i-p_i^2] = S[i-(r_i^2-1)p_i^2+1, i]$$
for some $r_i^2\ge 2$. Like before, take $r_i^2$ to be the maximal one having fixed $p_i^2$.
In general $p_i^\ell$ is the smallest such number strictly bigger than $(r_i^{\ell-1}-1)p_i^{\ell-1}$. If no such $p_i^\ell$ exists, then $L_i=\ell-1$.

Note that for each index i, we have $L_i=O(\log (i+1))$ due to $p_i^\ell$ values increasing geometrically with $\ell$. (if $p_i^{\ell+1}$ exists, it's not just strictly bigger than $(r_i^\ell-1)p_i^\ell$ but bigger than that by at least $p_i^\ell/2$. This establishes the geometric increase.)

  Suppose now all $(p_i^\ell,r_i^\ell)$ values are given to us. The minimum cost is given by the recurrence
  $$\mathrm{dp}(i,j) = \min\left\{\mathrm{dp}(i, j-1) + 1, \min_\ell \left(\mathrm{dp}\left(i,j - r_j^\ell p_j^\ell\right) + \mathrm{dp}(j-r_j^\ell p_j^\ell+1,j-p_j^\ell)\right)\right\}$$
  with the understanding that for $i>j$ we set $\mathrm{dp}(i,j) = +\infty$.
  The table can be filled in $O(n^2 + n\sum_j L_j)$ time.

We already observed above that $\sum_j L_j = O(\sum_j \log (j+1)) = \Theta(n\log n)$ by bounding the sum term by term. But actually if we look at the whole sum, we can prove something sharper.

Consider the suffix tree $T(\overleftarrow{S})$ of the reverse of $S$ (i.e., the prefix tree of S). We will charge each contribution to the sum $\sum_i L_i$ to an edge of $T(\overleftarrow{S})$ so that each edge will be charged at most once. Charge each $p_i^j$ to the edge emanating from $\mathrm{nca}(v(i), v(i-p_i^j))$ and going towards $v(i-p_i^j)$. Here $v(i)$ is the leaf of the prefix tree corresponding to $S[1..i]$ and nca denotes the nearest common ancestor.

This shows that $O(\sum_i L_i)=O(n)$. The values $(p_i^j,r_i^j)$ can be calculated in time $O(n+\sum_i L_i)$ by a traversal of the suffix tree but  I will leave the details to a later edit if anyone is interested.

Let me know if this makes sense.


Concatenating polyhedra at their region of contact Given two polyhedra(with triangulated faces), P1 and P2. I want to create a polyhedron P, which is the result of joining the two at their region of contact. With join I do not mean union but physically, it is more like welding P1 and P2, so if there is say a cylinder(P1) and a cube(P2) aligned on same axis with P1 partially out of P2, union operation will result in disappearance of the part of cylinder inside the cuboid but I want to preserve that region in P. In other words, P1 and P2 should be concatenated at their region of contact.

I would like to know if there is any practical algorithm for this? I think that it is more like computing overlay of P1 and P2 but I do not find any approach for the same in 3D.

I was recently referred to an article 'Mesh arrangements for solid geometry' by Qingnan Zhou et. al. [pdf]
and the corresponding code by Dr. Campen which exactly solves this problem.

This algorithm inserts new vertices and edges in the region of intersection between $P1$ and $P2$ thereby a generating new polyhedron $P$ and evaluates boolean operators on $P$ by selecting/rejecting vertices and edges depending on the operator. For my problem, $P$ forms the solution.

However, out of curiosity I would like to know if anyone has an alternative to this approach.

Update: I have tested the tool referred above against my original problem, it successfully prevents self-intersection by inserting new vertices and edges at the region of contact between $P1$ and $P2$.


What use are the minimum values on minimax trees? Consider a minimax tree for an adversarial search problem. For example, in this picture (alpha-beta pruning):

When marking the the tree with $[\min,\max]$ values bottom-up, we first traverse node $3$ and assign $B.\max = 3$. Then we traverse $12$ and $8$ in this order, it will make sure $B.max = 3$.

But why is $B.\min = 3$? What is the use of that value?

This figure (which is in fact correct) is used in the explanation of the alpha-beta pruning algorithm on a minimax tree. Alpha-beta pruning is a method used to prune parts of the minimax tree in an adversarial search problem. In the context of a tic-tac-toe game, minimax trees are meant to allow the computer to search through the space of all possible game boards (configurations of x's and o's) assuming the player moves are optimal. This allows the computer to come up with a move that provides the best outcome (this is why the connect-four game on your computer is so incredibly difficult to beat!). For a more complete description, I highly suggest "AI a Modern Approach" by Stuart and Norvig (pg. 162-170 ish in the 2nd ed.).

Now that we've cleared up some confusion on to the algorithm. Alpha-beta pruning tries to avoid expanding subtrees based on how the minimax algorithm works. We know that the max node at the top level will take the largest value of all its children. So, node $B$ finds the value $3$, and so far, this is the maximum value its willing to pass up to its parent so it puts this value in the MAX slot. Then it finds $12$. Remember that $B$ is a MIN node, so it wants to minimize the value it passes up to its parent, thus it keeps the value $3$ in the MAX slot. Again for $8$. When $B$ has searched all of its children, it knows the maximum lower bound ($\alpha$) solution and the minimum upper bound ($\beta$) solution of its subtree and maintains those values in MIN ($\alpha$) and MAX ($\beta$) (as [3, 3]).

Note: min and max labeled in the figure are NOT the minimum and maximum values of the subtree! They are (quite confusingly labeled) the alpha-beta bounds of the solutions of the subtree (remember this is an adversarial search problem).

Next we move to node $C$. Here we come across a $2$ in the first position. Node $C$, wanting to select the lowest value from its subtree now KNOWS that its parent will not pick its value since node $B$ found a larger value already. Therefore, we can prune the rest of the subtree and continue on to $D$.

Finally, to answer the specific question: Why is $B$.min = 3?
A value for $\alpha$ (the maximum lower bound of solutions at this node) and $\beta$ (the minimum upper bound of solutions at this node) is maintained at each node in order to perform the pruning. These values bound the possible cases in which the value from a node (or its subtree) may be part of the solution.

In this example, it does not appear to play a role, however, try to look at more complicated examples (i.e. trees with a height > 3) like this one and see if you can make sense of it.

I cannot do justice to minimax or alpha-beta pruning here (mostly because I haven't used them in years), so if you would really like to understand this please check out a book on AI like the one by Stuart and Norvig (the wikipedia page surprisingly has no visualization either).


Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$ I have seen some algorithms with complexities like $\log^3 n$ and $\sqrt n$. In view of getting a better idea on how to compare these I wanted to know for which values of $k$ does $\log^k n \in \Omega(\sqrt n)$ hold true?

I suspect $k$ would need to be a function of $n$. Because if it were a constant $C_1$, we could always find a larger constant $C_2$ that makes the previous statement false.

This is what I have tried.

$\log^k n \in \Omega(\sqrt n)$

$\log^{2k} n \in \Omega(n)$

$\log(\log^{2k}n) \in \Omega(\log n)$

$2k \log\log n \in \Omega(\log n)$

From here, I can see that if $k$ is $\log n$, then $2\log n \log\log n \in \Omega(\log n)$ is true.

However, I doubt this is a tight bound.

Let's redo your calculation. You want
$$ \log^kn \geq C \sqrt{n} $$
to hold for some $C>0$ and large $n$. Taking the logarithm,
$$
k \log \log n \geq \log C + \tfrac{1}{2}\log n,
$$
and so
$$
k \geq \frac{\log C + \tfrac{1}{2}\log n}{\log\log n}
$$
should hold for large $n$. In other words,
$$
k = \frac{\log n}{2\log\log n} + \Omega\left(\frac{1}{\log\log n}\right).
$$


Data structure for ordered counted set Is there a name for a counted set (multiset) that is ordered?

For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the items were added to the cart unless an item of the same type was already added in which case a number associated with item is incremented.

Is this a well studied data structure or just a specialized multiset? I imagine it could be represented with an internal data structure of a dictionary and an array.

Just use a regular dictionary (also dynamic set) and attach a counter to each entry. The insert operation then finds already existing entries and can increase the counter; similarly for delete.

If you want to search the literature, some sources (e.g. Algorithms by R. Sedgewick and K. Wayne (2011, 4th ed)) call the abstract data structure for multi sets a bag. This notion seems to be used in practice as well.

Note that some implementations will assume that you assign data to keys, and that the same key can occur multiple times with different data. In this case, using a counter is not enough, so these may not directly do what you want (since they may not even bother to detect duplicate keys).


Could anyone prove why O(n^(log n)) < O((log n)^n)? Could someone provide a rigorous proof of why $O(n^{log n}) \leq O((\log n)^n)$ is true? I'm trying to do this by induction but it isn't working. Thanks.

Using $ < $ with the big-oh notation is a bit of abuse of notation.
Formally, I take your statement to mean $\forall f(n) \in O(n^{\log n}), \; f(n) \in O((\log n)^n)$.

Let $f(n) \in O(n^{\log n})$, by definition of big-oh we know that the function is eventually bounded from above by $c n^{\log n}$ for some constant $c > 0$.
Then, for sufficiently large $n$,
$$
f(n) \le c n^{\log n} = c 2^{\log(n^{\log n})} = c2^{\log^2 n} < c2^n < c (\log n)^n,
$$
showing that $f(n) \in O((\log n)^n)$.

In particular the constant c in the last term can be made arbitrarily small. Indeed $n^{\log n} \in o((\log n)^n)$. A simple way to see this is by taking the limit of the ratio of the two functions:

$$
\lim_{n \to \infty} \frac{n^{\log n}}{(\log n)^n} =
\lim_{n \to \infty} \frac{2^{\log^2 n}}{2^{n \log n}} =
2^{\lim_{n \to \infty} \log^2 n - n \log n} = 0
$$


Can I find all the common subsequences between 2 sequences by using dynamic programming? I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one.

Thank you.

Denote the two strings by $s = s_1,\ldots, s_n$ and $t = t_1,\ldots, t_m$. Let $\mathcal{U}(i,j)$ denote the multiset of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$ which contain $s_i$ and $t_j$. Let $\mathcal{U}(\leq i,j)$ be the union of $\mathcal{U}(I,j)$ over all $i \leq I$, and define $\mathcal{U}(i,\leq j),\mathcal{U}(\leq i, \leq j)$ similarly. These multisets obey the recurrences:
$$
\mathcal{U}(i,j) =
\begin{cases}
\emptyset & \text{if } s_i \neq t_j, \\
\{ w s_i : w \in \mathcal{U}(\leq i-1,\leq j-1) \} & \text{if } s_i = t_j.
\end{cases} \\
\mathcal{U}(\leq i,j) = \mathcal{U}(\leq i-1,j) \cup \mathcal{U}(i,j) \\
\mathcal{U}(i,\leq j) = \mathcal{U}(i,\leq j-1) \cup \mathcal{U}(i,j) \\
\mathcal{U}(\leq i,\leq j) = \mathcal{U}(\leq i-1,\leq j-1) \cup \mathcal{U}(i,\leq j-1) \cup \mathcal{U}(\leq i-1,j) \cup \mathcal{U}(i,j)
$$
with the base cases $\mathcal{U}(0,0) = \{\epsilon\}$ and $\mathcal{U}(k,0) = \mathcal{U}(0,k)$ for $k > 0$.

If you want you can even keep track of the indices from which the subsequences are taken. The recurrences above ensure that each pair of matching subsequences is counted exactly once.

If you want instead to count the number of common subsequences, all you need to do is to keep track of the size of the multisets involved. Similarly, if you want instead to determine the longest common subsequence, all you need to do is keep track of that. In the latter case, double counting of subsequences is allowed (since we are only interested in the maximum length anyhow), and this simplifies the recurrence.

Indeed, if you are interested just in the set of common subsequences, then you can use a simpler recurrence. Let $\mathcal{V}(i,j)$ denote the set of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$. The sets $\mathcal{V}(i,j)$ obey the recurrence:
$$
\mathcal{V}(i,j) = \mathcal{V}(i,j-1) \cup \mathcal{V}(i-1,j) \cup
\begin{cases}
\emptyset & \text{if } s_i \neq t_j, \\
\{ws_i : w \in \mathcal{V}(i-1,j-1)\} & \text{if } s_i = t_j,
\end{cases}
$$
with base cases $\mathcal{V}(i,0) = \mathcal{V}(0,j) = \{\epsilon\}$. This is the form of the standard recurrence for longest common subsequence.

If you're interested in multisets but prefer a simpler recurrence, you can use the geekstogeeks idea, which requires multiset subtraction to avoid double counting. Let $\mathcal{W}(i,j)$ denote the multiset of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$, which obeys the following recursion:
$$
\mathcal{W}(i,j) = \mathcal{W}(i,j-1) \cup (\mathcal{W}(i-1,j) \setminus \mathcal{W}(i-1,j-1)) \cup
\begin{cases}
\emptyset & \text{if } s_i \neq t_j, \\
\{ws_i : w \in \mathcal{W}(i-1,j-1)\} & \text{if } s_i = t_j,
\end{cases}
$$
with base cases $\mathcal{W}(i,0) = \mathcal{W}(0,j) = \{\epsilon\}$. Depending on the application, the operation of multiset subtraction could be unavailable, and in this case you can use the idea outlined at the beginning of the answer.


Is there a way to determine if a collection is a palindrome within a time bound? I'm learning about data structures, and there's a problem where, given a collection of words $X = (x_1, x_2, \dots, x_n)$ (can include duplicates), I have to find out if it's a palindrome or not. I'm looking for an algorithm that runs in $O(c n)$ time, where $c$ is the maximum length of any word in $X$.

A collection is a palindrome if all the characters in $X$ can be rearranged into a palindrome.  For example, $X =$ (nun, ap, pa) is a palindrome (since apnunpa is) and (run, urn, appa) is a palindrome (since apurnnrupa is).  The characters can be re-ordered, even within a word. The alphabet is also limited and finite.

I read about palindrome trees, but the question can be answered with a basic data structure. Any ideas on how to design an algorithm with worst-case running time $O(n)$?

Original Question:

My main question is what implementation would be best for find if a collection is a palindrome. The best one I found to remain within the time constraints would be a binary heap. What I don't get is how I can check if the characters can form a palindrome or not. My normal implementation would be to form combinations of all then check if its a palindrome, which is O(n!). Any ideas on what method works?

If n is the number of words, it's impossible. It would mean that any roblem with just two words could be solved in constant time. But you could have two words of arbitrary equal length, and the time to confirm that one is the other reversed is unlimited if the length of the words is unlimited.

PS. Your edit changed this from a rather interesting problem to one that is really boring and trivial. You take an array with 26 counters, one for each letter, initialised to all zeroes. You go through the letters, and for each letter you increase the corresponding counter. When you are done, you check that there is at most one odd counter.

When you ask a question, it's only polite to take your time to state the question properly. Your original question has nothing whatsoever to do with the edited one.

And if you haven't figured it out: In a palindrome, the first and last letter, the second and second to last letter, and so on, are equal. Which means you have even numbers of each letter. There may be one letter in the middle (like in oxo) that doesn't have a match, or there may be none (like in otto). Which means at most one letter has an odd count. So to figure if a palindrome can be formed, just count the letters.


Counting and finding all perfect/maximum matchings in general graphs Recently i've been dealing with a problem that led me to the following questions:

Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph?
Is there a good algorithm for finding all maximum/perfect matchings in a general graph?
Are these two problems equivalent in their complexity?

I've stumbled upon the following references:

Algorithms for Enumerating All Perfect Maximum and Maximal Matchings In Bipartite Graphs- Suggesting an algorithm for enumerating all maximum matchings in a bipartite graph.
Finding All the Perfect Matchings
in Bipartite Graphs- Suggesting an algorithm for finding all perfect matchings in bipartite graphs

Both algorithms' complexity depend on the number of perfect matchings in the graph (meaning exponential running time in the worst case).

Moreover, both articles deal with bipartite graphs, I couldn't find similar articles dealing with the same problem in general graphs.

I'd appreciate information and references about the above problems.

Counting the number of perfect matchings in bipartite graphs amounts to computing the permanent of 0–1 matrices, which is $\# P$-complete. It follows that there is a reduction from all the other counting problems you mention (which are all in $\# P$) to this problem. You can compute the number of perfect matchings in planar bipartite graphs, and you can approximate the number of perfect matchings in general bipartite graphs. See for example this survey. Approximating the number of perfect matchings in general graphs is apparently more difficult, see for example this paper or that paper. Both papers mention that their algorithms seem to perform well on random graphs, but not necessarily that well in the worst case.

The problems of counting and of enumerating matchings in graphs are of different kinds, so it's hard to say whether they are "equivalent". Note, however, that if you could enumerate matchings then you could count them. This shows that, in some sense, enumerating is harder than counting. For the case of perfect matchings in bipartite graphs, there appears to be a difference, since you can approximate the number of perfect matchings, but computing them exactly is $\# P$-hard.


Does there exist a type system for a non-let-polymorphic lambda calculus? I'm wondering if there is a way to extend Hinley-Milner's type system to allow polymorphic types without the need of a let construct, by adding an intersection type (as Dan pointed out) that represents the possible types of a function type.

Say I have this expression:

$\lambda x.\lambda y.(x\ (x\ y))$

While running the type inference algorithm, I'd normally, after looking at the expression $(x\ y)$, assign to $x$ some type $Y \rightarrow A$, where $Y$ is the type of $y$ and $A$ is whatever $x$ returns. Then, since $x$ also takes $(x\ y)$ which has the type $A$, I replace $Y$ with $A$, such that the type of $x$ becomes $A \rightarrow A$ and give to the whole thing the type $(A \rightarrow A) \rightarrow (A \rightarrow A)$.

But what if I, instead of replacing $Y$ with $A$ when I see $(x\ (x\ y))$, add a new type to $x$, say, $A \rightarrow B$, such that the final type is $((Y \rightarrow A) \wedge (A \rightarrow B)) \rightarrow (Y \rightarrow B)$, which is also a tautology and seems like a better representation of what the function does.

Now say I give to this abstraction the term $\lambda n.n$ like this:

$(\lambda x.\lambda y.(x\ (x\ y))\ \lambda n.n)$

Since $\lambda n.n$ has the type $N \rightarrow N$, I'd need to unify $N \rightarrow N$ with $((Y \rightarrow A) \wedge (A \rightarrow B))$. So I instantiate two copies of $N \rightarrow N$, say $N_1 \rightarrow N_1$ and $N_2 \rightarrow N_2$, and unify $N_1 \rightarrow N_1$ with $Y \rightarrow A$ and $N_2 \rightarrow N_2$ with $A \rightarrow B$. Because $A$ would be equal to $N_1$ on one side and equal to $N_2$ on the other side, $N_1$, $Y$, $A$ and $B$ are all equal to $N_2$, so the type $Y \rightarrow B$ becomes $N_2 \rightarrow N_2$, which is consistent with the expression you'd get after evaluating the lambda term.

With this type system I should be able to type things like this:

$(\lambda i.\lambda x.\lambda y.((i\ x)\ (i\ y))\ \lambda n.n)$

But these examples are simple, and it becomes a pain to type something like:

$(\lambda x.\lambda y.(x\ (x\ y))\ \lambda x.\lambda y.(x\ (x\ y)))$

I'm having trouble trying to figure out what the actual rules of this system would be, like what would you do if you'd have to unify two intersection types (or whether that situation is even possible).

So my question is, am I moving towards a type system that already exists? If yes, which one? If not, is this because my type system wouldn't meet the requirements of a type system (such as being decidable)?

I am not sure what you mean by type system being decidable. I guess you mean type checking and type inference. (strictly speaking type inference is not a decision problem, although it can be casted as one and people usually think of it that way).

In addition to intersection types, I would also suggest looking at System F where universal quantification does not appear only at the let construct. For system F, type inference is undecidable: paper


How to show that given language is unambiguous Given following grammar:

$$
\begin{align}
S \rightarrow &A1B \\
A \rightarrow & 0A \mid \varepsilon \\
B \rightarrow & 0B \mid 1B \mid \varepsilon \\
\end{align}
$$

How can I show that this grammar is unambiguous? I need to find a grammar for the same language that is ambiguous, and demonstrate it.

I know if I was asked to prove that the language is ambigious then I should find two different parse trees for same string, but I don't know what to do.

To show a grammar is unambiguous you have to argue that for each string in the language there is only one derivation tree.

In this particular case you can observe that $A$ only generates $0$'s, so the $1$ generated by the start symbol $S$ must be the first $1$ in the string.

Any grammar can be made ambiguous by adding chain productions like $S\to S$.


Maximum subarray of bounded length I'm giving an array $A[0..n-1]$ and an integer $w$.  The goal is to find indices $i,j$ that maximize

$$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$

subject to the requirements that $0 \le i \le j \le n$ and $j \le i+w$.  Or, in other words, I want to find the sequential window of width at most $w$ such that the sum of the numbers in the window is maximized.

Is there an $O(n)$ time algorithm for this task?  Or, what is the most efficient algorithm for this task?

There is a trivial $O(nw)$ time algorithm, but I can't see how to do better than that.  If $w=\infty$, Kadane's algorithm solves this in $O(n)$ time, but I can't see how to generalize it to my problem.  So, can we do better than $O(nw)$ time?

I encountered this problem in the context of an image processing task I'm facing.

The problem you are describing can be solved in $O(n)$.

Let's define the prefix sum as:
$$\text{psum}[i] = \sum_{0 \le j \le i} A[j]$$
Then your function can be expressed as:
$$\Phi(i, j) = \text{psum}[j-1] - \text{psum}[i-1]$$

Assuming we fix the right boundary $j-1$ (we want to find the window of size at most $w$ ending at $j-1$ with the maximal sum). It should be easy to see, that this window has the sum:
$$\text{psum}[j-1] - \min_{i \ge j - w}\left\{\text{psum}[i-1]\right\}$$

For the actuall implementation we use a data structure called Minimum Queue. It is a queue (FIFO) that does the normal push/pop operations in amortized constant time and it additionally supports extracting the minimum of its current stored elements in constant time.

With it we can find the maximal window in linear time:

best = 0
initialize min_queue
min_queue.push(psum[-1])  # psum[-1] can be defined as 0
for j = 1 to n:
    if len(min_queue) > w:
        min_queue.pop()
    cur = psum[j-1] - min_queue.min()
    best = max(best, cur)
    min_queue.push(psum[j-1])

One way of implementing a Minimum Queue is to store the elements in a dequeue using value-index pairs. And you keep this queue in non-decreasing order, i.e. you only store the subset of pairs that are or can become the minimum at some point and ignore the remaining elements. This means whenever you push a new element, you remove all previous elements that are bigger from the back of the queue, since the currently added element will dominate them at all times. Therefore the minimum will always be the first element.

This approach, and also two (similar) alternatives are described on cp-algorithms.com.


What does $\mathbf{Q}^+$ mean in approximation texts? Often, in a lot of texts concerning approximation algorithms I see the following notation (for example, here in page 19 of the PDF or the first page of the introduction):

  ... and a cost function on vertices $c:V\to \mathbf{Q}^+$ ...

Is this just the positive rationals? Or is this something else?

I'm going to say yes, positive rationals, because:

That's what it means throughout math literature.
That's a sensible domain for a cost function. It would possibly be a different algorithm problem if "negative" cost were legal. Furthermore real numbers introduce questions of representation and comparing them, so while mathematicians or economists often consider real numbers for quantity, computer scientists are more cautious.
There is no front or back matter indicating otherwise.


What's harder: Shuffling a sorted deck or sorting a shuffled one? You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (a black box function taking no arguments and returning an independently uniformly random bit). Consider the following two tasks:

The array is currently sorted. Produce a uniformly (or approximately uniformly) randomly selected permutation.
The array consists of some permutation selected uniformly at random by nature. Produce a sorted array.

My question is

  Which task requires more energy asymptotically?

I am unable to define the question more precisely because I don't know enough about the connection between information theory, thermodynamics, or whatever else is needed to answer this question. However, I think the question can be made well-defined (and am hoping someone helps me with this in an answer!).

Now, algorithmically, my intuition is that they are equal. Notice that every sort is a shuffle in reverse, and vice versa. Sorting requires $\log n! \approx n \log n$ comparisons, while shuffling, since it picks a random permutation from $n!$ choices, requires $\log n! \approx n \log n$ random bits. Both shuffling and sorting require about $n$ swaps.

However, I feel like there should be an answer applying Landauer's principle, which says that it requires energy to "erase" a bit. Intuitively, I think this means that sorting the array is more difficult, because it requires "erasing" $n \log n$ bits of information, going from a low-energy, high-entropy ground state of disorder to a highly ordered one. But on the other hand, for any given computation, sorting just transforms one permutation to another one. Since I'm a complete non-expert here, I was hoping someone with a knowledge of the connection to physics could help "sort" this out!

(The question didn't get any answers on math.se, so I'm reposting it here. Hope that is ok.)

By Landauer's principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! \approx n \log_2 n$ bits. This will take $(n \ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n \log_2 n$ random bits to the random array is reversible, and thus the energy expended can be made arbitrarily small.

Note that these are just theoretical lower bounds. The energy currently consumed by these processes on an actual digital computer bears no relation to the above analysis.


Regular Expression for the language that requires one symbol to occur at least once I am trying to figure out the simplest way to do this using a regular expression.

Three symbols a, b, c.
The sequence length is unlimited, i.e. *.
The symbol a must be somewhere in the sequence at least once, but can appear more than once.
The sequence may have only a.

More formally, $\{ w \in \{a,b,c\}^* ~|~ \#_a(w)\ge 1 \}$, where $\#_a(w)$ is the number
of $a$s in $w$.

The best I get is

  $( ( b \mid c )^*\, a\, ( b \mid c )^* )^+$

Is that the simplest way?

The simplest regular expression I can think of for this is $\left(a \mid b \mid c\right)^* a \left(a \mid b \mid c\right)^*$. This is simpler than yours by the following measures of complexity:

It contains less nesting (and fewer parentheses in general)
It contains fewer quantifiers


What is a mod b if a < b? So when you are decrypting an encryption with modular arithmetic, I know the modulus operator (%) gives the remainder of a/b, but what if a is less than b?

For example, 5%2 is 1, since the answer is 2 remainder 1. But for something like 2%9, how do you find the answer?

If $a,b$ are both positive integers, then we can always write $a = kb+\ell$ where $0 \leq \ell < b$. We call $\ell$ the remainder and $k$ the quotient. In your first example, $5 = 2 \cdot 2 + 1$ so 5 % 2 == 1. In your second example, $2 = 0 \cdot 9 + 2$, so 2 % 9 == 2. More generally, if $a < b$ then a % b == a.

There is also a rule for signed integers, but unfortunately I can't remember it. Also, 0 % x == 0 whenever $x \neq 0$, and x % 0 will cause an exception ("division by zero").


Regular expression for $\{a^k b^m c^n \mid k+m+n \text{ is odd} \}$ I have to make a regular expression from the following laguage:

  {$a^kb^mc^n : $ where k + m + n is odd}

Is is possible for the sum of three numbers to be odd (other than three consecutive odd numbers)?

I have this so far:

  {(abbbccccc) + (abbbbbccc) + (aaabccccc) + (aaabbbbbc) + (aaaaabccc) + (aaaaabbbc)}

but I am realizing that there are way more possibilities to this pattern... How can I formulate a string that encompasses all of this?

What you need is that either exactly two of $k$, $m$, $n$ even, or all three odd, because two odds and an even make an even; and three evens make an even.

An odd number of $a$'s translates to the regular expression $a (a a)^*$, an even number to $(a a)^*$.

Pulling the above together:
$$
a (a a)^* (b b)^* (c c)^* \mid  (a a)^* b (b b)^* (c c)^* \mid (a a )^* (b b)^* c (c c)^* \mid a (a a)^* b (b b)^* c (c c)^*
$$


comparison in speed between the processor and the hard disk I'm reading through William Stalling's operating system intrnals and design principles book. Talking about interrupts, it gives the following examples when comparing the speed of a processor and a hard disk:

  To give a specific example, consider a PC that operates at 1 GHz, which would
  allow roughly 10^9 instructions per second. A typical hard disk has a rotational speed
  of 7200 revolutions per minute for a half-track rotation time of 4 ms, which is 4 million
  times slower than the processor.

My question is how was the result calculated? How did we know that the hard disk is 4 million times slower?

This is to some extent a comparison between apples and oranges. The assumption is that the basic operation on a CPU takes 1 ns (since the clock frequency is 1 GHz), whereas a basic operation on the hard disk takes 4 ms. The quoted factor is just 4 ms / 1 ns = 4×106.


Function to generate longer bit-sequence from shorter sequence with certain properties im not familiar with the terminology of computer-science which makes it pretty difficult to search for the problem I have.

I'm looking for a function that generates a sequence of bits (B) of a given length (i.e. 1024 bit) from a chosen bit-sequence (A) (i.e. 32 bit).

This function needs to have the following properties:

The relation A->B has to be unique
A slight change of A (i.e. 1 bit) results in a slight change of B (~1024bit/32bit = ~32)

While searching I came across hash-algorithms but they achive kind of the oppisite I want to do. They shorten a sequence and a small change of the first one results in a big change of the other one.

Do you know of such a function or do I have to come up with something myself?

Example (with fewer bits):

Let bit-sequence A be given as 0b0101 (integer-representation: 5).
Let function F map A to B so that B = 0b1001 0010 0101 0111 (example). Here, B can be split into 4 4-bit integers (9, 2, 5, 7).

Changing 1 bit of A from 0b0101 (5) to 0b0100 (4) results in 4 changed bits of B so that the resulting bits are 0b1011 0000 0101 0110 (integer: 11, 0, 5, 6).

The 4 integers contained in B will be used in further computations and I'm looking for function F.

Let $\pi$ be a random permutation on $\{1,\ldots,1024\}$, and let $K$ be a random bit string of length 1024 bits. The following mapping seems to satisfy your needs (with probability close to 1):
$$
A \mapsto \pi(A^{32} \oplus K).
$$
In particular, changing $b$ bits of $A$ will result in changing $32b$ bits of the result.

If you are OK with changing more than 32 bits, then you can take a random sparse affine function, that is the function whose $i$th bit is an XOR of a small number of bits of $A$ chosen at random, XORed with a random bit.


What are the general applications of Computer Science in the field of Psychology? I am keenly interested to do a project in Computer Science that can aid to address the problems in the field of Psychology. Now I want to know what are the most general and research-oriented issues or problems areas in Psychology that can be solved through computation or at least aid to be solved via Computer Science.
Looking for authentic answers. Thank you

Here are some of the areas that intuitively come into my mind where Computer Science and Psychology can go along together. As a student of Computer Science, one has to study the following core subjects at the undergrad level that are either directly or indirectly related to Psychology:

1. Data Structures and Algorithms: All the data structures do exist in the real world and the human mind perceives them to store, arrange, sort and search the required data as per their strength and limitation. Now the question arises, could there be a data structure or algorithm that is beyond the perception and capacity of human mind? Perhaps certainly or maybe.

2. Design and Analysis of Algorithms: Could there be a general algorithm for curing a mental disease, achieving happiness, finding love or the best match, finding career, overcome stress or depression, defeating a rival, rehabilitating a heroine addict or leading a "perfect life"? All of such aspects of human life can be addressed computationally. And yes the answers to these questions are indeed subjective and debatable as well.

3. Artificial Intelligence: Can we ever have machines more intelligent than humans? Oh yes, we certainly have such intelligent machines. But do such machines recognize vision and pattern as we humans do? That is an area of continuous research in Computer Science.

4. Human Computer Interaction: In the modern world, humans do interact with computers almost on a daily basis. Commercial hardware, software applications and games, all of them are designed with the "interface" keeping in view the human user's perception, expectation and limitation in consideration. Now the question arises: Can we have Computers as our personal psychiatrists? Can we treat mental or psychological patients with Computer-Aided Psychotherapy? I really want to explore!!!!

5. Professional/Ethical Issues in Computing: Can we ever be able to fully secure personal or professional data via Computers? Can we get rid of pornography from the internet? Can we develop a game that counters games leading to suicide like "Blue Whale"? Can we rid the world from religious fanaticism, terrorism, racism and hate crimes via Computer Science?  All of such questions and problem areas are pending to be addressed.


Why do we need to run the bellman-ford algorithm for n-1 times? I'm a little confused about the concept of the Bellman-Ford(BF) algorithm to compute the shortest path in a general graph with negative weights knowing that there are no negative cycles present. I understand why Dikjstra doesn't work for a graph with negative weights. So in the Bellman-Ford algorithm we decide to update all nodes and their neighbors even though they might be visited before. My confusion can be summarized in a couple of questions:

Why running the BF algorithm once won't make sure that all nodes' distances have the minimum distance from the source?
Why do we have to run BF for N-1 (N: number of nodes) times to make sure all the nodes have the minimum distance from the source? Is it sort of because there are negative weights? How negative weights complicate things?

Answering your first question is simple. Try out a few graphs and see for yourself why it doesn't work. As to your second question, $n-1$ is the maximal length of a shortest path in the graph. After $k$ iterations of the Bellman–Ford algorithm, you know the minimum distance between any two vertices, when restricted to paths of length at most $k$. This is why you need $n-1$ iterations. Negative weights have absolutely nothing to do with it.

For a more sophisticated answer, consult the recent paper of Jukna and Schnitger, On the optimality of Bellman–Ford shortest path algorithm. They show that among the class of Bellman–Ford-like algorithms, the Bellman–Ford algorithm is optimal.


Prove Matrix Correspondence is NP-complete Consider the following problem. Given a $m \times n$ integer matrix $A$ and a $p \times q$ integer matrix $B$, do there exist one-to-one functions
$$r:\{1,2,...,m\} \rightarrow \{1,2,...,p\}$$
$$c:\{1,2,...,n\} \rightarrow \{1,2,...,q\}$$
where for all $1 \leq i \leq m$ and $1 \leq j \leq n$, $A[i,j] \leq B[r(i),c(j)]$?

What is the best way to show this problem is NP-complete? I am currently considering reducing the clique problem to this problem.

As you mentioned, we can reduce maximum clique problem to this. In fact we can reduce the more general subgraph isomorphism problem to this one easily. Given graphs $G$ and $H$, define $A$ and $B$ as their (undirected) incidence matrices. Then we can see that solving the matrix correspondence tells whether $G$ is isomorphic to some subgraph of $H$, which is an NP-complete problem.


From context-free to context-sensitive I have a context-free language $L(G)$. I'm reading in a book that $L(G') = L(G) - \{{\epsilon}\}$ is context-sensitive but I cannot find a proof or confirmation of this fact; moreover, in other texts the production $S\to\epsilon$ is allowed (as long $S$ isn't on the right hand side of any production)
I'm quite confused.

The book is Formal Models of Computation: The Ultimate Limits of Computing
by Arthur Charles Fleck and the passage in question says:

  Given two context free grammars $G_1$ and $G_2$ first determine if $\epsilon\in L(G_1)$ and $\epsilon\in L(G_2)$. If so, $L(G_1)\cap L(G_2) \neq \emptyset$,  otherwise $L(G_1) - \{{\epsilon}\}$ and $L(G_2) - \{{\epsilon}\}$ are context-sensitive.

Maybe what the book says is that they are also context sensitive (since the set of context-free languages is properly contained in the set of the context-sensitive)?

Saying that CF grammars are properly contained in CS grammars is not quite
correct, at least according to some authors (Hopcroft-Ullman
1979, page 223). Their reason is that the CS languages cannot contain the empty
word $\epsilon$, at least according to a strict definition of what a
CS grammar is: the right-hand side must be at least as long as the
left-hand side. Other definitions of CS grammars, such as given in
wikipedia, do allow the rule $S\to\epsilon$, provided $S$ never
appears in a right-hand side. The purpose is to allow CS languages to
contain the empty word, so that they define the same family of
languages as the linear bounded automata (LBA). And it also makes CF languages a subset of CS languages.

Context-free (CF) languages can contain the empty word.

Thus, for an author belonging to the strict school (no $\epsilon$ in
CS languages), only $\epsilon$-free CF languages are contained in the
CS languages.

From what I read in your question, my understanding is that the
authors of your book belong to the strict school. So they will not
consider a CF language as CS, unless they first remove the empty word,
which does not change their CF character as shown in the answer by
D.W. that indicates how to obtain the CF grammar $G'$ from the CF
grammar $G$.

Apparently the author is analyzing the intersection of two CF grammar,
and wants to use the fact that (for him) $\epsilon$-free CF languages
are contained in the CS languages. So he considers separately the case
when the intersection contains $\epsilon$, and the case when it does
not contains it. If it does no contain it, he can remove it from the
two languages, and then consider them CS languages, for whatever he is
doing.

That is my explanation of what you are reading. Of course, a larger piece of context would help ascertain that view. Or even better, the definition of CS language they give.


Preconditions and postconditions What are preconditions and postconditions in this C++ function?

I have this example in my slides but still didn't get the idea!

*Comment function declaration:
    void showInterest(double balance, double rate);
    //Precondition: balance is nonnegative account balance
    //      rate is interest rate as percentage
    //Postcondition: amount of interest on given balance,
   //       at given rate …
*Often called Inputs & Outputs

Preconditions and postconditions are just ways to describe a function in more detail, and give some hints on how you can use this function or what to expect from it.

Preconditions are conditions that have to hold before (pre is Latin for before) the function gets called by a user. These are usually conditions about the parameter. E.g. a simple precondition for the function square_root(x) might be: x has to be non-negative. Because the function cannot handle negative numbers, maybe even crashes, or just return wrong values. But there are even other preconditions. Other preconditions could involve global states, or the state of objects. E.g. before you call this function you need to call another. So the user has to make sure, that all the conditions are satisfied, before he calls the method.

Postconditions are about after the call (again, Latin). That can mean the return value of the function, or the global state of the program or object after calling the function. This are conditions a user can expect from the program. It is kinda like a guarantee, if a user calls the function in a way that satisfies all preconditions, then he will get something that is described in the postconditions.


Storing nodes in state space search I'm taking an introductory course in AI and we've been given the assignment to solve a puzzle using different search algorithms on a state space (BFS, DFS etc). I understand the theory and everything, but I'm not sure what information I should store in the nodes of the tree.

Assume that I have a matrix to represent the game board. Should each node in the tree contain the entire board? For example, in the case of 19x19 Go, would each node consist a matrix of size 19x19 (the problem I'm trying to solve is a 1 player game, and not Go or chess or anything like that, however)? If this is the case, even with pruning, it sounds to me like this would take up an insane amount of space. For example, at depth 1, a state space of the game of Go would have 19*19 nodes each containing a 19*19 matrix (correct me if I'm wrong here). At the same time, I can't find a better option.

What is the general approach to storing these kinds of states?

Any help is greatly appreciated.
Please let me know if the question is in any way unclear.

The common answer to "What to store?" is "As much as you need and nothing more."

You can instead store a reference to the previous state and the move(s) you made on the previous state to get to the current state.

This is more compact that a full copy of the state in each node but less convenient to work with because you'd need to reconstruct the state by following all the moves made since the last known full state node.

The next option is to throw away parts of the graph that you aren't looking at at the moment and instead recreate it later when needed.

Both of these options trade space for time.